Moving the Wedding Cake

EasyrecursionAlso known as Tower of Hanoi

A bakery has finished a wedding cake built from separate round tiers, the biggest at the bottom and each tier smaller than the one under it. It sits on stand A, and the photographer wants it on stand C. There is one empty spare stand, B.

The tiers are heavy and soft. You can lift only one tier at a time, always the top tier of a stand, and you may never set a tier on top of a smaller one, or it gets crushed. Plan the move.

Your task

Write moveCake(tiers). The cake has tiers tiers, all on stand A. Return the list of moves that gets the whole cake onto stand C, in the order you make them.

Write each move as two letters: the stand you lift from, then the stand you put the tier on. "AC" means: take the top tier of A and place it on C. Every move must be legal (lift from a stand that has a tier, never place a tier on a smaller one), and your list must use the fewest moves possible. With 0 tiers, return an empty list.

moveCake(tiers: int) → string[] Several answers can be correct; any valid one is accepted.

Examples

Example 1

Input

tiers = 1

Output

["AC"]

Why

One tier: lift it from A and put it on C. One move.

Example 2

Input

tiers = 2

Output

["AB", "AC", "BC"]

Why

The big tier cannot go to C while the small one sits on it. So the small tier goes to the spare stand B first, the big tier goes A → C, and the small tier goes from B onto it. Putting the small tier on C first would block C, because the big tier can never sit on it.

Constraints

0 ≤ tiers ≤ 12
Stands are named "A" (start), "B" (spare) and "C" (goal).
The shortest plan is unique, so there is exactly one correct list.

Start with brute force

Treat every arrangement of tiers on the three stands as a state and search them all, breadth first, until every tier is on C. That finds the shortest plan, but each tier can be on any of three stands, so there are 3ⁿ arrangements to store: 531,441 for 12 tiers.

At this size the search still finishes, but it is heavy and it hides the pattern. The plan itself has 2ⁿ − 1 moves, so nothing can be faster than writing those down. Aim for a method that spends a fixed amount of work per move and remembers almost nothing else.

Hints

0 of 4 shown

Hint 1
Try 2 tiers by hand. Before the big bottom tier can move to C, where does the small tier have to be?
Hint 2
Look at the moment the biggest tier moves from A to C. Stand C must be empty, and A holds only the biggest tier. So where are all the other tiers at that moment?
Hint 3
They are all stacked on B. So the plan for n tiers has three parts: move the top n − 1 tiers from A to B, move the biggest tier from A to C, then move those n − 1 tiers from B to C. Each part with n − 1 tiers is the same puzzle, with the stands playing different roles.
Hint 4
Write a helper move(count, from, to, spare) that adds moves to one shared list. If count is 0, do nothing. Otherwise: move count − 1 tiers from from to spare (using to as the spare), add the move from + to, then move count − 1 tiers from spare to to (using from as the spare).

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

Stop thinking about all the tiers at once and look only at the biggest one. It can move to C only when C is empty and nothing sits on it, which means every other tier is parked on B at that moment. That single fact gives the whole plan:

Move the top n − 1 tiers from A to B.
Move the biggest tier from A to C.
Move the n − 1 tiers from B to C, on top of it.

Steps 1 and 3 are the same puzzle with one tier fewer, so the function calls itself for them. Only the roles of the stands change. Trace 3 tiers:

Move 2 tiers A → B, using C as the spare: AC, AB, CB. (This is the 2-tier answer with B and C swapped.)
Move the biggest tier: AC.
Move 2 tiers B → C, using A as the spare: BA, BC, AC.

That is 7 moves. In general, moves(n) = 2 × moves(n − 1) + 1, which gives 2ⁿ − 1. A common slip is passing the stands in the wrong order to the inner calls; read each call out loud as "move this many tiers from here to there, using that as the spare" and check it matches the plan.

Reference solution

function moveCake(tiers) {
  const moves = [];
  function move(count, from, to, spare) {
    if (count === 0) return;          // nothing to carry
    move(count - 1, from, spare, to); // park the smaller tiers
    moves.push(from + to);            // carry the biggest one
    move(count - 1, spare, to, from); // stack the smaller tiers on top
  }
  move(tiers, 'A', 'C', 'B');
  return moves;
}

def move_cake(tiers):
    moves = []
 
    def move(count, src, dst, spare):
        if count == 0:
            return  # nothing to carry
        move(count - 1, src, spare, dst)  # park the smaller tiers
        moves.append(src + dst)           # carry the biggest one
        move(count - 1, spare, dst, src)  # stack the smaller tiers on top
 
    move(tiers, 'A', 'C', 'B')
    return moves

TimeO(2ⁿ)The answer itself has 2ⁿ − 1 moves, and the recursion does a constant amount of work per move.

SpaceO(n)The recursion is at most n calls deep. The output list of 2ⁿ − 1 moves is not counted as extra space.

Learn the idea: Recursion Divide and Conquer

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code