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
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.
4
15
Returns: 80
It takes Dave 15 moves to completely solve the puzzle with 4 disks, and Earl 80 moves.
9
265
Returns: 16418
1
0
Returns: 0
19
524287
Returns: 1162261466
1
1
Returns: 2
19
469957
Returns: 1141770746
19
112769
Returns: 117099635
19
267522
Returns: 968892396
19
398718
Returns: 1034488176
19
471981
Returns: 1142891524
2
1
Returns: 1
2
2
Returns: 7
2
3
Returns: 8
3
3
Returns: 4
3
5
Returns: 23
3
0
Returns: 0
4
5
Returns: 11
4
7
Returns: 13
4
2
Returns: 7
5
4
Returns: 22
5
25
Returns: 218
5
16
Returns: 202
6
13
Returns: 73
6
57
Returns: 716
6
60
Returns: 720
7
12
Returns: 36
7
55
Returns: 350
7
38
Returns: 255
8
106
Returns: 1041
8
55
Returns: 661
8
179
Returns: 5795
9
430
Returns: 17818
9
357
Returns: 17380
9
1
Returns: 2
10
342
Returns: 8436
10
138
Returns: 5484
10
313
Returns: 6913
11
1227
Returns: 150556
11
1663
Returns: 159650
11
1661
Returns: 159647
12
4066
Returns: 531321
12
511
Returns: 9841
12
2455
Returns: 451669
13
4871
Returns: 1354859
13
6275
Returns: 1419371
13
6204
Returns: 1417536
14
9278
Returns: 4016059
14
4515
Returns: 549188
14
129
Returns: 5468
15
17606
Returns: 11992791
15
1064
Returns: 147771
15
29688
Returns: 14112684
16
641
Returns: 50303
16
38386
Returns: 36216681
16
11357
Returns: 4222487
17
49370
Returns: 19135011
17
128491
Returns: 128913758
17
122606
Returns: 127539075
18
1
Returns: 1
18
38688
Returns: 36223524
18
171075
Returns: 331590032
18
262142
Returns: 387420487
19
123456
Returns: 127566252
19
504281
Returns: 1150057751
19
424288
Returns: 1047310438
19
593
Returns: 20615
3
2
Returns: 3
19
100000
Returns: 114951514
19
10000
Returns: 1679818
5
26
Returns: 219
19
342222
Returns: 994771932
19
14526
Returns: 2308740
10
200
Returns: 5899
19
341673
Returns: 994410460
19
262145
Returns: 968551223
19
500000
Returns: 1149513687