Matthew van Eerde's web log

  • Matthew van Eerde's web log

    What is a perfect score in Yahtzee?

    • 9 Comments

    The dice game Yahtzee takes thirteen turns. Each turn involves rolling a set of five dice (with two possible rerolls, the player having the option to reroll only a subset of the dice), then marking one of thirteen boxes and scoring points according to whether the numbers on the dice meet the rules of the box. After each box is marked, the game is over.

    The thirteen boxes and their rules are:

    1. ONES: score is the sum of those dice showing a one (could be zero.)
    2. TWOS: score is the sum of those dice showing a two (could be zero.)
    3. THREES: score is the sum of those dice showing a three (could be zero.)
    4. FOURS: score is the sum of those dice showing a four (could be zero.)
    5. FIVES: score is the sum of those dice showing a five (could be zero.)
    6. SIXES: score is the sum of those dice showing a six (could be zero.)
    7. THREE OF A KIND: if three of the dice show the same number, the score is the sum of all five dice; otherwise, zero.
    8. FOUR OF A KIND: if four of the dice show the same number, the score is the sum of all five dice; otherwise, zero.
    9. FULL HOUSE: if three of the dice show the same number as each other, and the other two show the same number as each other, score 25; otherwise, zero.1
    10. SMALL STRAIGHT: if there are four dice which show (1 2 3 4), or (2 3 4 5), or (3 4 5 6), score 30; otherwise, zero. (There is no defined order for the rolled dice, so order is not important.)
    11. LARGE STRAIGHT: if the five dice show (1 2 3 4 5), or (2 3 4 5 6), score 40; otherwise, zero. (Order is not important.)
    12. CHANCE: score the total of the five dice (minimum possible score is 5.)2
    13. YAHTZEE (FIVE OF A KIND:) if all five dice show the same number, score 50; otherwise, zero.

    There are two bonuses possible:

    1. At the end of the game, if the point total for boxes 1-6 (ONES through SIXES) is at least 63, the player gets a bonus of 35. (63 corresponds to getting three ones + three twos + three threes + ... + three sixes, but there are other possibilities. I don't know where 35 came from.)
    2. At any time the player checks a box, if...
      • the five dice all have the same number as each other
      • AND the Yahtzee box is already checked
      • AND this was not a result of "taking a zero in Yahtzee"
      ... then the player gets a bonus 100 points. This bonus can take effect multiple times per game.

    So a perfect Yahtzee game looks like this. On the first turn...

    Roll Box Score
    (x x x x x) any Yahtzee YAHTZEE 50
    Subtotal 50

    ... then on the following turns, in no particular order (but see below:)

    Roll Box Score
    (1 1 1 1 1) ONES 5
    (2 2 2 2 2) TWOS 10
    (3 3 3 3 3) THREES 15
    (4 4 4 4 4) FOURS 20
    (5 5 5 5 5) FIVES 25
    (6 6 6 6 6) SIXES 30
    (6 6 6 6 6) THREE OF A KIND 30
    (6 6 6 6 6) FOUR OF A KIND 30
    (x x x x x) any Yahtzee FULL HOUSE 0 or 25 (see below)1
    (x x x x x) any Yahtzee SMALL STRAIGHT 0 (but see below)
    (x x x x x) any Yahtzee LARGE STRAIGHT 0 (but see below)
    (6 6 6 6 6) CHANCE 30
    Subtotal 195 or 220

    Now we look at the bonuses and add it all up:

    Category Score
    Base score 245 or 270
    Bonus for scoring >= 63 in ONES through SIXES 35
    Bonus for scoring twelve additional YAHTZEEs after scoring 50 in YAHTZEE 1200
    Total 1480 or 1505

    So a perfect score in Yahtzee is 1480 or 1505.

    Well...

    ... not quite. There's another rule about Yahtzees (the "Joker" rule) which I didn't tell you about yet, because it's kind of complicated. If...

    • You roll a Yahtzee
    • AND the YAHTZEE box is already checked (a zero score is OK; you don't get the 100 point bonus, but this rule still applies)
    • ... then you MUST score this in the ONES-through-SIXES box for the number you rolled (say, 3)...
    • ... UNLESS that box has also already been checked (a zero score is OK), in which case...

    ... you can score this roll in any unchecked box and it automatically meets the scoring criterion (wow!) So you would get 30 points in SMALL STRAIGHT or 40 points in LARGE STRAIGHT. (Or 25 points in FULL HOUSE.)1

    This gives an additional 70 or 95 points, bring the total to 1575. (It also creates additional order dependencies; the boxes for FULL HOUSE, SMALL STRAIGHT, and LARGE STRAIGHT must be checked after the ONES through SIXES box for the corresponding number is checked.)

    1 Does five-of-a-kind count as a full house? I'm not sure. Mathematically it would make sense. It turns out not to matter for this calculation because of the Joker rule, but it may matter in an actual game. The official rules say "Score in this box only if the dice show three of one number and two of another", so I guess not, but I would be comfortable adopting a "house rule" which allowed a Yahtzee to count as a "native" full house. Normally a house rule should be agreed upon by all players before the start of the game, but I'm pretty sure it would be possible to convince the other players to let you score your (3 3 3 3 3) in FULL HOUSE while YAHTZEE was still open. ("You want to throw away 25 points?  Really?  Um, go right ahead...")

    2 The lowest possible Yahtzee score is 5: get (1 1 1 1 1) and score it in Chance, then get zeros in all the other boxes.

  • Matthew van Eerde's web log

    Command-line app to set the desktop wallpaper

    • 0 Comments

    Working on Windows, I find myself installing Windows a lot.

    I find that I like to change a lot of the settings that Windows offers to non-default values.  (That is, I'm picky.)

    I have a script which automates some of these things, which I add to now and again.  Some of the bits of the script are straightforward, but once in a while the tweak itself is of interest.

    One of the things I love about my work setup is the many large monitors.  So, one of the things I like to change is the desktop wallpaper image.

    Changing the desktop wallpaper required some code, which makes it "of interest."  Here's the code.

    // main.cpp

    #include <windows.h>
    #include <winuser.h>
    #include <stdio.h>

    int _cdecl wmain(int argc, LPCWSTR argv[]) {
        if (1 != argc - 1) {
            wprintf(L"expected a single argument, not %d\n", argc);
            return -__LINE__;
        }
       
        if (!SystemParametersInfo(
            SPI_SETDESKWALLPAPER,
            0,
            const_cast<LPWSTR>(argv[1]),
            SPIF_SENDCHANGE
        )) {
            DWORD dwErr = GetLastError();
            wprintf(L"SystemParametersInfo(...) failed with error %d\n", dwErr);
            return -__LINE__;
        }
       
        wprintf(L"Setting the desktop wallpaper to %s succeeded.\n", argv[1]);   
        return 0;
    }

     

    Binaries attached.

    Warning: if you pass a relative path to this tool, it won't qualify it for you, and the SystemParametersInfo call won't either - so the wallpaper you want won't be set, though all the calls will succeed.  Make sure to specify a fully-qualified path.

     

  • Matthew van Eerde's web log

    How to create a shortcut from the command line

    • 0 Comments

    Working on Windows, I install Windows a lot.  This means a lot of my customizations have to be re-applied every time I install.  To save myself some time I created a script which applies some of them. Last time I showed how to set the desktop wallpaper from a command-line app.

    This time, a script to create a shortcut.  The example usage creates a shortcut to Notepad and puts that in the "SendTo" folder.  I find this very useful because I often need to edit text files that have non-".txt" assocations.  (There are also other shortcuts I create with it.)

     

    Here's the script:

    >create-shortcut.vbs

    If WScript.Arguments.Count < 2 Or WScript.Arguments.Count > 3 Then
        WScript.Echo "Expected two or three arguments; got " & WScript.Arguments.Count
        WScript.Echo "First argument is the file to create"
        WScript.Echo "Second is the command to link to"
        WScript.Echo "Third, if present, is the arguments to pass"
        WScript.Quit
    End If

    Set shell = WScript.CreateObject("WScript.Shell")

    Set link = shell.CreateShortcut(WScript.Arguments(0))
    link.TargetPath = WScript.Arguments(1)

    If WScript.Arguments.Count = 3 Then
        link.Arguments = WScript.Arguments(2)
    End If

    link.Save

    >cscript create-shortcut.vbs "%appdata%\Microsoft\Windows\SendTo\Notepad.lnk" notepad.exe

  • Matthew van Eerde's web log

    Generating primes using the Sieve of Eratosthenes plus a few optimizations

    • 0 Comments

    When solving Project Euler problems I frequently need to iterate over prime numbers less than a given n. A Sieve of Eratosthenes method quickly and easily finds the small prime numbers; there are more complicated methods that find larger prime numbers, but with a couple of tweaks the Sieve of Eratosthenes can get quite high.

    A naive implementation for finding the set of primes below n will:

    1. Allocate an array of n booleans, initialized to false.
    2. Allocate an empty list
    3. For each i in the range 2 to n:
      1. If the boolean value at this index in the array is true, i is composite. Skip to the next value and check that.
      2. If the boolean value at this index in the array is false, i is prime!
      3. Add i to the list of primes
      4. For each multiple of i in the range 2i to n, set the boolean value at that index in the array to true

    There are a handful of simple optimizations that can be made to this naive implementation:

    1. Step 3d) will have no effect until the multiple of i reaches i2, so the range can be changed to "i2 to n"
    2. As a direct consequence of this, step 3d) can be skipped entirely once i2 passes n.
    3. Instead of allocating an array of n booleans, an array of nbits will suffice.
    4. All the even-indexed bits are set to true on the first pass. Manually recognize that 2 is prime, and only allocate bits for odd-numbered values. Change the outer loop in 3) to "in the range 3 to n", incrementing by two each time. Change the loop 3d) to increment by 2i each time.
    5. Storing the list of primes takes a lot of memory - more than the sieve. Don't bother creating a list of primes, just write an enumerator that travels the sieve directly.

    With these optimizations I can enumerate primes from 2 up to 5 billion (5 * 109) in about seven minutes.  Source and binaries attached.

    >primes 5000000000
    Will enumerate primes <= 5000000000 = 5e+009
    Memory for sieve: 298.023 MB
    Initialization complete: 983 milliseconds since start
    Sieving to 70711
    Sieving complete: 4.70292 minutes since start
    Picking up the rest to 5000000000
    Pickup complete: 6.12252 minutes since start
    Primes: 234954223
    1: 2
    23495423: 442876981
    46990845: 920233121
    70486267: 1410555607
    93981689: 1909272503
    117477111: 2414236949
    140972533: 2924158169
    164467955: 3438252577
    187963377: 3955819157
    211458799: 4476550979
    234954221: 4999999883
    Enumerating complete: 7.43683 minutes since start
    Freeing CPrimes object

    There are more complicated sieves like the Sieve of Atkin which perform better but at the cost of being much more complex. So far I haven't had to resort to any of those.

  • Matthew van Eerde's web log

    Programmatically grabbing a screenshot of the primary display

    • 0 Comments

    It's sometimes difficult to explain to people what my job actually is. "I test Windows sound." "Cool.  How does that work?"

    A product like Windows has a lot of components that interact with each other.  If everything works, the user doesn't know that most of these components even exist; everything is invisible and seamless.

    Most testing involves the connection ("interface") between two components.  "I test APIs."  To the uninitiated, this is just a word.  It sounds like "I test wakalixes."  "You test what, now?"

    There are two interfaces which are easier to explain.  There's the software-to-hardware interface, where the driver talks to the hardware.  "I test the HD Audio, USB Audio, and Bluetooth audio class drivers."  "Huh?" "They make the speakers and the microphone work."  "Oh, cool.  So you sit around and use Skype all day?"

    But the easiest of all to explain is the user interface.  "I make sure that the Sound Recorder app, the volume slider, and the Sound control panel work." "Oh, that!  I had this annoying problem once where..."

    What does the test result for an invisible interface look like? A lot of logging.  "I expected this call to succeed; it returned this HRESULT."  "I poked the hardware like this and got a bluescreen."  "There seems to be an infinite loop here."  Lots of text. 

    Boring.

    UI testing has logging too.  But with UI testing you can also... TAKE PICTURES!  A UI bug is a lot easier to understand (triage, and fix) if there's a screenshot attached (preferably with a big red rectangle highlighting the problem.)

    It is therefore valuable to have an automatable utility that can take a screenshot and dump it to a file.  Here's one I cribbed together from the "Capturing an Image" sample code on http://msdn.microsoft.com/en-us/library/dd183402(v=VS.85).aspx.  Source and binaries attached.

    This version only captures the main display, and not secondary monitors (if any.)

    Pseudocode:

    screen_dc = GetDC(nullptr);

    memory_dc = CreateCompatibleDC(screen);

    rect = GetClientRect(GetDesktopWindow());

    hbmp = CreateCompatibleBitmap(screen_dc, rect);

    SelectObject(memory_dc, hbmp);

    BitBlt(memory_dc, rect, screen_dc);

    bmp = GetObject(hbmp);

    bytes = allocate enough memory

    bytes = GetDIBits(screen_dc, bmp, hbmp)

    file = CreateFile();

    WriteFile(bitmap header);

    WriteFile(bytes);

Page 1 of 1 (5 items)

November, 2011