/********************************/
/* 0. CONTENTS AND INTRODUCTION */
/********************************/
/* 0. this
* 1. Utilities
* 2. Tokens
* 3. Grids
* 4. Players
* 5. Connected Tokens Counter/Tester
* 6. Games
* 7. Let's play!
*
* This is the source code for programming assignment #16, the last (but not least!)
* programming assignment of the 2017-2018 school year. As Knuth wrote in the preface
* to Selected Papers on Fun & Games (2011):
*
* “All work and no play makes jack.” ... Thank goodness for mathematics
* and computer science, whose methods offer many ways by which our left
* brains and our right brains can both be happy, simultaneously.
*
* So let's have some fun! First, I'd like to introduce you to a few friends who always
* hang out in the library.
*/
import java.util.Collections;
import java.util.Collection;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Stack;
import java.util.List;
/****************/
/* 1. UTILITIES */
/****************/
// A couple of tools will be useful.
class Error
{
public static boolean print(String message)
{
System.out.println("Error: " + message + ".");
return false;
}
}
class Tokens
{
public static final Token NO_TOKEN = new ElementaryToken('-');
public static boolean isNoToken(Token token) { return token == Tokens.NO_TOKEN; }
}
/*************/
/* 2. TOKENS */
/*************/
// Tokens keep track of who's where, like the Xs and Os in a game of Tic-Tac-Toe
// or the black and white stones in a game of Go.
interface Token
{
Character symbol();
}
interface PlaceableToken extends Token
{
int index();
int row();
int column();
boolean putAt(int i);
boolean belongsOn(Grid grid);
boolean isOn(Grid grid);
}
interface ErasableToken extends PlaceableToken
{
boolean erase();
}
interface NonErasableMoveableToken extends PlaceableToken
{
boolean moveTo(int i);
}
interface VersatileToken extends ErasableToken, NonErasableMoveableToken
{
}
/** The essence of a token.
*/
class ElementaryToken implements Token
{
private final Character symbol;
public ElementaryToken(Character c)
{
this.symbol = c;
}
public final Character symbol()
{
return symbol;
}
public String toString()
{
return symbol.toString();
}
}
/** A token that is married to a single grid and cannot be placed elsewhere.
*/
class MonogamousPlaceableToken extends ElementaryToken implements PlaceableToken
{
protected final TokenGrid grid;
protected int index;
public MonogamousPlaceableToken(Character symbol, TokenGrid grid)
{
super(symbol);
this.grid = grid;
this.index = Grid.OFF_GRID;
}
public final int index()
{
return this.index;
}
public final int row()
{
return this.index / grid.columnCount();
}
public final int column()
{
return this.index % grid.columnCount();
}
public final boolean isPlaced()
{
return this.grid.isGridIndex(this.index);
}
public final boolean isOn(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 putAt(int i)
{
if (this.isPlaced())
return Error.print("Token is in place at " + this.index);
if (!grid.isGridIndex(i))
return Error.print("Invalid index: " + i);
if (!Tokens.isNoToken(grid.get(i)))
return Error.print("Another token is at " + i);
this.index = i;
if (!grid.place(this))
this.index = Grid.OFF_GRID;
return this.index != Grid.OFF_GRID;
}
}
/** A monogamous token that can be placed, erased, or moved.
*/
final class MonogamousVersatileToken extends MonogamousPlaceableToken
implements VersatileToken
{
public MonogamousVersatileToken(Character symbol, TokenGrid grid)
{
super(symbol, grid);
}
public final boolean erase()
{
if (!this.isPlaced())
return Error.print("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.print("Placed token not erased");
return putAt(i);
}
}
/************/
/* 3. GRIDS */
/************/
// Our game boards are grids, and these grids are our boards. Grids are
// where the tokens go. (Are you bored yet?)
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);
}
/** Like the name suggests: a fixed-size rectangular grid.
*/
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;
}
}
/** A fixed-size rectangular grid that may contain tokens.
*/
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))
return Error.print("Attempt to place no token");
if (!token.isOn(this))
return Error.print("Token has not been placed on grid");
final int i = token.index();
if (!Tokens.isNoToken(this.get(i)))
return Error.print("A token is already at " + i);
tokens[i] = token;
return true;
}
public final boolean erase(int i, ErasableToken token)
{
if (Tokens.isNoToken(token))
return Error.print("Attempt to erase no token");
if (token.isOn(this))
return Error.print("Token has not been erased");
if (this.get(i) != token)
return Error.print("Token found does not match");
tokens[i] = Tokens.NO_TOKEN;
return true;
}
public String toString()
{
StringBuilder sb = new StringBuilder();
sb.append(this.heading + "\n\n ");
Character ch = FIRST_COL_HEADER;
for (int col = 0; col < this.columnCount(); col++) {
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();
}
}
// All aboard! Next stop: PLAYERS ...
/**************/
/* 4. PLAYERS */
/**************/
// Players move their tokens around. Some players make their own tokens too!
interface Player
{
boolean placeTokenAt(int i);
boolean eraseTokenAt(int i);
boolean moveToken(int from, int to);
}
/** Makes a specified number of its own tokens.
*/
class VersatileTokenMaker
{
private final Character symbol;
protected final Stack<VersatileToken> tokenStack = new Stack<VersatileToken>();
public VersatileTokenMaker(int n, Character symbol, TokenGrid grid)
{
this.symbol = symbol;
while (n-- > 0)
tokenStack.push(new MonogamousVersatileToken(symbol, grid));
}
public String toString()
{
StringBuilder sb = new StringBuilder();
sb.append(this.symbol);
return sb.toString();
}
}
/** Makes own tokens and can put, erase, or move them on a particular grid.
*/
class VersatileTokenMakerMover extends VersatileTokenMaker implements Player
{
private final ImmutableTokenGrid grid;
public VersatileTokenMakerMover(int n, Character symbol, TokenGrid grid)
{
super(n, symbol, grid);
this.grid = grid;
}
public final boolean placeTokenAt(int i)
{
if (tokenStack.empty())
return Error.print("Player out of tokens");
return tokenStack.pop().putAt(i);
}
public final boolean eraseTokenAt(int i)
{
if (!grid.isGridIndex(i))
return Error.print("Invalid index " + i);
Token token = grid.get(i);
if (Tokens.isNoToken(token))
return Error.print("No token to erase");
if (!((ErasableToken)token).erase())
return Error.print("Failed to erase");
tokenStack.push((VersatileToken)token);
return true;
}
public final boolean moveToken(int from, int to)
{
if (!grid.isGridIndex(from))
return Error.print("Invalid index: " + from);
if (!grid.isGridIndex(to))
return Error.print("Invalid index: " + to);
Token token = grid.get(from);
if (Tokens.isNoToken(token))
return Error.print("No token to move");
return ((VersatileToken)token).moveTo(to);
}
}
/**************************************/
/* 5. CONNECTED TOKENS COUNTER/TESTER */
/**************************************/
// Here's a long row to hoe: telling when K tokens are aligned in a row.
interface ElementTester
{
boolean isOneOfKInARow(int i);
}
final class MatchingTokenCounterTester implements ElementTester
{
private final TokenGrid grid;
private final int M, N, K, upper, lower = 0;
private final Character VOID = Tokens.NO_TOKEN.symbol();
public MatchingTokenCounterTester(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 symbol(int i) { return grid.get(i).symbol(); }
/** Indicates whether the token at index i is one of K matching tokens in a row.
*
* Considers a horizontal, a vertical, and two diagonal rows.
*/
public boolean isOneOfKInARow(int i)
{
return EW(i) >= K || NS(i) >= K || NWSE(i) >= K || NESW(i) >= K;
}
// NEXT: The tricky counting methods...
/** Counts matching tokens connected in a horizontal (east-west) row.
*/
public int EW(int index)
{
final int i = index, row = row(index);
final Character si = symbol(i);
if (si == VOID ) return 0;
int d, j, count = 1;
for (d = 1, j = i - d;
j >= lower && count <= K && si == symbol(j) && row(j) == row;
d++, j = i - d, count++);
for (d = 1, j = i + d;
j < upper && count <= K && si == symbol(j) && row(j) == row;
d++, j = i + d, count++);
return count;
}
/** Counts matching tokens connected in a vertical (north-south) row.
*/
public int NS(int index)
{
final int i = index, col = col(i);
final Character si = symbol(i);
if (si == VOID ) return 0;
int d, j, count = 1;
for (d = 1, j = i - (d * M);
j >= lower && count <= K && si == symbol(j) && col(j) == col;
d++, j = i - (d * M), count++);
for (d = 1, j = i + (d * M);
j < upper && count <= K && si == symbol(j) && col(j) == col;
d++, j = i + (d * M), count++);
return count;
}
/** Counts matching tokens connected in a diagonal (NW-SE) row.
*/
public int NWSE(int index)
{
final int i = index, row = row(i), col = col(i);
final Character si = symbol(i);
if (si == VOID ) return 0;
int d, j, count = 1;
for (d = 1, j = i - (d * M) - d;
j >= lower && count <= K && si == symbol(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 && si == symbol(j) &&
row(j) == row + d && col(j) == col + d;
d++, j = i + (d * M) + d, count++);
return count;
}
/** Counts matching tokens connected in a diagonal (NE-SW) row.
*/
public int NESW(int index)
{
final int i = index, row = row(i), col = col(i);
final Character si = symbol(i);
if (si == VOID ) return 0;
int d, j, count = 1;
for (d = 1, j = i - (d * M) + d;
j >= lower && count <= K && si == symbol(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 && si == symbol(j) &&
row(j) == row + d && col(j) == col - d;
d++, j = i + (d * M) - d, count++);
return count;
}
}
/************/
/* 6. GAMES */
/************/
// It's all Fun & Games...
interface Game
{
public void play();
}
// ... of a certain sort: https://en.wikipedia.org/wiki/M,n,k-game
/* P,q,s,t-M,n,k-Games?
*
* Don't be afraid to think outside the M,n,k-box. Erasing yields Go. What about P
* Players? (Why only two?) Or a Quota Q of moves? Maybe the first player should
* Start with S tokens to be more fair? What if each player had a Total of T tokens
* to put? When they're all in play, they'd have to move. Use your imagination!
*
* See: https://en.wikipedia.org/wiki/Games_played_with_Go_equipment
*
*/
/** Tic-Tac-Toe
*
* Three in a row.
*
* See also: https://www.webofstories.com/play/donald.knuth/22
*/
final 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 ElementTester tester = new MatchingTokenCounterTester(K, grid);
private final int X_TOK_CNT = (MAX_TURNS / 2) + (MAX_TURNS % 2);
private final int O_TOK_CNT = MAX_TURNS / 2;
private final Player playerX = new VersatileTokenMakerMover(X_TOK_CNT, 'X', grid);
private final Player playerO = new VersatileTokenMakerMover(O_TOK_CNT, 'O', grid);
private Player currentPlayer = playerX;
private final List<Integer> plannedMoves = new ArrayList<Integer>(MAX_TURNS);
private final List<Integer> actualMoves = new ArrayList<Integer>(MAX_TURNS);
/** Prepare to play a game consisting of the moves provided.
*/
public TicTacToeGame(List<Integer> moves)
{
for (Integer i : moves)
{
plannedMoves.add(i);
if (plannedMoves.size() == MAX_TURNS)
break;
}
}
/** Prepare to play a complete game consisting of pseudo-random moves.
*/
public TicTacToeGame()
{
for (int i = 0; i < MAX_TURNS; i++)
plannedMoves.add(i);
Collections.shuffle(plannedMoves);
}
public final void play()
{
int turnsTaken = 0;
for (Integer i : plannedMoves)
{
if (!currentPlayer.placeTokenAt(i))
{
output(currentPlayer.toString() + " tried to make a bad move.");
return;
}
actualMoves.add(i);
if (tester.isOneOfKInARow(i))
{
output(currentPlayer.toString() + " won!");
return;
}
currentPlayer = currentPlayer == playerX ? playerO : playerX;
turnsTaken++;
}
output(turnsTaken == MAX_TURNS ? "Cats game." : "Game in progress.");
}
private void output(String message)
{
System.out.println(grid);
System.out.println(message);
System.out.print("Moves made: ");
System.out.println(actualMoves);
}
}
/** Connect-4
*
* Left as an exercise: Four in a row.
*
* (Don't defy gravity!)
*
* See: https://en.wikipedia.org/wiki/Connect_Four
*/
final class ConnectFourGame implements Game
{
/* The parameter named moves in the constructor below
* should contain up to N x M integers (e.g. 6 x 7 = 42)
* each of which should be greater than or equal to zero
* and less than M. Duplicates are expected. The numbers
* identify columns into which tokens are placed.
*/
public ConnectFourGame(List<Integer> moves)
{
}
public ConnectFourGame()
{
}
public void play()
{
}
}
/******************/
/* 7. LET'S PLAY! */
/******************/
// Got game? Let's play!
public class PlayGame
{
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] + ".");
}
}
