Post date: Jul 4, 2017 12:13:56 AM
Problem 15 in the Project Euler compendium asks for the number of paths through a 20x20 square lattice starting from (0,0) and ending at (20, 20), using steps of (0,1) and (1, 0). We started by searching for a closed formula for this in the Online Encyclopedia of Integer Sequences. Searching for "paths 2-dimensional square lattice" soon brings us to sequence A000984, which has as one of its comments "The number of lattice paths from (0,0) to (n,n) using steps (1,0) and (0,1)," which fits the problem description perfectly. Although this sequence entry would allow us to simply look the answer up immediately, we will implement the formula which is (2n, n) where (n, k) denotes the binomial coefficient. Thus the solution is given as:
(defn euler-15 [] (binomial-coefficient (* 2 20) 20))
To avoid potential issues with stack overflow that might result from using recursive definitions of our algorithm, we use an iterative solution to compute the binomial coefficient: (n, k) = Product[i=1..k](n+1-i)/i. We essentially transliterate the program from the definition - take the integers from 1 to k, map them to their terms in the product, and use reduce to compute the product:
(defn binomial-coefficient "Calculate the binomial coefficient." [n k] (->> (range 1 (inc k)) (map #(/ (inc (- n %)) %)) (reduce *)))
This problem asks for the sum of the digits in the number 2^1000. In our solution, the main dilemmas are whether or not to use a threading macro to express this otherwise one-liner and what to alias the numeric-tower package which must be referenced to compute the exponential:
(defn euler-16 [] (reduce + (map char->int (str (nt/expt 2 1000)))))
Here (reading inside out) we compute 2^1000, convert it to a string, map the characters in the string to their integer equivalent, and sum them using reduce. Easy peasy.
In this problem, we're asked to find the count of all characters in the words for the first 1000 integers, omitting spaces and punctuation. The first task in counting these is to define the words we'll be using to write out the numbers:
(def units-words ["zero" "one" "two" "three" "four" "five" "six" "seven" "eight" "nine"]) (def teens-words ["ten" "eleven" "twelve" "thirteen" "fourteen" "fifteen" "sixteen" "seventeen" "eighteen" "nineteen"]) (def tens-words ["zero" "ten" "twenty" "thirty" "forty" "fifty" "sixty" "seventy" "eighty" "ninety"])
Next we define the function that returns the string for numbers less than 100:
(defn sub-hundred-words [N] (cond (< N 10) (get units-words N) (< N 20) (get teens-words (- N 10)) (factor? 10 N) (get tens-words (int (/ N 10))) :else (let [tw (get tens-words (int (/ N 10))) uw (get units-words (mod N 10))] (str tw uw))))
Here, we dispatch on the number's linguistic type and take the appropriate words from our word lists. We call this function within the function that computes the string for numbers under 1000:
(defn sub-thousand-words [N] (cond (< N 100) (sub-hundred-words N) (factor? 100 N) (str (get units-words (int (/ N 100))) "hundred") :else (str (get units-words (int (/ N 100))) "hundredand" (sub-hundred-words (mod N 100)))))
Again, we use the strategy of dispatching on linguistic type.
In our solution to this problem, we map all the numbers from 1 to 999 to their strings, concatenate them, and count the characters in the large resulting string. We then add on the number of characters from the string "onethousand" giving us the answer:
(defn euler-17 [] (let [addon (count "onethousand") bigstr (apply str (map sub-thousand-words (range 1 1000))) bigstrcnt (count bigstr)] ;(println bigstr) (+ addon bigstrcnt)))
Problem 18 gives us a triangular array of numbers and asks us to find the maximal sum of all paths from the top to the bottom. Here is the array and its access function:
(def e18triangle [ [75] [95 64] [17 47 82] [18 35 87 10] [20 04 82 47 65] [19 01 23 75 03 34] [88 02 77 73 07 63 67] [99 65 04 28 06 16 70 92] [41 41 26 56 83 40 80 70 33] [41 48 72 33 47 32 37 16 94 29] [53 71 44 65 25 43 91 52 97 51 14] [70 11 33 28 77 73 17 78 39 68 17 57] [91 71 52 38 17 14 91 43 58 50 27 29 48] [63 66 04 68 89 53 67 30 73 16 69 87 40 31] [04 62 98 27 23 9 70 98 73 93 38 53 60 04 23]]) (defn tri-at [i j] (get (get e18triangle i 0) j 0))
The function that finds the maximal path is a simple recursive function:
(defn max-path "Find the maximal sum of a length n path through the triangle starting at i j." [i j n] (cond (= n 1) (tri-at i j) (> i (count e18triangle)) 0 :else (let [here (tri-at i j) l (max-path (inc i) j (dec n)) r (max-path (inc i) (inc j) (dec n))] (+ here (if (> l r) l r))))) (def max-path (memoize max-path))
We compute the maximal sum recursively by checking whether the left or right branch's maximal sum is greater and adding that to the number at the starting point. Our recursion terminates for a path of length 1 which returns the value from the starting point.
Finally, our solution calls max-path to compute the maximal sum path:
(defn euler-18 [] (max-path 0 0 15))