Blog
Project Euler in Clojure: The First 25 Problems - Problems 22-25
Problem 22Problem 22 starts with a text file and... well, I'll let you read it here. We start with two helper functions:(defn letter-value [c] (inc (- (int c) (int \A)))) (defn e22-evaluate [s] (reduce + (map letter-value s)))The first function gives the numeric value for a letter (A=1, etc.) while the second computes the string value for a name string. The solution is fairly simple: (defn euler-22 [] (let [names (read-string (str "[" (slurp "resources/p022_names.txt") "]")) snames (sort names) nvals (map e22-evaluate snames) cnt (count names) x (range 1 (inc cnt)) zip (map vector x nvals)] (reduce (fn [z [x y]] (+ z (* x y))) 0 zip)))Here, we use slurp to read the file into a string, use str to turn it into an array by bracketing it, and read the string. Next we sort the array and get the evaluation value for all of the names. Next we get a sequence corresponding to 1..(count names) and zip it with the evaluation values. Finally we use reduce to calculate the Problem's answer. Problem 23A number n is abundant if the sum of its proper divisors exceeds n. Problem 23 asks us to find the sum of all the positive integers which cannot be written as the sum of two abundant numbers. These numbers, according to the problem are all less than 28124.Our first function checks to see if a number is abundant: (defn abundant? [N] (> (reduce + (proper-divisors N)) N))Our solution starts by finding all abundant numbers less than 28124 and collecting all numbers that are sums of pairs of abundant numbers. Next we take all numbers less than 28124 and form a set from them. Finally, we remove all the numbers that were formed from sums of abundant numbers and use reduce to get the solution to the problem: (defn euler-23 [] (let [count28123 (range 1 28124) abundants (filter abundant? count28123) abundant-pairs (combo/cartesian-product abundants abundants) sums (into #{} (map (fn [[x y]] (+ x y)) abundant-pairs)) non-pairs (set/difference (into #{} count28123) sums)] (reduce + non-pairs))) Problem 24This problem asks what the 1000000'th entry is in the list of lexicographically sorted permutations of the digits from 1..9. The solution is a fairly straightforward transliteration:(defn euler-24 [] (let [s "0123456789" ps (combo/permutations s) nss (map #(apply str %) ps) snss (sort nss)] (first (drop 999999 snss))))We first form the permutations of the characters from 1-9. We then convert the permutation sequences into strings. Next we sort the strings. Finally, we get the 1000000'th element. Problem 25This problem asks for the index of the first Fibonacci number having 1000 digits:(defn euler-25 [] (loop [idx 2 a (bigint 1) b 1] ;(println cnt a b res) (if (= (count (str b)) 1000) idx (recur (inc idx) b (+ a b)))))Our solution simply loops, producing the next Fibonacci number at each iteration until the number of digits is 1000. When this happens, the index is returned. I hope you've enjoyed these solutions to the first few Project Euler problems. |
Project Euler in Clojure: The First 25 Problems - Problems 19-21
Problem 19My 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])) Problem 20In 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 21Problem 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))) |
Project Euler in Clojure: The First 25 Problems - Problems 15-18
Problem 15Problem 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 *))) Problem 16This 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. Problem 17In 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 18Problem 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)) |
Project Euler in Clojure: The First 25 Problems - Problems 10-14
Project Euler in Clojure: The First 25 Problems - Problems 5-9
Project Euler in Clojure: The First 25 Problems - Problems 2-4
Project Euler in Clojure: The First 25 Problems - Problem 1
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. The Namespace Declaration(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). Project Euler - Problem 1The 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. |
Heartbleed and code opacity
There is an old open source saying that "Many eyes make all bugs shallow". So what happened with the now infamous heartbleed bug? Supposedly, open source code is less prone to these kind of security breaches because so many eyes can look at it. In addition, open source is supposed to have better fix properties because fixes can be turned around and disseminated quickly. However, something happened with heartbleed. One issue is that most eyes are shallow, not deep. If code is opaque (as is the case for Open SSL) than it doesn't matter how many eyes are on it - bugs can be hiding in the submerged depths where only the deepest eyes are likely to stumble upon them. And it is likely that the number of deep eyes looking at the code is still as small as is usual in any other software, closed or open. The second issue is that the decentralized nature of open source movement actually harms as much as helps with dissemination. Commercial software, with its lists of registered users at least has a starting point to make issues known and patches distributed. Open source projects tend to have much more chaotic and imprecise means of the same. No one, commercial nor open source, can be sure that software will be patched - but at least commercial software has a starting point. So, what can the open source community learn from this issue? First, make sure that the code is written in the clearest possible way. Make sure that as many eyes can peer into its depths without obscuring murk. It may hurt performance, especially with ubiquitous software like Open SSL, but the alternative, as we have seen, sucks. An old wise man once said that "Premature optimization is the root of all evil." Although this is true, code that needs to be secure cannot afford any optimization - the code must be lucid enough to be easily understood and checked, lest hard-to-detect security defects sneak in. God knows you probably shouldn't be wrapping OS calls (the putative source of this defect). Second, for code as ubiquitous and as important for security as this code is, independent review by people qualified to do so is vital. Most projects have only people related to the project reviewing the code. This is probably fine for the latest Zul Zebra Zaga game, or other kind of fart app, but not so good for a piece of code upon which most of the current internet's security rests. Third, it is almost certain that the crucial parts of the Open SSL code, had it been written in a simple intelligible form would have been small enough to be formally verified. And, again, given the criticality of this code to secure operation of the internet, it should have been done. Do all of these ideas have costs? Yes. But so do bugs that have as high an impact as heartbleed appears to. We've known how to not come a cropper when the stakes are high for at least the past thirty years. The fact that these kinds of issues are still arriving (and in such crucial code) is an embarrassment to the whole industry. |
Software Engineering: 8 - Align process with your environment
You wouldn't wear a parka in July would you? If you were in Antarctica, you would, because there at that time of year, it's winter... Plus, let's be clear - it's Antarctica, and the average temperatures, even at the height of Antarctic summer, don't get above zero. Your environment matters. A lot. It matters when designing processes for your organization, as well. A good process must be aligned with four important features of your professional environment - the market into which you're selling your products, the nature of the products themselves, your organization, and the skills and abilities of the teams within it. Let's look at market influences first. If my market is consumer-oriented, dominated by social media and moving at lightning speed, I don't want to wait for a traditional process to "get it right". I'm going to be putting my best agile practices into place and releasing every two weeks. On the other hand, if I'm releasing into a more static enterprise environment, I probably don't need frequent releases (in fact, my rather conservative IT customers are probably unhappy if they have a new version of the product more than once a year). As such, a traditional process with decent change control mechanisms might bring better results with less uncertainty on which features will be delivered. It's the same with product alignment - a web-based product can have more frequent releases than one that needs to be updated on every client's system. The process for the first product should target a minimal time to release, whereas this factor is less important in the process used to develop the latter. The process for the second should take the essential difficulty of the upgrade process into account and, if possible, use this essential issue to its advantage (not that one shouldn't make the upgrade process as simple as possible in any case). If my product needs language translation, I probably (for cost reasons) don't want to have new features translated for each two-week release. I'd cut the releases to once each quarter (even if my internal releases were on a two-week cadence) and integrate a sprint/iteration/whatever to have the product translated, rechecked, and released. Similarly, organization counts. If I have a company that boxes both time and features and that doesn't keep teams stable, my process should look different from one that boxes only time and has stable teams. If my marketing department needs a half a year to plan a product launch, it doesn't matter much if my team can release on two week's notice and my process should take this into account. It's the same with the skills and abilities of the team. An inexperienced team will need a lot more design and code reviews in its definition of done than an experienced team - maybe even more QA cycles. And your process needs to take this into account. That being said, if your process isn't aligned with these four facets of your environment, it doesn't mean there's a total disaster brewing. A good team can make almost any process work (For varying values of "work". N.B.: The converse is not true - a bad team can make hash even if you have a good process in place). A poor match between environment and process usually just means that it will be more work to get the results you want (And who wants that?). The other thing to realize is that any standardized process you put into place will vary in its alignment from release-to-release, product-to-product, team-to-team, etc. Markets change; products change; teams change. As such, one must be ready to adapt one's process. And, again, failure to do so won't necessarily bring disaster, just more work. So, when putting a process into place consider carefully the four environmental attributes listed above - market, product, organization, and team. If you don't you might find yourself in a situation analogous to being at the bottom of the world in shorts, sandals, and a tee shirt. And nobody wants that. |
Getting ready to record the third This, Not This! EP
The headline says it all. The band is looking for a more organic feel with all of us recording basic tracks at the same time. We'll be recording this upstairs in my house, again, trying for a more organic feel. In all of this, I'm taking the philosophy that simpler is better and that's reflected in way I'm miking the drums. I started by using my bedroom for the drums - it's the room with the best sound in the house. It's basic sizes are not multiples giving it complex room modes and it also a gabled ceiling to add reverberant space and further reduce room modes. It also has a bed and some furniture in it for reflection and absorption. Finally, it opens into the hallway that opens onto the bottom floor, giving it a huge ambiance, if needed. We started miking by getting a pretty good sound for the drums in the overheads (a pair of matched Mike Joly modded MXL 990s). Next, a Shure Beta 52 was placed to reinforce the kick and a couple of packing blankets tossed over that to reduce bleed. Then, I added a Shure SM61 (a venerable old dynamic vocal mike with a nice high-end sizzle) to reinforce the snare. I balanced the mix and put up an Audio Technica AT3035 as a room mike and added that in for some more ambiance (since it's going to be smashed to hell when I mix, any LDC mike would work here, but the AT3035 is familiar to me). Until this setup doesn't give us what we need, this will be the default. In the past, I've used another mike on the hi-hat, but that always seemed to lead to nothing but snare bleed and heartache, so I'm not using one this time. Another omission? Individual tom mikes. In general, I find that using these only added to the ringiness of the toms (not my favorite sound) and that boosting the overheads in the mix during the fills works just as well. This simpler miking technique should also reduce (if not completely obviate) phase issues, too. So, simple, simple, simple and it sounds pretty good. The guitars will be recorded using Cascade FatHead II ribbon mikes. The engineer on our first album used them and I had good luck with them on the last album, as well. They just seem to sound good for this purpose. Gary will go in the laundry room, Phil in the guest bedroom. The bass will be DI'ed from the control room, as I can muck about with it as much as I need with my standard plugins. As for vocals, Debbie will be using an Ear Trumpet Labs Edwina in the guest bathroom. This is an LDC built by a local microphone maker named Phil Graham, optimized for live use. Intention notwithstanding, it sounded very good for Debbie's vocals on the last album and it has a certain mojo in it's look that seems to make people comfortable while recording. Pretty straightforward setup here - pop screen in front, an absorbing screen in back to try to tame some room reflections. You notice that I'm not mentioning preamps here. They say that clean is the new color. If I really need color, I'll put it in by re-amping, not preamping. I'm keeping everything clean by using solid state preamps - a combination an M-Audio Octane, a PreSonus Digimax, and three Symetrix 202s. I may break down here and use a UA 610 as a preamp for Debbie's vocals (Yes, clean is the new color, but we can go too far with everything, can't we?). I've also been taking time to set up separate headphone mixes for all involved. The four channels for Dave, Gary, Phil, and myself will go through my Furman HDS, while Debbie's channel will be a separate full mix (controlled by the recordist - i.e., me) fed into a discrete headphone amp. My upstairs looks like the cable fairy came to visit. All tidied and zip-tied around the edges of the rooms, but still a quite unique look. Have I mentioned that I have a very tolerant and loving wife? I do. So, on to recording... Of course, the main battle in recording an album like this is getting everyone together at the same time to do it, so I don't see it starting until the first week of August. The songs that we will be recording include Goodbyes, Takedown (not to be confused with Takeaway), Proof of Life, and a new one with the working title Hardhitter. In the mean time, I'll probably have Dave do some drumming for some tracks on my solo album. |