6 ms·

Learning Clojure with Project Euler

38 points by grokcode 17y ago

alrex021 17y ago
wiki for Clojure solutions http://clojure-euler.wikispaces.com/ http://clojure-euler.wikispaces.com/ nice ;) Actually, on serious note, a great way to compare if your clojure code looks anything like it should.
alrex021 17y ago
>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)
zck 17y ago
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.)
- cema 17y ago
  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.
spuz 17y ago
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 :)
- grokcode 17y ago
  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.
  - spuz 17y ago
    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.
    - grokcode 17y ago
      Sure makes sense. Any idea why clojure doesn't do automatic tail call optimization, and instead depends on recur?
      - cjenkins 17y ago
        The first reply at http://groups.google.com/group/clojure/browse_thread/thread/3a2da6a71a2213be 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.
      - deleted 17y ago
        [deleted]
scrame 17y ago
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.

38 points by grokcode 17y ago

wiki for Clojure solutions http://clojure-euler.wikispaces.com/ http://clojure-euler.wikispaces.com/ nice ;) Actually, on serious note, a great way to compare if your clojure code looks anything like it should.

alrex021 17y ago

>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)

zck 17y ago

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.)

cema 17y ago
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.

spuz 17y ago

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 :)

grokcode 17y ago
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.
- spuz 17y ago
  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.
  - grokcode 17y ago
    Sure makes sense. Any idea why clojure doesn't do automatic tail call optimization, and instead depends on recur?
    - cjenkins 17y ago
      The first reply at http://groups.google.com/group/clojure/browse_thread/thread/3a2da6a71a2213be 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.
    - deleted 17y ago
      [deleted]

scrame 17y ago

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.