HanoiState
SRM 378 · 2007-11-20 · by bmerry
Problem Statement
In the classic Towers of Hanoi problem, there are three pegs, labeled A, B and C, and n discs, of sizes 1 to n. Each disc has a hole in the center, so that it can be placed on a peg. Initially, all the discs are stacked on peg A in order of size, with the smallest disc on top. Only one disc may be moved at a time. In each move, you remove the top disc from one of the pegs, and place it on another peg. A disc may be placed on an empty peg or stacked on top of a larger disc, but it may not be placed on top of a smaller disc.
target is a string consisting of n characters, each of which is either A, B or C. The goal of the game is to make the minimum number of moves so that character i of target is the peg containing the disc of size i + 1. There is only one shortest sequence of moves. Return the state of the game after making moves of these moves, in the same format as target.
Constraints
- target will contain between 1 and 30 characters, inclusive.
- Each character of target will be either 'A', 'B' or 'C'.
- moves will be between 0 and m, inclusive, where the shortest solution to the game takes m moves.
"CCC" 4 Returns: "BBC"
The full sequence of states is AAA, CAA, CBA, BBA, BBC, ABC, ACC, CCC. After 4 moves the state is BBC.
"AAC" 7 Returns: "AAC"
"AAAAAAAAAAAAAAAAAAAAAAAAAAAA" 0 Returns: "AAAAAAAAAAAAAAAAAAAAAAAAAAAA"
"ABCABCABCABCABCABCABCABCABCABC" 100000000 Returns: "CCCCCCCCBAAAABBBBACBAAAAACBAAA"
"A" 0 Returns: "A"
Submissions are judged against all 56 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class HanoiState with a public method string partwayState(string target, int moves) · 56 test cases · 2 s / 256 MB per case