FunctionRacerProblemsRace

Tower Moves

MediumRecursionPython, JavaScript, TypeScript, Java, C++

Three pegs are named by the one-letter strings start, goal and spare, all different. discs discs of different sizes are stacked on start, the smallest on top. A move takes the top disc of one peg and puts it on top of another peg, and a disc may never be placed on a smaller disc. Return the shortest sequence of moves that brings every disc from start to goal, as a list of two-element lists [from, to] naming the pegs. The shortest sequence is unique. With 0 discs return an empty list.

For example, discs = 2, start = "A", goal = "C", spare = "B" gives [["A", "B"], ["A", "C"], ["B", "C"]].

Example 1

discs 2
start "A"
goal "C"
spare "B"
returns [["A","B"],["A","C"],["B","C"]]

The small disc moves out of the way to B, the large disc moves to C, then the small disc joins it on C.

Example 2

discs 1
start "A"
goal "C"
spare "B"
returns [["A","C"]]

A single disc moves straight from A to C.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Recursion problems