import java.util.List;
import java.util.Stack;
import java.util.Collection;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Collections;
/**************/
/* INTERFACES */
/**************/
interface Token
{
Character getSymbol();
}
interface PlaceableToken extends Token
{
int getIndex();
int getRow();
int getColumn();
boolean placeAt(int i);
boolean belongsOn(Grid grid);
boolean isPlacedOn(Grid grid);
}
interface ErasableToken extends PlaceableToken
{
boolean erase();
}
interface NonErasableMoveableToken extends PlaceableToken
{
boolean moveTo(int i);
}
interface MoveableToken extends ErasableToken, NonErasableMoveableToken
{
}
interface Grid
{
final int OFF_GRID = -1;
int size();
int rowCount();
int columnCount();
boolean isGridIndex(int i);
int toIndex(int r, int c);
}
interface ImmutableTokenGrid extends Grid
{
Token get(int i);
}
interface MutableTokenGrid extends ImmutableTokenGrid
{
boolean place(PlaceableToken token);
boolean erase(int i, ErasableToken token);
}
interface Player
{
boolean placeTokenAt(int i);
boolean eraseTokenAt(int i);
boolean moveToken(int from, int to);
}
interface Game
{
public void play();
}
/*****************/
/* ERROR HANDLER */
/*****************/
class Error
{
public static boolean handle(String text)
{
System.out.println(text);
return false;
}
}
/**********/
/* TOKENS */
/**********/
class Tokens
{
public static Token NO_TOKEN = new SimpleToken('-');
public static boolean isNoToken(Token token)
{
return token == Tokens.NO_TOKEN;
}
}
class SimpleToken implements Token
{
private final Character symbol;
public SimpleToken(Character c)
{
this.symbol = c;
}
public final Character getSymbol()
{
return symbol;
}
public String toString()
{
return symbol.toString();
}
}
class FixedGridPlaceableToken extends SimpleToken
implements PlaceableToken
{
protected final TokenGrid grid;
protected int index;
public FixedGridPlaceableToken(Character symbol, TokenGrid grid)
{
super(symbol);
this.grid = grid;
this.index = Grid.OFF_GRID;
}
public final int getIndex()
{
return this.index;
}
public final int getRow()
{
return this.index / grid.columnCount();
}
public final int getColumn()
{
return this.index % grid.columnCount();
}
public final boolean isPlaced()
{
return this.grid.isGridIndex(this.index);
}
public final boolean isPlacedOn(Grid grid)
{
return grid != null && this.grid == grid && this.isPlaced();
}
public final boolean belongsOn(Grid grid)
{
return grid != null && this.grid == grid;
}
public final boolean placeAt(int i)
{
if (this.isPlaced())
return Error.handle("placeAt: already placed");
if (!grid.isGridIndex(i))
return Error.handle("placeAt: invalid index " + i);
if (!Tokens.isNoToken(grid.get(i)))
return Error.handle("placeAt: other token at " + i);
this.index = i;
if (!grid.place(this))
this.index = Grid.OFF_GRID;
return this.index != Grid.OFF_GRID;
}
}
final class FixedGridMovableToken extends FixedGridPlaceableToken
implements MoveableToken
{
public FixedGridMovableToken(Character symbol, TokenGrid grid)
{
super(symbol, grid);
}
public final boolean erase()
{
if (!this.isPlaced())
return Error.handle("erase: token has not been placed");
final int eraseFrom = this.index;
this.index = Grid.OFF_GRID;
return this.grid.erase(eraseFrom, this);
}
public final boolean moveTo(int i)
{
if (this.isPlaced() && !this.erase())
return Error.handle("moveTo: was placed but not erased");
return placeAt(i);
}
}
/*********/
/* GRIDS */
/*********/
class FixedSizeRectangularGrid implements Grid
{
private final int rowCount, columnCount, size;
protected FixedSizeRectangularGrid(int rowCount, int columnCount)
{
this.rowCount = rowCount;
this.columnCount = columnCount;
this.size = rowCount * columnCount;
}
public final int size()
{
return size;
}
public final int rowCount()
{
return rowCount;
}
public final int columnCount()
{
return columnCount;
}
public final boolean isGridIndex(int i)
{
return i >= 0 && i < size;
}
public final int toIndex(int r, int c)
{
final int i = r * columnCount() + c;
return isGridIndex(i) ? i : Grid.OFF_GRID;
}
}
final class TokenGrid extends FixedSizeRectangularGrid
implements MutableTokenGrid
{
private final char FIRST_COL_HEADER = 'A';
private final int FIRST_ROW_NUMBER = 1;
private final Token[] tokens;
private final String heading;
public TokenGrid(int rowCount, int columnCount, String heading)
{
super(rowCount, columnCount);
this.heading = heading;
final int n = this.size();
tokens = new Token[n];
for (int i = 0; i < n; i++)
tokens[i] = Tokens.NO_TOKEN;
}
public final Token get(int i)
{
return tokens[i];
}
public final boolean place(PlaceableToken token)
{
if (Tokens.isNoToken(token) || !token.isPlacedOn(this))
return Error.handle("place: no token or token not on grid");
final int i = token.getIndex();
if (!Tokens.isNoToken(this.get(i)))
return Error.handle("place: other token already in place " + i);
tokens[i] = token;
return true;
}
public final boolean erase(int i, ErasableToken token)
{
if (Tokens.isNoToken(token) || token.isPlacedOn(this))
return Error.handle("erase: no token or token is not erased");
if (this.get(i) != token)
return Error.handle("erase: tokens do not match");
tokens[i] = Tokens.NO_TOKEN;
return true;
}
public String toString()
{
int c;
Character ch;
StringBuilder sb = new StringBuilder();
sb.append(this.heading + "\n\n ");
for (c = 0, ch=FIRST_COL_HEADER; c < this.columnCount(); c++)
{
sb.append(ch.toString() + ' ');
ch = (char)(ch + 1);
}
int i = 0;
for (Token token : tokens)
{
if (0 == i++ % this.columnCount())
{
sb.append("\n");
int rowNum = 1 + (i / this.columnCount());
sb.append(rowNum);
sb.append(rowNum < 10 ? " " : " ");
}
sb.append(token.toString() + ' ');
}
sb.append("\n");
return sb.toString();
}
}
/***********/
/* PLAYERS */
/***********/
class TokenHolderMover implements Player
{
private final Character symbol;
private final ImmutableTokenGrid grid;
private final Stack<MoveableToken> tokenStack = new Stack<MoveableToken>();
public TokenHolderMover(int n, Character symbol, TokenGrid grid)
{
this.grid = grid;
this.symbol = symbol;
while (n-- > 0)
tokenStack.push(new FixedGridMovableToken(symbol, grid));
}
public final boolean placeTokenAt(int i)
{
if (!hasToken())
return Error.handle("placeTokenAt: out of tokens");
return getLooseToken().placeAt(i);
}
public final boolean eraseTokenAt(int i)
{
if (!grid.isGridIndex(i))
return Error.handle("eraseTokenAt: invalid index " + i);
Token token = grid.get(i);
if (Tokens.isNoToken(token))
return Error.handle("eraseTokenAt: no token to erase");
if (!((ErasableToken)token).erase())
return Error.handle("eraseTokenAt: failed to erase");
tokenStack.push((MoveableToken)token);
return true;
}
public final boolean moveToken(int from, int to)
{
if (!grid.isGridIndex(from) || !grid.isGridIndex(to))
return Error.handle("moveToken: invalid from or to index");
Token token = grid.get(from);
if (Tokens.isNoToken(token))
return Error.handle("moveToken: no token to move");
return ((MoveableToken)token).moveTo(to);
}
public String toString()
{
StringBuilder sb = new StringBuilder();
sb.append(this.symbol);
return sb.toString();
}
private final boolean hasToken()
{
return !tokenStack.empty();
}
private final MoveableToken getLooseToken()
{
return tokenStack.pop();
}
}
/*************/
/* OFFICIALS */
/*************/
final class Official
{
private final TokenGrid grid;
private final int M, N, K, upper, lower = 0;
private final Character VOID = Tokens.NO_TOKEN.getSymbol();
public Official(int k, TokenGrid grid)
{
this.grid = grid;
upper = grid.size();
M = grid.columnCount();
N = grid.rowCount();
K = k;
}
private int row(int i) { return i / M; }
private int col(int i) { return i % M; }
private Character charAt(int i) { return grid.get(i).getSymbol(); }
public boolean bingo(int i)
{
return bingoEW(i) || bingoNS(i) || bingoNWSE(i) || bingoNESW(i);
}
public boolean bingoEW(int index)
{
final int i = index, row = row(index);
final Character c = charAt(i);
if (c == VOID ) return false;
int d, j, count = 1;
for (d = 1, j = i - d;
j >= lower && count <= K && c == charAt(j) && row(j) == row;
d++, j = i - d)
count++;
for (d = 1, j = i + d;
j < upper && count <= K && c == charAt(j) && row(j) == row;
d++, j = i + d)
count++;
return count >= K;
}
public boolean bingoNS(int index)
{
final int i = index, col = col(i);
final Character c = charAt(i);
if (c == VOID ) return false;
int d, j, count = 1;
for (d = 1, j = i - (d * M);
j >= lower && count <= K && c == charAt(j) && col(j) == col;
d++, j = i - (d * M))
count++;
for (d = 1, j = i + (d * M);
j < upper && count <= K && c == charAt(j) && col(j) == col;
d++, j = i + (d * M))
count++;
return count >= K;
}
public boolean bingoNWSE(int index)
{
final int i = index, row = row(i), col = col(i);
final Character c = charAt(i);
if (c == VOID ) return false;
int d, j, count = 1;
for (d = 1, j = i - (d * M) - d;
j >= lower && count <= K && c == charAt(j) &&
row(j) == row - d && col(j) == col - d;
d++, j = i - (d * M) - d)
count++;
for (d = 1, j = i + (d * M) + d;
j < upper && count <= K && c == charAt(j) &&
row(j) == row + d && col(j) == col + d;
d++, j = i + (d * M) + d)
count++;
return count >= K;
}
public boolean bingoNESW(int index)
{
final int i = index, row = row(i), col = col(i);
final Character c = charAt(i);
if (c == VOID ) return false;
int d, j, count = 1;
for (d = 1, j = i - (d * M) + d;
j >= lower && count <= K && c == charAt(j) &&
row(j) == row - d && col(j) == col + d;
d++, j = i - (d * M) + d)
count++;
for (d = 1, j = i + (d * M) - d;
j < upper && count <= K && c == charAt(j) &&
row(j) == row + d && col(j) == col - d;
d++, j = i + (d * M) - d)
count++;
return count >= K;
}
}
/***************/
/* TIC-TAC-TOE */
/***************/
// https://www.webofstories.com/play/donald.knuth/22
class TicTacToeGame implements Game
{
private final int N = 3, M = 3, K = 3;
private final int MAX_TURNS = N * M;
private final TokenGrid grid = new TokenGrid(N, M, "Tic-Tac-Toe");
private final Official official = new Official(K, grid);
private final Player pX = new TokenHolderMover(5, 'X', grid);
private final Player pO = new TokenHolderMover(4, 'O', grid);
private final List<Integer> plannedMoves = new ArrayList<Integer>(MAX_TURNS);
private final List<Integer> actualMoves = new ArrayList<Integer>(MAX_TURNS);
private Player pCurrent = pX;
public TicTacToeGame(List<Integer> moves)
{
for (Integer i : moves)
{
plannedMoves.add(i);
if (plannedMoves.size() == MAX_TURNS)
break;
}
}
public TicTacToeGame()
{
for (int i = 0; i < 9; i++)
plannedMoves.add(i);
Collections.shuffle(plannedMoves);
}
private void output(String message)
{
System.out.println(grid);
System.out.println(message);
System.out.print("Moves: ");
System.out.println(actualMoves);
}
public void play()
{
int turnsTaken = 0;
for (Integer i : plannedMoves)
{
if (!pCurrent.placeTokenAt(i))
{
output(pCurrent.toString() + " attempted a bad move.");
return;
}
actualMoves.add(i);
if (official.bingo(i))
{
output(pCurrent.toString() + " won!");
return;
}
pCurrent = pCurrent == pX ? pO : pX;
turnsTaken++;
}
if (turnsTaken == MAX_TURNS)
output("Cats game.");
else
output("Game is in progress.");
}
}
/*************/
/* CONNECT-4 */
/*************/
// https://en.wikipedia.org/wiki/Connect_Four
class ConnectFourGame implements Game
{
// This class is left as an exercise.
/* The parameter named moves in the constructor below
* should contain up to N x M integers, each of which
* should be greater than or equal to zero and less
* than M (duplicates are allowed) representing a
* series of columns into which players' moves are to
* be made.
*/
public ConnectFourGame(List<Integer> moves)
{
}
public ConnectFourGame()
{
}
public void play()
{
}
}
/**********************/
/* PLAY AN M,N,K-GAME */
/**********************/
// https://en.wikipedia.org/wiki/M,n,k-game
public class Play_An_MNK_Game
{
public static void main(String[] args)
{
final String TIC_TAC_TOE = "Tic-Tac-Toe";
final String CONNECT_FOUR = "Connect-4";
final int n = args.length;
if (n == 0 || (args[0].equals(TIC_TAC_TOE) && n == 1))
{
(new TicTacToeGame()).play();
return;
}
else if (args[0].equals(CONNECT_FOUR) && n == 1)
{
(new ConnectFourGame()).play();
return;
}
else if (n > 1)
{
final List<Integer> moves = new ArrayList<Integer>();
for (int i = 1; i < n; i++)
moves.add(Integer.parseInt(args[i]));
if (args[0].equals(TIC_TAC_TOE))
{
(new TicTacToeGame(moves)).play();
return;
}
if (args[0].equals(CONNECT_FOUR))
{
(new ConnectFourGame(moves)).play();
return;
}
}
System.out.println("Sorry, I don't know how to play " + args[0] + ".");
}
}
