Project Euler Problem 38

Ivar Thorson bio photo By Ivar Thorson

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

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!