Coupa Software Interview Questions

Tower of Hanoi is a fun puzzle game that consists of a set of 3 pegs (A, B, C) and n number of disks. You are required to move all disks from the source peg A to destination peg C, under the following conditions:

• You can only move one disk for each action.
• You can only move the disk onto the top of another peg; you cannot place it off to the side or under existing disks.
• You cannot place a larger disk onto a smaller disk.

Initially, all disks are on the source A peg and sorted by decreasing width from bottom to the top (widest on the bottom, smallest on the top).

You must develop an algorithm to move all disks from A to the destination peg C with the optimal solution. Also, return every step made from the starting state to the final state.

Example

Input:

n = 3

Output:

#return list of {"A":[],"B":[],"C":[]} 
tower_of_hanoi_solver(n) -> [
        {"A": [1, 2, 3], "B": [], "C": []},
        {"A": [2, 3], "B": [], "C": [1]},
        {"A": [3], "B": [2], "C": [1]},
        {"A": [3], "B": [1, 2], "C": []},
        {"A": [], "B": [1, 2], "C": [3]},
        {"A": [1], "B": [2], "C": [3]},
        {"A": [1], "B": [], "C": [2, 3]},
        {"A": [], "B": [], "C": [1, 2, 3]}
    ]