Monday, August 1, 2011

Playing GOLF, hole 2

The first hole of playing GOLF, involved the first most simple tests one could write for Conway's Game Of Life. In this next post we will add tests for a gameboard with life cells (actually just one life cell for now). For this I created a new TestFixture, so all tests are nicely separated in the ReSharper runner.

 type ``Given a gameboard with 1 live cell`` ()= 
   let gameboard =  
     [[0; 0; 0]; 
     [0; 1; 0]; 
     [0; 0; 0]] 
   let dead_gameboard =  
     [[0; 0; 0]; 
     [0; 0; 0]; 
     [0; 0; 0]]
   [<Test>] member test. 
    ``When I ask for generation 0, should not change gameboard`` ()= 
     conway gameboard 0 |> should equal gameboard 
   [<Test>] member test. 
    ``When I ask for generation 1, the life cell should be dead`` ()= 
     conway gameboard 1 |> should equal dead_gameboard  

The example above immediately adds two new tests. The first one will be green immediately using the current implementation, this is why I didn't bother to split this example up. The second test, however, will not pass. The current implementation simply returns the gameboard as is and doesn't yet alter it. We need to implement our conway function further to make this test turn green. This is the code, I will explain it part by part, so it's not too overwhelming if you've done little to no F# coding.

 module GOL 
 let kill gameboard = 
   let rec kill_row new_row =  
     let length = List.length (List.head gameboard) 
     if List.length new_row = length then 
       kill_row (0 :: new_row)  
   [1 .. List.length gameboard] |> x -> kill_row List.Empty)  
 let conway gameboard n = 
   match n with 
     | 0 -> gameboard 
     | 1 -> kill gameboard 

This is actually quite a naive way of implementing the red test case. For making a first generation, we kill off the entire gameboard. I did this on purpose, because this way, you can see the basic way you can use for working with lists, or better, lists of lists in our case. The gameboard is actually a list of lists, so if we want to do some operation on it, we do this list per list (or row per row). This basic implementation is also the most simple implementation you can give, to make the test pass.

As for the starting point of our conway function, which you can find at the bottom of the example code, I used F#'s feature of pattern matching. This is actually something very powerful and looks a lot like a switch case in regular programming languages. Except that pattern matching in F# is more like a switch case on speed, since it gives you more opportunities. In this example the speed is still a bit missing, we just have two cases up until now, a 0 and a 1 case. For the 0 case we just return the gameboard as is. For generation 1 we kill off the gameboard.

As for the kill function, the actual starting point is the bottom line with the in it (the other lines represent an inner function, but more about that in a while). This tells the compiler to execute the function kill_row for the input we give it. This input is actually a list of integers of 1 up until the length of our game board (which is the number of rows in it).

The kill_row function is an internal function of the kill function. This has the advantage that the gameboard input parameter is accessible and we can use it to calculate the length of one row. For this we take the first row, using List.head and of this we take the length, with List.length. This calculation of the length is something that will be done only once, not for each recursive call.

The input parameter for kill_row is an empty list. Item per item in a row, we will prepend the number 0 (kill off one cell) to this list. This process continues until we get a row of all zero's that has the same length as the length of one row of our game board (the length variable). And since the input for the function is a list (one of integers), each resulting row will be put in this list. We actually transform a list of integers into a list of rows (where each row is again a list of integers).

This might seem an unusual way of working, but is actually quite a common pattern of iterating over lists and building new lists in a functional language. It takes some getting used to as well. And from time to time it just looks weird, since most of us are used to doing this with loops.

This implementation also made our tests green, so on to hole number 3.

No comments:

Post a Comment