TopCoder problem "HanoiState" used in SRM 378 (Division II Level Three)



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.

 

Definition

    
Class:HanoiState
Method:partwayState
Parameters:String, int
Returns:String
Method signature:String partwayState(String target, int moves)
(be sure your method is public)
    
 

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.
 

Examples

0)
    
"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.
1)
    
"AAC"
7
Returns: "AAC"
2)
    
"AAAAAAAAAAAAAAAAAAAAAAAAAAAA"
0
Returns: "AAAAAAAAAAAAAAAAAAAAAAAAAAAA"
3)
    
"ABCABCABCABCABCABCABCABCABCABC"
100000000
Returns: "CCCCCCCCBAAAABBBBACBAAAAACBAAA"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8303

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10798&pm=8303

Writer:

bmerry

Testers:

PabloGilberto , Olexiy , marek.cygan , ivan_metelsky

Problem categories:

Recursion, Simulation