Problem 38 is essentially just a variation on old themes: find a particular concatenated number that is pandigital when multiplied by the numbers 1, 2, …n. You may note the similarity of the code to problem 32. Without going into detail, here is the solution:
;; Uses as-int from problem 37 (defn pandigital-9? [a] (= "123456789" (apply str (sort (rest (.split (str a) "")))))) (defn multiply-and-concat [num upto] (apply str (map #(* num %) (range 1 (inc upto))))) (defn euler-38  (reduce max (for [a (range 1 10000) b (range 2 10) c [(multiply-and-concat a b)] :when (= 9 (count c)) :when (pandigital-9? c)] (as-int c))))
Looking at Chouser’s solution on clojure-euler, I did notice that he chose to use
(.length s) to get the length of a string, rather than
count (which works in linear time). It’s easy for me to forget that buried underneath Clojure’s sequence library there also java’s string abstraction, but I wonder if using
length is really more performant here…
user> (def sss (apply str (repeat 10000000 \a))) #'user/sss user> (dotimes [_ 5] (time (.length sss))) "Elapsed time: 0.059609 msecs" "Elapsed time: 0.01091 msecs" "Elapsed time: 0.009638 msecs" "Elapsed time: 0.00977 msecs" "Elapsed time: 0.009879 msecs" nil user> (dotimes [_ 5] (time (count sss))) "Elapsed time: 0.024554 msecs" "Elapsed time: 0.001281 msecs" "Elapsed time: 0.001032 msecs" "Elapsed time: 0.001038 msecs" "Elapsed time: 9.83E-4 msecs" nil
For the purposes of this probably inaccurate micro-benchmark, it seems that using Clojure’s
count is faster than using
length However, the only conclusion I feel it is safe to draw here is that
count seems to work in constant time for strings. I’m guessing that Chouser did this back in the end of 2008, when
length on strings may have indeed been faster than an older, possibly linear time implementation of
count. The situation now seems to be reversed.
Ciao for now!