Connection Status:
Competition Arena > BestYahtzeeScore

BestYahtzeeScore

SRM 262 · 2005-09-09 · by Olexiy

SRM 262 · 2005-09-09 · by Olexiy · Brute Force, Dynamic Programming, Recursion, Search
Class Name: BestYahtzeeScore
Return Type: int
Method Name: bestScore
Arg Types: (string)
Problem Statement

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.

Notes

  • 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.

Constraints

  • rolls will contain exactly 15 characters.
  • Each character in rolls will be between '1' and '6', inclusive.
Examples
0)
"354621111111111"
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.

1)
"666663213214444"
Returns: 50

Here you get Yahtzee after the first roll. You should keep all the dice.

2)
"666111333222555"
Returns: 25
3)
"566111333222555"
Returns: 25
4)
"666111555333222"
Returns: 25
6)
"652353235164412"
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.

30)
"144165526421151"
Returns: 0

You can't satisfy the requirements for any category.

Submissions are judged against all 79 archived test cases, of which 7 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class BestYahtzeeScore with a public method int bestScore(string rolls) · 79 test cases · 2 s / 256 MB per case

Submitting as anonymous