Problem Statement
In this problem we consider a modification of the classical Hanoi Towers game. The rules of our modification are as follows:
- There are three pegs: peg A, peg B and peg C.
- Each peg initially contains zero or more discs.
- All discs have the same size and there are three types of discs: type A, type B and type C.
- In one move you can move a disc from the top of one peg onto the top of another peg.
- Your goal is to have all discs of type A on peg A, all discs of type B on peg B and all discs of type C on peg C.
- You must achieve your goal in the minimum possible number of moves.
The initial locations of the discs are given in the
Return the minimum number of moves required to achieve the goal of the game.
Definition
- Class:
- HanoiTower
- Method:
- moves
- Parameters:
- String, String, String
- Returns:
- int
- Method signature:
- int moves(String pegA, String pegB, String pegC)
- (be sure your method is public)
Notes
- It's always possible to achieve the goal of the game.
Constraints
- pegA, pegB and pegC will contain only the characters 'A', 'B' and 'C'.
- The total number of characters in pegA, pegB and pegC will be between 1 and 10, inclusive.
Examples
"A"
"AA"
"AA"
Returns: 4
Move all discs of type A to peg A directly.
"B"
"C"
"A"
Returns: 5
There is exactly one disc of each type in this example, so we will refer to each disc by its type. The following sequence of moves is the shortest: 1. Move disc A to peg A. 2. Move disc C to peg C. 3. Move disc A to peg C. 4. Move disc B to peg B. 5. Move disc A to peg A.
"CBA"
""
""
Returns: 5
Again, there is exactly one disc of each type here, so we will refer to each disc by its type. The following sequence of moves is the shortest: 1. Move disc A to peg C. 2. Move disc B to peg B. 3. Move disc A to peg B. 4. Move disc C to peg C. 5. Move disc A to peg A.
"BBBBBBBBBA"
""
""
Returns: 11
Move the disc of type A to peg C. Then move all discs of type B to peg B. Finally, move disc A back to peg A.
"CCCCBBBAAA"
""
""
Returns: 16
"A"
""
""
Returns: 0
"BBBB"
"CCC"
"AAA"
Returns: 16
"C"
"B"
""
Returns: 1
"CB"
"AACA"
"AA"
Returns: 13
"B"
"C"
"B"
Returns: 4
"B"
""
"B"
Returns: 2
"C"
"C"
""
Returns: 2
"BBB"
""
"AB"
Returns: 5
""
"AAACC"
"AAAAA"
Returns: 10
"BB"
"A"
"AAABAB"
Returns: 10
"C"
"CCCABB"
"A"
Returns: 13
"CABA"
""
"BCC"
Returns: 12
"B"
"C"
""
Returns: 2
""
"CBA"
"BABBC"
Returns: 13
""
"C"
""
Returns: 1
"BBBCC"
"C"
"A"
Returns: 10
""
"AA"
""
Returns: 2
"BC"
"CCBA"
"AAC"
Returns: 15
"BC"
""
"B"
Returns: 3
"C"
""
"B"
Returns: 2
"C"
""
"A"
Returns: 3
"CCC"
"AAB"
"BBAB"
Returns: 17
"B"
"ABACA"
"AAA"
Returns: 14
""
""
"BBB"
Returns: 3
"CCC"
"AAC"
"AAC"
Returns: 12
"CA"
"AAC"
"BAB"
Returns: 15
"BBAA"
""
"B"
Returns: 7
""
"A"
"B"
Returns: 2
""
"AA"
"BA"
Returns: 4
"CBCA"
"C"
"BBB"
Returns: 12
"BBCC"
"C"
""
Returns: 5
"CAA"
"A"
""
Returns: 6
"C"
"AABC"
"BB"
Returns: 12
""
""
"AC"
Returns: 3
""
"A"
"ABC"
Returns: 6
"CBA"
""
""
Returns: 5
"CCB"
"A"
"BA"
Returns: 10
""
"AABB"
""
Returns: 6
"BCB"
""
"AB"
Returns: 7
""
""
"BBB"
Returns: 3
"CCAC"
"AB"
"ABC"
Returns: 15
""
"C"
"AB"
Returns: 5
"CCCC"
"ACBC"
"B"
Returns: 13
"CACB"
"CA"
"ABC"
Returns: 16
"BA"
"A"
"B"
Returns: 6
"CBB"
"AAB"
"A"
Returns: 11
""
"ABABBC"
"AC"
Returns: 12
"BA"
"CAC"
"BB"
Returns: 12
"BB"
"A"
""
Returns: 4
"CACC"
"CAAAB"
"B"
Returns: 15
"C"
"AB"
"ABBB"
Returns: 11
""
"C"
"ABB"
Returns: 6
"C"
"ABACB"
"A"
Returns: 11
"BCAA"
"CAB"
"ABC"
Returns: 19
"CBACBACBAA"
""
""
Returns: 19
"ABC"
"ABC"
"ABCA"
Returns: 17
"BC"
"ABCCBA"
"BA"
Returns: 18
"ABCABC"
""
""
Returns: 7
"BBB"
"CCC"
"AAAA"
Returns: 16
"CCC"
"BBB"
"AAAA"
Returns: 10
"BBA"
"AA"
"CCC"
Returns: 8
"CBAB"
"ABBA"
"BA"
Returns: 17
"ABBC"
"BACCB"
"C"
Returns: 9