Project Euler #4

Did problem #4 today. Find the largest product of 2 three digits that is a palindrome.

This one wasn't too hard (given that I don't know clojure well enough to not have to scour docs for the order of arguments and such). First made a function that just returns all the products of 100...999, (actually 101; no product of 100 * anything can be a palindrome) as a list of 2 item vectors of the product and its palindrome, as strings.

Then ran it through a filter which removed all the non-palindromes. Then a map to get one of the elements of the vector. Then mapped it to an integer. Then applied max to that.

However, I hated that solution.

So, I improved upon it slightly by reversing the range to start from the high point and counting down, thinking that I could generate the palindromes in pre-sorted order, and I could just take the first one. Unfortunately, my plan did not work. But, I did realize how to better use the for comprehension to do the filtering for me, rather than after the fact, so I didn't bother doing as many int -> string -> int conversions, which did make it faster. I also eliminated the function wrapping the for, and just stuck it inline. So what I ended up with is here:

(apply max (for [a (range 1000 101 -1) b (range 1000 a -1)

:when (=

(.toString (* a b))

(apply str (reverse (.toString (* a b)))))] (* a b)))

Project Euler in Clojure

Problem 3; what's the biggest prime factor of some big #?

I went a lot of ways here, but finally ended up with the following. First, I made a function which would factor a number. I poked at this a lot of times before I ended up on the for comprehension, which I'm not sure is the best way by far, but I wanted to play with it. It runs up a counter from 2 to the sqrt(target), and if the target MOD the number is 0, returns the number and the "other" factor in a list, then flattens the list of lists when done. (Ideas welcome for removing the flatten... something with cons/conj?)

Then I wrote a "prime" method which tells me if a number is prime. It does this by just factoring the number using my factor func, then counts the factors. If it's 2, it's prime (1 and the # itself).

Then it was a simple matter of calling factor on my big #, filtering the factors returned through the prime method, and calling max on the result. Ah, but max doesn't take a seq... so I had to 'apply' max to the result. Lots of lessons learned here, and looking for advice on how this could be more clojurific.

(defn factor [m] (flatten (for [a (range 1 (Math/sqrt m)) :when (zero? (mod m a))] (list a (/ m a)))))

(defn prime [n] (= 2 (count (factor n))))

(apply max (filter prime (factor 600851475143)))

Learning Clojure

I've started my journey down clojure land. 4clojure and Project Euler are my first goals. Started with project Euler. Here are my first couple solutions. Critiques on clojure idioms, style, optimizations welcome.

#1. http://projecteuler.net/problem=1

Find the sum of all the multiples of 3 or 5 below 1000.

(reduce + (filter #(or (zero? (mod % 3)) (zero? (mod % 5))) (range 1 1000)))

#2. http://projecteuler.net/problem=2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

My solution:

(defn fib [x]

(cond

(<= x 3) x

:else (+ (fib (- x 2)) (fib (- x 1)))))

(reduce + (filter even? (take-while #(< % 4000000) (map fib (iterate inc 1)))))

The unusual form of fibonacci is due to the requirement; the sequence starts with 1 and 2 instead of 0 and 1, so the first 3 terms are 1,2,3 so that is a teensy teensy point of optimization.

I actually started with a range, but that starts with 0 which isn't quite right, and if you have a starting point (say... 1), on a range, you need an ending point. And while I could have used an obviously too high end point (which is actually what I started with), it didn't feel right, so I dug around for the function I knew existed, but couldn't locate.... until I found iterate.