programming is fun
November 2, 2024
Steve entered the Western States 100 lottery after qualifying in January... They are limited to 369 runners each year, and it's a legendary race, so there's a lot of demand. They have an interesting lottery structure: every year that you qualify and enter the lottery, if you are not picked, you get twice the entry tickets the next year.
November 2, 2024
After some early morning text messages where I tried (and to be honest, failed miserably) to calculate his odds, I wrote a little program in C to do the calculation.
Then, because sometimes programming is fun, I decided to see what it would look like in Perl. I haven't written a ton of Perl, I usually lean towards PHP for this sort of thing, but I ported SWELL's resource-processor script to Perl a while back and enjoyed it, and having a simple task is good for learning.
The first pass I did used a builtin array shuffle module, which proved too slow, then I ended up simplifying it and got it significantly faster than the C version (which didn't reshuffle, but did end up with pointless memmove()s). Once I had it all working (using strict, e.g. you have to declare everything), I decided to see how small I could get it to be. Here's what I ended up with (you can pipe the table on their lottery entry page to it):
$nwin = 250; # I think the lottery picked about 250-something winners last year, the rest were golden tickets and such
$nlot = 100000; # someone could quantify the margin of error based on this, with statistics you would oh look a bird
for ($pid = 0; <>; ) {
($nt, $np) = split(/\s+/, s/,//r);
($nt > 0 and $np > 0 and not exists $wcnt{$nt}) or die "invalid input: $_\n";
$wbin{$pid} = $nt;
$wcnt{$nt} = 0;
push(@tk, ($pid++) x $nt) while ($np-- > 0);
}
printf("%d tickets for %d entrants, running %d lotteries for %d winners:\n", $tkcnt = @tk, $pid, $nlot, $nwin);
for ($x = 0; $x < $nlot; $x++) {
%in = { };
$in{$id = $tk[rand($tkcnt)]}++ == 0 and exists $wbin{$id} and $wcnt{$wbin{$id}}++ while (%in < $nwin);
}
printf("%d tickets: %.2f%% win\n", $_, $wcnt{$_} * 100.0 / $nlot) foreach (sort { $a <=> $b } keys %wcnt);
Here is the most recent input:
512 1 512 256 15 3,840 128 55 7,040 64 139 8,896 32 215 6,880 16 296 4,736 8 594 4,752 4 963 3,852 2 1,538 3,076 1 2,077 2,077and here is the most output with that table:
45661 tickets for 5893 entrants, running 100000 lotteries for 250 winners: 1 tickets: 0.66% win 2 tickets: 1.29% win 4 tickets: 2.56% win 8 tickets: 5.08% win 16 tickets: 9.99% win 32 tickets: 18.98% win 64 tickets: 34.12% win 128 tickets: 56.51% win 256 tickets: 80.91% win 512 tickets: 96.24% winSo, Steve's odds as of this afternoon are about 0.66%, but that will almost certainly go down (there's still a month left of the lottery; it only opened yesterday). Interestingly, one entrant there has been turned down 8 times before -- they currently have a 96% chance of getting in. And those who have been turnwed down 6 times before are slightly more likely than not to get in.
2 Comments
