« back

Finding Palindromes Using Clojure - Project Euler Problem 4

14 Nov 2012

Today, let's take a look at how to detect palindromes and then use that info to find the solution to Project Euler's problem number 4...

Although it took me a lot longer to arrive at this solution then it would probably appear by the length of the code, I really had a problem with thinking I found a solution only to find that a function I wanted to use was deprecated. Where Did Clojure Contrib Go? can be a help but the posts that are already out on the web about how to do things can really be misleading compared to the current state of the language. If you are thinking "Oh, duh, just call reverse", no dice. Part of the challenge was to do it without using reverse.

Let's take a look at how to detect a palindrome and then we can move to solving the rest of the problem. Basically, I want to take a string or a number, reverse it, and then compare it to the original to see if they are the same. With my tests, I just walked through examples starting with a single digit and going up from there. I have included all of my tests just so you could see them but just to be clear, I did not just write all of these out directly before I wrote the code, I started with one, wrote some code, refactored, and did the whole red, green, refactor cycle again. The code below is my final solution. As you will see below, a foreshadowing that I will likely be using numbers. For me, the easiest way to deal with that is just to convert it to a string. In my namespace I included string.

2     (ns project_euler.core
3     	(:require [clojure.string :as str]))

 2     ;tests
 3     ;for 1 character
 4     (it "should return true for a one character palindrome"
 5 		(should= true (palindrome? 1)))
 7 	;for 2 characters
 8 	(it "should return true for a two character palindrome"
 9 		(should= true (palindrome? 11)))
11 	(it "should return false for a two chatacter non-palindrome"
12 		(should= false (palindrome? 12)))
14 	;and then for additional cases
15 	(it "should return true for a 5 digit palindrome"
16 		(should= true (palindrome? 1095901)))
18 	(it "should be able to detect string palindromes as well"
19 		(should= true (palindrome? "abba")))
21 	(it "should be should return false when strings are not palindromes"
22 		(should= false (palindrome? "abcd")))
24     ;code
25     (defn palindrome? [n]
26     	(let [b (str n)]
27     	(= b (str/join "" (reduce conj '() b)))))

So now for the rest of the Project Euler problem. Here it is in it's entirety. Find the largest palindrome made from the product of two 3-digit numbers.

2     ;test
3     (it "should generate a list of products from all 3 digit numbers"
4 		(should= [10000 10100 10200 10300 10400] (take 5 (generate-products-of-3-digit-numbers))))
6 	;code
7 	(defn generate-products-of-3-digit-numbers []
8     	(for [x (range 100 1000) y (range 100 1000)] (* x y)))

And then for the final number...

2     ;test
3     (it "should f ind the largest palindrome"
4 		(should= 906609 (find-largest-palindrome)))
6 	;code
7 	(defn find-largest-palindrome []
8     	(reduce max (filter palindrome? (generate-products-of-3-digit-numbers))))

BOOM! I just dropped a sweet bomb of awesome palindrome solving knowledge on you.

comments powered by Disqus