Programming Challenges: 110208 Yahtzee

I completed the Yahtzee problem today, after a couple of days effort.

I first double checked my previous 2004 solution’s scoring function, there were a few gems in there that I had to reproove, like how the full house was worked out.

// a - e are the five dice rolls  
int array[7] = { 0,0,0,0,0,0,0 };  


// full house  
if ( ( array[a] + array[b] + array[c] + array[d] + array[e] ) == 13 )  
    scores[count][12] = 40;  

I then rewrote the recursive function to remove my fancy std::list<int> stuff and used simple arrays of ints, and wrote a completely naive checker. But at 6 billions checks per score set, it was never going to fit the time limit.

I then thought about it for a day, and this morning, wrote a version the skipped the skippable stuff, but it got the wrong answer, then I noticed a case I’d skipped that I shouldn’t have. I added that back in, and all of a sudden my code started giving really bad (low) score results.

I noticed the my best score function was entering (new_score > best_score) when they were the same values.

Much muttering, explaining to my wife and children later…

I noticed a compiler warning:

warning C4390: ';' : empty controlled statement found; is this the intent?  

from this:

if( new_value > best_value );  
    //cout << "b: " << best_value << " n: " << new_value << endl;  
    memcpy(best_set, current_set, sizeof(int)*13);  
    best_value = new_value;  

after removing the stupid semicolon and debugging text, my solution solved the puzzle!



Jake Nicholson 2010-09-03 04:48:25

Hi Simeon,

Grats on solving this challenge, it’s apparently not too easy. I took a crack at it a couple years ago, and have just recently been working on it anew (i’m getting ‘wrong answer’ now, trying to find a case where it’s wrong…). If you don’t mind I’m going to blab about my approaches so far, and if you care to share any insights I’d appreciate it.

My original approach (years ago) was to recursively try all 13! assignments, but try to prune the search by backtracking under certain conditions. I recall having trouble knowing exactly what these conditions would be, since the upper-bonus possibility made it tricky to know when a branch should be pruned. Is this similar to your approach, and if so what were your pruning criteria?

My approach this time around was to start by ignoring the upper-bonus rule, and find the optimal assignment using a matching algorithm (hungarian algorithm). If this assignment would yield the upper bonus, then I consider it the best assignment in any case (possibly incorrect assumption, but I don’t think so). If this assignment would not yield the bonus then I find the optimal matching for just the upper categories to see if a matching exists which would yield the upper bonus. If none exists, then I consider the original assignment as the best (again, incorrect assumption?). If the upper bonus is possible then I generate all upper-category assignments which yield the upper bonus and then for each I generate the maximum assignment of the lower categories using the unassigned rolls. I take as my final assignment that which yields the highest score if it’s > the original assignment score.

This method seems to find all the cases I could manufacture where it’d be better to score a roll in an upper category to get the bonus, instead of taking a yahtzee or other lower category score. However my submission gives a ‘wrong answer’ result.



Simeon 2010-09-04 17:44:41

Hi Jake,

Sorry for delay responding, have just been travelling, and it will take me a few more days to have a worthwhile response.


Simeon 2010-09-20 14:31:29

Hi Jake,

The basic answer is that I calculate the points for each row as they are read in. The I run a recursive search for the maximum allocation/assignment.

I calculate the bonus in the recursion termination step. The two tricks I do is I order my recursion reverse order (i.e. do the zero or fixed value items first with total 1’s last), and for any level of the recursion, skip rows that have a zero in the current place, yet do a single recursion of a unmarked zero row.

Thus in a hand that there is only one row that is a full-house and the rest are not, I only have two branches at that level in the recursion tree.