Problem 004: Largest Palindrome Product

From Project Euler:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

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

For this one we'll need to define a few helpers. First, we need a function that determines if a number is palindromic. In order to do that, we'll need to create a function to reverse a number. We could do this easily by converting the number to a string, reversing it, and then converting it back to a number (to avoid issues with leading zeroes) but that's cheating and we can just do it with integer math. Each iteration we have an accumulated number, we just take modulo 10 of our current number and add it to 10 times our accumulator, and then divide our number by 10 to chop off that digit:

(defn reverse-num [n]
  (letfn [(helper [i reversed]
            (if (== i 0)
              reversed
              (helper (quot i 10)
                      (+ (mod i 10)
                         (* 10 reversed)))))]
    (helper n 0)))

We can then use that to define is-palindromic?:

(defn is-palindromic? [n] (== n (reverse-num n)))

Once we have those, we can (mostly) brute force things to get the correct result. We can use a for comprehension to get all the numbers that are products of two 3-digit numbers. We'll do one optimization which is where the second variable y only ranges from the first variable x to 999, since multiplication is commutative and once we've checked 101 * 500 we don't need to check 500 * 101.

(def N 1000)

(println (->> (for [x (range 100 N)
                    y (range x N)]
                (* x y))
              (filter is-palindromic?)
              (apply max)))

There are several other optimizations we can do, if you're interested you can look in the forums for all sorts of creative solutions. However, this code gives the result in a reasonable amount of time (note that on my machine the JVM takes about 1.5s to start up):

$ time clj 4.clj 
906609

real 0m1.747s
user 0m3.478s
sys 0m0.176s