Learning Clojure with Project Euler | Hacker News Reader

Learning Clojure with Project Euler

grok-code.com

38 pointsgrokcode10 comments

The 2nd and 3rd solutions are also incorrect.

The second solution will run indefinitely:

  (defn e2 [limit]
    (filter #(and (< % limit)
             (zero? (mod % 2)))
          fibs))

Using a predicate in the filter function of "< limit and mod 2 == 0" does not work as the fibs sequence is evaluated even after the terms in the sequence become greater than the limit (all it means is that every term above the limit is filtered out). Replacing the limit check with take-while would fix this.

The third solution is also broken, it works fine for small values of n but enter a large number such as is given in the problem and you quickly run out of stack. Replacing the recursive call with recur will enable tail-call optimisation and give your stack a lot more breathing room.

I recommend the clojure-euler wiki for more reliable examples of good clojure code :)

Ha thanks for your comments spuz. Not sure what happened on #2 that I ended up posting broken code. For number #3, I don't think recur will work without changing the algorithm a bit. There are 2 recursive calls depending on the conditional, and recur needs to be last for it to compile. Also in my defense it works on my machine ;)

So, yes its a learning process. I'm updating the post. Thanks again for your comments.

I tried your solution to #3 on my old windows laptop and trying to find the prime factors for 600851475143 gave a stack overflow. However, replacing the recursive calls with recur produced the correct result. I think this is because only one of the two branches that recurse is ever executed so tail-call optimisation is still possible in this case. If it was called twice (as in some implementations of the Fibonacci sequence) I'm guessing it would fail.

Sure makes sense. Any idea why clojure doesn't do automatic tail call optimization, and instead depends on recur?

The first reply at http://groups.google.com/group/clojure/browse_thread/thread/... goes into pretty good detail from the language designer.

The short version is that it's a limitation in the JVM currently that he's hoping is removed some day.

wiki for Clojure solutions http://clojure-euler.wikispaces.com/

nice ;)

Actually, on serious note, a great way to compare if your clojure code looks anything like it should.

>The above simply creates a lazy sequence of all of the numbers between (inclusive) 1 and limit - 1.

> (range 1 (- limit 1))

this is wrong, it should be: (range 1 limit)

which will produce: (1 2 3 ... 999)

This is interesting. I'd be interested to see the runtimes of these programs. It's fascinating to see how fast some of the most seemingly-complicated problems go. (It's also fun to use a programming language with unlimited-size integers, as I think Clojure has -- for an example, see problem 97. Arc just did the arithmetic in 44 milliseconds without me having to do any optimization.)

Clojure promotes Integer's to Long's and BigInteger's, if needed. Compare (type 5) (type 555555555555) (type 55555555555555555555555555555555555555555555555555555555555)

The difference is thus visible to the programmer and can be controlled with type hints.

Funny, I just started a new repo for doing euler problems with clojure. I'm only on the first couple problems, but am generally pretty impressed. For the seconed problem (sum of fibonaccis), my commit message is this: confirmed, timed at: "Elapsed time: 0.41989 msecs" -- original c solution will no longer run.

My old 32 bit machine died and the original (crappy) C solution now segfaults immediately, and was much slower.

Anyway, calculating and summing all the fibonacci numbers in less than half a millisecond is pretty cool.

Reply on news.ycombinator.com