.gitignore

*.pyc
*.un~

go.c

/* Go is a 2 player board game with simple rules. Two players alternate turns
 * placing stones on a grid. If a stone is surrounded on 4 sides by stones of
 * the opponent, it is captured. If a group of stones are surrounded, they are
 * captured.
 * See http://en.wikipedia.org/wiki/Rules_of_Go#Capture for a visual explanation.
 * 
 * Below is an implementation of a Go board. Please write some code in the
 * move() function to check for captures and output something when a capture
 * occurs. The sample moves represent a capture of two black stones.
 */

#include <stdio.h>
#include <string.h>

#define BOARD_SIZE 19

typedef unsigned char board_t[BOARD_SIZE][BOARD_SIZE];

enum {
    EMPTY = 0x1,
    BLACK = 0x2,
    WHITE = 0x4,
};

int move(board_t board, int color, size_t row, size_t col) {
    board[row][col] = color;
    return 0;
}

void print_board(board_t board) {
    for (size_t r = 0; r < BOARD_SIZE; r++) {
        for (size_t c = 0; c < BOARD_SIZE; c++) {
            if (board[r][c] == EMPTY)
                putchar('_');
            else
                printf("%d", board[r][c]);
        }
        putchar('\n');
    }
}

int main() {
    board_t board;
    memset(board, EMPTY, sizeof(unsigned char) * BOARD_SIZE * BOARD_SIZE);
    move(board, BLACK, 4, 4);
    move(board, BLACK, 4, 5);
    move(board, WHITE, 3, 4);
    move(board, WHITE, 3, 5);
    move(board, WHITE, 4, 3);
    move(board, WHITE, 4, 6);
    move(board, WHITE, 5, 4);
    move(board, WHITE, 5, 5);
    print_board(board);
    return 0;
}

go.py

#!/usr/bin/env python

# Go is a 2 player board game with simple rules. Two players alternate turns
# placing stones on a grid. If a stone is surrounded on 4 sides by stones of
# the opponent, it is captured. If a group of stones are surrounded, they are
# captured.
# See http://en.wikipedia.org/wiki/Rules_of_Go#Capture for a visual explanation.

# Below is an implementation of a Go board. Please write some code in the
# move() method to check for captures and output something when a capture
# occurs. The sample moves represent a capture of two black stones.

EMPTY = 0
BLACK = 1
WHITE = 2

class Board(object):
    def __init__(self):
        self.board = [[EMPTY] * 19 for _ in xrange(19)] # 2d 19x19 matrix of 0's

    def __str__(self):
        s = ''
        for row in self.board:
            if s:
                s += '\n'
            for sq in row:
                if sq:
                    s += str(sq)
                else:
                    s += '_'
        return s

    def flipIfSurrounded(self, baseColor, coords):
        for testPoint in coords:
            for p in [(-1,0),(1,0),(0,-1),(0,1)]:
                otherPoint = (testPoint[0]+p[0], testPoint[1]+p[1])
                otherColor = self.board[otherPoint[0]][otherPoint[1]]
                if not otherColor:
                    # Leak; stop now
                    return
                if otherColor == baseColor and not otherPoint in coords:
                    coords.append(otherPoint)

        # Coords that are left should be flipped
        otherColor = WHITE if baseColor == BLACK else BLACK
        for flipPoint in coords:
            self.board[flipPoint[0]][flipPoint[1]] = otherColor


    def move(self, color, row, col):
        self.board[row][col] = color
        otherColor = BLACK if color == WHITE else WHITE
        for p in [(-1,0),(1,0),(0,-1),(0,1)]:
            otherPoint = (row+p[0], col+p[1])
            otherColor = self.board[otherPoint[0]][otherPoint[1]]
            if otherColor and otherColor != self.board[row][col]:
                self.flipIfSurrounded(otherColor, [otherPoint])

if __name__ == "__main__":
    b = Board()
    b.move(BLACK, 4, 4)
    b.move(BLACK, 4, 5)
    b.move(WHITE, 3, 4)
    b.move(WHITE, 3, 5)
    b.move(WHITE, 4, 3)
    b.move(WHITE, 4, 6)
    b.move(WHITE, 5, 4)
    b.move(WHITE, 5, 5)
    print b

Makefile

go: go.c
	gcc -o go -O go.c -Wall -Wextra -std=c11 -ggdb

test.py

import sys
import unittest
from go import *

class TestGo(unittest.TestCase):

    def setUp(self):
        self.b = Board()

    def test_single_capture(self):
        self.b.move(BLACK, 3, 4)
        self.b.move(WHITE, 3, 3)
        self.b.move(WHITE, 3, 5)
        self.b.move(WHITE, 2, 4)
        self.b.move(WHITE, 4, 4)
        self.assertEqual(self.b.board[3][4], WHITE)

    def test_double_capture(self):
        self.b.move(BLACK, 3, 3)
        self.b.move(BLACK, 3, 4)
        self.b.move(WHITE, 3, 2)
        self.b.move(WHITE, 3, 5)
        self.b.move(WHITE, 2, 3)
        self.b.move(WHITE, 2, 4)
        self.b.move(WHITE, 4, 3)
        self.b.move(WHITE, 4, 4)
        self.assertEqual(self.b.board[3][4], WHITE)
        self.assertEqual(self.b.board[3][3], WHITE)

    def test_double_region_capture(self):
        self.b.move(BLACK, 3, 3)
        self.b.move(BLACK, 3, 4)
        self.b.move(BLACK, 3, 6)
        self.b.move(BLACK, 3, 7)
        self.b.move(WHITE, 3, 2)
        self.b.move(WHITE, 3, 8)
        self.b.move(WHITE, 2, 3)
        self.b.move(WHITE, 2, 4)
        self.b.move(WHITE, 2, 6)
        self.b.move(WHITE, 2, 7)
        self.b.move(WHITE, 4, 3)
        self.b.move(WHITE, 4, 4)
        self.b.move(WHITE, 4, 6)
        self.b.move(WHITE, 4, 7)
        self.b.move(WHITE, 3, 5)
        self.assertEqual(self.b.board[3][4], WHITE)
        self.assertEqual(self.b.board[3][3], WHITE)
        self.assertEqual(self.b.board[3][6], WHITE)
        self.assertEqual(self.b.board[3][7], WHITE)

if __name__ == "__main__":
    unittest.main()