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.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Search
  4. Gena Playing Hanoi
  5. Discussions

Gena Playing Hanoi

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 33 Discussions, By:

votes

Please Login in order to post a comment

  • w00tles
    6 years ago+ 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)
    
    7|
    Permalink
  • DelhitePKD
    5 years ago+ 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.

    5|
    Permalink
  • itsmedurgesh
    6 years ago+ 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?

    5|
    Permalink
  • lizzael_v_c
    5 years ago+ 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.

    4|
    Permalink
  • detritusonice
    6 years ago+ 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.

    4|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature