def printTowers(towers):
    """Prints the current state of the towers."""
    max_height = max(len(rod) for rod in towers.values())  # Find the tallest stack
    for level in range(max_height, 0, -1):
        for rod in "ABC":
            if len(towers[rod]) >= level:
                print(f" {towers[rod][level - 1]} ", end=" ")
            else:
                print(" | ", end=" ")
        print()
    print(" A   B   C \n" + "-" * 10)


def solveTowerOfHanoi(n, source, auxiliary, target, towers):
    if n == 0: # edge case if user wants a tower of 0
        return
    if n == 1: # last one
        disk = towers[source].pop()  # Remove top disk from source and move to target
        towers[target].append(disk)
        print(f"Disk {disk}: {source} -> {target}")
        printTowers(towers)
        return

    solveTowerOfHanoi(n - 1, source, target, auxiliary, towers)
    disk = towers[source].pop()
    towers[target].append(disk)
    print(f"Disk {disk}: {source} -> {target}")
    printTowers(towers)

    solveTowerOfHanoi(n - 1, auxiliary, source, target, towers)


# Works with both even and odd number
num_disks = 5
towers = {"A": list(range(num_disks, 0, -1)), "B": [], "C": []}

print("Starting state:")
printTowers(towers)

solveTowerOfHanoi(num_disks, "A", "B", "C", towers)