83 lines
1.7 KiB
C++
83 lines
1.7 KiB
C++
// Design an algorithm to figure out if someone has won in a game of
|
|
// tic-tac-toe.
|
|
|
|
#define CATCH_CONFIG_MAIN
|
|
#include <catch.hpp>
|
|
|
|
#include <array>
|
|
|
|
enum class Owner {
|
|
Invalid = 0,
|
|
None = 1,
|
|
X = 2,
|
|
O = 4,
|
|
};
|
|
|
|
static const int Dim = 3;
|
|
|
|
using Row = std::array<Owner, Dim>;
|
|
using Board = std::array<Row, Dim>;
|
|
|
|
static bool is_winner(const Board& board, int x, int y, int dx, int dy) {
|
|
int merged = 0;
|
|
|
|
for (auto i = 0; i < Dim; i++) {
|
|
merged |= int(board[y+i*dy][x+i*dx]);
|
|
}
|
|
auto owner = Owner(merged);
|
|
return owner == Owner::X || owner == Owner::O;
|
|
}
|
|
|
|
static bool has_winner(const Board& board) {
|
|
return false
|
|
// Columns
|
|
|| is_winner(board, 0, 0, 1, 0)
|
|
|| is_winner(board, 0, 1, 1, 0)
|
|
|| is_winner(board, 0, 2, 1, 0)
|
|
// Rows
|
|
|| is_winner(board, 0, 0, 0, 1)
|
|
|| is_winner(board, 1, 0, 0, 1)
|
|
|| is_winner(board, 2, 0, 0, 1)
|
|
// Diagonals
|
|
|| is_winner(board, 0, 0, 1, 1)
|
|
|| is_winner(board, 2, 0, -1, 1)
|
|
;
|
|
}
|
|
|
|
static Board make_board(const std::string& defn) {
|
|
Board board;
|
|
int x = 0;
|
|
int y = 0;
|
|
|
|
for (auto& row : board) {
|
|
row.fill(Owner::None);
|
|
}
|
|
|
|
for (auto ch : defn) {
|
|
switch (ch) {
|
|
case 'x':
|
|
board[y][x] = Owner::X;
|
|
break;
|
|
case 'o':
|
|
board[y][x] = Owner::O;
|
|
break;
|
|
default:
|
|
board[y][x] = Owner::None;
|
|
}
|
|
if (++x == Dim) {
|
|
x = 0;
|
|
y++;
|
|
}
|
|
}
|
|
return board;
|
|
}
|
|
|
|
TEST_CASE("cc19.2", "winner") {
|
|
CHECK(has_winner(make_board("")) == false);
|
|
CHECK(has_winner(make_board("o o")) == false);
|
|
CHECK(has_winner(make_board("oxo")) == false);
|
|
CHECK(has_winner(make_board("ooo")) == true);
|
|
CHECK(has_winner(make_board("o oo o o")) == true);
|
|
CHECK(has_winner(make_board("o o o")) == true);
|
|
}
|