Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Domino Chain by kurosawa4434
from re import findall
def domino_chain(tiles: str) -> int:
domino = set(findall(r'(\d)-(\d)', tiles))
memo = {}
def search(num, rest):
if not rest:
return 1
m_key = frozenset({num} | rest)
if m_key in memo:
return memo[m_key]
subtotal = sum(search(r[num == r[0]], rest-{r}) for r in rest if num in r)
memo[m_key] = subtotal
return subtotal
total = 0
for d in domino:
total += search(d[0], domino-{d})
if d[0] != d[1]:
total += search(d[1], domino-{d})
return total//2
if __name__ == '__main__':
#These "asserts" using only for self-checking and not necessary for auto-testing
assert domino_chain("0-2, 0-5, 1-5, 1-3, 5-5") == 1
assert domino_chain("1-5, 2-5, 3-5, 4-5, 3-4") == 2
assert domino_chain("0-5, 1-5, 2-5, 3-5, 4-5, 3-4") == 0
assert domino_chain("0-1, 0-2, 1-3, 1-2, 3-4, 2-4") == 6
assert domino_chain("0-1, 0-2, 1-3, 1-2, 3-4, 2-4, 3-0, 0-4") == 0
assert domino_chain("1-2, 2-2, 2-3, 3-3, 3-1") == 5
assert domino_chain("1-4, 3-4, 0-4, 0-5, 4-5, 2-4, 2-5") == 0
assert domino_chain("1-4, 1-5, 0-2, 1-6, 4-6, 4-5, 5-6") == 0
assert domino_chain("1-2, 2-3, 2-4, 3-4, 2-5, 2-6, 5-6") == 8
assert domino_chain("1-2, 2-3, 3-1, 4-5, 5-6, 6-4") == 0
assert domino_chain("1-2, 1-4, 1-5, 1-6, 1-1, 2-5, 4-6") == 28
print("Basic tests passed.")
Sept. 4, 2017
