Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
In search of Eulerian path solution in Clear category for Domino Chain by vinc
# for reading:
# https://en.wikipedia.org/wiki/Eulerian_path
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(', ')}
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])+(v in 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())])
else:
# if all vertices have even degree, then check all of them
queue = deque([(v, set()) 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 = queue.popleft()
if len(closed) == len(tiles):
result += 1
for child in graph[node]:
if frozenset({node, child}) not in closed:
queue.append((child, closed | {frozenset({node, child})}))
if len(nodes_with_odd_degree) == 0:
result //= 2 # exclude inverted chains
return result
Aug. 28, 2017
Comments:
