Here is my solution to Problem 15 of Project Euler. As always, my progress you can tracked on GitHub at https://github.com/stevenproctor/project-euler-clojure.
Problem 15 of Project Euler is to find the starting number with the longest Collatz sequence, summarized from the problem page as:
Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner. How many routes are there through a 2020 grid?
I started this problem, by trying to tracing and counting the routes through grids of 2×2, 3×3, and 4×4, and even setled in and did a 5×5 square. Having these numbers, and knowing I had two choices for ever position I was in, except for when the path got to the far edge and bottom, I had a hint at the growth rate of the problem. I tried some powers of 2 with the relationship of the numbers, and some factorials with the numbers. After seeing some possible relationships with the factorials that might be leading me in the right direction, I tried a number of permutation calculations, and the combination calculations. Having seen the numbers show up in different combination results, I then spent time back-calculating from those numbers into my
ns, and found that the pattern seemed to match 2n Choose n.
The source code to this was the
(defn factorial [n] (multiply (range 1M (inc (bigdec n)))))
And, I could have done it recursively, but I figured I would just operate against the sequence of numbers, especially now that the reducers are available in the Clojure 1.5-Alpha 3 release (at the time of this writing) of Clojure. After I get through a few more problems (of which I am working ahead of these posts), I am thinking it would be interesting to run the same Project Euler Problems against 1.4 and 1.5 using the reducers library, just substituting map/reduce for the reduce/combine functionality, and seeing how much effort it takes to move them over, as well as the differences in the timings of the different problems.
The other base function I needed was a
(defn combination [n k] (cond (zero? n) 0 (zero? k) 1 :else (/ (factorial n) (* (factorial (- n k)) (factorial k)))))
This function just does the basic calculation for combinations, from the formula:
With that, and my stumbling upon the matching of the fact that is the solution to the number of paths through the square the function
problem15 is defined as:
(defn problem15 ( (problem15 20)) ([n] (combination (+ n n) n)))
As always, any feedback you have for me is greatly appreciated.
Pingback: LaTeX in WordPress « Proctor It