446 PurelyFunctional.tv Newsletter

00 Longest Alternating Substring.md

Longest Alternating Substring

Write a function that takes a string of digits and returns the longest substring that contains only alternating odd/even digits. If two substrings have the same length, return the one that appears first.

Examples

(longest-alt-subs "") ;=> ""
(longest-alt-subs "1") ;=> "1"
(longest-alt-subs "123") ;=> "123"
(longest-alt-subs "13") ;=> "1"
(longest-alt-subs "122381") ;=> "2381"

Thanks to this site for the problem idea, where it is rated Expert in Python. The problem has been modified.

Please submit your solutions as comments on this gist.

To subscribe: https://purelyfunctional.tv/newsletter/

(defn longest-alt-prefs [input-string]
  (loop [[new-char & rest-chars] input-string
         answer []]
    (let [last-dig (last answer)
          new-dig (and new-char (Integer/parseInt (str new-char)))]
      (if (or (and last-dig new-dig
                   (not= (even? last-dig) (even? new-dig)))
              (and new-dig (not last-dig)))
        (recur rest-chars (conj answer new-dig))
        answer))))

(defn longest-alt-subs [input-string]
  (->> (for [i (range (count input-string))]
         (longest-alt-prefs (drop i input-string)))
       (sort-by count)
       (partition-by count)
       last
       first
       (str/join "")))

(defn longest-alt-subs [s]
  (if (empty? s)
    ""
    (reduce (fn [a b] (max-key count b a))
            (subs s 0 1)
            (re-seq #"(?:[02468][13579])+[02468]?|(?:[13579][02468])+[13579]?" s))))

(require '[clojure.string :as str])

(defn alternating-substrings [s]
  (if (empty? s)
    [s]
    (->> (map vector s (range))
         (partition-by (fn [[char index]]
                         ;; since index alternates we can check if char follows index
                         ;; this helps us to avoid checking alternation of neighbour chars
                         (= (even? (int char)) (even? index))))
         (map #(str/join (map first %))))))

(defn first-longest [xs]
  (apply (partial max-key count) (reverse xs)))

(defn longest-alt-subs [s]
  (first-longest (alternating-substrings s)))

(defn longest-alt-subs [s]
  (->> (range (count s))
       (partition-by #(even? (+ % (int (nth s %)))))
       (map #(subs s (first %) (inc (last %))))
       reverse
       (apply max-key count "")))

(defn longest-alt-subs [s]
  (let [chodd? (fn [ch] (case ch (\1 \3 \5 \7 \9) true false))]
    (if (< (count s) 2)
      s
      (->> (reduce (fn [res c]
                     (let [p (peek (peek res))]
                       (if (= (chodd? p) (chodd? c))
                         (conj res [c])
                         (conj (pop res) (conj (peek res) c)))))
                   [[(first s)]]
                   s)
           rseq
           (apply max-key count)
           (apply str)))))

Somewhat faster to access chars by index in S. Refactored.

(defn longest-alt-subs [s]
  (let [iodd? (fn [i] (case (.charAt ^String s ^int i) (\1 \3 \5 \7 \9) true false))
        len (.length ^String s)]
    (if (< len 2)
      s
      (let [[longstart longend start]
            (reduce (fn [lls i]
                      (if (not= (iodd? (dec i)) (iodd? i))
                        lls
                        (let [[longstart longend start] lls]
                          (if (> (- i start) (- longend longstart))
                            [start i i]
                            [longstart longend i]))))
                   [-1 -1 0]
                   (range 1 len))]
        (if (> (- len start) (- longend longstart))
          (subs s start)
          (subs s longstart longend))))))

(defn longest-alt-subs [s]
  (let [even-odd #"([02468][13579])*[02468][13579]?"
        odd-even #"([13579][02468])*[13579][02468]?"
        empty-str #""
        pattern  (re-pattern (str even-odd "|" odd-even "|" empty-str))
        alt-subs (->> (re-seq pattern s)
                      (map first))]
    (reduce (fn [longest el]
              (if (< (count longest) (count el))
                el
                longest))
     ""
     alt-subs)))

(defn longest-alt-subs [s]
  (->> (take-while seq (iterate rest s))
       (mapcat #(reductions conj [] %))
       (filter #(apply = 1 (map count (partition-by odd? (map int %)))))
       reverse
       (apply max-key count "")
       (apply str)))

EDIT
@mchampine, nice use of rest and reductions to generate windows!
I shamelessly copied your idea - interestingly this is the third of recent challenges
in which a windows function is handy:

(defn windows 
  "Constructs a lazy seq of all contiguous subsequences of xs."
  [xs]
  (->> xs (iterate rest)
       (sequence (comp (take-while seq)
                       (mapcat #(reductions conj [] %))
                       (map seq)
                       (filter identity)))
       (cons ()) lazy-seq))

(defn alternating-subs? [xs]
  (= (count xs) 
     (->> xs (sequence (comp (map int) 
                             (partition-by odd?)))
          count)))

(defn longest-alt-subs [digs]
  (->> digs windows
       (filter alternating-subs?)
       (sort-by (comp - count))
       first
       (apply str)))

(defn char->long [c]
  (- (long c) 48))

(defn longest-alternating-substring [s]
  (let [{:keys [max-alts alts]} (reduce (fn [{:keys [max-alts alts] :as acc} [prev-char next-char]]
                                          (if (or (and (odd? prev-char)
                                                       (even? next-char))
                                                  (and (even? prev-char)
                                                       (odd? next-char)))
                                            (update acc :alts (fnil conj [prev-char]) next-char)
                                            (-> acc
                                                (update :max-alts #(if (> (count alts) (count %))
                                                                     alts
                                                                     %))
                                                (assoc :alts nil))))
                                        {}
                                        (partition 2 1 (map char->long s)))]
    (clojure.string/join "" (if (> (count alts) (count max-alts))
                              alts
                              max-alts))))

loop version

(defn longest-alternating-substring-loop [s]
  (loop [alts nil
         max-alts nil
         [[prev-char next-char :as item] & rest'] (partition 2 1 (map char->long s))]
    (if-not item
      (clojure.string/join "" (if (> (count alts) (count max-alts))
                                alts
                                max-alts))
      (recur (when (or (and (odd? prev-char)
                            (even? next-char))
                       (and (even? prev-char)
                            (odd? next-char)))
               (if (nil? alts)
                 [prev-char next-char]
                 (conj alts next-char)))
             (if (> (count alts) (count max-alts))
               alts
               max-alts)
             rest'))))