def hanoi_posts_to_int(nstacks, posts):
    ndisks = len(posts)
    base = 2**ndisks
    res = 0
    for j, post in enumerate(posts):
        res += (2**j)*(base**(nstacks-post))
    return res

def hanoi_neighbours(state, nstacks, ndisks):
    base = 2**ndisks
    nums = [(state // (base**j)) % base for j in range(nstacks-1, -1, -1)]
    top_nums = [2**ndisks if num == 0 else (num&~(num-1)) for num in nums]
    
    for j, tnj in enumerate(top_nums):
        for k, tnk in enumerate(top_nums):
            if (j == k) or (tnj >= tnk): continue
            neighbour = state - ((tnj)*(base**((nstacks-1)-j))) + ((tnj)*(base**((nstacks-1)-k)))
            yield neighbour
    
def hanoi_general(nstacks, posts):
    ndisks = len(posts)
    source = hanoi_posts_to_int(nstacks, posts)
    base = 2**ndisks
    target = ((2**ndisks)-1)*(base**(nstacks-1))
    to_explore = [source]
    explored = set([source])
    parent = {}
    while to_explore:
        to_explore_next = []
        for v in to_explore:
            for w in hanoi_neighbours(v, nstacks, ndisks):
                if w in explored: continue
                explored.add(w)
                parent[w] = v
                if w == target: break
                to_explore_next.append(w)
        to_explore = to_explore_next

    curr = target
    moves = 0
    while curr in parent:
        moves += 1
        curr = parent[curr]
    return moves

def hanoi(posts):
    return hanoi_general(4, posts)