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,
    MAYBE = 0x8,
};

typedef struct {
    int drow;
    int dcol;
} direction_t;

direction_t DIRECTIONS[] = { {0, -1}, {-1, 0}, {1, 0}, {0, 1} };

int is_bounded(int row, int col) {
    return row >= 0 && row < BOARD_SIZE && col >= 0 && col < BOARD_SIZE;
}

int maybe_capture(board_t board, int color, int row, int col) {
    if (! is_bounded(row, col)) return 1;
    if (board[row][col] == EMPTY) return 0;
    if (board[row][col] != color) return 1;
    board[row][col] = MAYBE;
    for (unsigned long i = 0; i < sizeof(DIRECTIONS); ++i) {
	if (! maybe_capture(board, color, row + DIRECTIONS[i].drow, col + DIRECTIONS[i].dcol))
	    return 0;
    }
    return 1;
}

void replace_maybe(board_t board, int color, int row, int col) {
    if (! is_bounded(row, col)) return;
    if (board[row][col] == MAYBE) {
	board[row][col] = color;
	for (unsigned long i = 0; i < sizeof(DIRECTIONS); ++i) {
	    replace_maybe(board, color, row + DIRECTIONS[i].drow, col + DIRECTIONS[i].dcol);
	}
    }
}

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 move(board_t board, int color, size_t row, size_t col) {
    board[row][col] = color;
    for (unsigned long i = 0; i < sizeof(DIRECTIONS); ++i) {
	direction_t dir = DIRECTIONS[i];
	int next_row = dir.drow + row;
	int next_col = dir.dcol + col;
	int opponent_color = color == WHITE ? BLACK : WHITE;
	if (is_bounded(next_row, next_col) && board[next_row][next_col] == opponent_color && maybe_capture(board, opponent_color, next_row, next_col)) {
	    replace_maybe(board, EMPTY, next_row, next_col);
	    print_board(board);
	    printf("\n");
	} else {
	    replace_maybe(board, opponent_color, next_row, next_col);
	}
    }
    return 0;
}

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, BLACK, 4, 6);
    move(board, WHITE, 3, 4);
    move(board, WHITE, 3, 5);
    move(board, WHITE, 3, 6);
    move(board, WHITE, 4, 3);
    move(board, WHITE, 4, 7);
    move(board, WHITE, 5, 4);
    move(board, WHITE, 5, 5);
    move(board, WHITE, 5, 6);

    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
MAYBE = 3

BOARD_SIZE = 19

class Board(object):
    def __init__(self):
        self.board = [[EMPTY] * BOARD_SIZE for _ in xrange(BOARD_SIZE)] # 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 is_bounded(self, row, col):
        return 0 <= row < BOARD_SIZE and 0 <= col < BOARD_SIZE

    def dirs(self, row, col):
        return [(row+1, col),
                (row-1, col),
                (row,   col+1),
                (row,   col-1)]

    def maybe_capture(self, color, row, col):
        if not self.is_bounded(row, col): return True # continue if we hit the edge
        if self.board[row][col] == EMPTY: return False # stop if we hit EMPTY
        if self.board[row][col] != color: return True # continue if we hit our color

        self.board[row][col] = MAYBE
        for r,c in self.dirs(row, col):
            if not self.maybe_capture(color, r, c):
                return False

        return True

    def replace_maybe(self, color, row, col):
        if not self.is_bounded(row, col): return
        if self.board[row][col] == MAYBE:
            self.board[row][col] = color
            for r,c in self.dirs(row, col):
                self.replace_maybe(color, r, c)

    def move(self, color, row, col):
        self.board[row][col] = color
        opponent_color = BLACK if color == WHITE else WHITE
        for r,c in self.dirs(row, col):
            if self.is_bounded(r, c) and self.board[r][c] == opponent_color and self.maybe_capture(opponent_color, r,c):
                self.replace_maybe(EMPTY, r, c)
                print self
                print "\n"
            else:
                self.replace_maybe(opponent_color, r, c)




b = Board()

b.move(BLACK, 4, 4)
b.move(BLACK, 4, 5)
b.move(BLACK, 4, 6)
b.move(WHITE, 3, 4)
b.move(WHITE, 3, 5)
b.move(WHITE, 3, 6)
b.move(WHITE, 4, 3)
b.move(WHITE, 4, 7)
b.move(WHITE, 5, 4)
b.move(WHITE, 5, 5)
b.move(WHITE, 5, 6)
print b