{{ message }}

Instantly share code, notes, and snippets.

# ericnormand/00 New Numbers.md

Last active Jul 1, 2021

New Numbers

A number is new if its digits are not a permutation of a smaller number. For instance, 789 is a new number because its permutations (879, 798, 897, 978, and 987) are all larger than it is. However, 645 is not a new number since 456 and 465 are smaller than it.

Write a function that takes an integer and returns true if it is a new number and false otherwise.

Examples

```(new-number? 789) ;=> true
(new-number? 645) ;=> false
(new-number? 444) ;=> true (it's permutations are not smaller than it)```

Bonus: You may find a clever way to write `new-number?`. In addition to that implementation, implement it in such a way that the definition (no permutations are smaller) is clear from the code.

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

### tugh commented Jun 14, 2021 • edited

```(defn new-number?
[n]
(->> n
str
sort
clojure.string/join
Integer/parseInt
(<= n)))

(defn new-number?
[n]
(let [min-permutation (-> n
str
sort
clojure.string/join
Integer/parseInt)]
(<= n min-permutation)))```

### ehonsey commented Jun 14, 2021 • edited

```(defn new-number? [n]
(if-let [digits (seq (str n))]
(= digits (sort digits))))```

### vpetruchok commented Jun 14, 2021

```(defn new-number? [n]
(->> (str n)
(map  #(Character/digit % 10))
(apply <=)))```

### frankadrian314159 commented Jun 14, 2021 • edited

``````(defn new-number?
[i]
(let [istr (str i)]
(= istr (->> istr
(map int)
(sort)
(map char)
(apply str)))))
``````

### miner commented Jun 14, 2021 • edited

```(defn new-number? [n]
(boolean (reduce (fn [a b] (if (pos? (compare a b)) (reduced false) b)) \0 (str n))))```

Updated (again) to deal with zero digits correctly. Thanks @mchampine.

```(defn new-number? [n]
(let [digs (seq (str n))]
(boolean (reduce (fn [a b] (if (pos? (compare a b)) (reduced false) b))
(first digs)
(drop-while #{\0} (rest digs))))))```

### mchampine commented Jun 14, 2021 • edited

I notice some solutions are getting incorrect results for 30 and 509, both of which are new numbers according to the edabit problem description.

```(defn new-number? [n]
(let [nzdigits (remove #{\0} (seq (str n)))]
(= nzdigits (sort nzdigits))))

(new-number? 789) ;=> true
(new-number? 645) ;=> false
(new-number? 444) ;=> true
(new-number? 30)  ;=> true
(new-number? 509) ;=> true
(new-number? 504) ;=> false```

;; Doh! Thanks @miner, I didn't notice the 1230 problem. Here's a totally different approach:

```(defn new-number? [n]
(->> (combo/permutations (str n))
(remove #(= \0 (first %)))
(map s/join)
(map #(Integer/parseInt %))
(apply min)
(<= n)))

(new-number? 1230) ;=> false```

### mcuervoe commented Jun 14, 2021 • edited

```(defn new-number? [n]
(let [nstr (str n)]
(every? (fn [[a b]] (<= (int a) (int b))) (map (fn [a b] [a b]) nstr (drop 1 nstr)))))```

### miner commented Jun 14, 2021 • edited

@mchampine Try 1230. That should not be a new-number. But I also got it wrong. For example, 100 should be a new number. Back to the drawing board. My improved version is posted above.

### steffan-westcott commented Jun 14, 2021 • edited

Oops. Here's my second attempt which handles `0` digits correctly:

```(defn new-number? [n]
(let [digits (seq (str n))
[zeroes [non-zero & rest-non-zeroes]] (split-with #{\0} (sort digits))
min-perm (concat [non-zero] zeroes rest-non-zeroes)]
(= min-perm digits)))```

### diavoletto76 commented Jun 15, 2021

```(defn new-number? [n]
(->> (str n)
(map str)
(apply <=)))```

### sztamas commented Jun 16, 2021

The clever way to write `new-number?` would be to check that the digits are sorted.
Going with the "bonus" solution of making the implementation clear from the code:

``` (defn new-number? [n]
(every? #(>= % n) (permutated-numbers n)))```

ie. all permutations are larger than `n`.

Also implementing `permutations`, as using it from a contrib package would leave no real challenge for this week :-).

```(defn n->digits [n]
(->> n str (map (comp #(Byte/parseByte %) str))))

(def digits->int (comp #(Integer/parseInt %) (partial apply str)))

(defn others [n xs]
(concat (take n xs) (drop (inc n) xs)))

(defn each-x-and-others [xs]
(map-indexed (fn [n x] [x (others n xs)]) xs))

(defn permutations [xs]
(if (next xs)
(distinct
(for [[x others]        (each-x-and-others xs)
permutated-others (permutations others)]
(cons x permutated-others)))
[xs]))

(defn permutated-numbers [n]
(->> n
n->digits
permutations
;; special case removing numbers starting with zero
;; ie. 012 not considered a permutation of 120
(remove (fn [digits] (= 0 (first digits))))
(map digits->int)))

(defn new-number? [n]
(every? #(>= % n) (permutated-numbers n)))
```

### safehammad commented Jun 16, 2021

Although Eric did say that the problem has been modified, I couldn't resist another attempt to handle `0` as per the original edabit problem as elegantly as possible:

1. Including zeroes, check all digits are ascending from the 2nd digit.
2. Excluding zeros, check all digits are ascending from the 1st digit.
```(defn new-number? [n]
(let [ascii (map int (str n))]
(and
(apply <= 0 (rest ascii))
(apply <= (remove #{(int \0)} ascii)))))

(new-number? 789) ;=> true
(new-number? 645) ;=> false
(new-number? 444) ;=> true
(new-number? 3) ;=> true
(new-number? 30) ;=> true
(new-number? 1230) ;=> false
(new-number? 205) ;=> true
(new-number? 502) ;=> false
(new-number? 2005) ;=> true
(new-number? 2050) ;=> false```

### mchampine commented Jun 16, 2021

handle `0` as per the original edabit problem as elegantly as possible:

Nicely done!

### KingCode commented Jun 16, 2021 • edited

My solution is not elegant nor readable - it uses arithmetic to extract digits, (but deals with zeros).

```(defn digits [n]
(->> 1
(iterate #(* % 10))
(take-while #(<= % n))
last                     ;; starting divisor
(vector nil n)
(iterate (fn [[q r d]]
[(quot r d) (rem r d) (quot d 10)]))
(reduce (fn [qs [q r d]]
(if (zero? d)    ;; stop with zero divisor
(reduced (conj qs q))
(conj qs q)))
[])
rest))

(defn new-number? [n]
(let [digs (digits n)
pos-digs (->> digs (remove #{0}))]
(and (= (apply min pos-digs) (first digs))
(or (= digs pos-digs)
(= 1 (count pos-digs))))))```

As a side note, I would have used instead of `reduce`, a `take-until` fn which differs slightly from `take-while` in that it keeps the first element which fails the test:

```(take-until odd? [2 4 6 7 9 10])
;;=> (2 4 6 7)```

### KingCode commented Jun 16, 2021 • edited

Oooops, after reading all the judicious comments, I realize the permutations do matter specifically because of the position of zero when it appears. So any number with a zero in it must not be a new-number unless it has a single non-zero digit, correct?

Which would make 203, 1230, 100003 not new-numbers, but 10, 50000 would be.

Another way to interpret this would be to consider permutations with leading zeros not numbers, and therefore not relevant, in which case
102 and 1230 would be new-numbers, but I chose instead to allow them, i.e. 012 is number 12 (which the repl allows) and therefore 102 is not a new-number.

I revised my solution accordingly.

### jpmonettas commented Jun 17, 2021 • edited

A more performant approach, just for fun. It doesn't use sequences or strings, just division :

```(defn new-number? [^long n]
;; moving from the back digits should be always decreasing
;; always but skipping zeroes
(loop [rem-digits n
prev 9
last-non-zero 9]
(let [d (rem rem-digits 10)
nextd (quot rem-digits 10)
more? (pos? nextd)]
(if (<= d prev)
;; when decreasing continue unles we reached the end
(if more?

(recur nextd d (if (zero? prev) last-non-zero prev))

true) ;; done, the number looks new

;; else not decreasing check decreasing over the zeroes bridge
(and (not more?)
(zero? prev)
(<= d last-non-zero))))))```

It follows the convention on the site, and also finds 8002 new numbers in the first million integers as a test

### jpmonettas commented Jun 17, 2021

@KingCode here is a shorter version of your digits fn, with the same approach but just one iterate and one reduce

```(defn digits [n]
(->> (iterate (fn [[remd d]] [(quot remd 10) (rem remd 10)]) [n 0])
rest
(reduce (fn [digits [remd d]]
(if (zero? remd)
(reduced (conj digits d))
(conj digits d)))
nil)))```

### KingCode commented Jun 18, 2021

Thank you @jpmonettas.. In addition to cutting the code in half, peeling the digits from the right
is both counter-intuitive and elegant, I like it!

I always prefer digitizing within the arithmetic domain, rather than with character/string methods
with their being conversion and platform dependent, even though (str 345) is much shorter and convenient.

It's true however that a digits fn distracts from the main challenge.

### KubqoA commented Jul 1, 2021 • edited

A bit late to the party, without handling the cases where there might be a leading `0`:

`(defn new-number? [x] (->> x str (map int) (apply <=)))`