468 Eric Normand Newsletter

00 Maxie and Minnie.md

Maxie and Minnie

The maxxie of a number n is the largest number you can achieve by swapping two of its digits (in decimal) (or choosing not to swap if it is already the largest possible). The minnie is the smallest with one swap (though you can't swap a zero digit into the most significant position).

Your task is to write a function that takes an integer and returns a tuple of the maxxie and minnie.

Examples

(swapmaxmin 213) ;=> [312, 123]
(swapmaxmin 12345) ;=> [52341, 12345] ;; the number was already the smallest
(swapmaxmin 100) ;=> [100, 100] ;; no swap possible because of zeroes

Notes

• Swap any two decimal digits
• No leading zeroes
• Don't swap if you can't make it bigger/smaller

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

Please submit your solutions as comments on this gist.

To subscribe: https://ericnormand.me/newsletter

(defn swapc [c i j]
  (if (= \0 (get c j)) c
      (assoc (assoc c i (get c j)) j (get c i))))

(defn allswaps [c]
  (for [f (range (dec (count c))) s (range f (count c))]
    (apply str (swapc (into [] c) f s))))

(defn swapmaxmin [n]
  (apply (juxt max min) (map read-string (allswaps (str n)))))

(defn generate-swaps [number]
  (let [v (-> number str vec)
        inds (-> v count range)]
    (for [i inds
          j inds
          :let [x (-> v
                      (assoc i (nth v j))
                      (assoc j (nth v i)))]
          :when (not= \0 (first x))]
      (Long/parseLong (apply str x)))))

(def swapmaxmin (comp (juxt #(apply max %) #(apply min %)) generate-swaps))

(defn swaps [n]
  (let [s (vec (str n))]
    (for [j     (range 1 (count s))
          i     (range j)
          :let  [s' (assoc s i (nth s j) j (nth s i))]
          :when (not= \0 (nth s' 0))]
      (read-string (apply str s')))))

(defn swapmaxmin [n]
  ((juxt #(reduce max n %) #(reduce min n %)) (swaps n)))

I think this works

(defn num->digits [num]
  (->> num str (mapv (comp parse-long str))))

(defn digits->num [digits]
  (reduce (fn [n d] (+ d (* 10 n))) digits))

(defn swap [xs i1 i2]
  (assoc xs i2 (xs i1) i1 (xs i2)))

(defn get-all-swaps [digits]
  (let [cnt (count digits)]
    (into
     (for [i (range 0 cnt)             ; where we swap from.
           j (range 1 cnt)             ; where we swap to.
           :let [xs (swap digits i j)] ; swap
           :when (not= 0 (first xs))]     ; dont swap a 0 to first pos.
       xs)
     [digits digits])))                ; in case we have no valid swaps.

(defn solve [n]
  (->> n
       num->digits
       get-all-swaps
       (map digits->num)
       (apply (juxt min max))))

Testing

(solve 12345) => [12345 52341]
(solve 213) => [123 312]
(solve 1) => [1 1]
(solve 92484957) => [29484957 99484257]
(solve 120142185) => [102142185 820142115]

Not pretty, but pretty fast. Trying to avoid testing all swaps by looking just for the best min/max swap. Refactored to use internal search function which adapts to starting point.

(defn swapmaxmin [n]
  (let [dv (mapv (fn [c] (- (long c) (long \0))) (str n))
        cnt1 (dec (count dv))
        sumv (fn [dv] (reduce (fn [r d] (+ (* r 10) d)) 0 dv))
        rfn-max (fn [_] (fn [j i] (if (> (dv i) (dv j)) i j)))
        rfn-min (fn [from] (if (zero? from)
                             (fn [j i] (cond (zero? (dv i)) j
                                             (< (dv i) (dv j)) i
                                             :else j))
                             (fn [j i] (if (< (dv i) (dv j)) i j))))
        search (fn [sfn-from]
                 (loop [from 0]
                   (let [i (reduce (sfn-from from) from (range cnt1 from -1))]
                     (if (= i from)
                       (if (< from cnt1) (recur (inc from)) n)
                       (sumv (assoc dv from (dv i) i (dv from)))))))]
    [(search rfn-max)
     (search rfn-min)]))

Well, not the shortest and sweetest compared to the snippets above, but it works B-)
I think may background in Racket (recursion) shines through.

(ns normand468.core)

(defn num->vec
  "return vector of Integer from a Natural"
  [n](loop [v nil rst n]
       (if (zero? rst) (vec v)
           (recur (conj v (mod rst 10)) (int (/ rst 10))))))

(defn vec->num
  "return Natural from vector of Integer"
  [v] (loop [n 0 rst v]
        (if (empty? rst) n
            (recur (+ (* 10 n) (first rst)) (rest rst)))))

(defn largest
  "return [index num] of the largest number to be swapped."
  [xs] (loop [xmax 0 xpos 0 rst xs idx 0]
         (if (empty? rst) [xpos xmax]
             (let [nxt (first rst)]
               (if (>= nxt xmax)
                 (recur nxt idx (rest rst) (inc idx))
                 (recur xmax xpos (rest rst) (inc idx)))))))

(defn smallest
  "return [index num] of the smallest number>0 to be xswapped."
  [xs] (loop [xmin 10 xpos 0 rst xs idx 0]
         (if (empty? rst) [xpos xmin]
             (let [nxt (first rst)]
               (if (<= nxt xmin)
                 (recur nxt idx (rest rst) (inc idx))
                 (recur xmin xpos (rest rst) (inc idx)))))))

(defn swapmax
  [x] (let [xs (num->vec x)
            large-x (largest (num->vec x))
            xpos (first large-x)
            xmax (second large-x)]
        (assoc xs 0 xmax, xpos (xs 0))))
       
(defn swapmin
  [x] (let [xs (num->vec x)
            small-x (smallest (num->vec x))
            xpos (first small-x)
            xmin (second small-x)]
        (if (> xmin 0) (assoc xs 0 xmin, xpos (xs 0))
            (assoc xs 1 xmin, xpos (xs 1)))))
            
(defn swapmaxmin
  [n] (let [vmax (swapmax n)
            vmin (swapmin n)]
         [(vec->num vmax) (vec->num vmin)])) 

I sorted the digits, bypassing one or both results depending on the presence of zeroes.

I wanted to do a single pass for both min and max values, and was looking for a sorted-vector-by within clojure.core, but couldn't find one, so translated java.util.Arrays.binSearch0 with the use of clojure.core/comparator

An IPersistentTreeVector would be nice, maybe using IPersistentTreeMap underneath (as is done with IPersistentTreeSet.java). Then a sorted-vector function could yield something that is super fast and truly O(log n), instead of what sorted-conj below, does. Alternatively, a transient coll could be used to do each insert.

(defn n->digs [n]
  (loop [n n acc ()]
    (let [[q r] [(quot n 10) (rem n 10)]]
      (if (zero? n)
        acc
        (recur (quot n 10) (conj acc r))))))

(defn digs->n [digs]
  (->> 1 
       (iterate (fn [pow] 
                  (* pow 10))) 
       (map #(* % %2) (reverse digs))
       (apply +)))

(defn insert-idx 
  [xs x pred]
  (let [cmptor (comparator pred)]
    (loop [lo 0 hi (dec (count xs))]
      (if (> lo hi)
        lo 
        (let [mid (bit-shift-right (+ lo hi) 1)
              midv (nth xs mid)
              cmp (cmptor midv x)]
          (cond 
            (< cmp 0)
            (recur (inc mid) hi)
            (> cmp 0)
            (recur lo (dec mid))
            :else
            mid))))))

(defn sorted-conj 
  ([xs x pred]
   (let [insert-loc (insert-idx xs x pred)]
     (-> xs (subvec 0 insert-loc)
         (into [x])
         (into (subvec xs insert-loc (count xs)))))))

(defn swapmaxmin [n]
  (let [[[max :as maxseq] [min :as minseq]] 
        (->> n n->digs
             (reduce (fn [[maxs mins] d]
                       [(sorted-conj maxs d >) 
                        (sorted-conj mins d <)])
                     [[] []]))]
    (cond 
      (and (zero? max) (zero? min))
      [n n]
      (zero? min)
      [(digs->n maxseq) n]
      :else
      [(digs->n maxseq) (digs->n minseq)])))

(swapmaxmin 202)
;;=> [220 202]
(swapmaxmin 100)
;;=> [100 100]
(swapmaxmin 1234)
;;=>[4321 1234]