Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 219
Good morning! Here's your coding interview problem for today.

This problem was asked by Salesforce.

Connect 4 is a game where opponents take turns dropping red or black discs into a 7 x 6 vertically suspended grid. The game ends either when one player creates a line of four consecutive discs of their color (horizontally, vertically, or diagonally), or when there are no more spots left in the grid.

Design and implement Connect 4.

Pull request description:
Day219
Resolves #452.

Patch:
diff --git a/day219/problem.go b/day219/problem.go
new file mode 100644
index 0000000..f028acb
--- /dev/null
+++ b/day219/problem.go
@@ -0,0 +1,102 @@
+package day219
+
+import "fmt"
+
+// Possible winning positions.
+// Vertical: 7 columns * 3 positions per column = 21 vertical winning positions.
+// Horizontal: 6 rows * 4 positions per column = 24 horizontal winning positions.
+// DiagUp: 12
+// DiagDown: 12
+// Total == 69 winning positions checking 4 positions == 276 checks
+
+// Player represents a ConnectFour player or none.
+type Player int
+
+const (
+	// None is neither player.
+	None Player = iota
+	// Red is a position owned by the 'red' player.
+	Red
+	// Black is a position owned by the 'black' player.
+	Black
+)
+
+// Column is zero-based from left to right.
+type Column int
+
+// Row is zero-based from bottom to top.
+type Row int
+
+// ConnectFourBoard represents a column-major board since
+// moves are played by column.
+// 7 vertical columns and 6 horizontal rows.
+type ConnectFourBoard struct {
+	board map[Column]map[Row]Player
+}
+
+// Move is a piece played by a player.
+// Player must be either 'Red' or 'Black' to play a valid move.
+func (cfb *ConnectFourBoard) Move(player Player, col Column) error {
+	if player != Red && player != Black {
+		return fmt.Errorf("must play either Red or Black, you tried %v", player)
+	}
+	if cfb.board == nil {
+		cfb.board = make(map[Column]map[Row]Player)
+	}
+	valid := false
+	for row := Row(0); row < 6; row++ {
+		if cfb.board[col] == nil {
+			cfb.board[col] = make(map[Row]Player)
+		}
+		if _, found := cfb.board[col][row]; !found {
+			cfb.board[col][row] = player
+			valid = true
+			break
+		}
+	}
+	if !valid {
+		return fmt.Errorf("column full. can't play in this column")
+	}
+	return nil
+}
+
+// Winner returns the winner of the current board.
+// If there is no winner yet, then Player=None is returned.
+func (cfb *ConnectFourBoard) Winner() Player {
+	height := Row(6)
+	width := Column(7)
+	for row := Row(0); row < height; row++ {
+		for col := Column(0); col < width; col++ {
+			player := cfb.board[col][row]
+			if player == None {
+				continue
+			}
+			if col+3 < width &&
+				player == cfb.board[col+1][row] &&
+				player == cfb.board[col+2][row] &&
+				player == cfb.board[col+3][row] {
+				return player
+			}
+			if row+3 < height {
+				if player == cfb.board[col][row+1] &&
+					player == cfb.board[col][row+2] &&
+					player == cfb.board[col][row+3] {
+					return player
+				}
+				if col+3 < width &&
+					player == cfb.board[col+1][row+1] &&
+					player == cfb.board[col+2][row+2] &&
+					player == cfb.board[col+3][row+3] {
+					return player
+				}
+				if col-3 >= 0 &&
+					player == cfb.board[col-1][row+1] &&
+					player == cfb.board[col-2][row+2] &&
+					player == cfb.board[col-3][row+3] {
+					return player
+				}
+			}
+		}
+	}
+	return None
+}


Test patch:
diff --git a/day219/problem_test.go b/day219/problem_test.go
new file mode 100644
index 0000000..7be5ea6
--- /dev/null
+++ b/day219/problem_test.go
@@ -0,0 +1,179 @@
+package day219
+
+import (
+	"testing"
+)
+
+func TestConnectFourVerticalAlternate(t *testing.T) {
+	t.Parallel()
+	var cfb ConnectFourBoard
+	for i := 0; i < 3; i++ {
+		if err := cfb.Move(Red, 0); err != nil {
+			t.Errorf("expected nil got %v", err)
+		}
+		if p := cfb.Winner(); p != None {
+			t.Errorf("expected no winner got %v", p)
+		}
+		if err := cfb.Move(Black, 0); err != nil {
+			t.Errorf("expected nil, got %v", err)
+		}
+		if p := cfb.Winner(); p != None {
+			t.Errorf("expected no winner got %v", p)
+		}
+	}
+	if err := cfb.Move(Red, 0); err == nil {
+		t.Errorf("expected an error inserting into a full column")
+	}
+	if err := cfb.Move(None, 1); err == nil {
+		t.Errorf("expected an error trying to insert non-red non-black")
+	}
+	if err := cfb.Move(Black+Red, 1); err == nil {
+		t.Errorf("expected an error trying to insert non-red non-black")
+	}
+}
+
+func TestConnectFourVerticalRedWins(t *testing.T) {
+	t.Parallel()
+	var cfb ConnectFourBoard
+	for i := 0; i < 3; i++ {
+		if err := cfb.Move(Red, 0); err != nil {
+			t.Errorf("expected nil got %v", err)
+		}
+		if p := cfb.Winner(); p != None {
+			t.Errorf("expected no winner got %v", p)
+		}
+		if err := cfb.Move(Black, 1); err != nil {
+			t.Errorf("expected nil, got %v", err)
+		}
+		if p := cfb.Winner(); p != None {
+			t.Errorf("expected no winner got %v", p)
+		}
+	}
+	if err := cfb.Move(Red, 0); err != nil {
+		t.Errorf("expected nil, got %v", err)
+	}
+	if p := cfb.Winner(); p != Red {
+		t.Errorf("expected Red winner got %v", p)
+	}
+}
+
+func TestConnectFourHorizontalBlackWins(t *testing.T) {
+	t.Parallel()
+	var cfb ConnectFourBoard
+	for i := Column(0); i < 3; i++ {
+		if err := cfb.Move(Black, i); err != nil {
+			t.Errorf("expected nil got %v", err)
+		}
+		if p := cfb.Winner(); p != None {
+			t.Errorf("expected no winner got %v", p)
+		}
+		if err := cfb.Move(Red, i); err != nil {
+			t.Errorf("expected nil, got %v", err)
+		}
+		if p := cfb.Winner(); p != None {
+			t.Errorf("expected no winner got %v", p)
+		}
+	}
+	if err := cfb.Move(Black, 3); err != nil {
+		t.Errorf("expected nil, got %v", err)
+	}
+	if p := cfb.Winner(); p != Black {
+		t.Errorf("expected Black winner got %v", p)
+	}
+}
+
+func TestConnectFourDiagonalDownRightRedWins(t *testing.T) {
+	t.Parallel()
+	var cfb ConnectFourBoard
+	for i := 0; i < 3; i++ {
+		if err := cfb.Move(Black, Column(0)); err != nil {
+			t.Errorf("expected nil got %v", err)
+		}
+		if p := cfb.Winner(); p != None {
+			t.Errorf("expected no winner got %v", p)
+		}
+		if err := cfb.Move(Red, Column(0)); err != nil {
+			t.Errorf("expected nil, got %v", err)
+		}
+		if p := cfb.Winner(); p != None {
+			t.Errorf("expected no winner got %v", p)
+		}
+
+	}
+	for i := 0; i < 3; i++ {
+		if err := cfb.Move(Red, Column(1)); err != nil {
+			t.Errorf("expected nil got %v", err)
+		}
+		if p := cfb.Winner(); p != None {
+			t.Errorf("expected no winner got %v", p)
+		}
+		if err := cfb.Move(Black, Column(1)); err != nil {
+			t.Errorf("expected nil, got %v", err)
+		}
+		if p := cfb.Winner(); p != None {
+			t.Errorf("expected no winner got %v", p)
+		}
+	}
+	for i := 0; i < 3; i++ {
+		if err := cfb.Move(Black, Column(2)); err != nil {
+			t.Errorf("expected nil got %v", err)
+		}
+		if p := cfb.Winner(); p != None {
+			t.Errorf("expected no winner got %v", p)
+		}
+		if err := cfb.Move(Red, Column(2)); err != nil {
+			t.Errorf("expected nil, got %v", err)
+		}
+		if p := cfb.Winner(); p != None {
+			t.Errorf("expected no winner got %v", p)
+		}
+	}
+	if err := cfb.Move(Red, 3); err != nil {
+		t.Errorf("expected nil got %v", err)
+	}
+	if p := cfb.Winner(); p != Red {
+		t.Errorf("expected Red winner got %v", p)
+	}
+}
+
+func TestConnectFourDiagonalUpRightRedWins(t *testing.T) {
+	t.Parallel()
+	var cfb ConnectFourBoard
+	if err := cfb.Move(Red, Column(0)); err != nil {
+		t.Errorf("expected nil got %v", err)
+	}
+	if err := cfb.Move(Black, Column(1)); err != nil {
+		t.Errorf("expected nil got %v", err)
+	}
+	if err := cfb.Move(Red, Column(1)); err != nil {
+		t.Errorf("expected nil got %v", err)
+	}
+	for i := 0; i < 2; i++ {
+		if err := cfb.Move(Black, Column(2)); err != nil {
+			t.Errorf("expected nil got %v", err)
+		}
+		if p := cfb.Winner(); p != None {
+			t.Errorf("expected no winner got %v", p)
+		}
+	}
+	if err := cfb.Move(Red, Column(2)); err != nil {
+		t.Errorf("expected nil got %v", err)
+	}
+	if p := cfb.Winner(); p != None {
+		t.Errorf("expected no winner got %v", p)
+	}
+	for i := 0; i < 3; i++ {
+		if err := cfb.Move(Black, Column(3)); err != nil {
+			t.Errorf("expected nil got %v", err)
+		}
+		if p := cfb.Winner(); p != None {
+			t.Errorf("expected no winner got %v", p)
+		}
+	}
+	if err := cfb.Move(Red, Column(3)); err != nil {
+		t.Errorf("expected nil got %v", err)
+	}
+	if p := cfb.Winner(); p != Red {
+		t.Errorf("expected Red winner got %v", p)
+	}
+}