For the most part the comments so far are:
- people misunderstanding the problem (which is not surprising; it's the sort of problem mathematicians are better at understanding than the general population, and the audience there is not necessarily mathematicians);
- programmer types whining "waah, this problem is in NP, I can't do it!". Is it in NP? I don't feel like thinking about that -- but I did it in a few minutes, and more importantly with a couple seconds of computation time. NP doesn't stand for "not possible";
- people saying "who cares, most of those combinations are politically unrealistic!" (which I have to admit is true);
- a few estimates of the answer based on some quick and dirty statistical assumptions, which look basically right;
- and a couple people (me included) who have gotten a numerical answer.
What's interesting to see is that a lot of people seem to believe you have to actually generate the sets in order to count them. That would of course be hopeless. The explanation of combinatorics as "counting without counting" comes to mind.
7 comments:
Your solution is lovely and elegant. I was impressed.
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.
To defend the CS types:
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.
Some CS types just don't understand the concept of an easy instance. Be glad they aren't cryptographers.
Great solution Isabel. Coincidentally, I've been reading parts of Generatingfunctionology recently.
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."
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".
I was surprised how close the quick and dirty statistical solution came to the exact answer.
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...)
Coincidently, given todays computation power, we can solve a knap sack problem with 50 problems exhaustively.
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.
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.
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. :-)
Here's the code:
use Memoize;
memoize 'calc';
memoize 'nCm';
my @evs = ( [55, 1], [34, 1], [31, 1], [27, 1], [21, 2], [20, 1], [17, 1],
[15, 3], [13, 1], [12, 1], [11, 4], [10, 4], [9, 3], [8, 2],
[7, 4], [6, 3], [5, 5], [4, 5], [3, 8] );
sub calc {
my ($i, $worktot) = @_;
return 0 if ($i > $#evs);
my ($val, $mul) = @{$evs[$i]}[0..1];
my ($sum, $goal, $count, $p) = (0, 270, $mul);
do {
$sum += nCm($mul, $count) *
(($p < $goal) ? calc($i + 1, $p) : 1)
if $goal + $val > ($p = $count * $val + $worktot);
} while (--$count >= 0);
return $sum;
}
sub nCm {
my ($n, $m) = @_;
$m = $n - $m if ($m > ($n/2));
my $total = 1;
for (1..$m) { $total *= $n-- / $_; }
$total;
}
printf("%s\n", calc(0, 0));
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 RoI
Post a Comment