Initial

1 files changed, 200 insertions, 0 deletions

diff --git a/board.cpp b/board.cpp
new file mode 100644
index 0000000..3b59aad
--- /dev/null
+++ b/board.cpp
@@ -0,0 +1,200 @@
+#include <cstring>
+#include <cctype>
+#include <cassert>
+#include "board.h"
+
+using namespace std;
+
+
+static optional<int> parsePosition(string_view str) {
+	if (str.size() != 2) return nullopt;
+	char a = toupper(str[0]), b = str[1];
+	if (a < 'A' || a > 'Z') return nullopt;
+	if (b < '0' || b > '9') return nullopt;
+	return N * (N - (b - '0')) + a - 'A';
+}
+
+Move::Move(int from, int to)
+		: from(from), to(to) {}
+
+optional<Move> Move::parse(string_view str) {
+	if (str.size() != 5) return nullopt;
+	if (str[2] != '-' && str[2] != ' ') return nullopt;
+
+	if (auto from = parsePosition(str.substr(0, 2))) {
+		if (auto to = parsePosition(str.substr(3, 2))) {
+			Move mv;
+			mv.from = *from;
+			mv.to = *to;
+			return mv;
+		}
+	}
+
+	return nullopt;
+}
+
+ostream& operator<<(ostream &os, const Move &mv) {
+	os << (char)('A' + mv.from % N) << (char)('0' + N - mv.from / N)
+	   << '-'
+	   << (char)('A' + mv.to % N) << (char)('0' + N - mv.to / N);
+	return os;
+}
+
+
+static int colour(uint8_t value) {
+	return value < 4;
+}
+
+static int rotateIndex(int index) {
+	int x = index % N, y = index / N;
+	return N * x + N-1 - y;
+}
+
+static int rotateIndex(int index, int nturns) {
+	for (int i = 0; i < nturns % 4; i++) {
+		index = rotateIndex(index);
+	}
+	return index;
+}
+
+
+Board::Board() {}
+
+Board Board::makeInitial() {
+	Board bd;
+	memset(bd.cells, EMPTY, N * N);
+
+	for (int i = 0; i < 4; i++) {
+		bd.cells[rotateIndex(N/2 - 1, i)] = BLACK;
+		bd.cells[rotateIndex(N/2 + 0, i)] = BLACK;
+		bd.cells[rotateIndex(N/2 + 1, i)] = BLACK;
+		bd.cells[rotateIndex(N + N/2, i)] = BLACK;
+
+		bd.cells[rotateIndex(BOARDMID - 2 * N, i)] = WHITE;
+		bd.cells[rotateIndex(BOARDMID - 1 * N, i)] = WHITE;
+	}
+
+	bd.cells[BOARDMID] = KING;
+	return bd;
+}
+
+bool Board::stoneFlankedH(int pos, uint8_t by) const {
+	return (cells[pos-1] == by || (pos-1 == BOARDMID && cells[BOARDMID] == EMPTY)) &&
+			(cells[pos+1] == by || (pos+1 == BOARDMID && cells[BOARDMID] == EMPTY));
+}
+
+bool Board::stoneFlankedV(int pos, uint8_t by) const {
+	return (cells[pos-N] == by || (pos-N == BOARDMID && cells[BOARDMID] == EMPTY)) &&
+			(cells[pos+N] == by || (pos+N == BOARDMID && cells[BOARDMID] == EMPTY));
+}
+
+bool Board::kingEncircled(int pos) const {
+	if (pos == BOARDMID) {
+		return cells[pos-1] == BLACK && cells[pos+1] == BLACK &&
+				cells[pos-N] == BLACK && cells[pos+N] == BLACK;
+	} else if (pos == BOARDMID-1) {
+		return cells[pos-1] == BLACK && cells[pos-N] == BLACK && cells[pos+N] == BLACK;
+	} else if (pos == BOARDMID+1) {
+		return cells[pos+1] == BLACK && cells[pos-N] == BLACK && cells[pos+N] == BLACK;
+	} else if (pos == BOARDMID-N) {
+		return cells[pos-1] == BLACK && cells[pos+1] == BLACK && cells[pos-N] == BLACK;
+	} else if (pos == BOARDMID+N) {
+		return cells[pos-1] == BLACK && cells[pos+1] == BLACK && cells[pos+N] == BLACK;
+	} else {
+		int x = pos % N, y = pos / N;
+		return (x > 0 && x < N-1 && cells[pos-1] == BLACK && cells[pos+1] == BLACK) ||
+				(y > 0 && y < N-1 && cells[pos-N] == BLACK && cells[pos+N] == BLACK);
+	}
+}
+
+void Board::apply(Move mv) {
+	cells[mv.to] = cells[mv.from];
+	cells[mv.from] = EMPTY;
+	int i = mv.to;
+	int x = i % N, y = i / N;
+
+	if (x > 1 && cells[i-1] != EMPTY && colour(cells[i-1]) != colour(cells[i])) {
+		if (cells[i-1] == KING ? kingEncircled(i-1) : stoneFlankedH(i-1, cells[i])) {
+			cells[i-1] = EMPTY;
+		}
+	}
+
+	if (y > 1 && cells[i-N] != EMPTY && colour(cells[i-N]) != colour(cells[i])) {
+		if (cells[i-N] == KING ? kingEncircled(i-N) : stoneFlankedV(i-N, cells[i])) {
+			cells[i-N] = EMPTY;
+		}
+	}
+
+	if (x < N-2 && cells[i+1] != EMPTY && colour(cells[i+1]) != colour(cells[i])) {
+		if (cells[i+1] == KING ? kingEncircled(i+1) : stoneFlankedH(i+1, cells[i])) {
+			cells[i+1] = EMPTY;
+		}
+	}
+
+	if (y < N-2 && cells[i+N] != EMPTY && colour(cells[i+N]) != colour(cells[i])) {
+		if (cells[i+N] == KING ? kingEncircled(i+N) : stoneFlankedV(i+N, cells[i])) {
+			cells[i+N] = EMPTY;
+		}
+	}
+}
+
+int Board::applyCW(Move mv) {
+	// TODO: make more efficient
+	apply(mv);
+	return checkWin();
+}
+
+int Board::checkWin() const {
+	for (int x = 0; x < N; x++) if (cells[x] == KING) return 1;
+	for (int y = 0; y < N; y++) if (cells[N * y] == KING) return 1;
+	for (int x = 0; x < N; x++) if (cells[N * (N-1) + x] == KING) return 1;
+	for (int y = 0; y < N; y++) if (cells[N * y + N-1] == KING) return 1;
+
+	for (int i = 0; i < N * N; i++) {
+		if (cells[i] == KING) return 0;
+	}
+
+	return -1;
+}
+
+bool Board::isValid(Move mv) const {
+	if (mv.from < 0 || mv.from >= N * N || mv.to < 0 || mv.to >= N * N) return false;
+	if (mv.from == mv.to) return false;
+	if (cells[mv.from] == EMPTY || cells[mv.to] != EMPTY) return false;
+
+	if (mv.to == BOARDMID) return false;
+
+	int x1 = mv.from % N, y1 = mv.from / N;
+	int x2 = mv.to % N, y2 = mv.to / N;
+	if (x1 != x2 && y1 != y2) return false;
+
+	if (x1 == x2) {
+		int delta = y2 < y1 ? -1 : 1;
+		for (int y = y1 + delta; y != y2; y += delta) {
+			if (cells[N * y + x1] != EMPTY) return false;
+		}
+	} else {
+		int delta = x2 < x1 ? -1 : 1;
+		for (int x = x1 + delta; x != x2; x += delta) {
+			if (cells[N * y1 + x] != EMPTY) return false;
+		}
+	}
+
+	return true;
+}
+
+bool Board::isValid(Move mv, int player) const {
+	uint8_t mask = player == 1 ? WHITE|KING : BLACK;
+	return isValid(mv) && (cells[mv.from] & mask) != 0;
+}
+
+ostream& operator<<(ostream &os, const Board &bd) {
+	for (int y = 0; y < N; y++) {
+		if (y != 0) os << '\n';
+		for (int x = 0; x < N; x++) {
+			if (x != 0) os << ' ';
+			os << ".O#-X"[bd.cells[N*y+x]];
+		}
+	}
+	return os;
+}