PROB6: TRIOMINOS

Determine the validity of a sequence of triominos plays.

DESCRIPTION

Fig. 1: Triominos board layout. N1 is the location for the first play. Grey triangles are considered "upward" and white triangles are considered "downward".

Fig. 2: Board after seven legal plays. Note that all pieces have adjacent edges and matching values on vertices. The turn of the play is written as 'a', 'b', 'c', ..., 'g' on the center of the piece.

The game of triominos is played on a board of infinite extent which follows the pattern shown in figure 1. There are 76 triangular play pieces with a digit on each vertex. The digits are in the range 0 through 5 with possible repetition on a given game piece. The 76 pieces represent all possible vertex labels up to a rotation of the piece.

Some example pieces, reading the vertex values clockwise would be "000", "010" and "025". Note, however, that "250" and "502" are simply rotations of the single piece "025". This means that "250" and "502" cannot both be played in the same game: they are the same piece.

Play proceeds as follows: The first piece is drawn at random and placed on the board at location "N1." After this, play proceeds in turns. Each player places a piece so that:


(1) The piece has at least one edge adjacent to the edge of another piece already on the board.

(2) The piece matches all vertex values of adjacent vertices.



We can ignore the particulars of the remaining rules of the game.

The point of this problem is, given a sequence of plays, you are to determine if they represent valid plays of the game in three respects:


(1) The placement of pieces follows the above rules.

(2) No piece is used more than once

(3) No space is occupied more than once.

INPUT: prob6.dat

The input file will contain one or more sequences of plays. Each sequence of plays will be separated by a single blank line. Each particular play is written in the form:


LOCATION PIECE


LOCATION is the label for the location where the piece is played. For example, the first play should always be "N1" (without the quotes). The offset values in the location name will never exceed 100. For example, neither S1E107 nor N223W33 will appear in the input file.

PIECE is the listing of the digits of the vertices of the piece written in clockwise order. The first vertex written is the top-most vertex for an "upward" triangle, and the bottom-most vertex for a "downward" triangle.

For example, an input file representing the plays given in figure 2, followed by the same pieces with plays 'c' and 'd' transposed is:

       column   1
       1234567890
line 1:N1 403[EOL]
     2:S1 230[EOL]
     3:N1E1 044[EOL]
     4:N1E2 430[EOL]
     5:N1E3 341[EOL]
     6:S1E2 203[EOL]
     7:S1E1 022[EOL]
     8:[EOL]
     9:N1 403[EOL]
    10:S1 230[EOL]
    11:N1E2 430[EOL]
    12:N1E1 044[EOL]
    13:N1E3 341[EOL]
    14:S1E2 203[EOL]
    15:S1E1 022[EOL]
      :[EOF]

Note that the first sequence of plays represents a legal sequence of plays, while the second one does not. This is because the third move in the second sequence is not edge-adjacent to any previous play.

OUTPUT: prob6.out

Other than the standard leader and trailer, the output file simply has the word "valid" or "invalid" on separate lines for each play sequence in the input file.

The correct output corresponding to the example input file would be:

       column   111111111122222222223
       123456789012345678901234567890
line 1:Program 6 by team 0[EOL]
     2:valid[EOL]
     3:invalid[EOL]
     4:End of program 6 by team 0[EOL]
      :[EOF]