path: root/board.cpp

#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 {
	if (by & (WHITE|KING)) by = WHITE|KING;
	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 {
	if (by & (WHITE|KING)) by = WHITE|KING;
	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) {
	int x2 = mv.to % N, y2 = mv.to / N;

	if (cells[mv.from] == KING) {
		apply(mv);

		if (cells[mv.to] == KING) {
			if (x2 == 0 || x2 == N-1 || y2 == 0 || y2 == N-1) return 1;
		}
	} else {
		bool haveking1 =
				(x2 > 0 && cells[mv.to - 1] == KING) ||
				(y2 > 0 && cells[mv.to - N] == KING) ||
				(x2 < N-1 && cells[mv.to + 1] == KING) ||
				(y2 < N-1 && cells[mv.to + N] == KING);

		apply(mv);

		bool haveking2 =
				(x2 > 0 && cells[mv.to - 1] == KING) ||
				(y2 > 0 && cells[mv.to - N] == KING) ||
				(x2 < N-1 && cells[mv.to + 1] == KING) ||
				(y2 < N-1 && cells[mv.to + N] == KING);

		if (haveking1 && !haveking2) return -1;
	}

	return 0;
}

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;
}