Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
430 PurelyFunctional.tv Newsletter

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/

@tugh
Copy link

tugh commented Jun 14, 2021

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

; or for better readability

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

@ehonsey
Copy link

ehonsey commented Jun 14, 2021

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

@vpetruchok
Copy link

vpetruchok commented Jun 14, 2021

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

@frankadrian314159
Copy link

frankadrian314159 commented Jun 14, 2021

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

@miner
Copy link

miner commented Jun 14, 2021

(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
Copy link

mchampine commented Jun 14, 2021

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
Copy link

mcuervoe commented Jun 14, 2021

(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
Copy link

miner commented Jun 14, 2021

@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
Copy link

steffan-westcott commented Jun 14, 2021

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

@miner
Copy link

miner commented Jun 15, 2021

@diavoletto76
Copy link

diavoletto76 commented Jun 15, 2021

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

@sztamas
Copy link

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
Copy link

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
Copy link

mchampine commented Jun 16, 2021

@safehammad

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

Nicely done!

@KingCode
Copy link

KingCode commented Jun 16, 2021

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
Copy link

KingCode commented Jun 16, 2021

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
Copy link

jpmonettas commented Jun 17, 2021

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
Copy link

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
Copy link

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
Copy link

KubqoA commented Jul 1, 2021

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

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