Archive for July, 2012

How Clojure is breaking my brain – Loops

Seeing how Chris Houser, aka Chouser, aka @chrishouser, one of the co-authors of the Joy Of Clojure, shared a link to my post on twitter, and with a few tweets:

I figured I should follow up the start of that conversation, and tease apart my current thinking about loops.  The short version is:

I never want to have to write a loop again.

As this is quite the bold statement, some elaboration is in order.

First I realized a number of years ago that every time I would write a loop, I would write a lot of duplicate code. The code wasn’t always identical, but it had the same structure, so much so, that many IDEs now have ‘for loop’ templates. I had realized there were certain structures to the loops, but I never had the “AH-HA!” moment to truly recognize the patterns.

Then a series of events started to come together: I read Structure and Interpretation of Computer Programs for the first time, we moved on to .NET 3.5 at work and were able to take advantage of LINQ, I started looking into Ruby, and finally, I started digging into Clojure.

Now I had heard people talk about some of the looping patterns before, hearing people talk about Smalltalk and Ruby, but it wasn’t until I started getting into Clojure that it fully clicked in that there really are only a handful of different loops: projection (map, select, transformation), collection (reduce, collect, aggregate, accumulate, sum, multiple), filtering (filter, exclude, include, where), grouping (group, frequencies), and maybe a couple of others I am leaving out now, as well as composition of the different looping constructs.

Projection

The projection looping pattern simply takes a collection of elements and applies some projection against them to get a new view of the objects. The Hello World example of this is the squares of a set of numbers.
The imperative version in C#, or any C-style language would be written as:

var squares = new List<int>();
for(int i = 1; i <= 10; 1++)
{
  squares.Add(i*i);
}
return squares;

In Clojure this would be:

(map #(* % %) (range 1 11))

In C# with LINQ this is:

  Enumerable.Range(1, 10).Select(x => x * x);

Collection

The collection looping pattern is about getting a single value out, though there may be cases when multiple values come out. The Hello World example of this tends to be the sum of the numbers in a sequence, or the multiple of the numbers.

The imperative version in C#, or any C-style language would be written as:

var sum = 0;
for(int i = 1; i <= 10; 1++)
{
  sum += i;
}
return sum;

In Clojure this would be:

(reduce + (range 1 11))

In C# with LINQ this is:

  Enumerable.Range(1, 10).Sum();

Filtering

The filter looping pattern is to find a subset of items that match a criteria.

The Hello World example of this tends to be getting only the even numbers in a sequence.

The imperative version in C#, or any C-style language would be written as:

var numbers = new List<int>();
for(int i = 1; i <= 10; 1++)
{
  if (!IsEven(i))
    continue;

  numbers.Add(i);
}
return numbers;

In Clojure this would be:

(filter even? (range 1 11))

In C# with LINQ this is:

  Enumerable.Range(1, 10).Where(x => IsEven(x));

Grouping

The grouping looping pattern is to create a set of groups of items, where each group match the same criteria.

The Hello World example of this tends to be grouping numbers of a sequence into those that are even, and those that are not.

The imperative version in C#, or any C-style language would be written as:

var groups = new Dictionary<bool, List<int>>();
for(int i = 1; i <= 10; 1++)
{
  var key = IsEven(i);
  if (!groups.ContainsKey(key))
  {
    groups[key] = new List<int>();
  }
  groups[key].Add(i);
}
return groups;

In Clojure this would be:

(group-by even? (range 1 11))

In C# with LINQ this is:

  Enumerable.Range(1, 10).GroupBy(x => IsEven(x));

In this type of looping, the differences between the imperative and the declarative styles really start to show, even in a simple example such as this.

What about for loops as a counter?

As you can see above, I was just going against a range of numbers, and if needed, would go against range generated with a increment.

OK. So!?

Well…

First, my disclaimer. I am sure I have some of the pattern names wrong, but I have tried to identify them generically to help describe the differences though name only. Second, I am by far not the first one to identify these, I am only trying to document my understanding at the time, and help spread knowledge about these concepts. I would love feedback on the correct pattern names, and the others that I might have left out, or missed, so that I can help keep this as accurate as possible.

Second, I realize that these are all trivial examples, but I hope they illustrate enough to clarify following point I am about to make, if you haven’t already bought into it.

The beauty of these is that the loops become easily composable, as well as the program is now freed from the implementation of these operations, which can be changed separately from the program. The operations could be lazily evaluated and only done on demand; they could be parsed and fed into one giant function that exhibits the same results but tuned to be able to require only one pass through the items; if the language, or program is idempotent, then they could parallelized either by splitting off work into smaller pieces and assembling the results together, or farmed out to multiple worker processes so that we have multiple subprograms working against a problem and then we get a result from those (first one wins, or some kind of voting system). But when I am writing the program those are details I don’t care about.

This allows me to first express what I want the program to do, and then (after) I have expressed my intent and am sure that it is correct, I, or preferably someone much smarter than me, can go back and determine how, and any better ways, to execute my intent.

So in summary, to take Steve McConnell’s quote in Code Complete:
…if you work for 10 years, do you get 10 years of experience or do you get 1 year of experience 10 times?
and ask:
…if you have been writing loops for 10 loops, have you just been writing same loop all 10 years?

–Proctor

, , ,

2 Comments

How Clojure is breaking my brain – Javascript

As I have been digging into Clojure, and working through the Project Euler problems for having something to program in Clojure, I have discovered that Clojure is really starting to break my brain.

One example of this I encountered recently was in some JavaScript I had to modify and extend.

The specific JavaScript that I had to modify was to extend functionality whose purpose was to try and find an identifier that corresponded to a given range. As it existed though, the data I needed to operate against was defined in two different arrays, one which had all of the numbers for the ranges for the different options, and a second arrays which had the identifiers for the different options.

So for a given set of data (the following ranges are adjoining in this example, but that does not always hold true), which would be outlined as such:

  • When the value is between a min of 0 and max of 4 the identifier is ‘A’,
  • When the value is between a min of 5 and max of 17 the identifier is ‘B’,
  • When the value is between a min of 18 and a max of 33 the identifier is ‘C’, and
  • When the value is between a min of 34 and a max of 51 the identifier is ‘D’.

So given the criteria outlined above, the previous version of the JavaScript had two arrays that were defined as:

var ranges = [0, 4, 5, 17, 18, 33, 34, 51];
var identifiers = ['A', 'B', 'C', 'D'];

And the code that did the checks for the the identifier that corresponded to a given value were defined as follows:

function someFunctionFor2Options(currentValue) {
  if (currentValue >= ranges[0] && currentValue <= ranges[1]) 
    return identifiers[0];
  if (currentValue >= ranges[2] && currentValue <= ranges[3])
    return identifiers[1];
  return null;
};
function someFunctionFor3Options(currentValue) {
  if (currentValue >= ranges[0] && currentValue <= ranges[1])
    return identifiers[0];
  if (currentValue >= ranges[2] && currentValue <= ranges[3])
    return identifiers[1];
  if (currentValue >= ranges[4] && currentValue <= ranges[5])
    return identifiers[2];
  return null;
};
function someFunctionFor4Options(currentValue) {
  if (currentValue >= ranges[0] && currentValue <= ranges[1])
    return identifiers[0];
  if (currentValue >= ranges[2] && currentValue <= ranges[3])
    return identifiers[1];
  if (currentValue >= ranges[4] && currentValue <= ranges[5])
    return identifiers[2];
  if (currentValue >= ranges[6] && currentValue <= ranges[7])
    return identifiers[3];

  return null;
};

If you look at the three functions above, you can see that they are the same, just with different number of if clauses depending on how many criteria were possible.

This is the first way that Clojure has broken my brain. I saw this, and immediately started thinking:

“Shouldn’t this be expressed in a different structure, one that makes the relationship between the id and the range explicit? Something like a map with the keys and values that I could destructure? With that nested in some kind of sequence, where I don’t care about the number of items, but just filter out the ones that match…”

As I am doing this in JavaScript this became an array (sequence) of JSON objects (maps).

var newStructure = [ {id: 'A', min: 0, max: 4 },
                     {id: 'B', min: 5, max: 17 },
                     {id: 'C', min: 18, max: 33 },
                     {id: 'D', min: 34, max: 51 } ];

This now allowed me to iterate over the sequence of JSON objects, and filter out the ones that meet a criteria, and then get the id for the first one. Which leads me to the second way that Clojure has started to break my brain and wriggle into it like the larvae of a Ceti Eel of Ceti Alpha V.

Where the way Clojure was twisting my brain, was that I started this by writing a couple of for loops in JavaScript to get the different results needed. As I was starting to type out the the third loop, I realized I was writing Yet Another Loop, and what I really wanted were higher order functions for JavaScript that could operate on a collection of items. I pulled out the search engine, and started looking for what higher order functions were available in JavaScript, but didn’t find any built in. I debated on writing my own, but decided I should investigate further to see if I could find any libraries as this seemed like it should be a solved problem for as long as JavaScript has been around, and found UnderscoreJS. This gave me the ability to not only use higher order functions but to be able to chain them and compose them in a reader friendly way, resulting in functions that now look like:

var newStructure = [ {id: 'A', min: 0, max: 4 },
                     {id: 'B', min: 5, max: 17 },
                     {id: 'C', min: 18, max: 33 },
                     {id: 'D', min: 34, max: 51 } ];

function isInRange(currentValue, candidate) {
  return (candidate.min <= currentValue && curentValue <= candidate.max);
}

function findIdentifierFor(currentValue) {
  return = _.chain(newStructure)
            .find(function(candidate) {return isInRange(currentValue, candidate);})
            .value()
            .id;
}

So in ending this segment of How Clojure is Breaking My Brain, I am yet again reminded of the quote that is quite popular in the functional programming circles from Alan J. Perlis in his “Epigrams in Programming” article for ACM SIGPLAN.

It is better to have 100 functions operate on one data structure than 10 functions on 10 data structures.

–Proctor

, ,

5 Comments

Setting the title in Terminal on OS X

Working through my Project Euler problems in Clojure, I wound up having a number of Terminal windows open at the same time: one for the REPL, one for a prompt to commit to my Project Euler git repo, one for a Midje program, one to start the Light Table Playground, and various others with other things I had going on.

With all of these windows, getting stacked on top of one another I was losing track of which Terminal window was which when I went to the Window menu for Terminal to get to the window I wanted.

I found this post Mac OS X Change the Terminal Window Title and then followed the instructions to get a nice little shell program setup to set the title of the window.

echo -n -e "33]0;$107"

Where I use the $1 instead the title itself, or a environment variable, per his two examples, to be able to have the first argument to the script, so now I can just run:

title "Light Table Playground"

I just figured I would share my find for anyone out there who hasn’t yet stumbled across it yet.

–Proctor

,

Leave a comment

Project Euler in Clojure – Problem 14

Here is my solution to Problem 14 of Project Euler. As always, my progress you can tracked on GitHub at https://github.com/stevenproctor/project-euler-clojure.

Problem 14 of Project Euler is to find the starting number with the longest Collatz sequence, summarized from the problem page as:

The following iterative sequence is defined for the set of positive integers:
n -> n/2 (n is even)
n -> 3n + 1 (n is odd)
[...]
Which starting number, under one million, produces the longest chain?

The first function I needed was a function to get the next number in the Collatz sequence.

(defn next-collatz [n]
  (cond (<= n 1) nil
   	(even? n) (/ n 2)
        (odd? n) (+ (* 3 n) 1)))

This function mimics the above definition of the sequence, with the distinction of the check to see if the number is less than, or equal to, 1. While not strictly necessary, when I was generating numbers from the REPL, I noticed that the sequence never really terminates, but ends in a repeating sequence of 4 -> 2 -> 1 -> 4 -> 2 -> 1 ->.... This can be seen by running the following at the REPL.

(take 15 (iterate next-collatz 8))

Wich results in the sequence (8 4 2 1 4 2 1 4 2 1 4 2 1 4 2). I used the condition (<= n 1) as a guard condition to as a way to be able to terminate the sequence and make it finite. This could probably be removed at this point, as I did not even use the nil return as a check, except that it would serve as a reminder of the function when playing at the REPL.

The next function I defined was a function to get the count of the numbers in the sequence. I defined it this way in the hopes of trying to memoize the values, but I kept getting an OutOfMemoryException when I tried to use it so I took the memoization away.

(defn collatz-count-for [n]
  {:pre  [(pos? n)]}
  (if (= n 1) 1
      (inc (collatz-count-for (next-collatz n)))))

In this function, I decided I would add a precondition to the function requiring that the parameter to the function be positive. This way I could avoid having to try and generate a Collatz sequence for negative numbers, as they are outside the scope of this problem. The function first checks if the number to generate the sequence for is 1, and if so, the count of the sequence returns 1. For all other positive numbers, we get the length of the sequence for the next Collatz number in the sequence, and increment that value, and return that as the Collatz count.

As I was writing this up, I decided I would take another stab at this, and did some searching to try and find a way to change the memory allocation for the project in the REPL. I found the following post How to Set JVM Memory for Clojure REPL in Emacs, and added the following to my project.clj file.

:jvm-opts ["-Xmx768M"]

When I ran with the following memoized version of the collatz-count-for, it now runs much quicker than it did before. Previously it was a rough mental counting of about 10-15 seconds, and now the first time is runs was 2-3 seconds, and sub second on runs after that even.

(def collatz-count-for (memoize 
  (fn [n]
    {:pre [(pos? n)]}
    (if (= n 1) 1
      (inc (collatz-count-for (next-collatz n)))))))

The changes needed to memoize the function collatz-count-for is that the defn is now a def, which assigns the identifier of collatz-count-for to the result of passing a now nameless function, with the previous function body, to the function memoize. This allows the function body to remain the same, and only the declaration of the function has to now change.

With those pieces to the problem in place, we can now find the number that generates the longest Collatz sequence.

(defn problem14
  ([] (problem14 1000000))
  ([n] (first (reduce
                (fn [memo x]
                  (if (> (second x) (second memo)) x memo))
                (map #(vector % (collatz-count-for %)) (range 1 (inc n)))))))

I started by mapping over the numbers from 1 to 1000000, to create vectors representing the pair of the number and the sequence length for that number. An example of which results in the following sequence (shown to the first 10 numbers):

([1 1] [2 2] [3 8] [4 3] [5 6] [6 9] [7 17] [8 4] [9 20] [10 7] ...)

I then feed that sequence into reduce, with a function to find the pair with the largest sequence length by calling second on the vector, resulting in the pair of number and sequence length with the largest sequence length. And having found that vector, I use first to find what the number with the largest sequence length is.

This seems like it might be generic enough (idiomatic pattern) that I was missing something that was already defined to do the map and reduce on a structure like this, but I could not find anything. If anybody knows of anything I would love to see how that might be made more expressive.

–Proctor

, ,

5 Comments

Project Euler in Clojure – Problem 13

Here is my solution to Problem 13 of Project Euler. As always, my progress you can tracked on GitHub at https://github.com/stevenproctor/project-euler-clojure.

Problem 13 of Project Euler is described as:

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
[...]

And my solution for this, including previously defined functions created as part of solving the previous problems, is the following:


(defn digits-of [n]
  (map #(Integer/parseInt (str %)) (str n)))

(defn digits-of [n]
  (map #(Integer/parseInt (str %)) (str n)))
(defn problem13 []
  (let [numbers [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]]
    (bigint (reduce str "" (take 10 (digits-of (sum numbers)))))))

Problem 13 was pretty straight-forward, as the problem, I took the list of the one-hundred numbers as a vector, and then called the function sum which has been used in a number of previous problems as well as the digits-of function which was created in my solution to Problem 8. With these two functions, to get the first 10 digits of the sum was to just call take on the result of calling digits-of on the sum of the numbers in the vector numbers.

The rest of the function is to make the output to the REPL nice. I take the individual digits and turn them into a string using reduce str "", and then call the function bigint to cast it to an integer value.

**Update**
I have posted my solution to Problem 14.
–Proctor

, ,

Leave a comment

Project Euler in Clojure – Problem 12

This is my solution to Problem 12 of Project Euler. As always, my progress you can tracked on GitHub at https://github.com/stevenproctor/project-euler-clojure.

Problem 12 of Project Euler is described as:

The sequence of triangle numbers is generated by adding the natural numbers.
So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.
[...]
What is the value of the first triangle number to have over five hundred divisors?

And my solution for this, including previously defined functions created as part of solving the previous problems, is the following:

(defn factors-starting-at [f n]
  (cond (= n 1) []
        (factor-of? f n) (cons f (factors-starting-at f (/ n f)))
        :else (recur (inc f) n)))

(defn prime-factors-of [n]
  (factors-starting-at 2 n))

(defn factors-count [n]
  (multiply (map #(inc %) (vals (frequencies (prime-factors-of n))))))

(defn triangle-numbers
  ([] (concat [1] (triangle-numbers 1 2)))
  ([s n] (let [t (+ s n)]
          (lazy-seq
            (cons t (triangle-numbers t (inc n)))))))

(defn problem12 []
  (first (drop-while #(<= (factors-count %) 500) (triangle-numbers))))

The functions factors-starting-at and prime-factors-of get the prime factors of a given number. The function factors-count calls frequencies on the sequence returned by prime-factors-of, and then increments each item in the sequence and multiplies the items together, to get the total number of factors for a number. I found this formula for getting the count of the factors from StackOverflow question: Algorithm to calculate the number of divisors of a given number.

The function triangle-numbers gets a lazy sequence of the triangle numbers, by taking the previous triangle number, and adding the index of the current triangle number.

The function problem12 then drops the items in the sequence while the result of factors-count is <= 500, and gets the first triangle number, which is the first number with a the count of the number of factors greater than 500.

–Proctor

, ,

2 Comments

Project Euler in Clojure – Problem 11

This is my solution to Problem 11 of Project Euler. As always, my progress you can tracked on GitHub at https://github.com/stevenproctor/project-euler-clojure.

Problem 11 of Project Euler is described as:

        08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
        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 08 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 09 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 09 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 08 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 08 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

What is the greatest product of four adjacent numbers in any
direction (up, down, left, right, or diagonally) in the 2020 grid?

I looked into using Incanter but didn’t get it setup as I am using Clojure 1.4, and had some issues getting the dependencies resolved. No big deal though, as I just used a vector of vectors to represent a matrix. I created a new file matrix.clj, which got the namespace definition for project-euler.matrix.

(ns project-euler.matrix)

The first function I defined was transpose, since I am going to want to work against the columns, but rows are easier to think about and work with.

(defn transpose [m]
  (vec (apply map vector m)))

Since I am going to need to find groups of four numbers in the matrix, I defined the following to functions to get all possible groups of four in the rows, and in the columns.

(defn partition-rows [m n step]
  (if (= (count m) 0)
      []
      (concat (partition n step (first m)) (partition-rows (rest m) n step))))

(defn partition-columns [m n step]
  (partition-rows (transpose m) n step))

The partition-rows function just concats the results of calling partition on each row with the group size, n, and the step, by calling partition on the first row of the matrix (first m), and then calling partition-rows again with the remaining rows in the matrix given (rest m). The function partition-columns simply transposes the matrix m and then calls partition-rows with that matrix.

The next two functions are two helper functions, which were defined after writing some of the following functions, and exist to better express intent.

(defn matrix-get [m r c]
  (nth (nth m r) c))

(defn row [m n]
  (nth m n))

The function matrix-get gets the rth row from the matrix m and then gets the cth item in that row. The function row gets the row for a matrix. Again nothing special about these functions except that they help to communicate the intent, and give the concept a name. These were littered around the code so the functions were created as part of tidying up. In looking at it as I was writing up this post, I realized I still didn’t pull out the concept of row in the function matrix-get, and the two functions should probably be defined as follows instead:

(defn row [m n]
  (nth m n))

(defn matrix-get [m r c]
  (nth (row m r) c))

Working through getting the diagonals, I posted a call for help about a clean way to get the diagonals for a matrix in the post Smelly matrix diagonals. I got some good comments, and after taking a bit to pick apart the functions, I went with the following from the comments, thanks to Mark.

(defn diagonals [m]
  (let [rdim (count m)
    cdim (count (first m))]
    (->> (for [r (range rdim), c (range cdim)]
            {(+ r (- cdim c)) [(matrix-get m r c)]})
         (apply merge-with into)
         vals)))

This worked great, but I also needed to get the diagonals going from the bottom left to the top right, which resulted in the function reverse-diagonals.

(defn reverse-diagonals [m]
  (let [rdim (count m)
    cdim (count (first m))]
    (->> (for [r (range rdim), c (range cdim)]
            {(+ r c) [(matrix-get m r c)]})
         (apply merge-with into)
         vals)))

As this was almost the same function as diagonals, with just a different function for getting the key, so I extracted a function matrix-lines which resulted in:

(defn matrix-lines [m f]
  (let [rdim (count m)
        cdim (count (first m))]
    (->> (for [r (range rdim), c (range cdim)]
            {(f rdim cdim r c) [(matrix-get m r c)]})
         (apply merge-with into)
         vals)))

(defn diagonals [m]
  (matrix-lines m (fn [rdim cdim r c] (+ r (- cdim c)))))

(defn reverse-diagonals [m]
  (matrix-lines m (fn [rdim cdim r c] (+ r c))))

Where the function matrix-lines will generate the lines based off of a function to generate a key for a given cell.

I have seen that it is idiomatic Clojure code to use _s to signify function variables that are not used, so looking at this with some fresh eyes, should those variables defined in the functions diagonals and reverse-diagonals be an _ instead, even though they are the first bindings to the function?

The last part of working with the matrix that I needed were functions to partition the diagonals, and get all the partitioned diagonals in both directions.

(defn partition-diagonals [m n diagonals-fn]
  (apply concat (map #(partition n 1 %) (diagonals-fn m))))

(defn partition-every-diagonal [m n]
  (concat (partition-diagonals m n diagonals) (partition-diagonals m n reverse-diagonals)))

The function partition-diagonals returns the result of concating every resulting seq from calling partition on every result of call the diagonals-fn which is the function to get the diagonals that was passed in as the second parameter. The function partition-every-diagonal simply concats the results of calling partition-diagonals with the functions diagonals and reverse-diagonals.

(defn problem11
  []
  (let [m [[ 8  2 22 97 38 15  0 40  0 75  4  5  7 78 52 12 50 77 91  8]
           [49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48  4 56 62  0]
           [81 49 31 73 55 79 14 29 93 71 40 67 53 88 30  3 49 13 36 65]
           [52 70 95 23  4 60 11 42 69 24 68 56  1 32 56 71 37  2 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  3 45  2 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  2 62 12 20 95 63 94 39 63  8 4  91 66 49 94 21]
           [24 55 58  5 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72]
           [21 36 23  9 75  0 76 44 20 45 35 14  0 61 33 97 34 31 33 95]
           [78 17 53 28 22 75 31 67 15 94  3 80  4 62 16 14  9 53 56 92]
           [16 39  5 42 96 35 31 47 55 58 88 24  0 17 54 24 36 29 85 57]
           [86 56  0 48 35 71 89  7  5 44 44 37 44 60 21 58 51 54 17 58]
           [19 80 81 68  5 94 47 69 28 73 92 13 86 52 17 77  4 89 55 40]
           [ 4 52  8 83 97 35 99 16  7 97 57 32 16 26 26 79 33 27 98 66]
           [88 36 68 87 57 62 20 72  3 46 33 67 46 55 12 32 63 93 53 69]
           [ 4 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  4 36 16]
           [20 73 35 29 78 31 90  1 74 31 49 71 48 86 81 16 23 57  5 54]
           [ 1 70 54 71 83 51 54 69 16 92 33 48 61 43 52  1 89 19 67 48]]]
    (apply max
           (map multiply
                (concat (partition-rows m 4 1)
                        (partition-columns m 4 1)
                        (partition-every-diagonal m 4))))))

The function problem11 applys the function max to the result of calling multiply on every possible partition of the matrix m, to get largest multiple of ‘four adjacent numbers in any direction’.

So far, this has been the Project Euler problem with the most code that was needed to solve the problem, including the ones I have solved but not posted answers to yet. While overall this is still not a great deal of code, I am wondering if there are any things that I am missing that might make this even more concise and expressive.

Is there anything that I have missed? Anything interesting in my approach? Again, I thank you in advance for any comments that you might have on this.

Thanks again,
–Proctor

, ,

1 Comment