let () = print_endline "__indiafoss_boot_ready__"
Game lab
Practice: Conway's Game of Life
In this lab you will implement the logic for Conway's Game of Life: a grid of cells, each alive or dead, where every cell updates at once under two rules. A live cell survives with 2 or 3 live neighbors; any other count kills it. A dead cell with exactly 3 live neighbors comes alive. Conway invented these two rules in 1970, and they're enough to produce complex shapes like gliders that crawl steadily across the board without ever stopping.
Most of this lab assumes that you did the Tic-Tac-Toe lab first. In its form, this lab is very similar. However, no worries if you haven't done that lab yet: the code is provided for you, and you can still complete this lab without it.
On the right is a game panel (hidden for now) that will render the board and let you run the simulation. You will implement the logic for counting live cells, counting a cell's live neighbors, and deciding whether each cell lives or dies from one generation to the next. All of the piping for the game is already in place so you will only be implementing the logic.
Three small functions build the core simulation: population counts live cells, and count_live_neighbors and next_cell_state together decide who lives and who dies each generation. Three stretch functions build on top of that: random_grid seeds a random board, and parse_rule with next_cell_state_general let you play variants of Life with different birth/survival rules.
Below you can read some of the important functions and definitions that you will have to use as you code up the solutions to the given functions.
let rows = 24
(* number of rows on the board *)
let cols = 24
(* number of columns on the board *)
type grid = bool list list
(* alive/dead for every cell, one list of rows, each row a list of cells *)
let make_grid () = List.init rows (fun _ -> List.init cols (fun _ -> false))
(* a fresh, all-dead board *)
(* reads the cell at (r, c). Lists have no `.(r).(c)` syntax, so every read in this exercise goes through this instead. *)
let get g r c = List.nth (List.nth g r) c
(* returns a NEW board with (r, c) set to v, everything else unchanged. *)
let set g r c v =
let rec replace_nth i v lst =
match lst with
| [] -> []
| x :: rest -> if i = 0 then v :: rest else x :: replace_nth (i - 1) v rest
in
replace_nth r (replace_nth c v (List.nth g r)) g
(* wraps a coordinate onto the board, so that the top edge wraps to the bottom and the left edge wraps to the right. *)
let wrap n limit = if n < 0 then n + limit else if n >= limit then n - limit else n
(* the eight (row, column) offsets around a cell *)
let neighbor_offsets =
[ (-1, -1); (-1, 0); (-1, 1); (0, -1); (0, 1); (1, -1); (1, 0); (1, 1) ]
The last two definitions are interesting. In Conway's Game of Life, the board is a torus: the top edge wraps to the bottom, and the left edge wraps to the right. The wrap function keeps a coordinate on the board by wrapping it around the edge. The neighbor_offsets list contains the eight (row, column) offsets around a cell, which you will use to count its live neighbors.
At some point, you might be wondering, does OCaml not have a built-in 2D array type? It does, but the game panel is written to use lists instead. For pedagogical purposes we just prefer to use lists because they are more ideologically aligned with some core tenets of functional programming (namely immutability).
Open the provided game code below and press Run to render the board. You need not read every function, though it is a useful example of idiomatic OCaml. The board starts with minimal functionality and gets built up as you finish the problems.
Provided game and board code
(* PROVIDED, continued -- drawing, session state, patterns, and the board's event wiring. Uses rows/cols/grid/make_grid/get/set/wrap/ neighbor_offsets from the cell just above. *)
let cell_html r c alive =
Printf.sprintf "<td class=\"%s\" data-xo-pos=\"%d:%d\"></td>"
(if alive then "life-on" else "life-off")
r c
let render_grid g =
"<table class=\"life\">"
^ String.concat ""
(List.init rows (fun r ->
"<tr>"
^ String.concat ""
(List.init cols (fun c -> cell_html r c (get g r c)))
^ "</tr>"))
^ "</table>"
type session = {
grid : grid;
running : bool;
speed : int; (* ms between generations *)
gen : int;
birth_input : string; (* current text of the Birth box *)
survive_input : string; (* current text of the Survive box *)
}
let speeds = [ ("slow", 500); ("medium", 200); ("fast", 80) ]
let new_session () =
{ grid = make_grid (); running = false; speed = 200; gen = 0;
birth_input = "3"; survive_input = "23" }
let session = ref (new_session ())
(* Forward references to functions this cell needs but that don't exist yet -- population (Problem 1), advance (defined right after next_generation), and random_grid (the Stretch problem) all live further down the page. Each ref starts as a stub; the cell that defines the real function reassigns it as its own last line. Declared here, before `controls` below, because `controls` itself reads `!rule_feature_ready`/`!custom_rule_ref` directly -- a plain, single-cell "used before declared" mistake if they lived any later, unrelated to any of the cross-cell forward-reference machinery this comment is otherwise about. *)
let population_ref : (grid -> int) ref = ref (fun _ -> failwith "not implemented")
let advance_ref : (unit -> unit) ref = ref (fun () -> ())
let random_grid_ref : (float -> grid) ref = ref (fun _ -> failwith "not implemented")
(* The same forward-reference trick, for the two stretch problems all the way at the bottom of the page (parse_rule and next_cell_state_general). *)
let parse_rule_ref : (int -> int -> int list * int list) ref =
ref (fun _ _ -> failwith "not implemented")
let next_cell_state_general_ref : (int list * int list -> bool -> int -> bool) ref =
ref (fun _ _ _ -> failwith "not implemented")
let custom_rule_ref : (string * (int list * int list)) option ref = ref None
let rule_feature_ready = ref false
let button pos label active =
Printf.sprintf "<button data-xo-pos=\"%s\" class=\"%s\">%s</button>" pos
(if active then "on" else "")
label
(* A text field whose value only reaches Game_lib.on_input once the student leaves it *)
let text_input pos label value =
Printf.sprintf
"<label>%s <input type=\"text\" inputmode=\"numeric\" size=\"6\" maxlength=\"9\" data-xo-pos=\"%s\"
value=\"%s\"></label>"
label pos value
let controls s =
"<div class=\"controls\">"
^ button "run" (if s.running then "Stop" else "Start") s.running
^ button "step" "Step" false
^ button "clear" "Clear" false
^ button "random" "Random" false
^ "</div><div class=\"controls\">"
^ String.concat ""
(List.map (fun (name, ms) -> button name name (s.speed = ms)) speeds)
^ "</div><div class=\"controls\">"
^ button "pattern:glider" "Glider" false
^ button "pattern:pulsar" "Pulsar" false
^ button "pattern:spaceship" "Spaceship" false
^ button "pattern:pentadecathlon" "Pentadecathlon" false
^ "</div>"
^ (if not !rule_feature_ready then ""
else
"<div class=\"controls\">"
^ button "rule:conway" "Conway" (!custom_rule_ref = None)
^ button "rule:highlife" "HighLife"
(match !custom_rule_ref with Some ("HighLife", _) -> true | _ -> false)
^ button "rule:seeds" "Seeds"
(match !custom_rule_ref with Some ("Seeds", _) -> true | _ -> false)
^ button "rule:maze" "Maze"
(match !custom_rule_ref with Some ("Maze", _) -> true | _ -> false)
^ "</div><div class=\"controls\">"
^ text_input "birth-input" "Birth" s.birth_input
^ text_input "survive-input" "Survive" s.survive_input
^ "</div>")
let beep freq ms = Game_lib.play ~freq ~ms
(* The clock is REQUESTED, not run, by this cell: [every] states a rate and the page's main thread owns the actual timer (the worker has no DOM and no way to cancel a stale one). [every 0] stops it. *)
let sync_clock () =
let s = !session in
Game_lib.every (if s.running then s.speed else 0)
let set_speed ms =
session := { !session with speed = ms };
sync_clock ()
(* PROVIDED -- a handful of classic Life patterns, so the board can show off what this game is actually capable of before you've written a line of code. *)
let pattern_of_lines lines ~r0 ~c0 =
let g = ref (make_grid ()) in
List.iteri
(fun dr line ->
String.iteri
(fun dc ch ->
if ch = '#' then g := set !g (wrap (r0 + dr) rows) (wrap (c0 + dc) cols) true)
line)
lines;
!g
let glider_pattern = [ ".#."; "..#"; "###" ]
let pulsar_pattern =
[
"..###...###..";
".............";
"#....#.#....#";
"#....#.#....#";
"#....#.#....#";
"..###...###..";
".............";
"..###...###..";
"#....#.#....#";
"#....#.#....#";
"#....#.#....#";
".............";
"..###...###..";
]
let spaceship_pattern = [ ".####"; "#...#"; "....#"; "#..#." ]
let pentadecathlon_pattern = [ "..#....#.."; "##.####.##"; "..#....#.." ]
let load_pattern name =
match name with
| "glider" -> Some (pattern_of_lines glider_pattern ~r0:2 ~c0:2)
| "pulsar" -> Some (pattern_of_lines pulsar_pattern ~r0:5 ~c0:5)
| "spaceship" -> Some (pattern_of_lines spaceship_pattern ~r0:10 ~c0:1)
| "pentadecathlon" -> Some (pattern_of_lines pentadecathlon_pattern ~r0:11 ~c0:7)
| _ -> None
(* PROVIDED. Drawing on the board never depends on a graded exercise, so these live here too -- clicking or dragging a cell to flip it works from the very first page load, before you've solved anything below. *)
let set_cell g r c alive = set g r c alive
let toggle_cell g r c =
set_cell g r c (not (get g r c))
let population_opt g = try Some (!population_ref g) with _ -> None
let refresh () =
let s = !session in
let population_caption =
match population_opt s.grid with
| Some n -> string_of_int n
| None -> "?"
in
let rule_caption =
match !custom_rule_ref with
| None -> ""
| Some (label, _) -> Printf.sprintf " — rule %s" label
in
Game_lib.render
(render_grid s.grid ^ controls s
^ Printf.sprintf "<p>generation %d — population %s%s</p>" s.gen
population_caption rule_caption)
let handle_mouse (m : Game_lib.mouse) =
let s = !session in
match m.pos with
| "birth-input" | "survive-input" -> ()
| _ ->
(match m.pos with
| "run" ->
session := { s with running = not s.running };
beep (if s.running then 300 else 480) 70;
sync_clock ()
| "step" -> if not s.running then !advance_ref ()
| "clear" ->
session := { s with grid = make_grid (); gen = 0; running = false };
beep 240 70;
sync_clock ()
| "random" -> (
match (try Some (!random_grid_ref 0.28) with _ -> None) with
| Some g ->
session := { s with grid = g; gen = 0 };
beep 520 70
| None -> ())
| pos when String.length pos > 8 && String.sub pos 0 8 = "pattern:" -> (
let name = String.sub pos 8 (String.length pos - 8) in
match load_pattern name with
| Some g ->
session := { s with grid = g; gen = 0 };
beep 440 90
| None -> ())
| pos when String.length pos > 5 && String.sub pos 0 5 = "rule:" ->
(* Fills in the Birth/Survive boxes with the numbers that make up the preset, whether or not parse_rule is written yet -- the whole point of the buttons is to show that tuning Life is just two numbers, even before you can press one. *)
let apply label birth survive =
session := { s with birth_input = string_of_int birth; survive_input = string_of_int survive };
match (try Some (!parse_rule_ref birth survive) with _ -> None) with
| Some rule ->
custom_rule_ref := Some (label, rule);
beep 380 90
| None -> ()
in
(match String.sub pos 5 (String.length pos - 5) with
| "conway" ->
custom_rule_ref := None;
session := { s with birth_input = "3"; survive_input = "23" };
beep 300 90
| "highlife" -> apply "HighLife" 36 23
| "seeds" -> apply "Seeds" 2 0
| "maze" -> apply "Maze" 3 12345
| _ -> ())
| "slow" -> set_speed 500
| "medium" -> set_speed 200
| "fast" -> set_speed 80
| pos -> (
match String.split_on_char ':' pos with
| [ r; c ] -> (
let r = int_of_string r and c = int_of_string c in
match (m.drag, m.button) with
| false, _ -> session := { s with grid = toggle_cell s.grid r c }
| true, `Left -> session := { s with grid = set_cell s.grid r c true }
| true, `Right ->
session := { s with grid = set_cell s.grid r c false })
| _ -> ()));
refresh ()
let valid_rule_number s =
s <> "" && String.for_all (fun ch -> ch >= '0' && ch <= '9') s
let apply_birth_survive birth_str survive_str =
if valid_rule_number birth_str && valid_rule_number survive_str then
match (try Some (!parse_rule_ref (int_of_string birth_str) (int_of_string survive_str)) with _ -> None) with
| Some rule ->
custom_rule_ref := Some ("Custom", rule);
beep 380 90
| None -> ()
let handle_input pos value =
let s = !session in
(match pos with
| "birth-input" ->
session := { s with birth_input = value };
apply_birth_survive value s.survive_input
| "survive-input" ->
session := { s with survive_input = value };
apply_birth_survive s.birth_input value
| _ -> ());
refresh ()
let handle_key key =
(match key with
| " " | "Spacebar" ->
session := { !session with running = not !session.running };
sync_clock ()
| "Enter" -> if not !session.running then !advance_ref ()
| "c" | "C" -> session := { !session with grid = make_grid (); gen = 0 }
| "r" | "R" -> (
match (try Some (!random_grid_ref 0.28) with _ -> None) with
| Some g -> session := { !session with grid = g; gen = 0 }
| None -> ())
| _ -> ());
refresh ()
let () = Game_lib.on_mouse handle_mouse
let () = Game_lib.on_key handle_key
let () = Game_lib.on_input handle_input
let () =
Game_lib.on_tick (fun () ->
!advance_ref ();
refresh ())
(* Repaints whenever some OTHER cell (population, count_live_neighbors, advance, ...) finishes running -- see src/game_host.ml's [repaint_all]. Without this, solving a problem only became visible on the board after the next click/keypress/tick, since [refresh] called from that OTHER cell's own code paints into that cell's own output, never into #game-panel. *)
let () = Game_lib.on_repaint refresh
let () = refresh ()
Background
Problem 1: population
Before anything else can happen, the board needs to know how many cells are alive right now. The number thus calculated will be displayed in the population counter on the game panel.
population : grid -> int returns how many cells on the whole board are alive
right now. The argument grid is the complete grid: a list of rows, each row
a list of cells. A recursive helper that pattern-matches on one row counts
that row; a second recursive helper combines the row counts across the whole
grid.
Hint: You are required to recurse on two levels: first over each row and then over each column. This being
the first problem, we have provided helpful stubs.
let population grid =
let rec count_row row =
failwith "not implemented"
in
let rec count_grid grid =
ignore count_row;
failwith "not implemented"
in
count_grid grid
(* This is piping for the game board. To be ignored. *)
let () = population_ref := population
let check b m = if not b then failwith m
let () =
check (population (make_grid ()) = 0) "empty grid has population 0";
check (population (List.init rows (fun _ -> List.init cols (fun _ -> true))) = rows * cols)
"fully alive grid has population rows*cols";
let g = set (set (set (make_grid ()) 0 0 true) 0 1 true) 5 5 true in
check (population g = 3) "hand-set 3-cell grid has population 3";
print_endline "all tests passed"
Cheat sheet: Problem 1
The let () = population_ref := population line is plumbing that registers your function with the game panel. Problem 1 and the three stretch problems each end with a line like this; Problems 2 and 3 don't need one, since next_generation calls them directly. Ignore the line wherever you see it.
Show reference solution
Reference solution:
let population grid =
let rec count_row row =
match row with
| [] -> 0
| true :: rest -> 1 + count_row rest
| false :: rest -> count_row rest
in
let rec count_grid grid =
match grid with
| [] -> 0
| row :: rest -> count_row row + count_grid rest
in
count_grid grid
count_row recurses down one row, adding 1 for every true cell it passes and skipping every false one. count_grid does the same thing one level up: it recurses down the list of rows, adding each row's count to the running total. Two small recursions instead of one big one.
Problem 2: count_live_neighbors
The next step is counting live cells around one particular cell. This is important for deciding which cells lives and dies in each generation.
count_live_neighbors : grid -> int -> int -> int returns the number of live
neighbors around one cell. Its arguments are the grid, row r, and column
c, in that order. Use wrap so a cell right on the edge of the board still
sees all eight neighbors.
Hint: neighbor_offsets gives you the eight (dr, dc) offsets to check. A recursive helper that walks that list, testing one offset at a time with get and wrap, works well.
let count_live_neighbors grid r c =
failwith "not implemented"
let check b m = if not b then failwith m
let () =
let g = set (set (set (make_grid ()) 5 4 true) 5 5 true) 5 6 true in
check (count_live_neighbors g 5 5 = 2) "blinker middle cell sees 2 live neighbors";
check (count_live_neighbors g 5 4 = 1) "blinker end cell sees 1 live neighbor";
let g2 = set (make_grid ()) 10 10 true in
check (count_live_neighbors g2 10 10 = 0)
"a live cell does not count itself as its own neighbor";
let g3 = set (set (make_grid ()) 23 23 true) 0 23 true in
check (count_live_neighbors g3 0 0 = 2)
"corner (0,0) sees neighbors that wrap off the opposite edges";
print_endline "all tests passed"
Cheat sheet: Problem 2
Show reference solution
Reference solution:
let count_live_neighbors grid r c =
let rec count_offsets offsets current_count =
match offsets with
| [] -> current_count
| (dr, dc) :: rest ->
let live = if get grid (wrap (r + dr) rows) (wrap (c + dc) cols) then 1 else 0 in
count_offsets rest (current_count + live)
in
count_offsets neighbor_offsets 0
count_offsets recurses down neighbor_offsets one (dr, dc) pair at a time, threading the running total through as current_count instead of combining it on the way back up. Each offset is wrapped onto the board with wrap and checked with get; a live neighbor adds 1, a dead one adds 0.
Problem 3: next_cell_state
With count_live_neighbors in hand, the last piece is turning that neighbor count into a decision: does this one cell live or die in the next generation?
next_cell_state : bool -> int -> bool decides whether one cell is alive in
the next generation. alive is its current state and live_neighbors is its
number of live neighbors; the returned boolean is its next state.
- a live cell with 2 or 3 live neighbors survives; anything else dies
- a dead cell with exactly 3 live neighbors is born
Hint: this is a direct transcription of the two rules above into a match on the pair (alive, live_neighbors).
let next_cell_state alive live_neighbors =
failwith "not implemented"
let check b m = if not b then failwith m
let () =
check (next_cell_state true 2 = true) "a live cell with 2 neighbors survives";
check (next_cell_state true 3 = true) "a live cell with 3 neighbors survives";
check (next_cell_state true 1 = false) "a live cell with 1 neighbor dies (underpopulation)";
check (next_cell_state true 4 = false) "a live cell with 4 neighbors dies (overpopulation)";
check (next_cell_state false 3 = true) "a dead cell with exactly 3 neighbors is born";
check (next_cell_state false 2 = false) "a dead cell with 2 neighbors stays dead";
print_endline "all tests passed"
Cheat sheet: Problem 3
Show reference solution
Reference solution:
let next_cell_state alive live_neighbors =
match (alive, live_neighbors) with
| true, (2 | 3) -> true
| false, 3 -> true
| _ -> false
This is a direct transcription of the two rules into pattern matches. The first two cases are survive-on-2-or-3 and born-on-exactly-3. The wildcard below them marks everything else dead.
Provided: next_generation
The next function is provided. It computes a new generation without changing the board it receives, demonstrating the immutability of lists. Open the block and run it before continuing.
Provided code
let next_generation g =
List.init rows (fun r ->
List.init cols (fun c -> next_cell_state (get g r c) (count_live_neighbors g r c)))
The function above creates the new board. The provided plumbing below connects it to the controls; open the block and run it too.
Provided: advancing a generation
Provided code
(* Like next_generation, but calls next_cell_state_general_ref, for custom rule presets. *)
let next_generation_general (birth, survive) g =
List.init rows (fun r ->
List.init cols (fun c ->
!next_cell_state_general_ref (birth, survive) (get g r c)
(count_live_neighbors g r c)))
let advance () =
let s = !session in
let next_grid =
match !custom_rule_ref with
| None -> (try Some (next_generation s.grid) with _ -> None)
| Some (_, rule) -> (try Some (next_generation_general rule s.grid) with _ -> None)
in
match next_grid with
| None -> () (* count_live_neighbors / next_cell_state not real yet *)
| Some g' ->
let died_out =
match population_opt g', population_opt s.grid with
| Some 0, Some p when p > 0 -> true
| _ -> false
in
let stalled = g' = s.grid in
session := { s with grid = g'; gen = s.gen + 1 };
if died_out then (
beep 160 260;
session := { !session with running = false };
sync_clock ())
else if stalled && s.running then (
(* A still life: nothing will ever change again, so stop rather than burn a tick every 200ms redrawing an identical board. *)
beep 330 120;
session := { !session with running = false };
sync_clock ())
let () = advance_ref := advance
After you have run the above cell, you will be able to click the Step button on the board to advance one generation at a time. You can also click Start to run the simulation continuously, and Stop to pause it. The Clear button resets the board to all dead cells.
Provided: try some classics
Before the stretch problems, try the four pattern buttons on the board. Glider is the simplest thing that moves: five cells that walk diagonally forever, reproducing their shape every four generations. Pulsar stays put, expanding and contracting on a three-generation cycle. Spaceship travels in a straight line, while Pentadecathlon stays put on a longer 15-generation cycle.
Stretch: random_grid
A board where each cell is alive with roughly probability p, somewhere from 0.0 to 1.0.
Hint: Random.float 1.0 < p flips a coin with probability p.
let random_grid p =
failwith "not implemented"
let () = random_grid_ref := random_grid
let check b m = if not b then failwith m
let () =
let g0 = random_grid 0.0 in
check (List.length g0 = rows) "the grid has `rows` rows";
check (List.for_all (fun row -> List.length row = cols) g0) "every row has `cols` cells";
check (population g0 = 0) "p = 0.0 leaves every cell dead";
check (population (random_grid 1.0) = rows * cols) "p = 1.0 makes every cell alive";
print_endline "all tests passed"
Cheat sheet: Stretch 1
Show reference solution
Reference solution:
let random_grid p =
let rec random_row row =
match row with
| [] -> []
| _ :: rest -> (Random.float 1.0 < p) :: random_row rest
in
let rec random_of grid =
match grid with
| [] -> []
| row :: rest -> random_row row :: random_of rest
in
random_of (make_grid ())
A list has no cell to mutate, so there's no board to fill in place — but there's already a board of the right shape sitting around: make_grid (), the same all-dead grid the session starts from. random_row and random_of recurse over that, the same two-level walk population's count_row/count_grid use, except each old cell is thrown away (_, row) and replaced with a freshly-flipped coin — Random.float 1.0 < p, a number picked uniformly between 0.0 and 1.0 that lands below p with probability exactly p.
Stretch: parse_rule
Conway's rules ("a live cell survives on 2 or 3 neighbors, a dead cell is born on exactly 3") are one example of a whole family of similar automata. Two numbers describe any of them: a Birth number, whose digits are the neighbor counts that bring a dead cell to life, and a Survive number, whose digits are the neighbor counts a live cell survives on. Conway is birth 3, survive 23: born on exactly 3 neighbors and surviving on 2 or 3. Change birth to 36 and you get "HighLife", a different automaton on the same grid that is famous for containing a small pattern that replicates itself. Standard Life has no known example of such a pattern. parse_rule turns those two numbers into the lists that next_cell_state_general will use, one int per digit: parse_rule 3 23 becomes ([3], [2; 3]).
Hint: This is not too difficult. You should try it if you have the time. HighLife and Maze are quite trippy and worth having a look at.
let parse_rule birth survive =
failwith "not implemented"
let () = parse_rule_ref := parse_rule
let check b m = if not b then failwith m
let () =
check (parse_rule 3 23 = ([3], [2; 3])) "parse_rule 3 23 = ([3], [2;3]) (standard Life)";
check (parse_rule 36 23 = ([3; 6], [2; 3])) "parse_rule 36 23 = ([3;6], [2;3]) (HighLife)";
check (parse_rule 2 0 = ([2], [])) "parse_rule 2 0 = ([2], []) (Seeds has no survival rule)";
print_endline "all tests passed"
Cheat sheet: Stretch 2
Show reference solution
Reference solution:
let parse_rule birth survive =
let digits_of n =
let rec loop n acc =
if n <= 0 then acc
else loop (n / 10) (n mod 10 :: acc)
in
loop n []
in
(digits_of birth, digits_of survive)
digits_of turns a number like 36 into the list [3; 6] by peeling digits off the low end with arithmetic: n mod 10 is the last digit, and n / 10 is everything before it. loop keeps doing that, consing each digit onto the front of acc. The accumulator ends up in the right order even though the digits are discovered least-significant first: 36 gives up 6, then 3, and consing 3 onto the front of [6] restores reading order. 0 (or a negative number) has no digits worth keeping, so it becomes [], which is exactly the empty survive rule Seeds needs.
Stretch: next_cell_state_general
This is the general version of Problem 3's next_cell_state. Instead of baking the rule numbers 2, 3 and 3 directly into the code, take the (birth, survive) lists produced by parse_rule and look up the neighbor count in the applicable list: survive if the cell is alive now, or birth if it is dead.
Hint: List.mem answers "is this number in that list?" directly, so no match is required.
let next_cell_state_general (birth, survive) alive live_neighbors =
failwith "not implemented"
let () = next_cell_state_general_ref := next_cell_state_general
let () = rule_feature_ready := true
let check b m = if not b then failwith m
let () =
let conway = parse_rule 3 23 in
List.iter
(fun alive ->
List.iter
(fun n ->
check
(next_cell_state_general conway alive n = next_cell_state alive n)
(Printf.sprintf "conway rule agrees with next_cell_state (alive=%b, neighbors=%d)" alive n))
[0; 1; 2; 3; 4; 5; 6; 7; 8])
[true; false];
let highlife = parse_rule 36 23 in
check (next_cell_state_general highlife false 6 = true) "HighLife: a dead cell with 6 neighbors is born";
check (next_cell_state_general conway false 6 = false) "standard Life: a dead cell with 6 neighbors stays dead";
print_endline "all tests passed"
Cheat sheet: Stretch 3
Show reference solution
Reference solution:
let next_cell_state_general (birth, survive) alive live_neighbors =
if alive then List.mem live_neighbors survive else List.mem live_neighbors birth
Everything Problem 3's match hardcoded as literal numbers is now data: survive and birth are just lists to search, and List.mem does the searching. Feed it parse_rule 3 23 and it behaves exactly like next_cell_state; feed it two different numbers and the whole simulation changes rule without a single line of code being edited.