Solution 7
From Beautifulcode
Contents |
Solution 7
The Assumptions
The original problem was well specified, but there were areas that were unspecified. Therefore I make the following assumptions:
- The language is C++
- The participant are not malicious. Frankly if we have malicious code in a thread in our process all is lost.
Design
Overview
We design a set of interfaces which are visible to the IPlayScrabble interface:
- ITileset - Holds the tiles available to the player
- IBoard - A Board where the player can place there solution for validation
- IReferee - The interface to the referee the player calls to ask for validation
The Referee determines the number of players playing, and creates a tileset for each player. The tileset will contain all 15 tiles from the start, just like in the real game, but only 7 tiles will initially be available to the player. If the player request a tile before it is ready, the tileset will return the '\0' character.
Next the referee will create a thread for each player. The thread will load the player's interface, create a board for the player to use, and call the solve function.
In summary the referee has X player threads, X boards, X tilesets, and the current number of tiles available to all players. The referee now waits for all the player threads to terminate.
The current number of tiles available is a singlton which is shared by all of the tileset implementations. It is guarded by a mutex for all access. (Or on windows you can use the interlocked family of function if you want to really worry about speed).
TileSet::getCurrentTiles()
{
CriticalSection cs(tileMutex); //locks the mutex
return g_CurrentTileCount;
} // Leaving the scope releases the mutex
As each player solves the board they can at any time decide to grab the next tile, or if they prefer just keep tabs on the current tile count. When they believe they have a solution for their current number of tiles they call Go().
int Go(IBoard* board)
{
CriticalSection cs(refMutex); // lock
BoardImpl* bi = ConvertBoard(board);
boardTiles = bi.getCount();
currentTiles = getCurrentTiles();
if (boardTiles > currentTiles)
return 0; // Are they cheating or did they make a mistake either way the board is invalid.
else boardTiles < currentTiles)
return -1; // They were too late.
else
{
// Validate the board
if (/* Board is valid */)
{
incrementCurrentTiles(); // increment the global tile count
if (getCurrentTiles() == 15)
{
// Declare a winner!
// Set Tile count to -1;
}
}
}
} // Leaving the scope of the function releases the lock on the refMutex.
Interfaces
ITileSet
Methods:
- char GetTile(index)
- Get the tile at index, Return '\0' if index is out of range.
- int GetTileCount
- Get the number of tiles available, return -1 if the game is over.
IBoard
Methods:
- void PlaceTile(int x, int y, char tile)
- Place a tile at the specified coordinates.
- char GetTile(int x, int y)
- Get the tile at the specified coordinates. Return '\0' if no tile is present.
- void RemoveTile(intx, int y)
- Remove the tile at the specified coordinates.
- void ClearBoard()
- Clear the board of all tiles.
IReferee
Methods:
- int Go(IBoard* board)
- Ask the referee to validate the board 1 for valid, 0 for invalid, -1 for too late.
IPlayScrabble
Methods:
- bool Solve(ITileSet* ts, IReferee* ref)
- Tell the players code to start solving.
Helper Classes
CriticalSection
This is a class designed to keep us from accidentally holding mutex beyond our desired scope.
- On construction grabs the mutex lock.
- On destruction releases the mutex lock.
{ // begin scope
CriticalSection cs(myMutex); // acquires the lock
... // do work
} // Releases the lock
Why I believe my solution works
There are no possible dead locks, and the Players code can only interact with the referee when they submit a board. No player will ever be blocked waiting on a tile.
What makes it beautiful
This is the simplest solution with the smallest number of possible threads and synchronization primitives (that I know of), and correctly implements all the requirements of the challenge.
