December 7, 2014

Project Euler p. 4

First thing to note, I skipped problem 3 and jumped straight into 4 due to wanting to mess with string manipulation. And prime factorization is not really all that fun.

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.

This was the first time I needed to import a library, the mighty clojure.string!

(ns euler.p04
  (:require [clojure.string :as str]))

No mystery, import clojure.string and alias it to str. With access to string functions we can now declare what property we require of a string in order for it to classify as a palindrome.

A palindrome is a string that reads the same regardless if you start at the left end or the right end. One example would be the name Anna, which reversed is Anna.

In Clojure:

(defn palindrome? [word]
  (= word (str/reverse word)))

What we are looking for is palindrome numbers though, not strings. So we need a handy way to convert a number to its string representation, and then back again. For converting a number to a string we can use the handy clojure.core/str function and for converting a string to a number we can use:

(defn string->number [str]
  (let [n (read-string str)]
    (when (number? n) n)))

Of course, this information could be hidden in palindrome? but a function for asserting palindrome-ness should not have information on how to change the type of any kind of object. And doing this explicit (but unnecessary) type shifting makes the end logic easier to follow in my opinion.

So, now we have what we need in order to filter out palindrome numbers from a set of numbers. Now we need the correct group of numbers. This took me a while to figure out, since I did not want to import another module to do the permutations. After much (too much?) effort I arrived at this piece of code, which did the trick:

(defn three-digit-numbers []
  (for [x (range 1 1000)
        y (range 1 1000)]
    (* x y)))

Which can be generalized into:

(defn permutations [f x y]
  (for [a x
        b y]
    (f a b)))

(def three-digit-numbers (permutations * (range 1 1000) (range 1 1000)))

Since we can now tell whether a number is a palindrome, and generate all the permutations of the products of two three digit numbers, we can ask Clojure to figure out which is the largest palindrome:

(last (sort
      (map string->number
           (filter palindrome?
                  (map str
                       (three-digit-numbers))))))

Which is difficult to read, so ->> to the rescue!

(->>
  (three-digit-numbers)
  (map str)
  (filter palindrome?)
  (map string->number)
  (sort)
  (last))

And there we go! Could this be shorter? Probably. Could this be more Clojure-esque? Positively. Does it matter? Yes, but for the moment it shall suffice until I have learned more Clojure. :)

© Sebastian Hörberg 2018

Powered by Hugo & Kiss.