Practice: Conway's Game of Life
Conway's Game of Life is a grid of cells, each alive or
dead, and 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 gliders, shapes that
crawl steadily across the board without ever stopping.
The board in the sidebar shows up as soon as you press Run on
anything, even the very first cell below, before you've solved a single
problem. The simulation
itself calls your versions of population,
count_live_neighbors, next_cell_state, and
random_grid. At first population can't count
anything, so Start and Step just sit there doing nothing. Write and Run
one of these functions, and the board picks it up on your next click.
A reference solution sits collapsed under each problem if you get
stuck. Give it a real attempt first, then open it.
(* PROVIDED. From life_reference_solution.ml's PROVIDED header. *)
let rows = 24 (* number of rows on the board *)
let cols = 24 (* number of columns on the board *)
type grid = bool array array (* alive/dead for every cell *)
let make_grid () : grid = Array.make_matrix rows cols false (* a fresh, all-dead board *)
let copy_grid (g : grid) : grid = Array.map Array.copy g (* copies every row, not just the outer array *)
(* keeps a coordinate on the board by wrapping it around the edge *)
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) ]
Show provided code: board setup, drawing, session state
(* PROVIDED, continued -- drawing, session state, patterns, and the
board's event wiring. Uses rows/cols/grid/make_grid/copy_grid/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 : grid) =
"<table class=\"life\">"
^ String.concat ""
(List.init rows (fun r ->
"<tr>"
^ String.concat ""
(List.init cols (fun c -> cell_html r c 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 *)
death_input : string; (* current text of the Death box *)
}
let speeds = [ ("slow", 500); ("medium", 200); ("fast", 80) ]
let new_session () =
{ grid = make_grid (); running = false; speed = 200; gen = 0;
birth_input = "3"; death_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. Every
call below goes through `!xxx_ref`, so it always reads whatever is
CURRENTLY assigned -- no re-run of this cell is ever needed to pick
up a later solve. 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). custom_rule_ref is None for the
standard rule (the hardcoded next_cell_state Problem 3 already
wrote); Some (label, (birth, survive)) once a rule preset button
has been pressed. rule_feature_ready gates whether those preset
buttons even appear in controls -- see next_cell_state_general's
registration line, which is the only place it is set true. *)
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 (see the setup cell comment on parse_rule_ref, and
Game_lib.on_input's own comment for why it's commit-on-blur rather
than live per keystroke). *)
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 : session) =
"<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:acorn" "Acorn" 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 "death-input" "Death" s.death_input
^ "</div>")
(* A tone only when something worth hearing happened. A beep per generation
at 80ms intervals is not feedback, it is a fire alarm. *)
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: a glider that walks forever, a pulsar that breathes on
a 3-generation clock, a spaceship that crosses the whole board, and
an acorn that explodes into 60+ live cells of chaos before settling
down. [pattern_of_lines] just stamps an ASCII sketch ('#' alive,
anything else dead) onto a blank board at a given top-left corner,
wrapping the same way the board always does -- verified against a
standalone simulator before writing these coordinates in (a glider or
spaceship that isn't EXACTLY right just quietly stops looking like
one after a few generations).
No Gosper glider gun here on purpose: the classic "fires a glider
forever" gun needs on the order of 36 open columns ahead of it before
the first glider it fires would wrap around and collide with the gun
itself. This board is 24 wide -- a gun would eat itself within a few
dozen generations rather than actually running forever, which is the
entire point of a gun, so it's left out rather than included broken. *)
let pattern_of_lines (lines : string list) ~r0 ~c0 : grid =
let g = make_grid () in
List.iteri
(fun dr line ->
String.iteri
(fun dc ch ->
if ch = '#' then g.(wrap (r0 + dr) rows).(wrap (c0 + dc) cols) <- true)
line)
lines;
g
let glider_pattern = [ ".#."; "..#"; "###" ]
let pulsar_pattern =
[
"..###...###..";
".............";
"#....#.#....#";
"#....#.#....#";
"#....#.#....#";
"..###...###..";
".............";
"..###...###..";
"#....#.#....#";
"#....#.#....#";
"#....#.#....#";
".............";
"..###...###..";
]
let spaceship_pattern = [ ".####"; "#...#"; "....#"; "#..#." ]
let acorn_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)
| "acorn" -> Some (pattern_of_lines acorn_pattern ~r0:10 ~c0:8)
| _ -> 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.
See the immutability note under "Provided: next_generation" -- these
follow the same copy-first discipline. *)
let set_cell (g : grid) (r : int) (c : int) (alive : bool) : grid =
let g' = copy_grid g in
g'.(r).(c) <- alive;
g'
let toggle_cell (g : grid) (r : int) (c : int) : grid =
set_cell g r c (not 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)
(* Drag PAINTS rather than toggles. Toggling on drag would flip every cell
the pointer crossed twice on a doubled-back stroke, and a stroke that
re-enters a square it already covered would erase it -- drawing a glider
would be a fight. Left paints alive, right erases; a plain click still
toggles, which is what you want for correcting one cell. *)
let handle_mouse (m : Game_lib.mouse) =
let s = !session in
match m.pos with
(* Clicking into the Birth/Death boxes just moves focus there --
repainting the panel on this click (the way every other click
does) would replace the very input the click just focused,
throwing focus right back out before a single digit is typed. *)
| "birth-input" | "death-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/Death 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 death =
session := { s with birth_input = string_of_int birth; death_input = string_of_int death };
match (try Some (!parse_rule_ref birth death) 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"; death_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 ()
(* A Birth/Death box committing a new value (see Game_lib.on_input) --
fires once the student tabs or clicks away, never mid-keystroke.
[valid_rule_number] is the "small filter for bad inputs": only
plain digits are ever handed to parse_rule, so a stray letter or a
blank field just leaves the current rule alone instead of
crashing the board. *)
let valid_rule_number (s : string) : bool =
s <> "" && String.for_all (fun ch -> ch >= '0' && ch <= '9') s
let apply_birth_death birth_str death_str =
if valid_rule_number birth_str && valid_rule_number death_str then
match
(try Some (!parse_rule_ref (int_of_string birth_str) (int_of_string death_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_death value s.death_input
| "death-input" ->
session := { s with death_input = value };
apply_birth_death 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 (Html output is tagged with whichever cell it
was compiled under). *)
let () = Game_lib.on_repaint refresh
let () = refresh ()
Background
The board is a grid: a 24×24 array of arrays of bool,
one entry per cell, true meaning alive. make_grid and
copy_grid, defined near the top of the page, build and duplicate
one; both are plumbing you'll rarely need to read closely. Two names
defined right alongside them matter more for the problems below.
wrap keeps a row or column coordinate in range by wrapping it
around the edge, so the board has no border and a glider that walks off
one side reenters the other. neighbor_offsets holds the eight
(row, column) offsets around a cell.
Problem 1: population
How many cells on the whole board are alive right now? Population
matters later for noticing when the colony has died out.
Implement this however you like. The same goes for every problem
below. Open the reference solution afterward even when your own version
already works. The goal here is a feel for idiomatic OCaml.
let population (g : grid) : int =
failwith "not implemented"
(* PROVIDED -- this line hooks your function into the board by setting
the setup cell's population_ref. The board then repaints on its own,
since finishing this cell triggers the setup cell's on_repaint. *)
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 (Array.make_matrix rows cols true) = rows * cols)
"fully alive grid has population rows*cols";
let g = make_grid () in
g.(0).(0) <- true;
g.(0).(1) <- true;
g.(5).(5) <- true;
check (population g = 3) "hand-set 3-cell grid has population 3";
print_endline "all tests passed"
Show reference solution
Reference solution:
let population (g : grid) : int =
let count_row (row : bool array) : int =
Array.fold_left (fun total alive -> if alive then total + 1 else total) 0 row
in
Array.fold_left (fun total row -> total + count_row row) 0 g
This uses two Array.fold_left calls. One counts the live
cells in a single row. The other adds up those row counts across the
whole grid.
Problem 2: count_live_neighbors
How many of the cell at (r, c)'s eight neighbors are alive?
Use wrap so a cell right on the edge of the board still sees
all eight.
let count_live_neighbors (g : grid) (r : int) (c : int) : int =
failwith "not implemented"
let check b m = if not b then failwith m
let () =
let g = make_grid () in
g.(5).(4) <- true;
g.(5).(5) <- true;
g.(5).(6) <- true;
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 = make_grid () in
g2.(10).(10) <- true;
check (count_live_neighbors g2 10 10 = 0)
"a live cell does not count itself as its own neighbor";
let g3 = make_grid () in
g3.(23).(23) <- true;
g3.(0).(23) <- true;
check (count_live_neighbors g3 0 0 = 2)
"corner (0,0) sees neighbors that wrap off the opposite edges";
print_endline "all tests passed"
Show reference solution
Reference solution:
let count_live_neighbors (g : grid) (r : int) (c : int) : int =
let neighbor_is_alive (dr, dc) =
g.(wrap (r + dr) rows).(wrap (c + dc) cols)
in
let alive_neighbors =
List.filter (fun offset -> neighbor_is_alive offset) neighbor_offsets
in
List.length alive_neighbors
neighbor_is_alive tests one offset against the board.
List.filter keeps the offsets that pass that test, and
List.length counts how many are left.
Problem 3: next_cell_state
Given whether a cell is alive right now and how many live neighbors
it has, is it alive next generation?
- a live cell with 2 or 3 live neighbors survives; anything else dies
- a dead cell with exactly 3 live neighbors is born
let next_cell_state (alive : bool) (live_neighbors : int) : bool =
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"
Show reference solution
Reference solution:
let next_cell_state (alive : bool) (live_neighbors : int) : bool =
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
Every function before this one only reads the board, through
population and count_live_neighbors, or looks at
two plain numbers in next_cell_state. next_generation
introduces the idea this whole exercise turns on: immutability. It
reads a board and returns a brand new board, and the board it was given
stays untouched. Every cell's neighbor count in one generation has to come
from that same starting board. Update cells in place instead, and a cell
already flipped gets counted as a neighbor's state when a later cell asks
about it, so the count depends on the order you happened to visit cells
in. Gliders smear sideways across the board when this happens. Returning
a fresh board each time removes the ordering problem entirely: every
neighbor count gets decided against a board nothing has touched yet.
set_cell and toggle_cell, just below, follow the
same discipline.
Show provided code: next_generation
let next_generation (g : grid) : grid =
Array.init rows (fun r ->
Array.init cols (fun c -> next_cell_state g.(r).(c) (count_live_neighbors g r c)))
Provided: advancing a generation
advance is what Step, the Start/Stop clock, and the Enter
key all call. It runs one full generation using next_generation
above, plus some bookkeeping outside the game logic itself. A died-out
colony or a stalled, unchanging board stops the clock and plays a distinct
tone, instead of ticking forever on a board that will never move again.
Nothing here is a problem to solve.
Show provided code: advance
(* Composes with count_live_neighbors (Problem 2, above) the same
way next_generation composes with next_cell_state -- used only
once a rule preset button is pressed (see the setup cell's
custom_rule_ref), which needs the general STUDENT rule function
from further down the page instead of the hardcoded
next_cell_state this cell already has. *)
let next_generation_general (birth, survive) (g : grid) : grid =
Array.init rows (fun r ->
Array.init cols (fun c ->
!next_cell_state_general_ref (birth, survive) 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
Provided: try some classics
Before the stretch problems, worth a minute just to look: four buttons
have appeared in the sidebar's third row, each dropping a famous Life
pattern onto the board. Glider is the simplest thing that
moves -- five cells that walk diagonally forever, reproducing their own
shape every 4 generations (that's also why next_cell_state
being right matters: get one rule wrong and a glider smears sideways
instead of walking cleanly). Pulsar doesn't move at all --
it's 48 cells that expand, contract, and return to exactly their starting
shape every 3 generations, forever. Spaceship (a
"lightweight spaceship") is a glider's bigger, faster cousin, crossing the
board in a straight line instead of diagonally. Acorn
looks like nothing -- seven cells -- and then doesn't stop: it churns for
well over fifty generations, briefly holding more than 70 live cells, before
settling into a small quiet cluster of oscillators and still lifes.
Stretch: random_grid
A board where each cell is alive with roughly probability p,
somewhere from 0.0 to 1.0.
let random_grid (p : float) : grid =
failwith "not implemented"
(* PROVIDED -- registers your function with the board (see the setup
cell's random_grid_ref) so Random and the r/R key pick it up on the
very next press. *)
let () = random_grid_ref := random_grid
Show reference solution
Reference solution:
let random_grid (p : float) : grid =
let g = make_grid () in
for r = 0 to rows - 1 do
for c = 0 to cols - 1 do
g.(r).(c) <- Random.float 1.0 < p
done
done;
g
This one mutates, unlike the other problems. g gets built
once with make_grid, then filled in place. Nothing reads the
board mid-construction, so there's no reason to keep this one pure.
Stretch: parse_rule
Conway's rules ("a live cell survives on 2 or 3 neighbors, a dead
cell is born on exactly 3") are really just 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 Death number,
whose digits are the neighbor counts a live cell survives on.
Conway is birth 3, death 23 -- born on
exactly 3 neighbors, survives on 2 or 3. Change one digit -- birth
36 instead of 3 -- and you get "HighLife",
a different automaton on the exact same grid, famous for containing
a small pattern that replicates itself, something standard
Life has no known example of. parse_rule turns those
two numbers into the two lists next_cell_state_general
(next problem) will actually use, one int per digit:
parse_rule 3 23 becomes ([3], [2; 3]).
let parse_rule (birth : int) (death : int) : int list * int list =
failwith "not implemented"
(* PROVIDED -- registers your function with the board (see the setup
cell's parse_rule_ref); the rule preset buttons and the Birth/Death
text boxes in the sidebar call through this the moment you press or
edit one, no re-run needed. *)
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"
Show reference solution
Reference solution:
let parse_rule (birth : int) (death : int) : int list * int list =
let digits_of (n : int) : int list =
if n <= 0 then []
else
let s = string_of_int n in
List.init (String.length s) (fun i -> Char.code s.[i] - Char.code '0')
in
(digits_of birth, digits_of death)
digits_of turns a number like 36 into the
list [3; 6] one character at a time, converting each
digit character to its number with
Char.code s.[i] - Char.code '0' (the same trick behind
every char-to-int conversion: digit
characters are consecutive in ASCII, so subtracting '0''s
code gives the digit's value). 0 (or a negative number)
has no digits worth keeping, so it becomes [] --
exactly the empty survive rule Seeds needs.
Stretch: next_cell_state_general
The general version of Problem 3's next_cell_state: instead
of the rule numbers 2, 3 and 3 baked directly into the code, take the
(birth, survive) lists parse_rule just produced
and look the neighbor count up in whichever one applies --
survive if the cell is alive now, birth if it's
dead. List.mem answers "is this number in that list?"
directly, so there's no need for a match at all. Once this compiles,
four new buttons appear in the sidebar (Conway / HighLife / Seeds /
Maze) -- pressing one swaps which rule advance steps
with, live, on whatever's already on the board, and fills in the
Birth and Death boxes next to them with the two numbers that rule
is made of. Those boxes are editable too: type your own numbers in
and tab or click away, and the board adopts your rule immediately
-- change a single digit and watch the whole simulation's character
change.
let next_cell_state_general ((birth, survive) : int list * int list)
(alive : bool) (live_neighbors : int) : bool =
failwith "not implemented"
(* PROVIDED -- registers your function with the board (see the setup
cell's next_cell_state_general_ref) and turns on the rule preset
buttons (rule_feature_ready) -- both take effect on the very next
repaint, no re-run of anything else needed. *)
let () = next_cell_state_general_ref := next_cell_state_general
let () = rule_feature_ready := true
Show reference solution
Reference solution:
let next_cell_state_general ((birth, survive) : int list * int list)
(alive : bool) (live_neighbors : int) : bool =
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.