Skip to content

Instantly share code, notes, and snippets.

@ericnormand
Created May 10, 2022 11:00
Show Gist options
  • Save ericnormand/4ca47720a954307739aaeb12682de98a to your computer and use it in GitHub Desktop.
Save ericnormand/4ca47720a954307739aaeb12682de98a to your computer and use it in GitHub Desktop.
468 Eric Normand Newsletter

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

@mchampine
Copy link

mchampine commented May 10, 2022

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

@jonasseglare
Copy link

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

@steffan-westcott
Copy link

steffan-westcott commented May 10, 2022

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

@stuarts-exmos
Copy link

stuarts-exmos commented May 10, 2022

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]

@miner
Copy link

miner commented May 13, 2022

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

@Jimmysnielsen
Copy link

Jimmysnielsen commented May 26, 2022

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

@KingCode
Copy link

KingCode commented May 26, 2022

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]

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