Statistics

Problem Statement for "HanoiDistance"

Problem Statement

In the famous Towers of Hanoi puzzle, you have three pegs, labeled A, B, and C, and n discs, of sizes 1 through n, inclusive. The discs are initially stacked on peg A in order of size, with the smallest disc on top. The goal is move the entire stack from peg A to peg C, under the constraints that you can only move one disc at a time and you can never move a larger disc onto a smaller disc. In each move, you remove the top disc from one of the three pegs and place it on top of the discs on another peg. In some cases, you move a disc to an empty peg, in which case the disc goes on the bottom of the peg.

There is a unique sequence of moves that solves the Towers of Hanoi puzzle in the minimum number of moves. There are a total of 2n configurations of discs that are encountered during the course of this solution, counting the initial configuration. Call each of these configurations valid and all other configurations invalid.

Your little sister dropped your Towers of Hanoi puzzle and put the discs back on random pegs. She remembered to always put smaller discs on top of larger discs, but did not necessarily make a valid configuration. You would be embarrassed if your friends saw your puzzle in an invalid configuration, so you want to move the discs back into a valid configuration. Naturally, you want to do so in the minimum number of moves. As usual, you can only move one disc at a time and you can never place a larger disc on top of a smaller disc.

You will be given the number of discs, n, and three int[]'s, pegA, pegB, and pegC, representing the order of the discs on each of the pegs, with the top disc on each peg at the front of the int[] and the bottom disc at the back. Return the minimum number of moves required to reach a valid configuration.

Definition

Class:
HanoiDistance
Method:
distance
Parameters:
int, int[], int[], int[]
Returns:
long
Method signature:
long distance(int n, int[] pegA, int[] pegB, int[] pegC)
(be sure your method is public)

Constraints

  • n is between 1 and 50, inclusive.
  • pegA contains between 0 and n elements, inclusive.
  • pegB contains between 0 and n elements, inclusive.
  • pegC contains between 0 and n elements, inclusive.
  • Each element of pegA is between 1 and n, inclusive.
  • Each element of pegB is between 1 and n, inclusive.
  • Each element of pegC is between 1 and n, inclusive.
  • Each peg is sorted in increasing order.
  • Each integer between 1 and n, inclusive, must appear on some peg.
  • No element of pegA, pegB, or pegC may appear on more than one peg or more than once on the same peg.

Examples

  1. 4

    { 2 }

    { 4 }

    { 1,3 }

    Returns: 11

    THESE ARE NOT THE REAL EXAMPLES -- THEY'RE JUST PLACEHOLDERS!

  2. 4

    { 2,3 }

    { 1,4 }

    { }

    Returns: 9

  3. 10

    {1,2,3,5,6,7,9,10}

    {4,8}

    {}

    Returns: 143

    Should be 234?

  4. 7

    {3}

    {2,5,6}

    {1,4,7}

    Returns: 0

  5. 6

    { 2,3 }

    { 5,6 }

    { 1,4 }

    Returns: 54

  6. 50

    {7}

    {1,3,6,9,11,14,18,21,29,32,34,37,38,40,42,44,48,49}

    {2,4,5,8,10,12,13,15,16,17,19,20,22,23,24,25,26,27,28,30,31,33,35,36,39,41,43,45,46,47,50}

    Returns: 12639822298621

  7. 4

    { 1,2,3,4 }

    { }

    { }

    Returns: 0

    This configuration is already valid, so no moves are necessary.

  8. 4

    { }

    { 1,2,3,4 }

    { }

    Returns: 15

    The whole stack should be on peg A or peg C, not peg B. It takes 15 moves to transfer the entire stack to either of the other pegs.

  9. 50

    { 1,5,10,20,40,45,50}

    { 2,4,8,16,32,48}

    { 3,6,7,9,11,12,13,14,15,17,18,19, 21,22,23,24,25,26,27,28,29,30, 31,33,34,35,36,37,38,39,41,42, 43,44,46,47,49 }

    Returns: 405717644182423

  10. 1

    {1}

    {}

    {}

    Returns: 0

  11. 1

    {}

    {1}

    {}

    Returns: 1

  12. 1

    {}

    {}

    {1}

    Returns: 0

  13. 2

    {}

    {1}

    {2}

    Returns: 0

  14. 3

    {2}

    {3}

    {1}

    Returns: 5

  15. 4

    {3}

    {2,4}

    {1}

    Returns: 10

  16. 5

    {1,4}

    {5}

    {2,3}

    Returns: 22

  17. 6

    {1,2,4,5}

    {3,6}

    {}

    Returns: 39

  18. 7

    {2,3,5}

    {}

    {1,4,6,7}

    Returns: 9

  19. 8

    {2,5,8}

    {1,4,6}

    {3,7}

    Returns: 95

  20. 9

    {1,4}

    {3,5,6,7,8,9}

    {2}

    Returns: 501

  21. 10

    {3,4,9,10}

    {1,2,7,8}

    {5,6}

    Returns: 207

  22. 11

    {1,5,10}

    {2,3,6,7,9,11}

    {4,8}

    Returns: 1406

  23. 12

    {1,2,7,8,9}

    {3,4,5,6,10}

    {11,12}

    Returns: 572

  24. 13

    {1,2,3,6,7,10}

    {11,13}

    {4,5,8,9,12}

    Returns: 5528

  25. 14

    {1,3,4,5,14}

    {2,7,9,10,11,12}

    {6,8,13}

    Returns: 4317

  26. 15

    {1,10,11,14}

    {3,4,5}

    {2,6,7,8,9,12,13,15}

    Returns: 9759

  27. 16

    {1,2,5,6,16}

    {4,7,9,10,13}

    {3,8,11,12,14,15}

    Returns: 27903

  28. 17

    {3,4,10,12,16,17}

    {2,6,7,14}

    {1,5,8,9,11,13,15}

    Returns: 5743

  29. 18

    {1,3,9,10}

    {4,6,11,17,18}

    {2,5,7,8,12,13,14,15,16}

    Returns: 197867

  30. 19

    {1,3,6,8,12,13,16,18}

    {5,7,9,10,11,14}

    {2,4,15,17,19}

    Returns: 196459

  31. 20

    {5,15}

    {3,4,6,8,9,10,11,17}

    {1,2,7,12,13,14,16,18,19,20}

    Returns: 47219

  32. 21

    {4,5,8,10,12,15,17}

    {3,13,14,16,20}

    {1,2,6,7,9,11,18,19,21}

    Returns: 445284

  33. 22

    {2,3,8,11,16,17,20}

    {1,4,9,10,13,14,18,22}

    {5,6,7,12,15,19,21}

    Returns: 3126409

  34. 23

    {3,8,11,13,15,18,19,20,21,22}

    {2,4,5,10,14,16}

    {1,6,7,9,12,17,23}

    Returns: 4111079

  35. 24

    {1,5,12,13,14,16,18,19,20,22}

    {3,4,9,11,23}

    {2,6,7,8,10,15,17,21,24}

    Returns: 968189

  36. 25

    {3,6,10,11,12,16,20}

    {1,2,4,14,15,18,19,21,25}

    {5,7,8,9,13,17,22,23,24}

    Returns: 18345943

  37. 26

    {7,8,10,12,13,14,16,17,21}

    {2,3,5,9,11,15,18,19,20,24,25}

    {1,4,6,22,23,26}

    Returns: 1162713

  38. 27

    {2,4,7,9,12,18,20,22}

    {1,8,11,13,14,27}

    {3,5,6,10,15,16,17,19,21,23,24,25,26}

    Returns: 70662906

  39. 28

    {3,10,19,20,21,27,28}

    {2,6,8,9,11,12,13,14,17,24,26}

    {1,4,5,7,15,16,18,22,23,25}

    Returns: 48415674

  40. 29

    {1,2,10,14,19,20,22,26,28}

    {4,5,9,11,12,13,17,18,24,29}

    {3,6,7,8,15,16,21,23,25,27}

    Returns: 384771044

  41. 30

    {3,4,5,8,10,13,14,24,25,29,30}

    {1,2,9,12,19,20,26,27}

    {6,7,11,15,16,17,18,21,22,23,28}

    Returns: 25968483

  42. 31

    {1,4,11,12,13,14,15,19,25,26}

    {6,10,17,20,22,23,24,27,31}

    {2,3,5,7,8,9,16,18,21,28,29,30}

    Returns: 1156219449

  43. 32

    {6,9,10,11,17,19,20,21,24,29,30,31}

    {5,8,14,15,23,25,26}

    {1,2,3,4,7,12,13,16,18,22,27,28,32}

    Returns: 1940088656

  44. 33

    {1,3,7,11,12,13,15,17,29,32}

    {2,6,8,14,18,19,20,21,22,25,28,33}

    {4,5,9,10,16,23,24,26,27,30,31}

    Returns: 6073335675

  45. 34

    {6,7,8,9,13,16,19,21,25,30}

    {1,2,5,12,15,17,23,27,31,33}

    {3,4,10,11,14,18,20,22,24,26,28,29,32,34}

    Returns: 2809637375

  46. 35

    {1,5,6,8,11,13,21,24,25,26,28,29,31,32}

    {2,7,9,10,12,16,19,22,23,30,33,34}

    {3,4,14,15,17,18,20,27,35}

    Returns: 3698031474

  47. 36

    {6,10,14,16,17,19,22,25,26,27,29,30,32,35}

    {1,2,3,7,13,15,18,20,21,23,24,33}

    {4,5,8,9,11,12,28,31,34,36}

    Returns: 23502508967

  48. 37

    {2,3,5,9,13,16,17,18,19,21,22,23,26,28,33}

    {6,8,11,12,20,27,29,34,36}

    {1,4,7,10,14,15,24,25,30,31,32,35,37}

    Returns: 21876994006

  49. 38

    {7,10,21,22,26,27,33,35}

    {1,3,5,6,8,11,15,16,17,18,20,23,25,28,37,38}

    {2,4,9,12,13,14,19,24,29,30,31,32,34,36}

    Returns: 236218481339

  50. 39

    {13,15,18,19,22,24,25,30,31,37}

    {4,5,7,9,10,11,14,20,26,28,32,36,38}

    {1,2,3,6,8,12,16,17,21,23,27,29,33,34,35,39}

    Returns: 36905572287

  51. 40

    {2,7,8,9,14,15,17,25,29,31,37,39}

    {3,5,12,13,16,24,27,28,30,32,33,35,36}

    {1,4,6,10,11,18,19,20,21,22,23,26,34,38,40}

    Returns: 359477110746

  52. 41

    {11,12,15,18,27,30,31,36,39}

    {1,2,3,8,10,17,19,22,24,28,32,33,35,37,38,41}

    {4,5,6,7,9,13,14,16,20,21,23,25,26,29,34,40}

    Returns: 1436656434567

  53. 42

    {1,2,3,4,7,8,10,11,18,20,21,24,27,28,39,40,41}

    {6,9,12,13,15,22,29,30,31,34,35,37}

    {5,14,16,17,19,23,25,26,32,33,36,38,42}

    Returns: 2033929578192

  54. 43

    {2,15,19,22,23,24,33,37,43}

    {4,7,8,10,11,12,14,16,17,18,21,25,26,27,30,31,34,38,39,40,41}

    {1,3,5,6,9,13,20,28,29,32,35,36,42}

    Returns: 2278899560245

  55. 44

    {1,5,6,7,8,9,10,20,23,26,29,30,40,41,42,43}

    {2,4,11,12,13,14,15,16,18,24,25,27,28,31,34,36,37,38,39,44}

    {3,17,19,21,22,32,33,35}

    Returns: 9335983506423

  56. 45

    {1,2,4,7,8,11,14,18,27,28,32,35,39,43}

    {5,10,12,13,15,17,19,23,24,26,33,36,37,41,44}

    {3,6,9,16,20,21,22,25,29,30,31,34,38,40,42,45}

    Returns: 710783253803

  57. 46

    {2,6,9,12,14,15,20,26,30,36,42,44}

    {1,5,7,11,16,18,24,25,29,32,33,34,37,41,43,45}

    {3,4,8,10,13,17,19,21,22,23,27,28,31,35,38,39,40,46}

    Returns: 5584840944317

  58. 47

    {4,5,8,11,12,13,17,20,22,25,31,32,33,35,37,47}

    {3,6,7,9,10,14,15,16,18,21,24,28,30,34,38,39,40,43,46}

    {1,2,19,23,26,27,29,36,41,42,44,45}

    Returns: 3392889283428

  59. 48

    {2,5,6,8,9,10,13,21,24,27,29,30,33,39,42,44,45,48}

    {1,12,14,15,17,18,26,31,32,36,38,40,46}

    {3,4,7,11,16,19,20,22,23,25,28,34,35,37,41,43,47}

    Returns: 102769800224690

  60. 49

    {13,14,18,22,24,25,28,29,31,35,36,37,39,42,43,47}

    {2,4,5,6,7,8,11,16,17,19,23,26,30,34,38,40,41,44,46,48,49}

    {1,3,9,10,12,15,20,21,27,32,33,45}

    Returns: 468108043484413

  61. 50

    {2,4,8,9,11,15,17,24,30,36,37,38,43,49}

    {12,13,14,19,20,21,22,26,27,28,31,32,42,44,47,48}

    {1,3,5,6,7,10,16,18,23,25,29,33,34,35,39,40,41,45,46,50}

    Returns: 343017546270093

  62. 50

    {5,6,9,16,18,19,24,27,32,35,36,38,43,46}

    {1,4,10,11,15,17,20,21,22,28,30,31,33,34,39,41,42,44,45,47,48}

    {2,3,7,8,12,13,14,23,25,26,29,37,40,49,50}

    Returns: 241547345510089

  63. 50

    {4,6,12,14,17,18,21,25,28,30,31,33,38,41,44,46,50}

    {1,3,7,8,9,10,11,16,19,22,23,24,26,32,35,37,39,40,43,48}

    {2,5,13,15,20,27,29,34,36,42,45,47,49}

    Returns: 386948466958302

  64. 50

    {2,8,9,10,11,12,14,16,17,18,19,24,25,26,27,28,30,31,38,49,50}

    {4,6,13,21,23,37,39,41,43,45}

    {1,3,5,7,15,20,22,29,32,33,34,35,36,40,42,44,46,47,48}

    Returns: 12440099598261

  65. 50

    {6,15,17,18,19,23,25,31,33,49}

    {1,2,5,8,11,20,21,22,28,34,36,39,40,42,44,45,47,48}

    {3,4,7,9,10,12,13,14,16,24,26,27,29,30,32,35,37,38,41,43,46,50}

    Returns: 349622400239532

  66. 50

    {1,7,14,16,24,25,29,30,37,38,45,46,48}

    {4,5,9,21,23,27,32,35,39,40,43,44,47,50}

    {2,3,6,8,10,11,12,13,15,17,18,19,20,22,26,28,31,33,34,36,41,42,49}

    Returns: 760024493178535

  67. 50

    {2,3,4,5,7,10,16,18,20,22,25,26,29,31,41,44,46,47,49}

    {1,8,11,12,13,14,17,23,30,34,36,39,45}

    {6,9,15,19,21,24,27,28,32,33,35,37,38,40,42,43,48,50}

    Returns: 412000431292385

  68. 50

    {5,6,7,9,10,17,18,20,27,34,36,42,45,46,47}

    {1,4,11,13,14,15,19,24,25,26,33,35,37,38,40,44,48,49}

    {2,3,8,12,16,21,22,23,28,29,30,31,32,39,41,43,50}

    Returns: 129153886844159

  69. 50

    {1,2,5,6,8,13,17,20,23,24,25,26,27,30,34,42,44,46,47}

    {4,10,11,12,14,16,18,21,32,33,35,36,38,39,40,45}

    {3,7,9,15,19,22,28,29,31,37,41,43,48,49,50}

    Returns: 118671425580747

  70. 50

    {2,10,15,18,24,27,28,29,30,33,39,49,50}

    {4,6,8,12,13,16,19,20,21,25,35,40,41}

    {1,3,5,7,9,11,14,17,22,23,26,31,32,34,36,37,38,42,43,44,45,46,47,48}

    Returns: 305974476507

  71. 50

    {2,5,7,19,20,26,30,34,36,42}

    {1,3,6,8,10,13,16,17,18,21,22,24,25,27,28,31,33,39,40,43,45,47,49,50}

    {4,9,11,12,14,15,23,29,32,35,37,38,41,44,46,48}

    Returns: 967534504550078

  72. 50

    { 1, 5, 10, 20, 40, 45, 50 }

    { 2, 4, 8, 16, 32, 48 }

    { 3, 6, 7, 9, 11, 12, 13, 14, 15, 17, 18, 19, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 33, 34, 35, 36, 37, 38, 39, 41, 42, 43, 44, 46, 47, 49 }

    Returns: 405717644182423

  73. 50

    { 1, 5, 10, 20, 23, 24, 25, 26 }

    { 2, 4, 8, 16, 32, 48 }

    { 3, 6, 7, 9, 11, 12, 13, 14, 15, 17, 18, 19, 21, 22, 27, 28, 29, 30, 31, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 49, 50 }

    Returns: 140741782863594

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: