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/

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'))))