TopCoder problem "HanoiGoodAndBad" used in Member SRM 482 (Division I Level Two)



Problem Statement

    

The Towers of Hanoi puzzle consists of 3 pegs and a number of disks of distinct radii. The 3 pegs are the source, spare, and target. Initially, all disks are on the source peg, in ascending order by radius from top to bottom. The goal is to move all disks to the target peg, subject to the following rules:

  • Only one disk may be moved at a time.
  • No disk may be placed on top of a smaller disk.
  • A move consists of taking the highest disk from one peg, and placing it onto another peg above any disks already on that peg.

Dave and Earl are each solving a Towers of Hanoi puzzle with N disks. Dave makes as few moves as possible, solving the puzzle in only 2^N-1 moves. Earl, on the other hand, encounters every possible configuration of disks exactly once during the course of solving it, thereby requiring 3^N-1 moves to solve it. Pseudocode for their respective solutions are:

solve_Dave(source, target, spare, N)
{
	if(N>0)
	{
		solve_Dave(source, spare, target, N-1)
		move a disk from source to target
		solve_Dave(spare, target, source, N-1)
	}
}

solve_Earl(source, target, spare, N)
{
	if(N>0)
	{
		solve_Earl(source, target, spare, N-1)
		move a disk from source to spare
		solve_Earl(target, source, spare, N-1)
		move a disk from spare to target
		solve_Earl(source, target, spare, N-1)
	}
}

Given N, and the number of moves Dave has made toward the solution, return the number of moves Earl must make in order to reach the same configuration of disks as Dave.

 

Definition

    
Class:HanoiGoodAndBad
Method:moves
Parameters:int, int
Returns:int
Method signature:int moves(int N, int Dave)
(be sure your method is public)
    
 

Constraints

-N will be between 1 and 19, inclusive.
-Dave will be bewteen 0 and 2^N-1, inclusive.
 

Examples

0)
    
3
1
Returns: 2
Dave begins by moving a disk from the source peg to the target peg. Earl begins by moving a disk from the source peg to the spare peg, then to the target peg.
1)
    
4
15
Returns: 80
It takes Dave 15 moves to completely solve the puzzle with 4 disks, and Earl 80 moves.
2)
    
9
265
Returns: 16418

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14235&pm=10858

Writer:

pieguy

Testers:

ivan_metelsky , boba5551 , it4.kp , abal9002

Problem categories:

Recursion, Simple Math, Simulation