euler43.clj

;;
;; The number, 1406357289, is a 0 to 9 pandigital number because it is made
;; up of each of the digits 0 to 9 in some order, but it also has a rather
;; interesting sub-string divisibility property.

;; Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:

;; d2d3d4=406 is divisible by 2
;; d3d4d5=063 is divisible by 3
;; d4d5d6=635 is divisible by 5
;; d5d6d7=357 is divisible by 7
;; d6d7d8=572 is divisible by 11
;; d7d8d9=728 is divisible by 13
;; d8d9d10=289 is divisible by 17
;; Find the sum of all 0 to 9 pandigital numbers with this property.

; http://projecteuler.net/problem=43


; Generates all possible numbers using each digit once in each number.
; Returns a list of strings representing these numbers.
(defn pandigitals
  ([] (pandigitals (range 10)))
  ([available-digits]
    (case (count available-digits)
      0 ()
      1 (list (str (first available-digits)))
      (reduce (fn [generated-combinations digit]
                (when (= (count available-digits) 10)
                  (println "Calculating pandigitals starting with" digit))
                ; ignores combinations starting with 0
                (if (and (= digit 0) (= (count available-digits) 10))
                    generated-combinations
                    (let [remainder-combinations (pandigitals (remove #{digit} available-digits))]
                      (concat generated-combinations
                              (map #(str digit %) remainder-combinations)))))
              ()
              available-digits))))

; number must be a string representing a number
(defn divisible-substrings? [number]
  (every? (fn [[start-index end-index divisor]]
            ; previously using read-string to convert to a number, but it
            ; doesn't work for strings with leading zeros (ex. "028"),
            ; producing the exception
            ; java.lang.NumberFormatException: Invalid number
            ; Apparently this is because Clojure tries to parse it as an
            ; octal, and "028" is not an octal.
            ; http://stackoverflow.com/a/5662823/974795
            (= (rem (Integer. (subs number start-index end-index))
                    divisor)
               0))
          '([1 4 2]       ;; d2d3d4 is divisible by 2
            [2 5 3]       ;; d3d4d5 is divisible by 3
            [3 6 5]       ;; d4d5d6 is divisible by 5
            [4 7 7]       ;; d5d6d7 is divisible by 7
            [5 8 11]      ;; d6d7d8 is divisible by 11
            [6 9 13]      ;; d7d8d9 is divisible by 13
            [7 10 17])))  ;; d8d9d10 is divisible by 17

;(divisible-substrings? "1406357289")
; => true

(defn sum-divisible-pandigitals []
  (apply + (map read-string (filter divisible-substrings? (pandigitals)))))

(time
  (println "The sum of all 0 to 9 pandigital numbers with the divisibility property is"
           (sum-divisible-pandigitals)))

; 16695334890
; "Elapsed time: 193333.114 msecs"