import java.util.List;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Arrays;
import java.lang.Comparable;
class Lists
{
public static <T> List<T> unmodifiableList(int size, T value)
{
List<T> list = new ArrayList<T>(size);
while (size-- > 0) list.add(value);
return Collections.unmodifiableList(list);
}
}
// TOKENS
abstract class Token
{
abstract public int getValue();
}
final class XToken extends Token
{
public int getValue() { return 1; }
public String toString() { return "X"; }
}
final class NoToken extends Token
{
public int getValue() { return 0; }
public String toString() { return " "; }
}
final class OToken extends Token
{
public int getValue() { return 2; }
public String toString() { return "O"; }
}
class Tokens
{
public static final Token noToken = new NoToken();
public static final Token xToken = new XToken();
public static final Token oToken = new OToken();
public static List<Token> fixedLengthCopyOf(List<Token> original)
{
int n = original.size();
Token[] copy = new Token[n];
while (n-- > 0) copy[n] = original.get(n);
return Arrays.asList(copy);
}
}
// GAME INTERFACES
interface Game
{
final int INVALID_STATE = -3, NOT_STARTED = -2, IN_PROGRESS = -1;
boolean gameOver();
int getGameState();
String getGameStateDescription();
}
interface GameOfDiscreteMoves extends Game
{
int getMoveCount();
}
interface BoardGame extends GameOfDiscreteMoves
{
int getBoardSize();
}
interface SimpleTokenPlacementBoardGame extends BoardGame
{
final int FIRST_INDEX = 0, NO_PLAYER = 0, FIRST_PLAYER = 1;
int getCurrentPlayer();
Token getTokenAt(int i);
Token getTokenOfPlayer(int n);
List<Token> getBoardContents();
List<Integer> getAllPlaces();
List<Integer> getAvailablePlaces();
boolean putCurrentPlayerTokenAt(int i);
boolean mayPutCurrentPlayerTokenAt(int i);
// Shortcuts
boolean put(int i);
Token get(int i);
}
interface SimpleTwoPlayerTokenPlacementBoardGame extends SimpleTokenPlacementBoardGame
{
final int
SECOND_PLAYER = 2,
PLAYERS_TIED = 0,
FIRST_PLAYER_WON = 1,
SECOND_PLAYER_WON = 2;
}
// ABSTRACT GAMES
abstract class PartialAbstractConnectNGame implements SimpleTwoPlayerTokenPlacementBoardGame
{
// Immutable Values
protected final List<Token> emptyBoard;
protected final int boardSize;
protected final int rowSize;
protected final int colSize;
protected final int numberNeededToWin;
protected final Token firstPlayerToken = Tokens.xToken;
protected final Token secondPlayerToken = Tokens.oToken;
// Mutable Values
private int moveCount = 0;
private int gameState = NOT_STARTED;
private int currentPlayer = FIRST_PLAYER;
private Token currentPlayerToken = firstPlayerToken;
private final List<Token> boardContents;
private final List<Integer> availablePlaces;
protected PartialAbstractConnectNGame(int rowSize, int colSize, int neededToWin)
{
this.rowSize = rowSize;
this.colSize = colSize;
numberNeededToWin = neededToWin;
boardSize = rowSize * colSize;
emptyBoard = Lists.unmodifiableList(boardSize, Tokens.noToken);
boardContents = Tokens.fixedLengthCopyOf(emptyBoard);
availablePlaces = getAllPlaces();
}
// Shortcuts
public final boolean put(int i) { return putCurrentPlayerTokenAt(i); }
public final Token get(int i) { return getTokenAt(i); }
public final int getMoveCount() { return moveCount; }
public final int getBoardSize() { return this.boardSize; }
public final int getGameState() { return gameState; }
public final int getCurrentPlayer() { return currentPlayer; }
public final Token getTokenAt(int i) { return boardContents.get(i); }
public boolean gameOver() { return gameState >= 0; }
public boolean mayPutCurrentPlayerTokenAt(int i)
{
return availablePlaces.contains(i);
}
public List<Integer> getAllPlaces()
{
List allPlaces = new ArrayList(boardSize);
for (int i = 0; i < boardSize; i++) allPlaces.add(i);
return allPlaces;
}
public List<Integer> getAvailablePlaces()
{
return Collections.unmodifiableList(availablePlaces);
}
public final List<Token> getBoardContents()
{
return Collections.unmodifiableList(boardContents);
}
public final Token getTokenOfPlayer(int n)
{
switch(n)
{
case FIRST_PLAYER: return firstPlayerToken;
case SECOND_PLAYER: return secondPlayerToken;
default: return Tokens.noToken;
}
}
public final String getGameStateDescription()
{
switch(gameState)
{
case INVALID_STATE: return "Game state is invalid.";
case NOT_STARTED: return "Game has not started.";
case IN_PROGRESS: return "Game is in progress.";
case PLAYERS_TIED: return "Tie game.";
case FIRST_PLAYER_WON: return firstPlayerToken.toString() + " won.";
case SECOND_PLAYER_WON: return secondPlayerToken.toString() + " won.";
default: return "Unexpected state: " + gameState;
}
}
public final boolean putCurrentPlayerTokenAt(int i)
{
if (!mayPutCurrentPlayerTokenAt(i)) return false;
if (gameState == NOT_STARTED) gameState = IN_PROGRESS;
assert(gameState == IN_PROGRESS);
boardContents.set(i, currentPlayerToken);
// The next statement is a little tricky. Remove the element with VALUE of i.
// Do NOT remove the element at INDEX i unless it is the one with value of i.
availablePlaces.remove(Integer.valueOf(i));
moveCount++;
if (won(i, currentPlayerToken))
gameState = currentPlayer == FIRST_PLAYER ? FIRST_PLAYER_WON : SECOND_PLAYER_WON;
else if (gameOver())
gameState = PLAYERS_TIED;
if (gameOver())
{
currentPlayer = NO_PLAYER;
currentPlayerToken = Tokens.noToken;
availablePlaces.clear();
}
else
{
currentPlayer = moveCount % 2 == 0 ? FIRST_PLAYER : SECOND_PLAYER;
currentPlayerToken = getTokenOfPlayer(currentPlayer);
}
return true;
}
public String toString()
{
StringBuilder sb = new StringBuilder();
sb.append("Game Board:");
for (int i = 0; i < boardSize; i++)
{
if (i % rowSize == 0) sb.append("\n");
sb.append(getTokenAt(i));
}
sb.append("\n");
sb.append(getGameStateDescription());
return sb.toString();
}
abstract protected boolean won(int index, Token token);
}
abstract class AbstractConnectNGame extends PartialAbstractConnectNGame
{
private final int n, lower, upper; // These variables are simply synonyms.
protected AbstractConnectNGame(int rowSize, int colSize, int neededToWin)
{
super(rowSize, colSize, neededToWin);
n = numberNeededToWin;
lower = 0;
upper = boardSize;
}
final protected boolean won(int i, Token tok)
{
assert(mayPutCurrentPlayerTokenAt(i) && tok == getTokenAt(i));
return wonNS(i, tok) || wonEW(i, tok) || wonNWSE(i, tok) || wonNESW(i, tok);
}
private int getRow(int i) { return i / colSize; }
private int getCol(int i) { return i % rowSize; }
private boolean wonEW(int index, Token token)
{
final int i = index, row = getRow(index);
int j, k, count = 1;
for (j = 1, k = i - j; k >= lower && j <= n; j++, k = i - j)
{
if (getTokenAt(k) == token && getRow(k) == row)
count++;
else
break;
}
for (j = 1, k = i + j; k < upper && j <= n; j++, k = i + j)
{
if (getTokenAt(k) == token && getRow(k) == row)
count++;
else
break;
}
return count == numberNeededToWin;
}
private boolean wonNS(int index, Token token)
{
final int i = index, col = getCol(i);
int j, k, count = 1;
for (j = 1, k = i - (j * colSize);
k >= lower && j <= n; j++, k = i - (j * colSize))
{
if (getTokenAt(k) == token && getCol(k) == col)
count++;
else
break;
}
for (j = 1, k = i + (j * colSize);
k < upper && j <= n; j++, k = i + (j * colSize))
{
if (getTokenAt(k) == token && getCol(k) == col)
count++;
else
break;
}
return count == numberNeededToWin;
}
private boolean wonNWSE(int index, Token token)
{
final int i = index, row = getRow(i), col = getCol(i);
int j, k, count = 1;
for (j = 1, k = i - (j * colSize) - j;
k >= lower && j <= n; j++, k = i - (j * colSize) - j)
{
if (getTokenAt(k) == token && getRow(k) == row - j && getCol(k) == col - j)
count++;
else
break;
}
for (j = 1, k = i + (j * colSize) + j;
k < upper && j <= n; j++, k = i + (j * colSize) + j)
{
if (getTokenAt(k) == token && getRow(k) == row + j && getCol(k) == col + j)
count++;
else
break;
}
return count == numberNeededToWin;
}
private boolean wonNESW(int index, Token token)
{
final int i = index, row = getRow(i), col = getCol(i);
int j, k, count = 1;
for (j = 1, k = i - (j * colSize) + j;
k >= lower && j <= n; j++, k = i - (j * colSize) + j)
{
if (getTokenAt(k) == token && getRow(k) == row - j && getCol(k) == col + j)
count++;
else
break;
}
for (j = 1, k = i + (j * colSize) - j;
k < upper && j <= n; j++, k = i + (j * colSize) - j)
{
if (getTokenAt(k) == token && getRow(k) == row + j && getCol(k) == col - j)
count++;
else
break;
}
return count == numberNeededToWin;
}
}
// TIC TAC TOE GAME
final class TicTacToeGame extends AbstractConnectNGame
{
public TicTacToeGame() { super(3, 3, 3); }
}
final class Mark
{
public static final Mark X = new Mark('X', 1);
public static final Mark O = new Mark('O', -1);
public static Mark getOther(Mark mark)
{
return mark == X ? O : X;
}
public final Character glyph;
public final int value;
private Mark(char glyph, int value)
{
this.glyph = glyph;
this.value = value;
}
public String toString()
{
return glyph.toString();
}
}
final class Cell
{
private static final Cell[] cells =
{
new Cell(0, "upper row left"),
new Cell(1, "upper row center"),
new Cell(2, "upper row right"),
new Cell(3, "middle row left"),
new Cell(4, "middle row center"),
new Cell(5, "middle row right"),
new Cell(6, "lower row left"),
new Cell(7, "lower row center"),
new Cell(8, "lower row right")
};
private static final int CELL_COUNT = cells.length;
public static Cell get(int i) { return cells[i]; }
public static int count() { return CELL_COUNT; }
public final int index;
public final String name;
private Cell(int index, String name)
{
this.index = index;
this.name = name;
}
public String toString()
{
return this.name + " cell";
}
}
class Factorial
{
private static final String errorMessage = "factorial of negative integers is undefined";
private static int computeRecursively(int n)
{
assert(n >= 0);
return n > 1 ? n * computeRecursively(n - 1) : 1;
}
public static int of(int n)
{
if (n < 0) throw new ArithmeticException(errorMessage);
return computeRecursively(n);
}
}
class Moves
{
private static final int lastSequenceNum = Cell.count();
public static int computeBranchSize(int moveSequenceNum)
{
return (moveSequenceNum < lastSequenceNum) ?
Factorial.of(lastSequenceNum - moveSequenceNum) : 0;
}
}
class IsolatedMove
{
private final Mark mark;
private final Cell cell;
public IsolatedMove(Mark mark, Cell cell)
{
this.mark = mark;
this.cell = cell;
}
public Mark getMark() { return this.mark; }
public Cell getCell() { return this.cell; }
public int compareTo(IsolatedMove that)
{
Integer thisCellIndex = this.cell.index;
Integer thatCellIndex = that.cell.index;
if (thisCellIndex == thatCellIndex)
{
Integer thisMarkValue = this.mark.value;
Integer thatMarkValue = that.getMark().value;
return thisMarkValue.compareTo(thatMarkValue);
}
return thisCellIndex.compareTo(thatCellIndex);
}
public String toString()
{
StringBuilder sb = new StringBuilder();
sb.append(mark.toString());
sb.append(" in ");
sb.append(cell.toString());
return sb.toString();
}
}
final class Move extends IsolatedMove
{
private final Move prevMove;
private final List<Move> nextMoves;
private final int sequenceNum;
private final int finalBranchSize;
private final boolean winsGame;
private final boolean endsGame;
//private boolean allBranchesAreUnderstood = false;
private Boolean isSafe = null;
private int branchSize = 0;
private boolean isRoot() { return sequenceNum == 0; }
public Move(Mark mark, Cell cell, Move prevMove, boolean winsGame)
{
super(prevMove != null ? mark : null, prevMove != null ? cell : null);
this.prevMove = prevMove;
this.sequenceNum = (prevMove == null) ? 0 : prevMove.sequenceNum + 1;
final int nextMoveCount = Cell.count() - this.sequenceNum;
this.finalBranchSize = Moves.computeBranchSize(this.sequenceNum);
this.nextMoves = new ArrayList<Move>(nextMoveCount);
if (prevMove != null) prevMove.nextMoves.add(this);
this.winsGame = winsGame;
this.endsGame = winsGame || nextMoveCount == 0;
if (this.endsGame) {
this.branchSize = this.getFinalBranchSize();
for (Move move = this.prevMove; move != null; move = move.prevMove)
move.branchSize += this.branchSize;
setIsSafe(true);
this.getPrevMove().setIsSafe(!winsGame);
}
}
public int getSequenceNum() { return this.sequenceNum; }
public Move getPrevMove() { return this.prevMove; }
public List<Move> getNextMoves()
{
return Collections.unmodifiableList(nextMoves);
}
public int compareTo(Move that)
{
final Integer thisSequenceNum = this.sequenceNum;
final Integer thatSequenceNum = that.sequenceNum;
return thisSequenceNum == thatSequenceNum ?
super.compareTo(that) :
thisSequenceNum.compareTo(thatSequenceNum);
}
public String toString()
{
return super.toString() + " is move " + this.sequenceNum;
}
public boolean endsGame() { return endsGame; }
public boolean winsGame() { return winsGame; }
public boolean endsGameInTie() { return endsGame && !winsGame; }
public Boolean isSafe() { return isSafe; }
public int getFinalBranchSize() { return this.finalBranchSize; }
public int getBranchSize() { return branchSize; }
public boolean isFullyDeveloped()
{
return this.getBranchSize() == this.getFinalBranchSize();
/*
if (this.allBranchesAreUnderstood == true)
return true;
else if (!this.endsGame)
{
if (Cell.count() - this.moveNum > this.nextMoves.size())
return false;
else
for (Move move : nextMoves)
if (!move.isFullyUnderstood())
return false;
}
allBranchesAreUnderstood = true;
return true;
*/
}
private void setIsSafe(Boolean value)
{
// If a move is safe, then the player making the move can always prevent a loss.
// If a move is unsafe, then there is some way for the opponent to always win.
// If the safety of a move is unknown, then the value of isSafe is null.
// This player could be X or O, so we'll refer to this player as player A,
// and we'll call player A's opponent player B.
// The value of isSafe is initially set to null. Once the value changes, it
// should never revert to null. (This program learns. It doesn't unlearn.)
assert(value != null);
// First we set the value of isSafe for player A (this player). We assume the
// caller somehow figured out what the correct value should be.
this.isSafe = value;
// We need player B's previous move (if applicable) so we can look at all of
// the moves that this player could have made besides and including this one
// and so that we can get player A's previous move (if applicable).
Move B = this.prevMove;
// Our objective at this point is to update the isSafe value for A's
// previous move if possible. This is only possible if A actually made
// a previous move and all possible moves after A's last move have been
// explored, in which case we should know whether each subsequent move
// that A made was safe or not.
if (!B.isRoot() && !B.prevMove.isRoot() && B.prevMove.isFullyDeveloped())
{
Boolean A_canAlwaysFindAWayToAvoidLosing = true; // A presumption.
// Now we consider each move B could have made after A's previous move
// and each move A could have made after THAT move.
for (Move B_altMove : B.prevMove.nextMoves)
{
boolean A_foundAWayToAvoidLosing = false;
for (Move A_altMove : B_altMove.nextMoves)
{
if (A_altMove.isSafe() == true)
{
A_foundAWayToAvoidLosing = true;
break;
}
}
if (!A_foundAWayToAvoidLosing)
{
A_canAlwaysFindAWayToAvoidLosing = false;
break;
}
}
// Finally, we bubble up the safety value of A's previous move. The
// procedure repeats until there are no more previous moves of A's
// to consider or until we reach a point in the tree where we haven't
// explored far enough to know the answer yet.
B.prevMove.setIsSafe(A_canAlwaysFindAWayToAvoidLosing);
}
}
}
abstract class Game
{
private int moveCount = 0;
private final boolean[] x = new boolean[Cell.count()]; // X's moves
private final boolean[] o = new boolean[Cell.count()]; // O's moves
private final boolean[] available = new boolean[Cell.count()];
private boolean[] winner = null;
private Cell lastCell = null;
protected boolean[] c = x; // current player's moves
protected int getMoveCount() { return moveCount; }
abstract protected boolean wasWinningMove(int i);
public boolean gameOver() { return playersTied() || someoneWon(); }
public boolean playersTied() { return moveCount == Cell.count() && winner == null; }
public boolean someoneWon() { return winner != null; }
public boolean xWon() { return winner == x; }
public boolean oWon() { return winner == o; }
public boolean mayPutMarkIn(Cell cell) { return available[cell.index]; }
public Cell getLastCell() { return lastCell; }
public List<Cell> getAvailableCells()
{
List<Cell> availableCells = new LinkedList<Cell>();
for (int i = 0; i < Cell.count(); i++)
if (available[i])
availableCells.add(Cell.get(i));
return availableCells;
}
public boolean putMarkIn(Cell cell)
{
final int i = cell.index;
if (gameOver()) return false;
if (!mayPutMarkIn(cell)) return false;
c[i] = true;
available[i] = false;
moveCount++;
if (wasWinningMove(i)) winner = c;
else c = c == x ? o : x;
lastCell = cell;
return true;
}
public void reset()
{
moveCount = 0;
c = x;
winner = null;
int i = Cell.count();
while (i-- > 0) {
x[i] = o[i] = false;
available[i] = true;
}
}
public void printMoves()
{
for (int i = 0; i < Cell.count(); i++)
{
if (x[i]) System.out.print("X");
else if (o[i]) System.out.print("O");
else System.out.print(" ");
if ((i+1) % 3 == 0) System.out.println();
}
}
}
final class TicTacToeGame extends Game
{
// Rows and Columns (t: top; m: middle; b: bottom)
private boolean tRow() { return c[0] && c[1] && c[2]; }
private boolean mRow() { return c[3] && c[4] && c[5]; }
private boolean bRow() { return c[6] && c[7] && c[8]; }
private boolean lCol() { return c[0] && c[3] && c[6]; }
private boolean mCol() { return c[1] && c[4] && c[7]; }
private boolean rCol() { return c[2] && c[5] && c[8]; }
// Diagonals (f: forward; b: backward)
private boolean bDia() { return c[0] && c[4] && c[8]; }
private boolean fDia() { return c[2] && c[4] && c[6]; }
protected boolean wasWinningMove(int i)
{
if (getMoveCount() < 5) return false;
else if (i < 3)
if (tRow()) return true;
else if (i == 0) return lCol() || bDia();
else if (i == 1) return mCol();
else return rCol() || fDia();
else if (i < 6)
if (mRow()) return true;
else if (i == 3) return lCol();
else if (i == 4) return mCol() || bDia() || fDia();
else return rCol();
else
if (bRow()) return true;
else if (i == 6) return lCol() || fDia();
else if (i == 7) return mCol();
else return rCol() || bDia();
/*
if (c[0] && c[1] && c[2]) return true;
if (c[3] && c[4] && c[5]) return true;
if (c[6] && c[7] && c[8]) return true;
if (c[0] && c[3] && c[6]) return true;
if (c[1] && c[4] && c[7]) return true;
if (c[2] && c[5] && c[8]) return true;
if (c[0] && c[4] && c[8]) return true;
if (c[2] && c[4] && c[6]) return true;
return false;
*/
}
}
public class PlayTicTacToe
{
public static void main(String args[])
{
}
}
