Created
November 3, 2022 06:31
-
-
Save MishaelRosenthal/e897dc43f45cfa1d109a368951839a18 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
object CellState extends Enumeration { | |
type CellState = Value | |
val X, O, EMPTY = Value | |
} | |
import CellState._ | |
object GameStatus extends Enumeration { | |
type GameStatus = Value | |
val X_WON, O_WON, DRAW, NOT_DECIDED = Value | |
} | |
import GameStatus._ | |
type Triplet = Vector[CellState] | |
type Game = Vector[Triplet] | |
val emptyTriplet = Vector(EMPTY, EMPTY, EMPTY) | |
val xTriplet = Vector(X, X, X) | |
val oTriplet = Vector(O, O, O) | |
val emptyGame = Vector(emptyTriplet, emptyTriplet, emptyTriplet) | |
def checkTriplet(triplet: Triplet): GameStatus = { | |
if (triplet == xTriplet) | |
X_WON | |
else if (triplet == oTriplet) | |
O_WON | |
else | |
NOT_DECIDED | |
} | |
def diagonals(game: Game): Seq[Triplet] = Seq( | |
Vector(game(0)(0), game(1)(1), game(2)(2)), | |
Vector(game(0)(2), game(1)(1), game(2)(0)) | |
) | |
def whoWon(game: Game) = { | |
val transposed = game.transpose | |
val triplets = | |
game ++ transposed ++ diagonals(game) | |
val results = for { triplet <- triplets } yield checkTriplet(triplet) | |
if (results.contains(X_WON)) | |
X_WON | |
else if (results.contains(O_WON)) | |
O_WON | |
else if (game.flatten.contains(EMPTY)) | |
NOT_DECIDED | |
else | |
DRAW | |
} | |
def game2String(game: Game): String = { | |
def row2String(row: Triplet): String = { | |
row.map(cell => if (cell == EMPTY) " " else cell).mkString("|") | |
} | |
game.flatMap(row => List("-+-+-", row2String(row))).tail.mkString("\n") | |
} | |
def otherTurn(turn: CellState): CellState = if (turn == X) O else X | |
def remainingCells(game: Game): Seq[(Int, Int)] = { | |
for { | |
i <- game.indices | |
j <- game(i).indices | |
if game(i)(j) == EMPTY | |
} yield (i, j) | |
} | |
def updateGame(game: Game, i: Int, j: Int, turn: CellState) = | |
game.updated(i, game(i).updated(j, turn)) | |
def solveGameHelper(game: Game, turn: CellState): GameStatus = { | |
val winner = whoWon(game) | |
if (winner != NOT_DECIDED) winner | |
else { | |
val statuses = remainingCells(game).map { case (i, j) => | |
solveGameHelper(updateGame(game, i, j, turn), otherTurn(turn)) | |
} | |
if (turn == X) { | |
if (statuses.contains(X_WON)) { | |
X_WON | |
} else if (statuses.contains(DRAW)) { | |
DRAW | |
} else { | |
O_WON | |
} | |
} else { | |
if (statuses.contains(O_WON)) { | |
O_WON | |
} else if (statuses.contains(DRAW)) { | |
DRAW | |
} else { | |
X_WON | |
} | |
} | |
} | |
} | |
println("if X starts he can force a " + solveGameHelper(emptyGame, X)) | |
def checkMoves(game: Game, turn: CellState) = { | |
println("-------------------------------------") | |
println("Given the game:") | |
println() | |
println(game2String(game)) | |
println() | |
println("And it is " + turn + "\'s turn") | |
println("-------------------------------------") | |
val remaining = remainingCells(game) | |
remaining.foreach { case (i, j) => | |
println("if " + turn + " plays") | |
println() | |
val newGame = updateGame(game, i, j, turn) | |
println(game2String(newGame)) | |
println() | |
println( | |
"" + otherTurn(turn) + " can force a " + solveGameHelper( | |
newGame, | |
otherTurn(turn) | |
) | |
) | |
println("-------------------------------------") | |
} | |
} | |
checkMoves(emptyGame, X) | |
checkMoves(Vector(Vector(X, EMPTY, EMPTY), emptyTriplet, emptyTriplet), O) | |
checkMoves(Vector(Vector(EMPTY, X, EMPTY), emptyTriplet, emptyTriplet), O) | |
checkMoves(Vector(emptyTriplet, Vector(EMPTY, X, EMPTY), emptyTriplet), O) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment