Instantly share code, notes, and snippets.

# ericnormand/00 Maxie and Minnie.md

Created May 10, 2022 11:00
Show Gist options
• 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.

### nbardiuk commented May 10, 2022

```(defn- number->digits [number]
(loop [number number
digits '()]
(if (zero? number)
(vec digits)
(recur (quot number 10) (cons (rem number 10) digits)))))

(defn- digits->number [digits]
(->> digits
(reduce (fn [number digit]
(+ digit (* 10 number))))))

(defn- single-pair-swaps [xs]
(for [i (range 0 (count xs))
j (range i (count xs))]
(-> xs
(assoc i (get xs j))
(assoc j (get xs i)))))

(defn swapmaxmin [number]
(->> (number->digits number)
single-pair-swaps
(remove (comp zero? first))
(map digits->number)
(apply (juxt max min))))```

### mchampine commented May 10, 2022 • edited Loading

```(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 commented May 10, 2022

```(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 commented May 10, 2022 • edited Loading

```(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 commented May 10, 2022 • edited Loading

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 commented May 13, 2022 • edited Loading

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 commented May 26, 2022 • edited Loading

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 commented May 26, 2022 • edited Loading

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

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