That said, on to the next test. Let's make it a little more complex and skip two live cells, but go directly to three live cells.
[<TestFixture>] type ``Given a gameboard with three live neighbour cells`` ()= let gameboard = [[0; 0; 0]; [1; 1; 1]; [0; 0; 0]] let gameboard_after_gen_1 = [[0; 0; 0]; [0; 1; 0]; [0; 0; 0]] [<Test>] member test. ``When I ask for generation 1, the middle cell should still live`` ()= conway gameboard 1 |> should equal gameboard_after_gen_1
This test will be red, because all cells after a first generation will be dead. We will need to add extra code to keep certain cells (those with two living neighbours) alive. Remember the code we had up until now:
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 new_row else kill_row (0 :: new_row) [1 .. List.length gameboard] |> List.map(fun x -> kill_row List.Empty) let conway gameboard n = match n with | 0 -> gameboard | 1 -> kill gameboard
The line that needs to be altered is the one where we prepend (cons in F# terms) the number 0 with the new_row parameter. In stead of always consing 0, we will need to calculate which number needs to be consed. To do this calculation we will also need some notion of the row and cell index for which we need to calculate this value, so this needs to be added somehow as well. The row index can be send along via the List.map function at the bottom. The cell index can be calculated from the length of the new_row parameter up until now.
If we add the notion of a row_index, the code will look like this (changes are marked in red):
If we add a calculation of a new_cell_value for a certain cell index, it will look like this:let kill gameboard = let rec kill_rowrow_indexnew_row = let length = List.length (List.head gameboard) if List.length new_row = length then new_row else kill_rowrow_index(0 :: new_row) [1 .. List.length gameboard] |> List.map(fun x -> kill_rowxList.Empty)
let kill gameboard =let calc_next_cell_value x y = 0let rec kill_row row_index new_row = let length = List.length (List.head gameboard) if List.length new_row = length then new_row else let new_cell_value =
calc_next_cell_value (length - (List.length new_row)) row_index
kill_row row_index (new_cell_value :: new_row)
[1 .. List.length gameboard] |> List.map(fun x -> kill_row x List.Empty)
As for the calc_next_cell_value function, let's do this as naively as we did before. Implement just enough to make the test pass. I first tried it this way, using the build in Item function to get an item from a list:
let calc_next_cell_value x y = let current_cell_state = gameboard.Item(y).Item(x) let number_of_alive_neighbours = gameboard.Item(y).Item(x - 1) + gameboard.Item(y).Item(x + 1) if current_cell_state = 0 then 0 else if current_cell_state = 1 && number_of_alive_neighbours = 2 then 1
else 0
This might work, but the compiler seems to need type information concerning the list you get once you execute Item(y) on it (it is needed to resolve the Item(x) call). Adding this type information however, was not something I wanted to do. So instead of adding a type to the gameboard parameter, I wrote my own functions to get at a certain cell.
let cell x y = nth x (nth y gameboard) let calc_next_cell_value x y = let current_cell_state = cell x y let number_of_alive_neighbours = cell (x - 1) (y) + cell (x + 1) (y) if current_cell_state = 0 then 0 else if current_cell_state = 1 && number_of_alive_neighbours = 2 then 1 else 0
The nth function is written as a recursive function on the list and it actually adds some boundary checking. Once we go out of bounds (our n is bigger than our list length or smaller than 1), we always return 0. If we stay in bounds, we check if n is 1, this means we can return the head of the list. In all other cases, we decrement n and execute the nth function on the tail of the list.
let rec nth n list = if n > List.length list then 0 else if n < 1 then 0 else if n = 1 then List.head list else nth (n - 1) (List.tail list)
To make this implementation of the nth function more visible, suppose our list is as follows: [1; 2; 3; 4; 5] and we ask for the third element. The bottom else case will get executed. The nth function is called again with an n of 2 and a list of [2; 3; 4; 5] (the tail of the original list). Again the bottom else statement will be executed, which will call the nth function again with a n of 1 and a list of [3; 4; 5]. This time the n parameter equals 1 and the head of the list will be taken, which has the value of 3. This again is a very commonly used pattern when working with lists in functional languages.
But this implementation of nth actually keeps the problem of the compiler complaining about the type we get when executing the function (it is more or less the same problem we had with the Item(y) call). F# is quite strict in working with types. And this was one of the primary problems I had while implementing the Game Of Life. Where as a language as Scheme (from which I ripped the solution) doesn't bother with types, F# does. And if you execute the nth function as follows: (nth y gameboard), you actually want a list at a certain index in a list of lists. And if you execute the nth function again for the x parameter, you actually want the cell at position x in a list of integers. So one time you are operating on a list of lists and the next on a list of integers. F# doesn't like that. So, to solve this problem I added another function,to get the nth row in a list of lists.
let rec nth_row n list = if n > List.length list then [] else if n < 1 then [] else if n = 1 then List.head list else nth_row (n - 1)(List.tail list)
This function looks very similar to the nth function, with the difference that it explicitly tells the compiler it will return something of the list type.
On the calling side, I changed the code to this:
let cell x y = nth x (nth_row y gameboard)
The entire implementation now looks like this:
let rec nth_row n list = if n > List.length list then [] else if n < 1 then [] else if n = 1 then List.head list else nth_row (n - 1)(List.tail list) let rec nth n list = if n > List.length list then 0 else if n < 1 then 0 else if n = 1 then List.head list else nth (n - 1) (List.tail list) let do_generation gameboard = let cell x y = nth x (nth_row y gameboard) let calc_next_cell_value x y = let current_cell_state = cell x y let number_of_alive_neighbours = cell (x - 1) (y) + cell (x + 1) (y) if current_cell_state = 0 then 0 else if current_cell_state = 1 && number_of_alive_neighbours = 2 then 1 else 0 let rec kill_row row_index new_row = let length = List.length (List.head gameboard) if List.length new_row = length then new_row else let new_cell_value = calc_next_cell_value (length - (List.length new_row)) row_index kill_row row_index (new_cell_value :: new_row) [1 .. List.length gameboard] |> List.map(fun x -> kill_row x List.Empty) let conway gameboard n = match n with | 0 -> gameboard | 1 -> do_generation gameboard
You might have noticed I also changed the name of the kill function to do_generation. Refactoring this was needed!
And this is actually already the main part of our Game Of Life. The only thing that still needs to be added, are some more calculations for the alive count of a cell and some extra rule checks for keeping cells alive or killing them off, and off course the ability to calculate more than 1 generation.
I will add all of those at the next hole.
No comments:
Post a Comment