Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 39
Good morning! Here's your coding interview problem for today.

This problem was asked by Dropbox.

Conway's Game of Life takes place on an infinite two-dimensional board of square cells. Each cell is either dead or alive, and at each tick, the following rules apply:

Any live cell with less than two live neighbours dies.
Any live cell with two or three live neighbours remains living.
Any live cell with more than three live neighbours dies.
Any dead cell with exactly three live neighbours becomes a live cell.
A cell neighbours another cell if it is horizontally, vertically, or diagonally adjacent.

Implement Conway's Game of Life. It should be able to be initialized with a starting list of live cell coordinates and the number of steps it should run for. Once initialized, it should print out the board state at each step. Since it's an infinite board, print out only the relevant coordinates, i.e. from the top-leftmost live cell to bottom-rightmost live cell.

You can represent a live cell with an asterisk (*) and a dead cell with a dot (.).

Pull request:
Day39
Resolves #84 .

Patch:
diff --git a/README.md b/README.md
index e1c7e73..c6aca90 100644
--- a/README.md
+++ b/README.md
@@ -50,4 +50,5 @@ problems from
 * [Day 36](https://github.com/vaskoz/dailycodingproblem-go/issues/79)
 * [Day 37](https://github.com/vaskoz/dailycodingproblem-go/issues/81)
 * [Day 38](https://github.com/vaskoz/dailycodingproblem-go/issues/83)
+* [Day 39](https://github.com/vaskoz/dailycodingproblem-go/issues/84)
 * [Day 40](https://github.com/vaskoz/dailycodingproblem-go/issues/87)
diff --git a/day39/problem.go b/day39/problem.go
new file mode 100644
index 0000000..11e64f3
--- /dev/null
+++ b/day39/problem.go
@@ -0,0 +1,130 @@
+package day39
+
+import (
+	"math"
+	"strings"
+)
+
+// Coord represents a coordinate in the game of life.
+type Coord struct {
+	X, Y int64
+}
+
+// GameOfLife represents the game state.
+// '*' represents a live cell and '.' represents a dead cell.
+type GameOfLife struct {
+	living                 map[Coord]struct{}
+	minX, minY, maxX, maxY int64
+}
+
+// NewGameOfLife parses a starting board.
+// The given board's lower left coordinate with be 0,0
+func NewGameOfLife(board string) *GameOfLife {
+	gol := &GameOfLife{living: make(map[Coord]struct{})}
+	rows := strings.Split(board, "\n")
+	gol.maxY = int64(len(rows))
+	for y := 0; y < len(rows); y++ {
+		for x, val := range rows[len(rows)-1-y] {
+			if val == '*' {
+				gol.living[Coord{int64(x), int64(y)}] = struct{}{}
+				if int64(x) >= gol.maxX {
+					gol.maxX = int64(x) + 1
+				}
+			}
+		}
+	}
+	gol.minX, gol.minY = -1, -1
+	return gol
+}
+
+// String returns the string representation of the board now.
+func (gol *GameOfLife) String() string {
+	var sb strings.Builder
+	for y := gol.maxY - 1; y > gol.minY; y-- {
+		for x := gol.minX + 1; x < gol.maxX; x++ {
+			if _, alive := gol.living[Coord{x, y}]; alive {
+				sb.WriteRune('*')
+			} else {
+				sb.WriteRune('.')
+			}
+		}
+		sb.WriteRune('\n')
+	}
+	return sb.String()
+}
+
+// Step executes a single step of the simulation.
+func (gol *GameOfLife) Step() {
+	var birth, death []Coord
+	for coord := range gol.living {
+		if gol.willDie(coord) {
+			death = append(death, coord)
+		}
+		birth = append(birth, gol.willBeBorn(coord)...)
+	}
+	for _, d := range death {
+		delete(gol.living, d)
+	}
+	for _, b := range birth {
+		gol.living[b] = struct{}{}
+	}
+	gol.minX, gol.minY, gol.maxX, gol.maxY = math.MaxInt64, math.MaxInt64, math.MinInt64, math.MinInt64
+	for coord := range gol.living {
+		if coord.X <= gol.minX {
+			gol.minX = coord.X - 1
+		}
+		if coord.X >= gol.maxX {
+			gol.maxX = coord.X + 1
+		}
+		if coord.Y <= gol.minY {
+			gol.minY = coord.Y - 1
+		}
+		if coord.Y >= gol.maxY {
+			gol.maxY = coord.Y + 1
+		}
+	}
+}
+
+func (gol *GameOfLife) livingNeighbors(coord Coord) int {
+	var livingNeighbors int
+	for x := coord.X - 1; x <= coord.X+1; x++ {
+		for y := coord.Y - 1; y <= coord.Y+1; y++ {
+			if x == coord.X && y == coord.Y {
+				continue
+			}
+			if _, alive := gol.living[Coord{x, y}]; alive {
+				livingNeighbors++
+			}
+		}
+	}
+	return livingNeighbors
+}
+
+func (gol *GameOfLife) willBeBorn(coord Coord) []Coord {
+	var birth []Coord
+	checked := make(map[Coord]struct{})
+	for x := coord.X - 1; x <= coord.X+1; x++ {
+		for y := coord.Y - 1; y <= coord.Y+1; y++ {
+			if x == coord.X && y == coord.Y {
+				continue
+			}
+			coord := Coord{x, y}
+			if _, alive := gol.living[coord]; alive {
+				continue
+			}
+			if _, done := checked[coord]; !done {
+				checked[coord] = struct{}{}
+				living := gol.livingNeighbors(coord)
+				if living == 3 {
+					birth = append(birth, coord)
+				}
+			}
+		}
+	}
+	return birth
+}
+
+func (gol *GameOfLife) willDie(coord Coord) bool {
+	living := gol.livingNeighbors(coord)
+	return living < 2 || living > 3
+}


Test patch:
diff --git a/day39/problem_test.go b/day39/problem_test.go
new file mode 100644
index 0000000..8f05d17
--- /dev/null
+++ b/day39/problem_test.go
@@ -0,0 +1,40 @@
+package day39
+
+import "testing"
+
+var testcases = []struct {
+	board    string
+	steps    int
+	expected string
+}{
+	{"*\n*\n*", 1, "***\n"},
+	{"*\n*\n*", 2, "*\n*\n*\n"},
+	{"**\n**", 2, "**\n**\n"},
+	{"**\n*.", 1, "**\n**\n"},
+	{"..*\n.*.\n*..", 1, "*\n"},
+	{"**.\n*.*\n.*.", 2, "**.\n*.*\n.*.\n"},
+	{"**.\n*.*\n.*.", 20, "**.\n*.*\n.*.\n"},
+}
+
+func TestGameOfLife(t *testing.T) {
+	t.Parallel()
+	for n, tc := range testcases {
+		gol := NewGameOfLife(tc.board)
+		for i := 0; i < tc.steps; i++ {
+			gol.Step()
+		}
+		if result := gol.String(); result != tc.expected {
+			t.Errorf("TC%d Expected %v got %v", n, tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkGameOfLife(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			gol := NewGameOfLife(tc.board)
+			gol.Step()
+			_ = gol.String()
+		}
+	}
+}