Post date: Mar 16, 2017 4:50:58 PM
I enjoy programming. In addition to being my livelihood, it serves as one of my hobbies. I enjoy code kata and am always searching for new exercises. I had heard of Project Euler, but had not participated yet, and decided that this would be my next challenge. I found a site in github purporting to be Clojure solutions of these problems, but they were neither particularly complete nor well-documented. I thought I could do better, learn more Clojure, and refresh my knowledge of number theory along the way. In addition, the solutions are an interesting way to exercise a language.
I expect that these blog posts will be most useful to beginning to intermediate Clojure programmers. I've searched for the most straightforward solutions I could find for these problems and most of them have relatively simple solutions. Note that these solutions are spoilers for the problems. If you want the maximum benefits from these problems, you might want to solve them first yourself. My code has been checked for correctness, but you might find better solutions! Please share in the comments section any solutions you think are better, why, etc.
(ns euler.core (:require [clojure.math.combinatorics :as combo]) (:require [clojure.math.numeric-tower :as nt]) (:require [clojure.set :as set]))
We require three Clojure libraries, which are used for a few minor bits of code in the problems - from combo we get combo/cartesian-product, from nt we obtain nt/expt, and from set we use set/difference. These are useful libraries for anyone doing numeric and/or combinatorial problems (which many programming problems ultimately come down to).
The first PE problem wants the sum of all numbers not divisible by three or five less than 1000. The solution would seem to be so simple that it writes itself:
(defn euler-1a [] (reduce + (filter #(or (zero? (mod % 3)) (zero? (mod % 5))) (range 1 1000))))
This is a perfectly fine solution (and gets the correct answer) - we take a collection of numbers from 1 to 999 (the range function), filter the ones divisible by 3 or 5, and sum the remainder using reduce. However, the filter function is a bit opaque; its meaning somewhat obscure. The repetition in the test function is a code smell, as well. We can refactor this code a bit to obtain an easier to understand version:
(defn factor? [n k] "Is n a factor of k?" (zero? (mod k n))) (defn euler-1b [] (reduce + (filter #(or (factor? 3 %) (factor? 5 %)) (range 1 1000))))
This version is not only clearer, but provides the function factor? which will be useful in upcoming problems. But can we do a bit better? The problem description talks about ignoring numbers divisible by 3 or 5. Is there a clearer way to capture that? One solution can be obtained by defining a new function divisible-by?. This function, when passed an integer, returns a function to determine if another number is divisible by that integer:
(defn divisible-by? "Return a function that tests if a number is divisible by the argument." [n] (partial factor? n)) (defn euler-1c [] (reduce + (filter #(or ((divisible-by? 3) %) ((divisible-by? 5) %)) (range 1 1000))))
This solution is a bit clearer, using the same terminology as the original Project Euler problem. The trade off is that a function call in the function position of a form is a bit unusual. The good news is that this unusual usage calls out the special nature of divisible-by? function which, with any luck, will be examined by anyone looking at the code. This function will also be useful in future problems.
The final version of the code uses the threading macro ->>:
(defn factor? [n k] "Is n a factor of k?" (zero? (mod k n))) (defn divisible-by? "Return a function that tests if a number is divisible by the argument." [n] (partial factor? n)) (defn euler-1 [] (->> (range 1 1000) (filter #(or ((divisible-by? 3) %) ((divisible-by? 5) %))) (reduce +)))
This version looks a bit more Clojure-ish, even though to a classic Lisper, like me, the string of forms still looks a bit too prog-ish for comfort. In general, the longer the set of nested calls, the clearer the threaded solution becomes. Another choice would be to use an internal let to call out intermediate results like this:
(defn euler-1d [] (let [count999 (range 1 1000) nums-to-add (filter #(or ((divisible-by? 3) %) ((divisible-by? 5) %)) count999)] (reduce + nums-to-add)))
This form is useful when the intermediate results have some significance (not like in this problem) and naming them makes the algorithm easier to understand (also not like this problem). Generally speaking, a competent Clojure programmer should understand the usage of all of these forms of sequencing calls, be able to convert from one form to another, and select the one that is clearest for use. In the next post, we'll cover problems two through four, touching on lazy-seq, prime generation, and factorization.