Blog

Project Euler in Clojure: The First 25 Problems - Problems 22-25

posted Jul 5, 2017, 8:06 AM by Frank Adrian [ updated Jul 20, 2018, 3:36 PM ]

Problem 22

Problem 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 23

A 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 24

This 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 25

This 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

posted Jul 4, 2017, 4:52 PM by Frank Adrian [ updated Jul 20, 2018, 3:27 PM ]

Problem 19

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]))

Problem 20

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

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)))

Project Euler in Clojure: The First 25 Problems - Problems 15-18

posted Jul 3, 2017, 5:13 PM by Frank Adrian [ updated Jul 20, 2018, 3:28 PM ]

Problem 15

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 *)))

Problem 16

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.

Problem 17

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

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))

Project Euler in Clojure: The First 25 Problems - Problems 10-14

posted Apr 13, 2017, 10:46 PM by Frank Adrian [ updated Jul 20, 2018, 3:28 PM ]

Problem 10

This problem asks for the sum of the prime numbers less than 2000000. A simple transliteration of the problem using take-while and reduce does the trick, yielding the solution:

(defn euler-10 []
  (->> (gen-primes)
       (take-while #(< % 2000000))
       (reduce +)))

Problem 11

This problem starts by defining a 20x20 numeric grid:

(def e11grid [[ 8 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91  8]
              [49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00]
              [81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65]
              [52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91]
              [22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80]
              [24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50]
              [32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70]
              [67 26 20 68 02 62 12 20 95 63 94 39 63  8 40 91 66 49 94 21]
              [24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72]
              [21 36 23  9 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95]
              [78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14  9 53 56 92]
              [16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57]
              [86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58]
              [19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40]
              [04 52  8 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66]
              [88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69]
              [04 42 16 73 38 25 39 11 24 94 72 18  8 46 29 32 40 62 76 36]
              [20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16]
              [20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54]
              [01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48]])

Here, we've defined a corresponding matrix using an array of Clojure arrays as our data structure. The problem asks for the maximum of all products of four contiguous linear elements, oriented up-down, left-right, and diagonally, over the entire matrix. Let us suppose we are sitting at an interior point [i, j]. We can imagine four four-element rays emanating from where we stand, one heading to our east, one to our south, one to the southeast, and one to the southwest. Now map these four rays across the entire surface of the matrix, it's clear that, ignoring edge effects, we have covered all linear quadruples in the array. If we map all of these quadruples to their products and take the maximum, we have the answer to out problem. And this is essentially how we will solve our problem. To start, we need to deal with points of our rays that lie outside the bounds of the matrix. If we assume that any element outside the array bounds is zero, then rays that lie outside our matrix will have a corresponding product of zero, and will not interfere with the maximum we want to take. As such, we write a helper function that returns the element at matrix index [i, j] and zero for any coordinate outside the array bounds:

(defn grid-at [[i j]]
  (cond (or (< i 0) (< j 0) (> i 19) (> j 19)) 0
        :else (get (get e11grid i) j)))

Next we define offsets from an origin defining our four rays:

(def quad-deltas [[[0 0] [1 1] [2 2] [3 3]]         ;diagonal right
                  [[0 0] [1 0] [2 0] [3 0]]         ;left-to-right
                  [[0 0] [0 1] [0 2] [0 3]]         ;up-down
                  [[0 0] [-1 1] [-2 2] [-3 3]]])    ;diagonal left

We now define a helper function quad-products-at:

(defn quad-products-at [[i j]]
  (->> quad-deltas
      (map #(map (fn [[x y]] [(+ i x) (+ j y)]) %))
      (map #(->> %
                 (map grid-at)
                 (reduce *)))))

This function takes the four offset rays and uses the first map function to add them to each of the rays to give the four sets of four squares emanating from [i, j]. The second map maps the squares to their values using grid-at function and then produces their product via reduction. This produces four numbers for each square - the products along each of the four rays. To obtain the final answer to the problem, we map this function across each square of the matrix, obtaining the four products for each square, use concat to get the entire list of numbers, and use max to find the maximum:

(defn euler-11 []
  (->> (combo/cartesian-product (range 20) (range 20))
       (map quad-products-at)
       (apply concat)
       (apply max)))

Problem 12

The twelveth Project Euler problems wants the first triangular number with more than 500 factors. Remember that the n'th triangular number is given by T_n= n(n+1)/2. We define the function triangle:

(defn triangle [N]
  (/ (* N (inc N)) 2))

The function prime-factors uses the previously-defined function smallest-prime-factor to peel away factors of N, leaving it's factorization:

(defn prime-factors [N]
  (let [p (smallest-prime-factor N)]
    (if (= p N) [N] (conj (prime-factors (/ N p)) p))))

The function factorization uses the frequencies function to put the factorization of N into a standard form - a factor map where the keys are the prime factors of the number and the value associated with the key is the multiplicity of that prime in N:

(defn factorization [N]
  (frequencies (prime-factors N)))

factor-count uses the factorization to compute the number of factors of N:

(defn factor-count [N]
  (reduce * (map (fn [[k v]] (inc v)) (factorization N))))

Combining these functions gives the solution to this problem:

(defn euler-12 []
  (->> (range 2 1000000)
       (map triangle)
       (drop-while #(< (factor-count %) 500))
       (first)))

Problem 13

Problem 13 gives us a series of very large numbers and asks for us to return the integer produced by taking the first 10 digits of the sum of this series:

(def e13numbers [37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538
74324986199524741059474233309513058123726617309629
91942213363574161572522430563301811072406154908250
23067588207539346171171980310421047513778063246676
89261670696623633820136378418383684178734361726757
28112879812849979408065481931592621691275889832738
44274228917432520321923589422876796487670272189318
47451445736001306439091167216856844588711603153276
70386486105843025439939619828917593665686757934951
62176457141856560629502157223196586755079324193331
64906352462741904929101432445813822663347944758178
92575867718337217661963751590579239728245598838407
58203565325359399008402633568948830189458628227828
80181199384826282014278194139940567587151170094390
35398664372827112653829987240784473053190104293586
86515506006295864861532075273371959191420517255829
71693888707715466499115593487603532921714970056938
54370070576826684624621495650076471787294438377604
53282654108756828443191190634694037855217779295145
36123272525000296071075082563815656710885258350721
45876576172410976447339110607218265236877223636045
17423706905851860660448207621209813287860733969412
81142660418086830619328460811191061556940512689692
51934325451728388641918047049293215058642563049483
62467221648435076201727918039944693004732956340691
15732444386908125794514089057706229429197107928209
55037687525678773091862540744969844508330393682126
18336384825330154686196124348767681297534375946515
80386287592878490201521685554828717201219257766954
78182833757993103614740356856449095527097864797581
16726320100436897842553539920931837441497806860984
48403098129077791799088218795327364475675590848030
87086987551392711854517078544161852424320693150332
59959406895756536782107074926966537676326235447210
69793950679652694742597709739166693763042633987085
41052684708299085211399427365734116182760315001271
65378607361501080857009149939512557028198746004375
35829035317434717326932123578154982629742552737307
94953759765105305946966067683156574377167401875275
88902802571733229619176668713819931811048770190271
25267680276078003013678680992525463401061632866526
36270218540497705585629946580636237993140746255962
24074486908231174977792365466257246923322810917141
91430288197103288597806669760892938638285025333403
34413065578016127815921815005561868836468420090470
23053081172816430487623791969842487255036638784583
11487696932154902810424020138335124462181441773470
63783299490636259666498587618221225225512486764533
67720186971698544312419572409913959008952310058822
95548255300263520781532296796249481641953868218774
76085327132285723110424803456124867697064507995236
37774242535411291684276865538926205024910326572967
23701913275725675285653248258265463092207058596522
29798860272258331913126375147341994889534765745501
18495701454879288984856827726077713721403798879715
38298203783031473527721580348144513491373226651381
34829543829199918180278916522431027392251122869539
40957953066405232632538044100059654939159879593635
29746152185502371307642255121183693803580388584903
41698116222072977186158236678424689157993532961922
62467957194401269043877107275048102390895523597457
23189706772547915061505504953922979530901129967519
86188088225875314529584099251203829009407770775672
11306739708304724483816533873502340845647058077308
82959174767140363198008187129011875491310547126581
97623331044818386269515456334926366572897563400500
42846280183517070527831839425882145521227251250327
55121603546981200581762165212827652751691296897789
32238195734329339946437501907836945765883352399886
75506164965184775180738168837861091527357929701337
62177842752192623401942399639168044983993173312731
32924185707147349566916674687634660915035914677504
99518671430235219628894890102423325116913619626622
73267460800591547471830798392868535206946944540724
76841822524674417161514036427982273348055556214818
97142617910342598647204516893989422179826088076852
87783646182799346313767754307809363333018982642090
10848802521674670883215120185883543223812876952786
71329612474782464538636993009049310363619763878039
62184073572399794223406235393808339651327408011116
66627891981488087797941876876144230030984490851411
60661826293682836764744779239180335110989069790714
85786944089552990653640447425576083659976645795096
66024396409905389607120198219976047599490197230297
64913982680032973156037120041377903785566085089252
16730939319872750275468906903707539413042652315011
94809377245048795150954100921645863754710598436791
78639167021187492431995700641917969777599028300699
15368713711936614952811305876380278410754449733078
40789923115535562561142322423255033685442488917353
44889911501440648020369068063960672322193204149535
41503128880339536053299340368006977710650566631954
81234880673210146739058568557934581403627822703280
82616570773948327592232845941706525094512325230608
22918802058777319719839450180888072429661980811197
77158542502016545090413245809786882778948721859617
72107838435069186155435662884062257473692284509516
20849603980134001723930671666823555245252804609722
53503534226472524250874054075591789781264330331690])

The solution is transliterated from the problem description:

(defn euler-13 []
  (let [s (reduce + e13numbers)]
    (read-string (apply str (take 10 (str s))))))

Problem 14

The Collatz sequence for a number N is defined by the process N -> N/2 (if N even) and N -> 3N+1 (if N odd). The Collatz Conjecture states that for any positive integer, the Collatz sequence eventually reaches 1. The conjecture is still unproven. The problem asks for the number less than 1000 with the longest Collatz sequence.

We start with a function for calculating a Collatz step:

(defn collatz [N]
  (if (even? N) (/ N 2) (inc (* 3 N))))

The next function returns a lazy Collatz sequence for the given number:

(defn collatz-seq [N]
  (if (= N 1) [1] (conj (lazy-seq (collatz-seq (collatz N))) N)))

The following code solves the problem:

(defn euler-14 []
  (->> (range 1 1000000)
       (map (fn [x] [x (count (collatz-seq x))]))
       (reduce (fn [[i cc :as a] [i2 cc2 :as b]] (if (> cc cc2) a b)))
       (first)))

Here, the range is passed to a map which returns the pair of the number and the length of it's Collatz sequence. The reduction selects the pair with the longest sequence, and the final call strips the number out of the pair.

Project Euler in Clojure: The First 25 Problems - Problems 5-9

posted Mar 23, 2017, 9:37 AM by Frank Adrian [ updated Jul 20, 2018, 3:29 PM ]

Problems five through nine all have relatively simple solutions in Clojure. My apologies for those wanting more length.

Problem 5

Problem 5 asks for the smallest number cleanly divisible by all numbers 1 through 20. To meet the cleanly divisible criteria, our number must include all of the prime factors of the numbers from 1 through 20. To be the smallest, it must be the product of the minimum number of prime factors that meets the previous criterion.

We'll start by looking through the numbers one-by-one. Our number must be divisible by 2 and then 3. So the number must be divisible by 2*3. The next divisor, 4=2², meaning that to keep the number minimal, we need have only another single factor of 2 in the number or that the number must be divisible by 2*3*2. Five is a new prime divisor and so the number must be divisible by 2*3*2*5. Continuing in this manner, we can see that divisibility by 6 can be satisfied by the existing factors of 2 and 3, seven can be added to the list, and 8 can be accounted for by adding another factor of 2 to the product, meaning that the number must be divisible by 2*3*2*5*7*2. Nine brings in the second factor of 3 and continuing writing factors in this manner up to 20 (whose divisibility is already accounted for by 2 factors of 2 and one of 5 at that point) leaves us with a number that must be divisible by 2*3*2*5*7*2*3*11*13*2*17*19, which having all the factors of numbers less than or equal to 20 is the solution to the problem.

Using Clojure as a desk calculator gives us the answer:

(defn euler-5 "Expand numbers by prime factors and read off non-dupe factors."
  []
  (* 2 3 2 5 7 2 3 11 13 2 17 19))

Problem 6

This problem is another simple calculation problem - find the difference between the square of the sum of the numbers from 1 to 100 and the sum of the squares of these same numbers. Using reduce to calculate the sums leads to another fairly self-explanatory function:

(defn euler-6 []
  (let [to100 (range 1 101)]
    (- (* (reduce + to100) (reduce + to100)) (reduce + (map #(* % %) to100)))))

Problem 7

What is the 10001'st prime number? To determine this, we use a helper function, nth-prime:

(defn nth-prime [n]
  (nth (gen-primes) (dec n)))

Note the (dec n) - Clojure's counting is zero-based, the problem counts from 1. This allows us to write our solution for Problem 7:

(defn euler-7 []
  (nth-prime 10001))

Problem 8

Problem 8 gives us a very big number and asks us for the largest product of thirteen consecutive digits in this number. If we can find all thirteen-character substrings of this number, then we need only map a function over this collection that finds the product of the digits and then take the maximum of these mapped products. Lets start by finding the thirteen-character substrings. This is easily accomplished using Clojure's partition function:

(def ce8 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450)

(defn get-partitions [] (partition 13 1 (str ce8)))

This function returns a lazy sequence of lazy sequences of characters:

((\7 \3 \1 \6 \7 \1 \7 \6 \5 \3 \1 \3 \3) (\3 \1 \6 \7 \1 \7 \6 \5 \3 \1 \3 \3 \0) (\1 \6 \7 \1 \7 \6 \5 \3 \1 \3 \3 \0 \6) ...)

Each sub-sequence contains the thirteen characters of the substring it corresponds to. To convert these to their products, we must convert the character sequences to integer sequences and multiply. To do the first, we construct an auxiliary function char->int:

(defn char->int [c] (- (int c) (int \0)))

Once this function is available, we can solve the problem as follows:

(defn euler-8 []
  (->> (get-partitions)
       (map #(apply * (map char->int %)))
       (apply max)))

In this solution, we take the partitions, use the map function to get the products, and take the max. The internal function in the map form takes the sequence, converts its characters to integers, and multiplies them together.

Problem 9

There is a single Pythagorean triple (i.e., [a, b, c] such that a²+b²=c²) where a+b+c=1000. Our problem asks for a*b*c for this number. Assuming we can find all triples summing to 1000 and have a function that tests whether or not a triple is Pythagorean, we can write our solution as:

(defn euler-9 []
  (->> (triples-summing 1000)
       (filter pythagorean-triple?)
       (map #(apply * %))
       (first)))

The test for being a Pythagorean triple is simple:

(defn pythagorean-triple? [[a b c]]
  (= (* c c) (+ (* a a) (* b b))))

The code for producing a set of all positive integer pairs summing to N is:

(defn doubles-summing [N]
  (let [rangeN (range 1 (inc N))]
    (take (dec N) (map (fn [x] [x (- N x)]) rangeN))))

Here, we take the numbers i from 1 to N, and use the map function to pair them with N-i. We only use the first N-1 of these because we do not want to consider the number pair [N, 0]. We will use these doubles to find triples summing to N:

(defn triples-summing [N]
  (apply concat
         (let [rangeN (range 1 (inc N))]
           (map (fn [k] 
                  (let [doubles (doubles-summing (- N k))]
                    (map (fn [[a b]] [a b k]) doubles)))
                (take (dec N) rangeN)))))

In this function, the first map is applied to the numbers k from 1 to N, where for each it maps the doubles [a, b] summing to N-k and packages them into a triple [a, b, k] summing to N. The sequences of triples produced by this map are then concatenated to form the final list of all triples. Again, note the (take (dec N) ...) clause. This is again because we do not want to consider solutions of the form [a, b, 0], where a+b = N.

Project Euler in Clojure: The First 25 Problems - Problems 2-4

posted Mar 17, 2017, 12:17 PM by Frank Adrian [ updated Jul 20, 2018, 3:30 PM ]

Problem 2

The second Project Euler problem asks us to find the sum of the even Fibonacci numbers less than 4000000. As such, the simple generate, filter, and sum solution will look like that of Problem 1, but with a couple twists:

(defn euler-2 []
   (->> (fib-seq)
        (take-while #(< % 4000000))
        (filter even?)
        (reduce +)))

Here, we take from the sequence of Fibonacci numbers in order until the next Fibonacci number is greater than or equal to 4000000, filter the resulting collection to get the even elements, and sum them by reducing - a straightforward translation of the problem. The main trick would seem to be writing the function fib-seq. Our first attempt is as follows:

(defn fib-seq-bad
  "Returns a sequence of Fibonacci numbers."
  ([]
     (fib-seq 0N 1N))
  ([a b]
     (cons b (fib-seq-bad b (+ a b)))))

In this code, a represents the previous Fibonacci number and b represents the current Fibonacci number in the sequence. Assume we're at F_k in the sequence. The next time we call fib-seq-bad, F_k, the current value, will be the next previous value, and F_k+1=F_k+F_k-1(the current previous value)=a+b will be the next value. This gives us the recursion relation shown in the function. The zero arity function seeds the 2 arity function with initial values of 0 and 1 (previous and current values for the first time the function is called). The list is built by consing each current value to the list generated by the next values. The only problem comes when we actually try to run the function - it fails with a stack overflow error. The reason why is inherent in the solution - in order to cons the current Fibonacci number onto the tail of the sequence, you first need to build that sequence. And to build this infinite sequence, you must recurse infinitely. The good news about Clojure is that instead of forming this infinite list, we can instead use lazy-seq to form a lazy sequence.

So what is lazy-seq?

According to its Clojure documentation, lazy-seq:

Takes a body of expressions that returns an ISeq or nil, and yields a Seqable object that will invoke the body only the first time seq is called, and will cache the result and return it on all subsequent seq calls.

In our case, we'd use it like this:

(defn fib-seq
  "Returns a lazy sequence of Fibonacci numbers"
  ([]
     (fib-seq 0N 1N))
  ([a b]
     (lazy-seq
      (cons b (fib-seq b (+ a b))))))

In this code, the first time seq is called to get the contents of the list, the body is evaluated, leading to a list holding the current Fibonacci number, followed by the rest of the list. But when we attempt to build the rest of the list, our call to fib-seq immediately hits a lazy-seq call, which does not get invoked until the next seq is called. Each time this happens, another item is consed onto the end of the list, allowing us to realize the list in order and only as needed. As such, we've created a lazy sequence of Fibonacci numbers which can be processed by our solution. This is not the only lazy sequence we shall be building. Problem 3 also utilizes lazy-seq to generate a sequence of prime numbers.

Problem 3

In this problem, a key piece is generating a lazy sequence of primes. To do this, we use a sieve - in a map we hold associations between the next number that is going to be sieved out by the current set of primes and the primes that number will be sieved out by. To find the next prime, we look in the table at the next number, d. If we find d in the table, we know it is not prime and that the next number(s) sieved by the algorithm will be the sum of that number and the prime(s) that sieves the number. If d's not in the table, then it's prime. We'll step through the algorithm to demonstrate.

Start with an empty map and initial number d=2. Since 2 is not a key in the map, 2 must not be sieved yet and is thus a prime - add it to the list of primes and add to the map [d², (d)]. The map now holds {4 (2)}. The next number is 3. We check and it is not in the map - again this number is prime so add it to the list of primes. Add [9 (3)] to the map, giving a map of {4 (2), 9 (3)}. The next number is 4. It is in the map so it is not prime. For each of the sieve factors of d, add the sieve factor for the number and update the map. This gives us a map of {6 (2), 9 (3)}. The next number, 5, is not in the map and prime, leading to the resulting map {6 (2), 9 (3), 25 (5)}. Six is in the map and is not prime. We increment it in the sieve, resulting in the map {8 (2), 9 (3), 25 (5)}. We continue this way until we come to the number 10, when our map contains {10 (2), 12 (3), 25 (5), 49 (7) }. Ten is not prime, but when we add it's sieving factor to it, we find that the number 12 is already in the map. To fix this, we add both sieve factors under 12, giving the map {12 (2 3), 25 (5), 49 (7)}. Eleven is prime so we augment the map again giving {12 (2 3), 25 (5), 49 (7), 121 (11)}. Twelve, the next number, is not prime and we increment the number by both factors in the sieve, re-splitting the factors giving: {14 (2), 15 (3), 25 (5), 49 (7), 121 (11)}. We continue, adding primes to our list and updating the sieve properly depending on whether the currently examined number is prime or not.. The algorithm is shown here:

(defn gen-primes "Generates an infinite, lazy sequence of prime numbers"
  []
  (let [reinsert (fn [table x prime]
                   (update-in table [(+ prime x)] conj prime))]
    (defn primes-step [table d]
                 (if-let [factors (get table d)]
                   (recur (reduce #(reinsert %1 d %2) (dissoc table d) factors)
                                 (inc d))
                   (lazy-seq (cons d (primes-step (assoc table (* d d) (list d))
                                                 (inc d))))))
    (primes-step {} 2)))

In this code, reinsert does the job of updating the table with the sieved numbers and their sieving primes. The call to recur (when the number is in the table) handles the case where the number is not prime using reinsert to update the table (repeatedly for each prime sieving factor, using reduce), while the cons branch of the code handles the case when the current number is prime, adding of the current number being checked to the list of primes and updating the sieve with the square of the prime. The lazy-seq call in the cons branch ensures that the list will be delivered lazily. And, of course, we start at 2 with an empty map.

Why is the first sievable number for a given prime initialized to that prime's square? One can see that earlier multiples of this prime will be caught by composites and primes less than this number. So 2*5 will be caught by 2's sieve, 3*5 by 3's etc. The first number not caught by a number's sieve is that number squared (and after that, its increments take care of the sieving).

So what does the problem ultimately ask? It wants the maximal prime factor of 600851475143. How do we find the maximal factor? Assume a number N can be written as a product of prime numbers p₀ⁱp₁^j...p_n^k, with factors ordered from low to high. By dividing by p₀, we obtain a smaller number. Continuing removing smallest factors in this manner, we are eventually left with N=p_k, the maximal prime factor. To find the smallest prime factor of the number at any iteration, test against the sequence of primes until the first one is found that divides N. This will be the smallest prime factor.

The code to accomplish all this is:

(defn smallest-prime-factor "Iterate through the sequence of primes until you find a divisor."
  [N]
  (first (drop-while #(not (factor? % N)) (gen-primes))))

(defn max-prime-factor "Divide by smaller factors until you're left with the largest."
  [N]
  (let [p (smallest-prime-factor N)]
    (if (= N p) p (recur (/ N p)))))

This allows the solution to Problem 3 to be written simply as:

(defn euler-3 []
  (max-prime-factor 600851475143))

Problem 4

This problem (like several from the Project Euler corpus) deals with palindromic numbers (numbers whose digits read the same backward and forward). A prime requirement is to test whether a given number is a palindrome. For this, we check if the reverse of the number's string equals the number's string:

(defn palindrome? [N]
  (= (str N) (apply str (reverse (str N)))))

The problem asks for the maximal palindromic number formed from the product of two three digit numbers. The set of three digit numbers can be generated by:

(def three-digits (range 100 1000))

This returns the numbers from 100 to 999. The remainder of the problem can be written as follows:

(defn euler-4 []
  (->> (combo/cartesian-product three-digits three-digits)
       (filter (fn [[i j]] #(>= i j)))
       (map (fn [[i j]] (* i j)))
       (filter palindrome?)
       (apply max)))

In it, we generate all pairs of three digit numbers using combo/cartesian-product. We take those pairs and, since i*j=j*i, we get rid of half of them by trying only the ones where i>=j. Next we map these pairs to their products and filter them on whether the products are palindromic. Finally, we take the max of all of the palindromic products to find the answer.

Next post, we'll tackle problems five through nine.

Project Euler in Clojure: The First 25 Problems - Problem 1

posted Mar 16, 2017, 9:50 AM by Frank Adrian [ updated Jul 20, 2018, 3:30 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.

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 1

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.

Heartbleed and code opacity

posted Apr 10, 2014, 5:47 PM by Frank Adrian

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

posted Nov 5, 2013, 10:49 AM by Frank Adrian [ updated Nov 5, 2013, 10:55 AM ]

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

posted Jul 25, 2013, 10:04 AM by Frank Adrian [ updated Jul 25, 2013, 10:05 AM ]

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.

1-10 of 55