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.

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