- Prepare
- Algorithms
- Search
- Gena Playing Hanoi
- Discussions
Gena Playing Hanoi
Gena Playing Hanoi
+ 1 comment 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
from collections import deque def legal_moves(x): for i in range(len(x)): if x[i]: for j in range(len(x)): if not x[j] or x[i][-1] < x[j][-1]: yield (i, j) def is_goal(x): return all([len(x[i]) == 0 for i in range(1, len(x))]) def bfs(x): def tuplify(z): return tuple(tuple(t) for t in z) def do_move(g, m): y = [list(t) for t in g] y[m[1]].append(y[m[0]].pop()) # WLOG sort 2nd-4th stacks by order of largest disk y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0) return tuplify(y) visited = set() start = (tuplify(x), 0) q = deque([start]) visited.add(start) while q: node, depth = q.popleft() if is_goal(node): return depth for move in legal_moves(node): child = do_move(node, move) if child not in visited: visited.add(child) q.append((child, depth+1)) # load the representation from stdin N = int(raw_input()) A = [[] for i in range(4)] R = [int(t) for t in raw_input().split()] for i in range(N): A[R[i]-1] = [(i+1)] + A[R[i]-1] print bfs(A)
+ 0 comments Editorial in Hackerrank should contain a better explaination. There is not even a single comment line in the editorial code. Just a few comment lines, if added to the code can bring a huge impact for understanding solution.
+ 2 comments algorithm used in editorial section is not very clear and code is really unreadable. Can somebody please explain the algorithm or any different approach they adopted?
+ 1 comment Hardest medium problem in hackerrank! lol Optimization: BFS from top to bottom and from bottom to top, one level each. This will cut the tree in a half.
+ 0 comments Concerning the editorial:
there actually are at most 6 new states that can be generated by any parent state - disk configuration.
The largest of the four top disks (if applicable) cannot move, and the others have 1,2 (also if applicable) and 3 possible moves , disregarding pruning.
Sort 33 Discussions, By:
Please Login in order to post a comment