We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
note that if we swap any two of 2nd,3rd,4th stacks then the minimal distance to the solution remains unchanged
so WLOG after applying a move we can sort the 2nd,3rd,4th stacks by the size of their top disk. by doing so, we have chosen a unique representative for each class of equivalent nodes.
this reduces number of nodes to about 1/6 of the naive BFS
fromcollectionsimportdequedeflegal_moves(x):foriinrange(len(x)):ifx[i]:forjinrange(len(x)):ifnotx[j]orx[i][-1]<x[j][-1]:yield(i,j)defis_goal(x):returnall([len(x[i])==0foriinrange(1,len(x))])defbfs(x):deftuplify(z):returntuple(tuple(t)fortinz)defdo_move(g,m):y=[list(t)forting]y[m[1]].append(y[m[0]].pop())# WLOG sort 2nd-4th stacks by order of largest disky[1:4]=sorted(y[1:4],key=lambdat:t[-1]iftelse0)returntuplify(y)visited=set()start=(tuplify(x),0)q=deque([start])visited.add(start)whileq:node,depth=q.popleft()ifis_goal(node):returndepthformoveinlegal_moves(node):child=do_move(node,move)ifchildnotinvisited:visited.add(child)q.append((child,depth+1))# load the representation from stdinN=int(raw_input())A=[[]foriinrange(4)]R=[int(t)fortinraw_input().split()]foriinrange(N):A[R[i]-1]=[(i+1)]+A[R[i]-1]printbfs(A)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Gena Playing Hanoi
You are viewing a single comment's thread. Return to all comments →
note that if we swap any two of 2nd,3rd,4th stacks then the minimal distance to the solution remains unchanged
so WLOG after applying a move we can sort the 2nd,3rd,4th stacks by the size of their top disk. by doing so, we have chosen a unique representative for each class of equivalent nodes.
this reduces number of nodes to about 1/6 of the naive BFS