tag:blogger.com,1999:blog-264226589944705290.post9158163362214428110..comments2022-08-07T01:05:01.413-07:00Comments on God Plays Dice: Some electoral math from fivethirtyeight.comMichael Lugohttp://www.blogger.com/profile/15671307315028242949noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-264226589944705290.post-82392544995946542592008-06-12T09:32:00.000-07:002008-06-12T09:32:00.000-07:00guessing before reading anything else on this page...guessing before reading anything else on this page or those linked: generatingfunctionology? Even if it's not the quickest route, the overhead involved in setting up the problem lends itself to answering related questions, and thus gives a pretty good RoIAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-20621286228831908762008-06-11T21:57:00.000-07:002008-06-11T21:57:00.000-07:00I tried it, on your advice. My weapon of choice i...I tried it, on your advice. My weapon of choice is Perl. It wasn't hard, but it was surprisingly tricky to get it exactly right. The program also definitely requires memoization -- not entirely coincidentally a topic that you've discussed before, and somewhat coincidentally a Perl module that Mark-Jason Dominus developed. I'll note that even with your approach you used a software system to automate the tedium.<BR/><BR/>I'll also note that the number of function calls to "calc()", with Memoization, was only 13307, which surprised and pleased me, not least because the echo of l337. :-)<BR/><BR/>Here's the code:<BR/><BR/><BR/><BR/>use Memoize;<BR/>memoize 'calc';<BR/>memoize 'nCm';<BR/><BR/>my @evs = ( [55, 1], [34, 1], [31, 1], [27, 1], [21, 2], [20, 1], [17, 1],<BR/> [15, 3], [13, 1], [12, 1], [11, 4], [10, 4], [9, 3], [8, 2],<BR/> [7, 4], [6, 3], [5, 5], [4, 5], [3, 8] );<BR/>sub calc {<BR/> my ($i, $worktot) = @_;<BR/> return 0 if ($i > $#evs);<BR/><BR/> my ($val, $mul) = @{$evs[$i]}[0..1];<BR/> my ($sum, $goal, $count, $p) = (0, 270, $mul);<BR/><BR/> do {<BR/> $sum += nCm($mul, $count) *<BR/> (($p < $goal) ? calc($i + 1, $p) : 1)<BR/> if $goal + $val > ($p = $count * $val + $worktot);<BR/> } while (--$count >= 0);<BR/><BR/> return $sum;<BR/>}<BR/><BR/>sub nCm {<BR/> my ($n, $m) = @_;<BR/> $m = $n - $m if ($m > ($n/2));<BR/> my $total = 1;<BR/> for (1..$m) { $total *= $n-- / $_; }<BR/> $total;<BR/>}<BR/><BR/>printf("%s\n", calc(0, 0));Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-2444626867301679152008-06-11T21:02:00.000-07:002008-06-11T21:02:00.000-07:00I don't think this problem is NP hard. Actually f...I don't think this problem is NP hard. Actually finding all the combinations would be, but that wasn't what was asked. It can be solved in approximately n^2 time, using essentially the same method Isabel used, writing out an algorithm that is probably very similar to what matlab uses to solve equations.Drew Millerhttps://www.blogger.com/profile/03654706383898656619noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-84490517824030560302008-06-11T04:46:00.000-07:002008-06-11T04:46:00.000-07:00I was surprised how close the quick and dirty stat...I was surprised how close the quick and dirty statistical solution came to the exact answer.<BR/><BR/>As ray points out, this is related to knap sack problem. (The knap sack problem would ask for the smallest number of delegates possible above 270...)<BR/>Coincidently, given todays computation power, we can solve a knap sack problem with 50 problems exhaustively.Sorooshhttps://www.blogger.com/profile/11104409220802901253noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-88601328303043062262008-06-10T17:32:00.000-07:002008-06-10T17:32:00.000-07:00Great solution Isabel. Coincidentally, I've been r...Great solution Isabel. Coincidentally, I've been reading parts of Generatingfunctionology recently. <BR/><BR/>As for the computer scientists and their cries of NP-hard, I'm reminded of the quote "The person who says it cannot be done should not interrupt the person doing it."<BR/><BR/>Also, unless those people are potential Turing award winners that haven't released their proof to the public yet, the "NP" in NP-hard does not mean "non-polynomial".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-73499118674750563442008-06-10T16:53:00.000-07:002008-06-10T16:53:00.000-07:00To defend the CS types: The problem is NP-hard and...To defend the CS types: <BR/><BR/>The problem is NP-hard and large enough to be unwieldy if not outright infeasible -- if you give each state a random 15 digit number of electoral votes.<BR/><BR/>Some CS types just don't understand the concept of an easy instance. Be glad they aren't cryptographers.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-52272031043710219562008-06-10T16:33:00.000-07:002008-06-10T16:33:00.000-07:00Your solution is lovely and elegant. I was impres...Your solution is lovely and elegant. I was impressed.<BR/><BR/>Also, according to facebook (because that's the sort of person I am), you know Megan Cook, who is an old associate of mine from Michigan. Small world.General Mobiushttps://www.blogger.com/profile/14815113152456623147noreply@blogger.com