Statistics

Problem Statement for "HanoiState"

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

  1. "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.

  2. "AAC"

    7

    Returns: "AAC"

  3. "AAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    0

    Returns: "AAAAAAAAAAAAAAAAAAAAAAAAAAAA"

  4. "ABCABCABCABCABCABCABCABCABCABC"

    100000000

    Returns: "CCCCCCCCBAAAABBBBACBAAAAACBAAA"

  5. "A"

    0

    Returns: "A"

  6. "B"

    0

    Returns: "A"

  7. "B"

    1

    Returns: "B"

  8. "C"

    0

    Returns: "A"

  9. "C"

    1

    Returns: "C"

  10. "CCCC"

    0

    Returns: "AAAA"

  11. "CCCC"

    1

    Returns: "BAAA"

  12. "CCCC"

    2

    Returns: "BCAA"

  13. "CCCC"

    3

    Returns: "CCAA"

  14. "CCCC"

    4

    Returns: "CCBA"

  15. "CCCC"

    5

    Returns: "ACBA"

  16. "CCCC"

    6

    Returns: "ABBA"

  17. "CCCC"

    7

    Returns: "BBBA"

  18. "CCCC"

    8

    Returns: "BBBC"

  19. "CCCC"

    9

    Returns: "CBBC"

  20. "CCCC"

    10

    Returns: "CABC"

  21. "CCCC"

    11

    Returns: "AABC"

  22. "CCCC"

    12

    Returns: "AACC"

  23. "CCCC"

    13

    Returns: "BACC"

  24. "CCCC"

    14

    Returns: "BCCC"

  25. "CCCC"

    15

    Returns: "CCCC"

  26. "CBAC"

    0

    Returns: "AAAA"

  27. "CBAC"

    1

    Returns: "BAAA"

  28. "CBAC"

    2

    Returns: "BCAA"

  29. "CBAC"

    3

    Returns: "CCAA"

  30. "CBAC"

    4

    Returns: "CCBA"

  31. "CBAC"

    5

    Returns: "ACBA"

  32. "CBAC"

    6

    Returns: "ABBA"

  33. "CBAC"

    7

    Returns: "BBBA"

  34. "CBAC"

    8

    Returns: "BBBC"

  35. "CBAC"

    9

    Returns: "ABBC"

  36. "CBAC"

    10

    Returns: "ACBC"

  37. "CBAC"

    11

    Returns: "CCBC"

  38. "CBAC"

    12

    Returns: "CCAC"

  39. "CBAC"

    13

    Returns: "ACAC"

  40. "CBAC"

    14

    Returns: "ABAC"

  41. "CBAC"

    15

    Returns: "CBAC"

  42. "CABBCCBACCBACCABAACCCCACABABAB"

    0

    Returns: "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

  43. "BAACCBACBBBBACAACCAACCAABAACCA"

    432853159

    Returns: "BAACCBACBBBBACAACCAACCAABAACCA"

  44. "ABCCBCACCBCABABBAABCCBAABACBAC"

    536870911

    Returns: "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBA"

  45. "ABCCBCACCBCABABBAABCCBAABACBAC"

    536870912

    Returns: "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBC"

  46. "ABCCBCACCBCABABBAABCCBAABACBAC"

    536870913

    Returns: "ABBBBBBBBBBBBBBBBBBBBBBBBBBBBC"

  47. "ABCCBCACCBCABABBAABCCBAABACBAC"

    268435456

    Returns: "CCCCCCCCCCCCCCCCCCCCCCCCCCCCBA"

  48. "ABCCBCACCBCABABBAABCCBAABACBAC"

    268435455

    Returns: "CCCCCCCCCCCCCCCCCCCCCCCCCCCCAA"

  49. "CAAAABAACBCACCACCAACACCBABAAAB"

    1000000000

    Returns: "AAAAAAAAABCABBAABCABBAABBBCAAB"

  50. "CAAAABAACBCACCACCAACACCBABAAAB"

    100000000

    Returns: "BBBBBBBBCAAAACCCCABCAAAAABCAAA"

  51. "CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC"

    1073741823

    Returns: "CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC"

  52. "CCBAABBCBBABBCBBABABCBABAAABAB"

    395488233

    Returns: "BCCBACCCCCBACBACBACCABBAAAABCA"

  53. "ABCABCABCABCABCABCABCABCABCCAB"

    900909000

    Returns: "BBBACCAAAAABBBCCBACCAACBBCABAB"

  54. "CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC"

    1000000000

    Returns: "CCCCCCCCCABCAACCABCAACCAAABCCC"

  55. "BCBC"

    9

    Returns: "ABBC"

  56. "BACBAACC"

    201

    Returns: "BCCBAACC"

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: