TopCoder problem "YahtzeeRoll" used in SRM 222 (Division II Level Three)

Problem Statement


The game of Yahtzee is a popular dice game in which players roll 5 dice, and may (optionally) re-roll some or all of the dice on two further rolls. After all three rolls, the best "hand" that can created from the values showing on all of the dice is scored, and the player is awarded points. There are several different types of hands, and a player may only get points for each type of hand once per game.

You are playing Yahtzee, and have taken two of your three rolls. The values showing on the five dice are given in the int[] dice. Based upon the empty slots still available on your score card, and the values showing on the dice, you want to know which dice to re-roll in order to obtain the highest possible expected point outcome. Remember that, statistically speaking, your expected outcome is the probability of an event taking place multiplied by the payoff (in this case, points earned) by that event.

Looking over your scorecard, you realize that the only four remaining items are full house (three of a kind and two of a kind), worth 25 points, small straight (4 consecutive values, no wrapping), worth 30 points, large straight (all five dice are consecutive values), worth 40 points, and Yahtzee (all five dice show the same value), worth 50 points.

You are to return a double indicating the expected score outcome when the player optimally chooses which dice to re-roll.



Method signature:double bestChoice(int[] dice)
(be sure your method is public)


-The game of Yahtzee uses standard, six-sided dice, with values 1 through 6.
-Although Yahtzee includes many different ways to score points, it is assumed for this problem that the four hands described in the problem are the only ones available.
-If the dice form a large straight, 40 points are scored. Even though the hand technically also could be used as a small straight, no additional points are scored for the small straight.
-For both small and large straights, the values do not wrap; so, 5,6,1,2 is not a small straight.
-Your return must have an absolute or relative error less than 1e-9.


-dice will contain exactly five elements.
-Each element of dice will be between 1 and 6, inclusive.


{ 1, 1, 1, 1, 2 }
Returns: 8.333333333333334
Here, keeping all of your 1's and re-rolling the 2 gives you a 1/6 chance of scoring 50 points. Alternately, keeping the 2 and re-rolling one of your 1's gives you a 1/6 chance in scoring 25 points for the full house. Thus, the best option is to go for the Yahtzee. The probability of 1/6 multiplied by 50 points gives the expected 8.333 points.
{ 1, 1, 1, 2, 2 }
Returns: 25.0
Here, you already have a full house. Re-rolling anything is risky when keeping what you have is a guaranteed 25 points.
{ 2, 3, 4, 5, 5 }
Returns: 33.333333333333336
Here, we already have ourselves a small straight, but by re-rolling one of the 5's, we have a chance at a large straight if we roll either a 1 or a 6. So, we have a 1/3 chance of scoring 40 points, or a 2/3 chance of keeping our 30 points. (1/3) * 40 + (2/3) * 30 = 33.333.
{ 2, 2, 3, 4, 4 }
Returns: 17.77777777777778
At first glance, it might seem like re-rolling our 3 and going for a full house is the safest best. This is a 1/3 chance of scoring 25 points = 8.333 expected points. But, if we keep (2, 3, 4) and re-roll the other two, we actually have a 1/9 chance of making a large straight, and a 4/9 chance of making a small straight. (1/9) * 40 + (4/9) * 30 = 160/9 = 17.778 expected points, which is a much better choice.
{ 6, 1, 3, 5, 5 }
Returns: 9.722222222222221

Problem url:

Problem stats url:




PabloGilberto , lbackstrom , brett1479

Problem categories:

Advanced Math, Brute Force, Simulation