Post date: Jul 4, 2017 11:52:10 PM
My solution to Problem 19 is not elegant, but it makes up for that by being somewhat straightforward. In it, I set up counters for dates and days of the week. Starting a counter at Monday and January 1, 1900, we increment the day of week and date until we reach January 1, 1901. We then increment a counter each Monday until the date reaches Dec. 31, 2000 when we stop. The Monday counter holds the answer to the problem. The first routine increments the day of week counter (0 = Sunday, etc.):
(defn inc-dow [dow] (mod (inc dow) 7)) (defn sunday? [dow] (= dow 0))
Next we define the number of days in each month:
(def days-in-month-non-leap [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31])
One issue with the problem is that it doesn't mention that years ending in 000 are leap years, something that our leap year function takes into account (and which is necessary to solve the problem correctly):
(defn leap-year? [y] (or (= 0 (mod y 1000)) (and (= 0 (mod y 4)) (not (= 0 (mod y 100))))))
We zero-index our days of the month and months:
(defn first-of-month? [[y m d]] (= d 0)) (defn inc-cal [[y m d]] (let [d' (mod (inc d) (days-in-month y m)) m' (mod (inc m) 12) y' (inc y)] [(if (and (= 0 d') (= 0 m')) y' y) (if (= 0 d') m' m) d']))
After we define the function that increments the calendar date, we define a date comparison function:
(defn dt-cmp [[y1 m1 d1] [y2 m2 d2]] (let [ydiff (- y2 y1) mdiff (- m2 m1) ddiff (- d2 d1)] (if (= 0 ydiff) (if (= 0 mdiff) ddiff mdiff) ydiff)))
Finally, we have enough functions to easily write our solution (remember that the dates are all zero-indexed by their month and day). The first loop counts from January 1, 1900 to January 1, 1901 while the second loop then counts to December 31, 2000, incrementing the answer counter when Sunday falls on the first day of a month:
(defn euler-19 [] (loop [e19cnt 0 dt [1900 0 0] dow 1 dt-cmp-start (dt-cmp dt [1901 0 0]) dt-cmp-end (dt-cmp dt [2000 11 10])] ;(println dt) (cond (< 0 dt-cmp-start) (recur 0 (inc-cal dt) (inc-dow dow) (dt-cmp (inc-cal dt) [1901 0 0]) (dt-cmp (inc-cal dt) [2000 11 10])) (and (>= 0 dt-cmp-start) (< 0 dt-cmp-end)) (recur (if (and (first-of-month? dt) (sunday? dow)) (inc e19cnt) e19cnt) (inc-cal dt) (inc-dow dow) (dt-cmp (inc-cal dt) [1901 0 0]) (dt-cmp (inc-cal dt) [2000 11 10]))
In this problem we are asked to sum the digits in 100! where ! denotes the factorial function. We first define our factorial function:
(defn fact' [n acc] (if (< n 2) acc (recur (dec n) (* n acc)))) (defn fact [n] (fact' n (bigint 1)))
After this is defined, we can transcribe the solution - calculate 100!, turn it into a string, map the string's characters to numbers, and use reduce to sum the digits:
(defn euler-20 [] (reduce + (map char->int (str (fact 100)))))
Problem 21 asks for the sum of all amicable numbers < 10000. We start by defining a function that returns all proper divisors of N which loops through numbers < N/2 checking to see if they divide N evenly:
(defn proper-divisors [N] ;(println "D" N) (loop [tst 1 divisors []] (cond (> tst (/ N 2)) divisors (factor? tst N) (recur (inc tst) (conj divisors tst)) :else (recur (inc tst) divisors)))) (def proper-divisors (memoize proper-divisors))
Next comes our amicability check:
(defn amicable? [[x y]] (and (= y (reduce + (proper-divisors x))) (= x (reduce + (proper-divisors y)))))
We'll need to generate pairs of numbers (i, j) to test for amicability - we make sure to only use pairs with i < j to ensure that we don't count pairs twice:
(defn triangular-indices [N] (filter (fn [[i j]] (< i j)) (combo/cartesian-product (range 1 (inc N)) (range 1 (inc N)))))
Finally, we can write our solution:
(defn euler-21 [] (let [pairs (triangular-indices 10000) amicable-pairs (filter amicable? pairs)] (reduce (fn [z [x y]] (+ x y z)) 0 amicable-pairs)))