31
2
Challenge description
Dominoes is a game played with tiles with two values on it - one on the left, one on the right, for example [2|4]
or [4|5]
. Two tiles can be joined together if they contain a common value. The two tiles above can be joined like this:
[2|4][4|5]
We'll call a sequence of n
joined tiles a chain of length n. Of course, tiles can be rotated, so tiles [1|2]
, [1|3]
and [5|3]
can be rearranged into a chain [2|1][1|3][3|5]
of length 3.
Given a list of pairs of integers, determine the length of the longest chain that can be formed using these tiles. If the list is empty, the correct answer is 0
(note that you can always form a chain of length 1
from a non-empty list of tiles).
Sample input / output
[(0, -1), (1, -1), (0, 3), (3, 0), (3, 1), (-2, -1), (0, -1), (2, -2), (-1, 2), (3, -3)] -> 10
([-1|0][0|-1][-1|2][2|-2][-2|-1][-1|1][1|3][3|0][0|3][3|-3])
[(17, -7), (4, -9), (12, -3), (-17, -17), (14, -10), (-6, 17), (-16, 5), (-3, -16), (-16, 19), (12, -8)] -> 4
([5|-16][-16|-3][-3|12][12|-8])
[(1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1)] -> 7
([1|1][1|1][1|1][1|1][1|1][1|1][1|1])
[(0, 1), (2, 3), (4, 5), (6, 7), (8, 9), (10, 11)] -> 1
(any chain of length 1)
[] -> 0
(no chain can be formed)
Any restrictions on running time or memory? Think brute-forcing all permutations – Luis Mendo – 2017-01-03T16:09:22.233
3@LuisMendo: Pretty sure this problem is NP, so fire up your
O(n!)
as you wish – shooqie – 2017-01-03T16:28:16.650I guess it's P
– l4m2 – 2017-12-27T13:59:21.867