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:
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)
+	}
+}