FunctionRacerProblemsRace

Discs After k Moves

MediumRecursionPython, JavaScript, TypeScript, Java, C++

discs discs of different sizes sit on peg "A", the smallest on top, and must reach peg "C" using peg "B" as the spare, by the classic rules: a move takes the top disc of one peg and puts it on another peg, and a disc may never sit on a smaller disc. The shortest solution takes 2 ** discs - 1 moves and is unique. Return the position of every disc after the first k moves of that solution, as a list of peg names ordered from the smallest disc to the largest.

You could replay the moves one by one, but there is a direct recursion: during the first half of the solution the largest disc is still on the start peg while the smaller discs travel to the spare peg, and after its single move it stays on the goal peg while the smaller discs travel from the spare peg to the goal peg.

For example, discs = 2 and k = 1 give ["B", "A"]: the first move takes the small disc to B, and the large disc has not moved yet.

Example 1

discs 2
k 1
returns ["B","A"]

After one move the small disc is on B and the large disc is still on A.

Example 2

discs 2
k 2
returns ["B","C"]

After two moves the large disc has moved to C while the small disc waits on B.

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