Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
In search of Eulerian path (vinc's solution), discarding loops solution in Clear category for Domino Chain by flpo
from collections import defaultdict, deque
def domino_chain(tiles: str) -> int:
# build a graph
tiles = {tuple(map(int, tile.split('-'))) for tile in tiles.split(', ')}
### store loops and remove them from tiles
loops = {x for x, y in tiles if x == y}
tiles = {(x, y) for x, y in tiles if x != y}
graph = defaultdict(set)
for v1, v2 in tiles:
graph[v1].add(v2)
graph[v2].add(v1)
# check if the graph has either 0 or 2 vertices of odd degree
degrees = {v: len(graph[v]) for v in graph}
nodes_with_odd_degree = {v for v in graph if degrees[v] % 2}
if len(nodes_with_odd_degree) not in (0, 2):
return 0
if len(nodes_with_odd_degree) == 2:
# if there are two vertices with odd degree, then check only one of them
start = next(iter(nodes_with_odd_degree)) # any node with odd degree
queue = deque([(start, set(), [start])])
else:
# if all vertices have even degree, then check all of them
queue = deque([(v, set(), [v]) for v in graph])
# BFS-search from each vertex in the queue with a single passage
# along the edges
result = 0
while queue:
node, closed, chain = queue.popleft()
if len(closed) == len(tiles):
### eval loops factor
mul = 1
for loop in loops:
mul *= chain.count(loop)
result += mul
else:
for child in graph[node]:
if frozenset({node, child}) not in closed:
queue.append((child, closed | {frozenset({node, child})}, chain + [child]))
if len(nodes_with_odd_degree) == 0:
result //= 2 # exclude inverted chains
return result
Sept. 12, 2017
Comments:
