399 - PurelyFunctional.tv Newsletter

00 Digit search.md

Digit search

This is one of those weird programming puzzles with no real point except practice. But it's considered Very Hard in JavaScript. Let's see how we do in Clojure.

Write a function that takes a sequence of integers. You're trying to get all 10 digits by looking through the numbers sequentially. When you have found one instance of every decimal digit, return whatever number you were on when you found the last one. If you get to the end of the sequence without finding all the digits (for instance, maybe there was no 9), then just return nil.

Example

(digit-search   [5175 4538 2926 5057 6401 4376 2280 6137]) ;=> 5057
;; digits found: 517- 4-38 29-6 -0

(digit-search   [5719 7218 3989 8161 2676 3847 6896 3370]) ;=> 3370
;; digits found: 5719 -2-8 3--- --6- ---- --4- ---- ---0

(digit-search   [4883 3876 7769 9846 9546 9634 9696 2832]) ;=> nil
;; digits found: 48-3 --76 ---9 ---- -5-- ---- ---- 2---
;; 0 and 1 are missing

Thanks to this site for the challenge idea where it is considered Very Hard level in JavaScript.

I got in the possibly bad habit of using arguments after the first for behavior internal to the function while going through the 4clojure exercises. The use is clear when looking at the functions, but I can see how it might be confusing looking over the docstring. I could lift it into an internal function, but it feels ugly.

(defn digit-search
  "Search through a sequence of numbers until all digits have occurred once, returning that number"
  ([digits] (digit-search digits #{}))
  ([digits found]
   (if (empty? digits) nil
       (let [head (first digits)
             new-found (clojure.set/union found (set (str head)))]
         (if (= new-found #{\0 \1 \2 \3 \4 \5 \6 \7 \8 \9}) head
             (recur (rest digits) new-found))))))

(deftest digit-search-test
  (testing "Email Examples"
    (is (= (digit-search [5175 4538 2926 5057 6401 4376 2280 6137]) 5057))
    (is (= (digit-search [5719 7218 3989 8161 2676 3847 6896 3370]) 3370))
    (is (nil? (digit-search [4883 3876 7769 9846 9546 9634 9696 2832])))))

(def target #{\0 \1 \2 \3 \4 \5 \6 \7 \8 \9})

(defn digit-search
  ([numbers] (digit-search numbers #{}))
  ([numbers acc]
   (let [n (first numbers)]
     (when n
       (let [acc' (apply conj acc (seq (str n)))]
         (if (= target acc')
           n
           (recur (rest numbers) acc')))))))

;; Hi everyone - tried to write "a" function (as in one) and not use anything outside of clojure.core

(fn [sequence]
   (loop [cursor sequence
          digits #{}]
     (when-not (= 0 (count cursor))
       (let [intermediate-digits (->> (first cursor)
                                      (str)
                                      (into digits))]
         (if (= 10 (count intermediate-digits))
           (first cursor)
           (recur (rest cursor) intermediate-digits))))))

(defn digit-search [input]
  (loop [[[dset d] & r] (map (fn [n] [(set (str n)) n]) input)
         rem-digits #{\0 \1 \2 \3 \4 \5 \6 \7 \8 \9}]
    (when d
      (let [rem-digits' (clojure.set/difference rem-digits dset)]
       (if (empty? rem-digits')
         d
         (recur r rem-digits'))))))

(defn digit-search [input]
  (second
    (reduce
      (fn [[digits-found _] integer]
        (let [digits-found (into digits-found (str integer))]
          (if (= 10 (count digits-found))
            (reduced [nil integer])
            [digits-found nil])))
      [#{}]
      input)))

(digit-search [5175 4538 2926 5057 6401 4376 2280 6137])
=> 5057
(digit-search [4883 3876 7769 9846 9546 9634 9696 2832])
=> nil

(defn digit-search [xs]
  (->> xs (map #(vector (str %) %)) 
       (reduce (fn [[acc _] [s x]]
                 (let [acc' (into acc s)]
                   (if (= 10 (count acc'))
                     (reduced [nil x])
                     [acc' nil])))
               [#{} nil])
       second))

@KingCode, nice! I was trying to do a "reduced" variant but couldn't get it working. Btw, looks like you could just (str x) as you go:

(defn digit-search [xs]
  (->> xs (reduce (fn [[acc _] x]
                    (let [acc' (into acc (str x))]
                      (if (= 10 (count acc'))
                        (reduced [nil x])
                        [acc' nil])))
                  [#{} nil])
       second))

And you inspired me to try "reduced" solution based on your code. Not as elegant, but it's pretty short!

(defn digit-search [ns]
  (let [v (reduce (fn [a x] (let [a' (into a (str x))]
            (if (= 10 (count a')) (reduced x) a'))) #{} ns)]
    (if (int? v) v nil)))

(defn digit-search
  [ns]
  (let [n->digits (fn [n] (-> n str seq set))
        all-digits (-> "0123456789" seq set)
        reds (reductions (fn [[_ s] n]
                           [n (clojure.set/difference s (n->digits n))])
                         [-1 all-digits]
                         ns)
        res (drop-while #(not-empty (second %)) reds)]
    (when (not-empty res)
      (first (first res)))))

@hby A string is already seqable so you can just write all-digits (set "0123456789")

(defn digit-search [xs]
  (let [n (reduce (fn [acc x]
                    (let [digits (into acc (str x))]
                      (if (= (count digits) 10) (reduced x) digits)))
                  #{} xs)]
    (when (number? n) n)))

(defn digit-search [coll]
  ;; digs starts as 10 bits corresponding to 0-9 chars
  (loop [coll coll digs (bit-shift-left 1023 (long \0))]
    (when-first [i coll]
      (let [digs (long (reduce (fn [bits ch] (bit-clear bits (long ch))) digs (str i)))]
        (if (zero? digs)
          i
          (recur (rest coll) digs))))))

(defn digit-search [ds]
  (let [digits (into #{} "0123456789")
        r (reduce (fn [acc d]
                    (let [res (->> d str (into acc))]
                      (if (= digits res) (reduced d) res)))
                  #{} ds)]
    (when (number? r) r)))

(digit-search [5175 4538 2926 5057 6401 4376 2280 6137])
;; => 5057
(digit-search   [5719 7218 3989 8161 2676 3847 6896 3370])
;; => 3370
(digit-search [4883 3876 7769 9846 9546 9634 9696 2832])
;; => nil

edit: changed the final sexp in the function from a dumb if to when

@kthu got me interested in writing the progress info. Three observations:

1. The tally was even more fun to figure out than the original puzzle. (For me.)
2. I feel a bit dirty because I allowed the debug printing to choose the data structure used for the actual task.
3. Printing lazy sequences was the trickiest of it all.

Seems like Clojure makes hard things easy but some easy things hard. 😄

(defn- tally [seen n]
  (->> (reduce (fn [seen d]
                 (conj seen
                       (if ((set seen) d) \- d)))
               seen
               (str n))
       (drop (count seen))))

(defn digit-search
  {:test (fn []
           (testing "We can do Very Hard JavaScript"
             (is (= 5057 (digit-search [5175 4538 2926 5057 6401 4376 2280 6137])))
             (is (= 90 (digit-search [1234 5678 90])))
             (is (nil? (digit-search [01234 56789]))) ; ¯\_(ツ)_/¯
             (is (= 3370 (digit-search [5719 7218 3989 8161 2676 3847 6896 3370])))
             (is (nil? (digit-search [4883 3876 7769 9846 9546 9634 9696 2832])))))}
  [s]
  (let [dbg-state (atom [])
        found (reduce (fn [seen n]
                        (swap! dbg-state conj {:n n :tally (tally seen n)})
                        (->> n
                             (str)
                             (into seen)
                             (#(if (= 10 (count (set %)))
                                 (reduced n)
                                 %))))
                      []
                      s)]
    (println (map :n @dbg-state))
    (println (seq (map (comp (partial apply str) seq :tally) @dbg-state)))
    (when (number? found)
      found)))

Giving this function to the Calva test runner it prints this:

; Running tests for pftv-399...
(5175 4538 2926 5057)
(517- 4-38 29-6 -0--)
(1234 5678 90)
(1234 5678 90)
(668 56789)
(6-8 5-7-9)
(5719 7218 3989 8161 2676 3847 6896 3370)
(5719 -2-8 3--- --6- ---- --4- ---- ---0)
(4883 3876 7769 9846 9546 9634 9696 2832)
(48-3 --76 ---9 ---- -5-- ---- ---- 2---)
; 5 tests finished, all passing 👍, ns: 1, vars: 1

No love for string scans?

(defn digit-search [nums]
  (let [ds "0123456789"
        s (str (apply print-str nums) " ;" ds)
        i (transduce (map #(->> (.indexOf s (int %)) (.lastIndexOf s " "))) max -1 ds)]
    (read-string {:eof nil} (subs s (inc i)))))

I'm late to the game, but here's my solution:

(def goal
  (set "0123456789"))

(defn digit-search [xs]
  (loop [xs xs found #{}]
    (when-let [x (first xs)]
      (let [found' (into found (str x))]
        (if (= goal found')
          x
          (recur (rest xs) found'))))))

;; (digit-search   [5175 4538 2926 5057 6401 4376 2280 6137])
;; => 5057

;; (digit-search   [5719 7218 3989 8161 2676 3847 6896 3370])
;; => 3370

;; (digit-search   [4883 3876 7769 9846 9546 9634 9696 2832])
;; => nil

(defn digit-search
  [nums]
  (let [all-digits (into #{} (map #(char (+ (int \0) %)) (range 10)))
        res (reduce #(let [s (into %1 (str %2))] (if (= all-digits s) (reduced %2) s)) #{} nums)]
    (if (set? res) nil res)))

Write a function that takes a sequence of integers. You're trying to get all 10 digits by looking through the numbers sequentially. When you have found one instance of every decimal digit, return whatever number you were on when you found the last one. If you get to the end of the sequence without finding all the digits (for instance, maybe there was no 9), then just return nil.

(defn digits
  [n]
  (->> n
       (iterate #(quot % 10))
       (take-while pos?)
       (map #(mod % 10))))

(def found? #(= 10 (count %)))

(defn digit-search
  [ds]
  (let [ret (reduce
             (fn [acc [ns n]]
               (let [acc (into acc ns)]
                 (if (found? acc)
                   (reduced n)
                   acc)))
             #{}
             (map (juxt digits identity) ds))]
    (when-not (coll? ret)
      ret)))



(digit-search   [5175 4538 2926 5057 6401 4376 2280 6137]) ;=> 5057
;; digits found: 517- 4-38 29-6 -0

(digit-search   [5719 7218 3989 8161 2676 3847 6896 3370]) ;=> 3370
;; digits found: 5719 -2-8 3--- --6- ---- --4- ---- ---0

(digit-search   [4883 3876 7769 9846 9546 9634 9696 2832]) ;=> nil
;; digits found: 48-3 --76 ---9 ---- -5-- ---- ---- 2---
;; 0 and 1 are missing

@cgrand

No love for string scans?

     (transduce (map #(->> (.indexOf s (int %)) (.lastIndexOf s " "))) max -1 ds)]

Whoa, mind blown. I get it now, but it took some effort! Good to have that technique added to the tool chest.

(defn digit-search [coll]
  (loop [mask 1023
         coll coll]
    (when-first [n coll]
      (let [res (reduce #(bit-clear %1 (- (int %2) (int \0))) mask (str n))]
        (if (zero? res)
          n
          (recur res (rest coll)))))))

Ok, I've got another one, this time it's a branchless solution

(defn digit-search [nums]
  (->> nums (map-indexed (fn [i n] (zipmap (str n) (repeat [i n])))) (reduce #(into %2 %1) {})
    vals (cons [Integer/MAX_VALUE]) (take-last 10) (apply max-key first) second))

This is addictive. Should have thought of "reductions" earlier:

(defn digit-search [nums]
  (ffirst (filter #(= 10 (count (second %)))
                  (zipmap nums (rest (reductions #(into %1 (str %2)) #{} nums))))))

or a minor variant for a (long) one liner!

(defn digit-search [ns]
  (get ns (count (take-while #(< (count %) 10) (rest (reductions #(into %1 (str %2)) #{} ns))))))

@mchampine Nice ones!

transient set for performance, but not as fast as my previous "bits" solution

(defn digit-search [coll]
  (loop [coll coll digs (transient #{\0 \1 \2 \3 \4 \5 \6 \7 \8 \9})]
    (when-first [i coll]
      (let [digs (reduce disj! digs (str i))]
        (if (zero? (count digs))
          i
          (recur (rest coll) digs))))))

Uses vector indices to keep up with digits.

(defn digit-search [all-nums]
  (loop [nums all-nums
         digits (vec (take 10 (repeat false)))]
    (when (seq nums)
      (let [updated-digits (reduce #(assoc %1 %2 true) digits (map #(- (int %) 48) (seq (str (first nums)))))]
        (if (every? true? updated-digits)
          (first nums)
          (recur (rest nums) updated-digits))))))

(defn digit-search [nos]
  (let [result (reduce
                 (fn [digits-so-far n]
                   (let [digits (into digits-so-far (str n))]
                     (if (= 10 (count digits))
                       (reduced n)
                       digits)))
                 #{}
                 nos)]
    (if (set? result) nil result)))

(defn digitize [n]
  (map #(- (int %) 48)
       (seq (str n))))

(defn digit-search [digits]
  (loop [coll digits
         accumulator #{}]
    (if (empty? coll)
      nil
      (if
       (clojure.set/subset? #{0 1 2 3 4 5 6 7 8 9}
                            (clojure.set/union (set (digitize (first coll)))
                                               accumulator))
        (first coll)
        (recur (rest coll)
               (clojure.set/union
                (set (digitize (first coll)))

I hope it is not a faux pas to jump in with some JavaScript!

function extract_digits(integer, radix) {
    const remainder = integer % radix;
    const quotient = Math.floor(integer / radix);
    return (
        quotient === 0
        ? [remainder]
        : extract_digits(quotient, radix).concat(remainder)
    );
}

function digit_search(integers, radix = 10, found_digits = new Set()) {
    if (integers.length === 0) {
        return null;
    }
    extract_digits(integers[0], radix).forEach(
        (digit) => found_digits.add(digit)
    );
    return (
        found_digits.size === radix
        ? integers[0]
        : digit_search(integers.slice(1), radix, found_digits)
    );
}

(defn digit-search
  [xs]
  (loop [found #{}
         remain xs]
    (when-let [this (first remain)]
      (let [newfound (->> this
                          str
                          seq
                          set
                          (clojure.set/union found))]
        (if (= 10 (count newfound))
          this
          (recur newfound (rest remain)))))))```

Solution using tail-recursion-

(require '[clojure.set :refer [union]])

(defn digits [num]
    (set (str (Math/abs num))))

(defn digit-search [nums]
    (loop [nums nums s #{}] 
          (if (empty? nums) 
              nil 
              (let [num (first nums) new-s (union s (digits num))] 
                   (if (= 10 (count new-s)) 
                       num 
                       (recur (rest nums) new-s))))))

Ugly but it works hihi

(defn digits
  [number]
  (if (< number 10)
    [number]
    (conj (digits (quot number 10)) (rem number 10))))


(defn digit-search
  ([numbers] (digit-search numbers #{}))
  ([numbers decimals]
   (let [number (first numbers)]
     (if (not number)
       nil
       (let [digits (digits number)
             updated-decimals (reduce conj decimals digits)]
         (if (= 10 (count updated-decimals))
           number
           (digit-search (rest numbers) updated-decimals)))))))