8
\$\begingroup\$

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 [1-6] and [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 [2-3][3-3][3-5], producing [5-2][2-3][3-3][3-5] or [2-3][3-3][3-5][5-2].

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.

Examples:

  • 0-6 is valid, as is any other single domino
  • 0-6 6-0 is not valid, there is only one 0-6 domino in a set
  • 6-6 6-5 5-3 3-0 is valid, a simple linear arrangement
  • 6-6 6-5 3-0 5-3 is not valid, there is no 3 or 0 in play for the third domino to connect to prior to the 5-3 being played
  • 1-1 1-2 1-3 1-4 1-5 1-6 is not valid, all four open 1 ends are used up leaving nowhere to connect the 1-6
  • 1-1 1-2 1-3 1-4 1-5 3-6 1-6 is 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-4 is valid, the above illustrated example
  • 12-12 12-1 3-12 3-1 1-2 3-3 is 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.

\$\endgroup\$
  • \$\begingroup\$ Do we need to account for geometric constraints on placement, i.e. the domino chain crashing into itself? \$\endgroup\$ – xnor Dec 27 '17 at 20:46
  • \$\begingroup\$ @xnor you do not. I forgot to mention the common convention that the "line" can bend arbitrarily for convenience in any game of dominoes. also good for avoiding table edges :) \$\endgroup\$ – Sparr Dec 27 '17 at 20:50
  • \$\begingroup\$ I think it might be possible to produce a pathological order of play with a double 12 set of dominoes that cannot avoid self intersection. It's definitely possible with larger sets. Let's just ignore those cases. Worst case, they can be solved by bending the line in 3D :) \$\endgroup\$ – Sparr Dec 27 '17 at 20:51
  • \$\begingroup\$ Do we actually need to be able to handle dominoes that have values >6? If so, could you make that clearer in the spec and maybe add a test case. Otherwise, though, nice challenge - +1 from me. \$\endgroup\$ – Shaggy Dec 27 '17 at 23:45
  • \$\begingroup\$ @Shaggy added a test case for a larger domino \$\endgroup\$ – Sparr Jan 11 '18 at 0:47
1
\$\begingroup\$

Haskell, 188 174 168 bytes

f(p:r)=[p]!r$p?p
(s!(p:r))o|b<-[p,reverse p]=or[(q:s)!r$q%o|q<-b,elem(q!!0)o,all(`notElem`s)b]
(s!_)o=1<3
p@[x,y]?r=[c|x==y,c<-p]++r
p@[x,y]%(a:r)|a/=x=a:p%r|z<-y:r=p?z

Try it online! Usage example: f [[6,6],[6,5],[5,3],[3,0]] yields True.

Ungolfed:

f :: [[Int]] -> Bool
f (p:r) = check [p] (double p p) r

check :: [[Int]] -> [Int] -> [[Int]] -> Bool
check seen open [] = True
check seen open ([x,y]:r) = 
	  notElem [x,y] seen
   && notElem [y,x] seen
   && (elem x open && check ([x,y]:seen) (update [x,y] open) r 
   ||  elem y open && check ([y,x]:seen) (update [y,x] open) r)

double :: [Int] -> [Int] -> [Int]
double [x,y] rest = 
    if x==y 
    then [x,y] ++ rest 
    else rest

update :: [Int] -> [Int] -> [Int]
update [x,y] (a:rest) = 
    if x==a 
    then double [x,y] (y:rest) 
    else a : update [x,y] rest

Try it online!

\$\endgroup\$
0
\$\begingroup\$

R, 224 bytes

function(L,x=c(),y=c()){o=T
z=length
if(z(L)){p=sort(L[1:2])
w=rep(p,2-(p[2]>p[1]))
x=rbind(p,x)
if(z(y)){m=match(p,y,0)
v=which.max(m)
if(m[v]>0){y=y[-m[v]]
w=w[-v]}}
y=c(y,w)
L=L[-1:-2]
o=o&f(L,x,y)&!sum(duplicated(x))}
o}

Try it online!

The code receives the pieces as an ordered list and returns TRUE or FALSE according to the specs. The function recursively scans every piece, adds the piece to an index to verify the absence of duplicates, and keeps track of the available insertion points to check that the piece can effectively be added to the stack. The handling of piece connections (e.g. attaching a 1-2 by the 1 or by the 2) is done in a greedy fashion, so it is not entirely impossible that some weird configurations may blow up.

\$\endgroup\$
  • \$\begingroup\$ unfortunately greediness isn't good enough. consider 6-6 6-3 6-2 2-3 you need to be able to handle this with 2-_ or 3-_ next because the 2-3 could have been placed at either end. \$\endgroup\$ – Sparr Jan 11 '18 at 0:49
  • \$\begingroup\$ I'll have a look. \$\endgroup\$ – NofP Jan 11 '18 at 10:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.