in Programming

Project Euler Problem 4 Solution: Clojure

Problem Description, from Project Euler

Find the largest palindrome made from the product of two 3-digit numbers

Solution

I couldn’t think of many optimizations for this problem, other than avoiding duplicates when calculating the products of numbers. That’s why I just brute-forced it. The only (barely) interesting thing I did here was to write a function which recognized palindromes. Thinking about the problem now, I suppose we can predict whether the first and last digits of a product will be the same by looking at the hundreds and tens digits of the factors.


; flattens a nested list
(defn flatten [x] (let [s? #(instance? clojure.lang.Sequential %)] (filter (complement s?) (tree-seq s? seq x))))

(defn palindrome? [s]
    (if (or 
        ; all 1 letter strings or 
        ; nils are palindromes
        (<= (count s) 1)
        (nil? s)
        )
        true
        (and
            (= (first s) (last s))
            (palindrome? (take (- (count s) 2) (rest s)))
            )
        )
    )
(defn problem04 []
    (def x (range 100 1000))
    ; sort, then take the last
    (last (sort
        ; filter to only palindromes
        (filter
            #(palindrome? (str %))
            ; distinct products of all 3-digit numbers
            (distinct (flatten
                (map 
                    (fn [n] 
                        (map (fn [a] (* a n)) x)) 
                    x
                    )
                ))
            )
        ))
    )

Comments are closed.