SPOJ.com - Problem PROG0365

PROG0365 - Tic-tac-toe

no tags

Tic-tac-toe (also called Xs and Os or noughts and crosses) is a simple game for two players. It is played with paper and pencil on a $3 \times 3$ grid. Initially, all spaces in the grid are empty. One player marks spaces with crosses (here represented by the letter X) and the other player marks spaces with noughts (here represented by the letter O). Player in turn marks an empty space in the grid with their own symbol. The player who marks crosses always begins the game. The player who succeeds in placing three respective marks in a horizontal, vertical or diagonal row wins the game. If all places are filled up without any player winning, the game ends in a draw. The following game is won by the player marking crosses.

Players soon discovered that best play for both parties leads to a draw. Hence, tic-tac-toe is most often played by young children. Especially for beginners, the middle square is the most important square in the grid. In total there are 764 essentially different states of the grid, without taking into account the empty grid and without taking into account positions that are the same after rotation and/or mirroring the grid. There are 2096 valid ways players can mark empty spaces starting from the first mark and successive marks after that. As such, there are three possible opening marks: a mark in the middle, a mark in one of the corners and a mark in the middle of one of the borders.

Assignment

A given text file contains the configuration of a tic-tac-toe game that has just finished. The file contains three lines, each containing three characters. The possible characters are i) a space representing an empty space, ii) a letter X used as a marker by the first player, or iii) a letter O used as a marker by the second player. Your task is to determine which player has won the game. This is done in the following way:

Write a function readGrid that takes the location of a text file containing the configuration of a tic-tac-toe game as its argument. The function must read the information from the file, and return a list containing three strings. Each of these strings contains the three characters from the corresponding line in the text file.
Write a function showGrid that takes the configuration of the grid after having played a tic-tac-toe game. This configuration is represented as a list taking the form of the lists returned by the function readGrid. The function showGrid must return a string containing a formatted representation of the given configuration. The formatted string must contain three lines, representing the rows of the grid. The columns of the grid are separated by a single space in the formatted string. Empty space are represented by a dot (.).
Write a function winner that takes the configuration of the grid after having played a tic-tac-toe game. This configuration is represented as a list taking the form of the lists returned by the function readGrid. The function must return the string X wins if the player marking crosses has won the game, the string O wins if the player marking noughts has won the game, and the string draw if the game has ended in a draw.

Example

In the following interactive session we assume that the text files tictactoe1.txt, tictactoe2.txt and tictactoe3.txt are located in the current directory.

>>> readGrid('tictactoe1.txt')
['OX ', 'OX ', ' X ']
>>> readGrid('tictactoe2.txt')
['OOO', ' XX', 'X  ']
>>> readGrid('tictactoe3.txt')
['XXO', 'OOX', 'XOX']

>>> print(showGrid(['OX ', 'OX ', ' X ']))
O X .
O X .
. X .
>>> showGrid(['OX ', 'OX ', ' X '])
'O X .\nO X .\n. X .'
>>> print(showGrid(['XXO', 'OOX', 'XOX']))
X X O
O O X
X O X

>>> winner(['OX ', 'OX ', ' X '])
'X wins'
>>> winner(['OOO', ' XX', 'X  '])
'O wins'
>>> winner(['XXO', 'OOX', 'XOX'])
'draw'

Boter-kaas-en-eieren (ook wel oo maal oo of kruisje nulletje genoemd) is een eenvoudig spel voor twee spelers. Het wordt met potlood en papier gespeeld op een $3 \times 3$ rooster. Bij aanvang zijn alle velden leeg. Een speler zet kruisjes (hier voorgesteld door de letter X) en de andere speler zet rondjes (hier voorgesteld door de letter O). De spelers zetten om beurt elk hun eigen symbool op één van de lege velden van het rooster. De speler die kruisjes zet mag altijd beginnen. Degene die drie van zijn eigen symbolen op een rij heeft (diagonaal, verticaal of horizontaal) heeft gewonnen. Als alle veldjes ingevuld zijn zonder dat één van de spelers wint, dan eindigt het spel in een gelijkspel. Het volgende spelletje werd bijvoorbeeld gewonnen door de speler die kruisjes zet.

Voor iemand die het spel goed genoeg kent, is het eenvoudig om ieder spel in een gelijkspel te laten eindigen, ongeacht wat de tegenstander doet. Zeker voor beginners is het veld in het midden het belangrijkste veld. Er zijn in totaal 764 mogelijke bordposities, zonder daarbij het lege bord mee te rekenen en zonder posities dubbel te rekenen die door roteren of spiegelen hetzelfde zijn. Er zijn in totaal 2096 zetten toegestaan vanaf de eerste zet en daarna tussen de opeenvolgende bordposities. Zo zijn er drie verschillende openingszetten mogelijk: in het midden, in een hoek of in het midden van een rand.

Opgave

Een gegeven tekstbestand bevat de configuratie van een spelletje boter-kaas-en-eieren dat net is afgelopen. Het bestand bestaat uit drie regels, die elk drie karakters bevatten. De mogelijke karakters zijn i) een spatie die staat voor een leeg veld, ii) een letter X die is neergezet door de eerste speler, of iii) een letter O die is neergezet door de tweede speler. Aan jou de vraag om te bepalen welke speler gewonnen heeft. Hiervoor ga je als volgt te werk:

Schrijf een functie leesBord waaraan de locatie van het tekstbestand met de configuratie van een spelletje boter-kaas-en-eieren als argument moet doorgegeven worden. De functie moet de informatie uit het bestand inlezen, en een lijst teruggeven die drie strings bevat. Elk van deze strings bevat de drie karakters uit de overeenkomstige regel in het gegeven tekstbestand.
Schrijf een functie toonBord waaraan de configuratie van het rooster na een spelletje boter-kaas-en-eieren moet doorgegeven worden. Deze configuratie wordt voorgesteld als een lijst die de vorm aanneemt van de lijsten zoals die door de functie leesBord teruggegeven worden. De functie toonBord moet een string teruggeven die een opgemaakte weergave de gegeven configuratie voorstelt. Hiervoor moet de string bestaan uit drie regels, die de rijen van het rooster voorstellen. De kolommen van het rooster moeten in de string van elkaar gescheiden door een spatie. Lege veldjes moeten voorgesteld worden door een punt (.).
Schrijf een functie winnaar waaraan de configuratie van het rooster na een spelletje boter-kaas-en-eieren moet doorgegeven worden. Deze configuratie wordt voorgesteld als een lijst die de vorm aanneemt van de lijsten zoals die door de functie leesBord teruggegeven worden. De functie moet de string X wint teruggeven als de speler die kruisjes zet het spel heeft gewonnen, de string O wint als de speler die rondjes zet het spel heeft gewonnen, en de string gelijkspel als het spel geëindigd is op een gelijkspel.

Voorbeeld

Bij onderstaande voorbeeldsessie gaan we ervan uit dat de tekstbestanden tictactoe1.txt, tictactoe2.txt en tictactoe3.txt zich in de huidige directory bevinden.

>>> leesBord('tictactoe1.txt')
['OX ', 'OX ', ' X ']
>>> leesBord('tictactoe2.txt')
['OOO', ' XX', 'X  ']
>>> leesBord('tictactoe3.txt')
['XXO', 'OOX', 'XOX']

>>> print(toonBord(['OX ', 'OX ', ' X ']))
O X .
O X .
. X .
>>> toonBord(['OX ', 'OX ', ' X '])
'O X .\nO X .\n. X .'
>>> print(toonBord(['XXO', 'OOX', 'XOX']))
X X O
O O X
X O X

>>> winnaar(['OX ', 'OX ', ' X '])
'X wint'
>>> winnaar(['OOO', ' XX', 'X  '])
'O wint'
>>> winnaar(['XXO', 'OOX', 'XOX'])
'gelijkspel'

Submit solution!

Added by:	Peter Dawyndt
Date:	2013-04-03
Time limit:	10s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	PY_NBC
Resource:	None