Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
4 contributors

Users who have contributed to this file

@tonymorris @relrod @japgolly @spion
53 lines (35 sloc) 4.06 KB

TicTacToe

The goal is to write an API for the tic-tac-toe game. An API user, should be able to play a game of tic-tac-toe using this API, but importantly, it should be impossible for the API user to break the rules of the game. Specifically, if an attempt is made to break a rule, the API should reject the program. This is often done by way of a compile-time type error.

It is strongly advised that functional programming techniques are used to achieve the goal. This is because ensuring that the API adheres to the rules of tic-tac-toe, while rejecting a program otherwise, is difficult otherwise. No specific programming language is prescribed.

The following API functions should exist. By removing the need for some of these functions, the challenge becomes significantly easier. Removing some or all optional API functions is an advised path for someone who is looking to make the challenge easier.

  • move: takes a tic-tac-toe board and position and moves to that position (if not occupied) returning a new board. This function can only be called on a board that is empty or in-play. Calling move on a game board that is finished is a compile-time type error.

(optional) If fewer than 5 moves have been played, then this guarantees that the game is still in play, and so calling move will never produce a type-error in this case.

  • whoWon: takes a tic-tac-toe board and returns the player that won the game (or a draw if neither). This function can only be called on a board that is finished. Calling whoWon on a game board that is empty or in-play is a compile-time type error. As an optional consideration, whoWon should never be a draw if fewer than nine moves have been played. In the case that the game is completed, but fewer than nine moves have been played, return a value that can only be one of two possibilities (the winner) and never a draw.

  • playerAt: takes a tic-tac-toe board and position and returns the (possible) player at a given position. This function works on any type of board.

  • takeBack (optional): takes either a finished board or a board in-play that has had at least one move and returns a board in-play. It is a compile-time type error to call this function on an empty board.

  • isDraw (optional) if called on a game with fewer than 9 moves, a compile-time type-error results.

  • Other API functions that might be considered useful for general API use. Ensure that it is not possible to violate the game rules of tic-tac-toe. These functions can often be determined by also writing an interactive console application that uses the API -- other useful functions are likely to arise.

You should write automated tests for your API. For example, the following universally quantified property holds true:

forall Board b. forall Position p. such that (not (positionIsOccupied p b)). takeBack(move(p, b)) == b

You should encode this property in an automated specification test. For Scala, use ScalaCheck. For Haskell, QuickCheck. For Java, consider Functional Java. For .NET, use FsCheck. For other languages, you may need to search around.

Haskell-specific

If you choose to use Haskell, also take advantage of its tooling:

Extra-curricular

  • Write an opponent that never loses
  • Write an opponent with easy, medium, hard difficulty levels
You can’t perform that action at this time.