Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
408 - PurelyFunctional.tv Newsletter

Consecutive numbers

Write a function that takes a string of digits. Try to break up the digits into consecutive integers. If you can, return them, otherwise, return nil.

Examples

(consec "121314") ;=> [12 13 14]
(consec "121315") ;=> nil
(consec "444445") ;=> [444 445]
(consec "12") ;=> [1 2]
(consec "1") ; throws error

Thanks to this site for the challenge idea where it is considered Expert in JavaScript.

Please submit your solutions as comments on this gist.

@souenzzo
Copy link

souenzzo commented Dec 28, 2020

(letfn [(consec [x]
          (let [n (count x)]
            (if (< n 2)
              (let [message (str "The input x: " (pr-str x) " should contain at least 2 chars. Actual: " n)]
                (throw (ex-info message
                                {:cognitect.anomalies/message  message
                                 :cognitect.anomalies/category :cognitect.anomalies/incorrect
                                 :x                            x
                                 :n                            n})))
              (first (for [i (rest (range n))
                           :let [parts (partition i x)
                                 new-n (reduce (fn [acc part]
                                                 (+ acc (count part)))
                                               0
                                               parts)]
                           :when (== new-n n)
                           :let [number-part (sequence (comp (map (partial apply str))
                                                             (map edn/read-string))
                                                       parts)
                                 sequential (take (count number-part)
                                                  (iterate inc (first number-part)))]
                           :when (= number-part sequential)]
                       number-part)))))]
  {:121314=>12+13+14 (consec "121314")
   :121315=>nil      (consec "121315")
   :444445=>444+445  (consec "444445")
   :12=>1+2          (consec "12")
   #_#_:1=>throws (consec "1")})                      

@proush42
Copy link

proush42 commented Dec 28, 2020

I first thought of some very simple approaches, but realized that while they would handle the example cases, they would fail on:

"7891011" (should be: [7 8 9 10 11] )

I wanted to handle the general case, so I worked a little harder to do that.

;;
;; ["121314" 2] => (12 13 14 15 16 ...)
;; ["121314" 3] => (121 122 123 124 ...)
;;
(defn num-seq-with-n-digit-n0 [s n]
  (->> (Long. (.substring s 0 n))
       (iterate inc)))

;;
;; ["7891011" (7 8 9 10 11 12 13 ...)] => [7 8 9 10 11]
;; ["7891011" (78 79 80 81 82 ...)]    => nil
;;
(defn num-seq-match [target-str num-seq]
  (reduce (fn [nums n]
            (let [s (apply str nums)]
              (cond
                (> (count s) (count target-str)) (reduced nil)
                (= s target-str)                 (reduced nums)
                :else                            (conj nums n))))
          []
          num-seq))

(defn consec [s]
  (let [n0-lens (range 1 (inc (quot (count s) 2)))
        match  (fn [n0-len]
                  (num-seq-match s (num-seq-with-n-digit-n0 s n0-len)))]
    (some match n0-lens)))

@paulschun
Copy link

paulschun commented Dec 28, 2020

The annoying person who interprets "Write a function..." as meaning write exactly one function is back.

(defn consec [s]
  {:pre [(> (count s) 1)]}
  (loop [partition-size 1]
    (when (<= partition-size (/ (count s) 2))
      (let [partition-sequence (->> s
                                    (partition partition-size)
                                    (map (partial apply str))
                                    (map #(Long/parseLong %)))]
        (if (apply = (map - partition-sequence (range)))
          (vec partition-sequence)
          (recur (inc partition-size)))))))

@steffan-westcott
Copy link

steffan-westcott commented Dec 28, 2020

(defn consec [s]
  (first (for [first-len (range 1 (-> s count (quot 2) inc))
               :let [first-num (read-string (subs s 0 first-len))]
               nums (iterate #(conj % (inc (peek %))) [first-num])
               :let [s' (apply str nums)]
               :while (<= (count s') (count s))
               :when (= s s')]
            nums)))

Edits:

  • Use read-string to handle longer strings
  • Simplify building of nums result
  • Skip futile cases where first number has too many digits

@steffan-westcott
Copy link

steffan-westcott commented Dec 28, 2020

@sixofhearts @souenzzo You may want to take another look at your answer because (consec "99100") should equal (99 100)

@paulschun
Copy link

paulschun commented Dec 29, 2020

Well spotted @steffan-westcott!

@dfuenzalida
Copy link

dfuenzalida commented Dec 29, 2020

This version handles the simple case where all numbers have the same number of digits, will try to work on the more general case.

(defn splits-for
  "given a string s, return the seq of sizes that evenly split the whole string"
  [s]
  (let [c (count s)]
    (filter #(zero? (mod c %)) (range 1 c))))

(defn digits-to-nums
  "Convert seqs of seqs of digits into seqs of numbers they represent"
  [xss]
  (map #(clojure.edn/read-string (reduce str "" %)) xss))

(defn consec?
  "Returns true if a sequence of numbers is monotonically ascending by one at a time"
  [xs]
  (->> xs (partition 2 1) (map (partial apply -)) (every? #{-1})))

(defn consec
  "Returns consecutive numbers made of digits of the given string, or nil if none found"
  [s]
  (when (= 1 (count s)) (throw (RuntimeException. "1-digit string")))
  (->> (splits-for s)
       (map #(partition % s))
       (map digits-to-nums)
       (filter consec?)
       first))

;; (consec "121314") ;=> [12 13 14]
;; (consec "121315") ;=> nil
;; (consec "444445") ;=> [444 445]
;; (consec "12") ;=> [1 2]
;; (consec "1") ; throws error

@nbardiuk
Copy link

nbardiuk commented Dec 29, 2020

(defn consec
  ([s]
   (letfn [(parse-first [digits]
             (Long/parseLong s 0 digits 10))]

     (when (< (count s) 2)
       (throw (ex-info "cannot parse sequence" {})))

     (->> (range (/ (count s) 2))
          (some (comp #(consec s %) parse-first inc)))))

  ([s start]
   (letfn [(starts-with [n s]
             (let [sn (str n)]
               (when (str/starts-with? s sn)
                 [n (subs s (count sn))])))]

     (let [[n srest] (starts-with start s)]
       (loop [result [n]
              srest srest]
         (if (empty? srest)
           result
           (when-let [[n srest] (starts-with (inc (peek result)) srest)]
             (recur (conj result n) srest))))))))

@nbardiuk
Copy link

nbardiuk commented Dec 29, 2020

The challenge is interesting because it is hard to find good separation of conserns.
Because of different amount of digits for numbers in the sequence it is hard to separate parsing of numbers from checking whether they are consecuitive.

@mauricioszabo
Copy link

mauricioszabo commented Dec 30, 2020

I don't know why (conseq "1") should throw an error, but if I can relax that restriction, here's my try:

(defn consec
  ([a-str] (consec a-str []))
  ([a-str acc]
   (let [prev-number (peek acc)
         first-count (or (some-> prev-number str count) 1)]
     (->> a-str
          count
          (range first-count)
          (mapcat (fn [n]
                    (let [first-part (subs a-str 0 n)
                          remaining (subs a-str n)
                          number (bigint first-part)
                          rem-as-number (delay (bigint remaining))]
                      (when (or (nil? prev-number)
                                (= number (inc prev-number)))
                        (cond
                          (= "" remaining) acc
                          (= (inc number) @rem-as-number) (conj acc number @rem-as-number)
                          :else (consec remaining (conj acc number)))))))
          ; [1]
          not-empty))))

The results come in "bigint" formats. If this is not acceptable, we can replace : [1] to (map int)

@miner
Copy link

miner commented Dec 30, 2020

I think (consec "1") should return nil, not throw.

@miner
Copy link

miner commented Dec 30, 2020

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

(defn consec [nstr]
  (let [parse-inc (fn [nstr result]
                    (let [target (inc (peek result))
                          tstr (str target)]
                      (when (str/starts-with? nstr tstr)
                        (if (= nstr tstr)
                          (conj result target)
                          (recur (subs nstr (count tstr)) (conj result target))))))]
    (if (str/starts-with? nstr "0")
      (parse-inc (subs nstr 1) [0])
      (some (fn [end] (parse-inc (subs nstr end) [(Long/parseLong (subs nstr 0 end))]))
            (range 1  (inc (quot (count nstr) 2)))))))

Revised to fix bug with input "0123". Revised again to use some instead of (first (keep ...)).

@miner
Copy link

miner commented Dec 31, 2020

A leading "0" caused a problem with my original submission. It's worth testing with inputs like "0123" and "010910". Note that (Long/parseLong "010") returns 10, ignoring the leading zero. Also, (read-string "010") returns 8 as the leading zero is Clojure/Java notation for octal numbers. For this challenge I would not expect to support octal. My interpretation is that a leading zero can only be a single digit zero and all digits are decimal.

@kschltz
Copy link

kschltz commented Dec 31, 2020

(defn iter-str [s digits]
  (loop [first-n (Long/valueOf (subs s 0 digits))
         rem-str (second (re-find (re-pattern (str first-n "(.*)")) s))
         inc-seq [first-n]]
    (if-not (seq rem-str)
      inc-seq
      (let [nxt-n (-> (str "^" (inc first-n)) re-pattern (re-find rem-str))]
        (if-not (seq nxt-n)
          nil
          (recur (Long/valueOf nxt-n)
                 (second (re-find (re-pattern (str nxt-n "(.*)")) rem-str))
                 (conj inc-seq (Long/valueOf nxt-n))))))))

(defn consec [s]
  (let [s-len (-> s count (/ 2) Math/ceil int inc)]
    (->> s-len
         (range 1)
         (reduce (fn [a b]
                   (if a
                     (reduced a)
                     (iter-str s b))) nil))))``

@mauricioszabo
Copy link

mauricioszabo commented Dec 31, 2020

A slightly bigger version that brutes-force the process:

(defn- possibilities [a-str]
  (let [str-size (count a-str)]
    (for [slice-size (range 1 (inc (/ str-size 2)))
          :let [number-of-consecs (/ str-size slice-size)
                first-number (-> a-str (subs 0 slice-size) Long/parseLong)]]
      (->> (iterate inc first-number)
           (take number-of-consecs)))))

(defn- find-match [a-str possibility]
  (when-let [how-many (->> possibility
                           (reductions str "")
                           (map-indexed vector)
                           (filter #(-> % second (= a-str)))
                           ffirst)]
    (take how-many possibility)))

(defn consec [a-str]
  (when (-> a-str count (< 2)) 
    (throw (ex-info "String must have at least 2 digits" {:str a-str})))
  (->> a-str
       possibilities
       (map #(find-match a-str %))
       (filter identity)
       first))

@steffan-westcott
Copy link

steffan-westcott commented Dec 31, 2020

@miner I also found problems with strings with a leading 0 that also contained 8 or 9 😞 Here's another try, which should also cope with long strings. Here I'm using the str/starts-with? idea used by other answers here, rather than building up an entire string based on the initial number only:

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

(defn consec' [s first-num-len]
  (let [first-num (read-string (subs s 0 first-num-len))]
    (loop [n (inc first-num)
           nums [first-num]
           s' (subs s first-num-len)]
      (if (empty? s')
        nums
        (let [nstr (str n)]
          (when (str/starts-with? s' nstr)
            (recur (inc n) (conj nums n) (subs s' (count nstr)))))))))

(defn consec [s]
  (if (str/starts-with? s "0")
    (consec' s 1)
    (some #(consec' s %) (range 1 (-> s count (quot 2) inc)))))

@sztamas
Copy link

sztamas commented Dec 31, 2020

(defn consecutives? [s fi]
  (loop [s s
         xs (iterate inc fi)]
    (if (blank? s)
      (first xs)
      (when (starts-with? s (str (first xs)))
        (recur (subs s (count (str (first xs)))) (rest xs))))))

(defn consec [s]
  (when-not (re-matches #"\d{2,}" s)
    (throw (IllegalArgumentException. "must be a string of (at least 2) digits")))
  (let [firsts (->> (range (quot (count s) 2))
                    (map (comp #(Integer/parseInt %) (partial subs s 0) inc)))]
    (some #(when-let [last (consecutives? s %)] (vec (range % last)))
          firsts)))

@miner
Copy link

miner commented Dec 31, 2020

@steffan-westcott Good point about input such as "08" potentially being an issue for code using read-string as that would be an illegal octal number. Very large input strings could also cause errors if the code tries to read an integer that is bigger than a long. But I'm not going to support that.

@arthuronunes
Copy link

arthuronunes commented Jan 1, 2021

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

(defn ->sequence [value n]
  (let [initial-number (-> (subs value 0 n) Long/parseLong)]
    (loop [numbers-seq [initial-number]
           remaining-value (subs value n)]
      (if (empty? remaining-value)
        numbers-seq
        (let [last-number (last numbers-seq)
              next-number (inc last-number)
              next-number-str (str next-number)
              number-size (count next-number-str)]
          (when (str/starts-with? remaining-value next-number-str)
            (recur (conj numbers-seq next-number)
                   (subs remaining-value number-size))))))))

(defn consec [value]
  (let [start-with-zero? (str/starts-with? value "0")
        size (count value)
        limit (if start-with-zero? 1 (quot size 2))]
    (when (<= size 1)
      (throw (ex-info "String must be 2 or more characters" {:value value})))
    (loop [n 1]
      (when (<= n limit)
        (let [result (->sequence value n)]
          (if result
            result
            (recur (inc n))))))))

@MilanLempera
Copy link

MilanLempera commented Jan 5, 2021

(defn consec [str]
  (let [str-length (count str)]
    (when (< str-length 2)
      (throw (Exception. "consec requires at least 2 chars in input")))
    (let [max-length (quot str-length 2)
          lengths (range 1 (inc max-length))
          series (for [length lengths]
            (->> str
              (partition length)
              (map #(clojure.string/join "" %))
              (map #(Integer/parseInt %)))
          )
          consec-series (for [serie series
                              :let [snums (partition 2 1 serie)]
                              :when (every? (fn [[a b]] (= (inc a) b)) snums)]
        serie)]
      (first consec-series))))

@charJe
Copy link

charJe commented Feb 4, 2021

I chose to return nil on cases like "1" instead of error.

(defn consec [string]
  (some
   (fn [num]
     (loop [nums (list (Integer/parseInt (subs string 0 num)))
            num-string (subs string num)]
       (let [num (first nums)]
         (cond
           (and (empty? num-string)
                (< 1 (count nums)))
           , (reverse nums)
           :else
           , (let [next-num (Integer/parseInt (subs num-string 0 (count (str (+ 1 num)))))]
               (when (and (count (str (+ 1 num)))
                          (= (+ 1 num)
                             next-num))
                 (recur (cons next-num nums)
                        (subs num-string (count (str (+ 1 num)))))))))))
   (range 1 (+ 1 (quot (count string) 2)))))

@prairie-guy
Copy link

prairie-guy commented Apr 7, 2021

(defn split-by [ds k]                                                                                                                                 
  "(split-by "111213" 2) -> (11 12 13)"                                                                                                               
  (map (comp read-string join) (partition k ds)))

(defn ascending? [ns]                                                                                                                                 
  "(ascending? '(11 12 13)) -> (11 12 13)"                                                                                                            
  (if (= #{1} (set (map - (rest ns ) ns)))                                                                                                            
    ns))

(defn consec? [ds]
  "(consec? "111213") -> [11 12 13]"
  (->> (range 1 (inc (quot (count ds) 2)))
       (map (partial split-by ds))
       (filter ascending?)
       (first)
       vec))

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment