Statistics

Problem Statement for "Piglets"

Problem Statement

It's feeding time in the pig pen, where a trough is divided into n stalls to accommodate n piglets. The rude piglets immediately rush to the trough and distribute themselves arbitrarily among the stalls. After them come the fastidious piglets one at a time, at one-minute intervals.

A fastidious piglet doesn't want to feed in just any stall, since he doesn't like to be sandwiched between two piglets. As the trough fills up, however, a piglet who hasn't managed to occupy an end stall will eventually have a neighbor on each side. It is the fastidious piglet's goal to delay this sandwiching as long as possible. Among multiple stalls that afford the same delay, he prefers the leftmost. He makes his selection in the knowledge that all subsequent piglets arriving at the trough will choose a stall according to the same criteria.

Given a String describing a trough configuration such that '-' represents an empty stall and 'p' represents an occupied stall, return the zero-based index of the stall chosen by the next piglet. Return -1 if every stall is occupied.

Definition

Class:
Piglets
Method:
choose
Parameters:
String
Returns:
int
Method signature:
int choose(String trough)
(be sure your method is public)

Notes

  • A fastidious piglet will take a stall at the very end of the trough if possible, preferring the left end to the right end.
  • All currently empty stalls will eventually be occupied by fastidious piglets.

Constraints

  • trough contains between 1 and 15 characters, inclusive.
  • Each character in trough is either '-' or 'p'.

Examples

  1. "--p--"

    Returns: 0

    An end stall lets the piglet avoid sandwiching altogether.

  2. "p-p-p"

    Returns: 1

    The piglet is forced to choose a stall that is already sandwiched. As always in the case of a tie, he prefers the leftmost.

  3. "p--p"

    Returns: 1

    Whichever stall the next piglet chooses, he will be sandwiched by the piglet who follows one minute later.

  4. "p---p"

    Returns: 2

    If the piglet takes stall 1, he will be sandwiched in one minute. Stalls 2 and 3 allow him a two-minute delay.

  5. "ppp"

    Returns: -1

  6. "p----p"

    Returns: 3

  7. "p-------------p"

    Returns: 12

  8. "p---p---------p"

    Returns: 12

  9. "p---------p---p"

    Returns: 12

  10. "p--p------p---p"

    Returns: 12

  11. "p-"

    Returns: 1

  12. "p"

    Returns: -1

  13. "-"

    Returns: 0

  14. "p-------p-----p"

    Returns: 12

  15. "pp---p-------pp"

    Returns: 11

  16. "pp-pp---------p"

    Returns: 12

  17. "p------pp-----p"

    Returns: 12

  18. "p--------pp-p-p"

    Returns: 7

  19. "ppp--p-------pp"

    Returns: 11

  20. "p------p-----pp"

    Returns: 11

  21. "p----------pppp"

    Returns: 9

  22. "p-------p-----p"

    Returns: 12

  23. "p------p-p--p-p"

    Returns: 10

  24. "p-----p--p-p--p"

    Returns: 12

  25. "p--pp---------p"

    Returns: 12

  26. "p-p-----------p"

    Returns: 12

  27. "p--pp-p---p---p"

    Returns: 12

  28. "p---p---------p"

    Returns: 12

  29. "p-pp---p---p--p"

    Returns: 12

  30. "p------pp-p-p-p"

    Returns: 5

  31. "pp----pp-pp---p"

    Returns: 12

  32. "pp--p---p-----p"

    Returns: 12

  33. "p-p--p-----pp-p"

    Returns: 9

  34. "p-ppp---------p"

    Returns: 12

  35. "pp---p--p-----p"

    Returns: 12

  36. "p-p-----------p"

    Returns: 12

  37. "p-p-p--p-----pp"

    Returns: 11

  38. "p-------p-----p"

    Returns: 12

  39. "p----p-p-p----p"

    Returns: 12

  40. "p-p-ppp--p----p"

    Returns: 12

  41. "p--p------p-p-p"

    Returns: 8

  42. "p---------p-p-p"

    Returns: 8

  43. "p---p--p-ppp--p"

    Returns: 12

  44. "p-----p-pp----p"

    Returns: 12

  45. "p-----p-p-p---p"

    Returns: 12

  46. "p-p-----p--p--p"

    Returns: 12

  47. "p----p---p-p--p"

    Returns: 12

  48. "p------p--p-p-p"

    Returns: 8

  49. "p---pp-p----p-p"

    Returns: 10

  50. "p------------pp"

    Returns: 11

  51. "pp---------p--p"

    Returns: 12

  52. "pp---p-p----p-p"

    Returns: 10

  53. "p------p-p----p"

    Returns: 12

  54. "p-------------p"

    Returns: 12

  55. "-"

    Returns: 0

  56. "--"

    Returns: 0

  57. "p"

    Returns: -1

  58. "-p"

    Returns: 0

  59. "pp"

    Returns: -1

  60. "p---p-p--p"

    Returns: 7

  61. "p----p"

    Returns: 3

  62. "p-------------p"

    Returns: 12

  63. "p-----------p-p"

    Returns: 10

  64. "p------p------p"

    Returns: 12

  65. "p------p"

    Returns: 5

  66. "p-p"

    Returns: 1

  67. "p---p------p---"

    Returns: 14

  68. "p---p------p"

    Returns: 9

  69. "p----p-"

    Returns: 6

  70. "p---pp-p--p"

    Returns: 8

  71. "p-p-p------p"

    Returns: 9

  72. "p----"

    Returns: 4

  73. "p-------p----p"

    Returns: 11

  74. "p-----p-----p"

    Returns: 10

  75. "p----p--p"

    Returns: 6

  76. "p-p--p"

    Returns: 3

  77. "p-p-p-p-p-p---p"

    Returns: 12

  78. "ppp--p"

    Returns: 3

  79. "p---p----p--p"

    Returns: 10

  80. "ppp--------ppp-"

    Returns: 14

  81. "p----pp-pppppp"

    Returns: 3

  82. "p---p--p"

    Returns: 5

  83. "p-p-p-"

    Returns: 5

  84. "p---p----p----p"

    Returns: 12

  85. "p-----p---p"

    Returns: 8

  86. "p---p----p---p"

    Returns: 11

  87. "p----p--p----p"

    Returns: 11

  88. "p--p--p"

    Returns: 4

  89. "p---p-p---p"

    Returns: 8

  90. "p----------p--p"

    Returns: 12

  91. "pp---pp--"

    Returns: 8

  92. "p-----p------pp"

    Returns: 11

  93. "p---p---p--p"

    Returns: 9

  94. "pp-"

    Returns: 2

  95. "p-----p--p"

    Returns: 7

  96. "pp-----p-"

    Returns: 8

  97. "-p--"

    Returns: 0

  98. "pp---pp--p"

    Returns: 7

  99. "p------------p"

    Returns: 11

  100. "-p---p---p---p-"

    Returns: 0

  101. "p--"

    Returns: 2

  102. "p---pp----p--p"

    Returns: 11

  103. "p---pp-"

    Returns: 6

  104. "p"

    Returns: -1

  105. "p--p-"

    Returns: 4

  106. "p--------"

    Returns: 8

  107. "-p-------------"

    Returns: 0

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: