TopCoder problem "YahtzeeAdversary" used in TCHS07 Gamma 2 (Division I Level Three)



Problem Statement

    

In the game of Yahtzee, 5 dice (6 sided) are rolled (and then some of them re-rolled) in an attempt to make one of several formations with the dice. We will introduce a new two-player version of the game in which player one first rolls all five dice, and then player two chooses at least two of the five dice, which the first player must then re-roll. The goal of player two is to minimize the expected score of the first player.

In our version of the game, we are only concerned about four possible results:

  • Yahtzee: All five dice show the same value
  • Large Straight: All five dice form a straight (1,2,3,4,5 or 2,3,4,5,6)
  • Small Straight: Four of the five dice form a straight
  • Full House: Three dice show the same value, and the other two also have the same value (ex. {1, 3, 1, 1, 3} or {2, 2, 2, 2, 2})

You are given a int[] scores indicating how many points each of the four formations is worth. (In order, they are given as Yahtzee, Large Straight, Small Straight, Full House) You are also given a int[] dice, indicating the values shown on each of the five dice after player one has rolled. You should return a int[] indiciating the 0-based indices of the dice that should be selected for re-rolling, to minimize the expected score of player one. If more than one selection of dice produces the same expected score, return the one that comes first lexicographically. (See notes)
 

Definition

    
Class:YahtzeeAdversary
Method:reRollDice
Parameters:int[], int[]
Returns:int[]
Method signature:int[] reRollDice(int[] scores, int[] dice)
(be sure your method is public)
    
 

Notes

-Although a set of five dice may fit the criteria for more than one formation, it can only be scored for one of the formations. The formation of maximum value will be used as the score. (Ex. 1,2,3,4,5 can only count as a small or large straight, but not both at once.)
-A set of five like values, such as {1, 1, 1, 1, 1} is both a Yahtzee and a Full House. The higher score of the two is counted.
-int[] A1 comes before int[] A2 lexicographically if A1 has a lower value in the first position at which they differ.
-To calculate the expected score, multiply the score of each possible outcome by the probability of that outcome, and sum those values together.
 

Constraints

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

Examples

0)
    
{50, 40, 30, 25}
{1, 1, 1, 1, 1}
Returns: {0, 1, 2 }
This is standard Yahtzee scoring. Rerolling four dice instead of just three increases the likelihood of getting a full house or straight. Rerolling three is the best bet. Picking any three of the five (since they are all showing the same value), we choose the three that come first lexicographically.
1)
    
{50, 40, 30, 25}
{1, 2, 3, 4, 5}
Returns: {2, 3 }
Notice that any possible straight we could form (small or large) would contain 3 and 4 in it. Forcing these two to be rerolled is a good move.
2)
    
{50, 40, 30, 25}
{5, 4, 3, 2, 1}
Returns: {1, 2 }
Notice that for this same example (in a different order) it is still those same two values.
3)
    
{10000, 0, 0, 0}
{1, 1, 1, 1, 1}
Returns: {0, 1, 2, 3 }
A Yahtzee is the only thing that can score us any points. Either rerolling all five dice or only four leaves the same odds of landing the Yahtzee, so we choose the lexicographically first possibility.
4)
    
{0, 0, 10000, 0}
{4, 2, 3, 4, 4}
Returns: {1, 2 }
Here, only a straight will be worth any points. Leaving the opponent with three like dice makes it impossible to end up with four dice in a straight. Please note that we must reroll at least 2 dice.
5)
    
{0, 0, 0, 1}
{3, 3, 3, 3, 3}
Returns: {0, 1, 2, 3 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7563

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10718&pm=7563

Writer:

timmac

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Brute Force, Math