TopCoder problem "BestYahtzeeScore" used in SRM 262 (Division I Level Two)

Problem Statement


Yahtzee is a game played with 5 dice and a score card. The object of the game is to get the best score. A turn consists of the following:

  1. Roll all of the dice.
  2. Keep as many of the dice as you want.
  3. Re-roll the dice you decide not to keep. Note that at any time if you like your hand you can stop rolling.
  4. Repeat step two and three. Note that you can throw away some of the dice that you previously kept.
  5. Now that you've had up to three rolls, record the resulting roll in a single place on your score card (scoring only applies to the final hand you keep).

Your score card is divided up as follows:

  • 4 of a kind - 4 or more dice the same, scores the face value of ALL the dice.
  • full house - 3 dice equal to each other with the other 2 dice equal to each other as well. Scores 25 points.
  • small straight - Any 4 of the dice in consecutive order, scores 30 points.
  • large straight - All 5 dice in consecutive order, scores 40 points.
  • yahtzee - All 5 dice equal to each other, scores 50 points.

You are given a String rolls containing fifteen numbers, the first five of which are your first roll, and the next ten what you would get if you continued to roll in order. For instance, if input is "123456123456123" your first roll gives you "12345". If you keep the 1, 2, and 5, and reroll the other two your hand would now look like "12615". Now if you keep the two 1's and reroll the other three, your final hand would be "12314". You are to return the best possible score you can get.



Method signature:int bestScore(String rolls)
(be sure your method is public)


-You can choose only 1 category. That is, you can not get points for 2 categories if your hand satisfies requirements for both.
-Straights cannot wrap around. "12346" would count as a small straight, but not a large straight.
-You can reorder your dice as you want to fit into a category. That is, "64523" can be reordered as "23456" and scored as a large straight.


-rolls will contain exactly 15 characters.
-Each character in rolls will be between '1' and '6', inclusive.


Returns: 50
You get 3, 5, 4, 6 and 2 after the first roll. You should re-roll all dice and get with 1 on all five faces.
Returns: 50
Here you get Yahtzee after the first roll. You should keep all the dice.
Returns: 40
After the first roll you get "65235" and throw away all the dice. The second roll gives you "32351". You should keep "235" and re-roll the other two dice. You finish with "23564", which is a large straight.
Returns: 25
Returns: 0
You can't satisfy the requirements for any category.

Problem url:

Problem stats url:




PabloGilberto , brett1479 , Olexiy

Problem categories:

Brute Force, Dynamic Programming, Recursion, Search