A set of dominoes consists of tiles with two numbers on them such that every combination of integers from 0 to N are represented. Examples below refer to N=6 out of convenience, but N=9 and N=12 are also common. The orientation of the tiles does not matter (they are usually printed with dots rather than digits), so
[6-1] refer to the same tile, of which there is only one in a set.
Most games played with dominoes involve players taking turns adding dominoes to a line of those already played onto the table, such that one of the numbers on the new domino is placed adjacent to the same number at one end of the line on the table. Thus, you might add a
[2-5] to either end of an existing line of
Many such games require "doubles", dominoes with two of the same number on them, to be placed perpendicular to the other dominoes connected to them. Aside from scoring which we are unconcerned with here, this has no effect except when...
Many of those games then allow the "line" to fork at some or all doubles. Five Up is such a game where the line can fork into 3 new lines at each double, so all four sides of a double might have a matching domino attached.
Here is an example layout of dominoes from a "double 6" set in a game of Five Up (where A|B or A-B is a single domino):
4 - 0 3|0 0|0 0|2 0 - 1 4|1 1|1 1|6 3 1 - - 6 5 6 6|5 5|5 5|0 0|6 - 6|2 2|1 6 5 - 6 4 - 4
Your task is to take an list of dominoes in the order in which they were added to the table, and determine whether or not this order represents a legal game of Five Up.
You can write a whole program that takes input from stdin, or a function that takes input as one or more parameters.
Canonical input would be a list or array of two-tuples of integers. A list of lists, array of arrays, vector of tuples, etc are all valid forms in which to take input, as would be a string representing any of the above, or multiple strings. The input will only contain pairs of non-negative integers, valid dominoes.
Output should be a truthy or falsey value, for valid and invalid games respectively.
Your code should accept arbitrarily large domino numbers, within the capabilities of the maximum integer values of your language.
0-6is valid, as is any other single domino
0-6 6-0is not valid, there is only one
0-6domino in a set
6-6 6-5 5-3 3-0is valid, a simple linear arrangement
6-6 6-5 3-0 5-3is not valid, there is no
0in play for the third domino to connect to prior to the
1-1 1-2 1-3 1-4 1-5 1-6is not valid, all four open
1ends are used up leaving nowhere to connect the
1-1 1-2 1-3 1-4 1-5 3-6 1-6is valid, the 3-6 connects to the 1-3, then the 1-6 can connect to the 3-6
5-5 5-4 5-0 0-6 6-6 6-4 6-2 2-1 6-3 5-1 1-1 1-6 4-1 1-0 0-0 2-0 3-0 0-4is valid, the above illustrated example
12-12 12-1 3-12 3-1 1-2 3-3is valid, uses larger dominoes, and has an ambiguous placement
NOTE: The function required here is not a perfect check for valid Five Up games. We are ignoring here the rules about which domino gets played first, which would require more information about the variant of the game and number of players, and would disqualify a significant minority of inputs.