Quarto is board game for two players. The game is played on a board with 16 cells that are arranged in a $$4 \times 4$$ grid.

There are 16 pieces to play with, each of which has four distinguishing features. For example:

• size: big or small

• color: red or blue

• form: square or circular

• fill: hollow or solid

Features and properties may differ between various editions of the game.

At the start of the game, all pieces are alongside of the board. The first player is drawn randomly. He selects one of the 16 pieces and gives it to his opponent. He must place the piece on any cell of the board, then select one of the 15 remaining pieces alongside of the board and give it to his opponent. He in turn places the piece on any of the free cells of the board, and so on.

The winner is the first player to form a quarto. This is a row on the board with 4 pieces that share a common property. Such a row can be formed horizontally, vertically or diagonally. It may well be that more than one quarto is formed on a board, and 4 pieces in the same row may even share more than one common property. If all pieces have been placed on the board without forming a quarto, the game ends in a draw.

Quarto is distinctive from other board games in that there is only one set of common pieces, rather than a set for one player and a different set for the other.

Assignment

The features and properties of the 16 pieces used in a game of  Quarto are described in a text file. Each line of the file consists of 5 comma-separated fields (,). The fields themselves never contain commas. The header line consists of a field containing the word piece, followed by four fields containing the four distinguishing features of the pieces. This is followed by 16 lines, each describing a single piece. The first field contains the unique character that is used to represent the piece. The other fields are the four properties of the piece for the corresponding features. The same property never describes multiple features. Such a text file would for example look like this:

piece,size,color,form,fill
A,big,red,square,hollow
B,small,red,square,hollow
C,big,blue,square,hollow
D,small,blue,square,hollow
E,big,red,circular,hollow
F,small,red,circular,hollow
G,big,blue,circular,hollow
H,small,blue,circular,hollow
I,big,red,square,solid
J,small,red,square,solid
K,big,blue,square,solid
L,small,blue,square,solid
M,big,red,circular,solid
N,small,red,circular,solid
O,big,blue,circular,solid
P,small,blue,circular,solid

The pieces described in the above text file have four distinguishing features: size, color, form and fill. The size feature distinguishes two properties: big and small. The color feature distinguishes two properties: red and blue. The form feature distinguishes two properties: square and circular. The fill feature distinguishes two properties: hollow and solid.

The configuration of the pieces on a board is described by a 16-character string (str). These characters describe the pieces that are on the cells of the board, read from top to bottom and from left to right. A character that matches the unique character of a piece represents that piece (such characters appear only once in the description of the configuration). A character that does not match a unique character of a piece represents an empty cell (such characters may appear more than once in the description of the configuration).

Your task:

• Write a function read_pieces that takes the location (str) of a text file describing the features and properties of the pieces on a board. The function must return a dictionary (dict) that maps each feature (str) from the file onto a dictionary (dict) that maps the properties (str) of the feature onto a set with the unique characters (str) of all pieces having that property. Below — underneath the interactive session — is the dictionary that the function read_pieces returns for the text file that we used as an example above.

• Write a function piece_properties that takes a dictionary (dict) with the features and properties of the pieces on a board (structured as the dictionaries returned by the function read_pieces). The function must return a dictionary (dict) that maps the unique character (str) of each piece onto the set with all properties (str) of the piece.

• Write a function create_grid that takes two arguments: i) the configuration of the pieces on a board and ii) a dictionary (dict) with the properties of the pieces on the board (structured as the dictionaries returned by the function piece_properties). The function must return a representation of the grid consisting of a list in which the horizontal rows of the grid are listed from top to bottom. Each row is itself represented as a list in which the cells are listed from left to right. Each cell containing a piece is represented as a set containing the properties of that piece. Each cell that does not contain a piece is represented as an empty set.

• Write a function quarto that takes the same two arguments as the function create_grid. The function must return a set containing all rows of the board with 4 pieces that share a common property. Such a row is represented as a tuple with two elements: i) a description of the position of the row and ii) the common property of the four pieces on that row. Horizontal rows are described as H$$i$$ ($$i = 1, \ldots, 4$$), with the rows numbered from top to bottom. Vertical rows are described as V$$i$$ ($$i = 1, \ldots, 4$$), with the columns numbered from left to right. The main diagonal (top left to bottom right) is described as D1 and the antidiagonal (top right to bottom left) as D2.

  Note

  If the four pieces in a row share multiple common properties, there must be a tuple in the set returned by the function quarto for each common property. These share the same first element (the position of the row), but differ in the property that comes as a second element.

Example

In the following interactive session we assume the text file pieces.txt¹ to be located in the current directory. This is the text file containing the features and properties of the pieces on the game board that was used as an example above.

>>> pieces = read_pieces('pieces.txt')
>>> pieces['size']['big']
{'A', 'C', 'E', 'G', 'I', 'K', 'M', 'O'}
>>> pieces['color']['red']
{'A', 'B', 'E', 'F', 'I', 'J', 'M', 'N'}

>>> properties = piece_properties(pieces)
>>> properties['E']
{'big', 'circular', 'hollow', 'red'}
>>> properties['K']
{'big', 'blue', 'solid', 'square'}
>>> properties['O']
{'big', 'blue', 'circular', 'solid'}

>>> create_grid('N?BI??JO?FDLMEAG', properties)
[[{'small', 'circular', 'solid', 'red'}, set(), {'small', 'hollow', 'square', 'red'}, {'solid', 'square', 'big', 'red'}], [set(), set(), {'small', 'solid', 'square', 'red'}, {'circular', 'blue', 'big', 'solid'}], [set(), {'small', 'circular', 'hollow', 'red'}, {'small', 'hollow', 'blue', 'square'}, {'small', 'blue', 'square', 'solid'}], [{'circular', 'solid', 'big', 'red'}, {'circular', 'hollow', 'big', 'red'}, {'hollow', 'square', 'big', 'red'}, {'circular', 'blue', 'hollow', 'big'}]]
>>> create_grid('KHEF#DCMXABJPGOL', properties)
[[{'blue', 'big', 'solid', 'square'}, {'blue', 'circular', 'hollow', 'small'}, {'red', 'big', 'circular', 'hollow'}, {'red', 'circular', 'hollow', 'small'}], [set(), {'blue', 'hollow', 'small', 'square'}, {'blue', 'big', 'hollow', 'square'}, {'red', 'big', 'circular', 'solid'}], [set(), {'red', 'big', 'hollow', 'square'}, {'red', 'hollow', 'small', 'square'}, {'red', 'solid', 'small', 'square'}], [{'blue', 'solid', 'circular', 'small'}, {'blue', 'big', 'circular', 'hollow'}, {'blue', 'big', 'circular', 'solid'}, {'blue', 'solid', 'small', 'square'}]]

>>> quarto('N?BI??JO?FDLMEAG', properties)
{('H4', 'big'), ('V3', 'square'), ('D2', 'red')}
>>> quarto('KHEF#DCMXABJPGOL', properties)
{('H4', 'blue'), ('V2', 'hollow'), ('D1', 'square')}

In the interactive session, the variable pieces refers to the following dictionary (dict):

{
    'size': {
        'big': {'A', 'C', 'E', 'G', 'I', 'K', 'M', 'O'},
        'small': {'B', 'D', 'F', 'H', 'J', 'L', 'N', 'P'}
    },
    'color': {
        'red': {'A', 'B', 'E', 'F', 'I', 'J', 'M', 'N'},
        'blue': {'C', 'D', 'G', 'H', 'K', 'L', 'O', 'P'}
    },
    'form': {
        'square': {'A', 'B', 'C', 'D', 'I', 'J', 'K', 'L'},
        'circular': {'E', 'F', 'G', 'H', 'M', 'N', 'O', 'P'}
    },
    'fill': {
        'hollow': {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'},
        'solid': {'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P'}
    }
}

These are the two configurations of pieces on the game board that are passed to the functions make_grid and quarto in the interactive session.