Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Speedy category for Domino Chain by zhang9820110
def domino_chain(tiles: str) -> int:
# your code here
exlst = [str(i) for i in range(7) if tiles.count(str(i)) % 2 != 0] # exclude the tiles w/o chains 1
if len(exlst) != 2 and len(exlst) > 0: return 0
tlist = [i for i in tiles.replace("-","").split(", ") if i[0]!=i[1]] # tile list with the same number
rlist = [i[0] for i in tiles.replace("-","").split(", ") if i[0]==i[1]] # list of the rest tiles
plist = [[t.replace(str(i),"") for t in tlist if str(i) in t] for i in range(7)] # connection point list
nlen = [int("".join(tlist).count(str(i))/2) for i in range(7)] # list of connection point numbers
for i in rlist: # exclude the tiles w/o chains 2
if nlen[int(i)] == 0: return 0
result = 0
for i in range(7):
if len(plist[i]) == 0: continue
if len(exlst) == 2 and str(i) not in exlst: continue
rs = 1
if len(rlist) > 0: # combinations of the tlist
for r in rlist:
if int(r) == i or r in exlst:
rs *= nlen[int(r)] + 1
else: rs *= nlen[int(r)]
for p in plist[i]: # all possible start points
route = [set(str(i)+p)]
visited = []
clist = [p] # list of connection points
cp = p # current connection point of the chain
while 1:
found = False
for p1 in plist[int(cp)]:
if set(cp+p1) not in route:
route.append(set(cp+p1))
if route not in visited:
clist.append(p1)
cp = p1
found = True
break
else: route.pop()
if len(route) == 1: break
if not found and len(route) > 1:
visited.append(route[:])
route.pop()
clist.pop()
cp = clist[-1]
elif len(route) == len(tlist):
result += rs
visited.append(route[:-1])
cp = clist[-3]
route = route[:-2]
clist = clist[:-2]
return result/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.")
Jan. 9, 2018
Comments:
