430 PurelyFunctional.tv Newsletter

00 New Numbers.md

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.

Please submit your solutions as comments on this gist.

To subscribe: https://purelyfunctional.tv/newsletter/

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

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

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

@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.

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

See also: https://oeis.org/A179239

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

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

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

@safehammad

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

Nicely done!

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)

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.

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

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

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.

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