So, how can we compute this efficiently? The key to my program running quickly is that total number of electoral votes (538) is much smaller than the total number of possible election outcomes (2^50).
Imagine we have a partially computed an election in which k states have already voted, and that pk,i is the probability that the democrats have won exactly i electoral votes after the first k elections have run. Furthermore, let vk be the number of electoral votes for state k and ek be the probability state that state k elects a democrat.
How can we compute pk,i? Well, this simple little recurrence will do it.
pk,i = ek * pk-1,i - vk + (1 - ek) * pk-1, i. Basically, with probability ek the state votes democrat and has i - vk votes left, otherwise, with probability 1 - ek it votes republican (assuming two party system), and the democrat still has i votes left. For this problem, we only need about 539 * 51 table entries (we could even do something clever and push the needed space down to 539 entries, but I'll leave that as an exercise for the reader).
After I implemented this, the computation runs much more quickly than one second and provides an exact answer.
Looking at the code a bit more, I found a (slightly refactored) snippet of code like this. I assume the code is supposed to output the outcomes in order. Take a look at the comment, is it simpler than sorting? Is it even correct? I challenge both accounts.
def render_outcome(pdem, prep, ptie): dstring="Obama: <span style=\"color: #0000FF\">"+str(round(pdem,1))+"</span>" rstring="McCain: <span style=\"color: #FF0000\">"+str(round(prep, 1))+"</span>" tstring="Tie: <span style=\"color: #888888\">"+str(round(ptie, 1))+"</span>" if pdem>prep and prep>ptie: return dstring+"\n"+rstring+"\n"+tstring if prep>pdem and pdem>ptie: return rstring+"\n"+dstring+"\n"+tstring #just in case ... (easier to do this than a sort) if pdem>ptie and ptie>prep: return dstring+"\n"+tstring+"\n"+rstring if prep>ptie and ptie>pdem: return rstring+"\n"+tstring+"\n"+dstring if ptie>pdem and pdem>prep: return tstring+"\n"+dstring+"\n"+rstring if ptie>prep and prep>pdem: return tstring+"\n"+rstring+"\n"+dstring return tstring+"\n"+rstring+"\n"+dstring
Here is my alternative implementation.
def render_outcome2(pdem, prep, ptie): dstring="obama: <span style=\"color: #0000ff\">"+str(round(pdem,1))+"</span>" rstring="mccain: <span style=\"color: #ff0000\">"+str(round(prep, 1))+"</span>" tstring="tie: <span style=\"color: #888888\">"+str(round(ptie, 1))+"</span>" l = [(pdem, dstring), (prep, rstring), (ptie, tstring)] return '\n'.join(pair for pair in sorted(l, reverse=True))
Mine definitely seems simpler. It relies on the natural sorting order of python tuples to get the messages sorted in the right order.
Is his implementation correct? Well.. notice all of those < operators (not <=). What happens with ties?
>>> print states.render_outcome(.4, .3, .3) Tie: 0.3 McCain: 0.3 Obama: 0.4
In all fairness, quoting the page, Randall says "I made this tool to help me understand the race, especially on election night." I am sure he just wanted to get things done, and not have some nerd nitpick at all of the code. The Monte Carlo simulation is a bit easier to code than the dynamic program I posted and it gets things done. His code basically works. I don't think he actually sucks at programming, I just wanted to put some blood on the pages for reddit. Furthermore, I was thinking about using this problem as an interview question, but after trying it on a few of my coworkers (who all have at least a BS in computer science from a nice university), I think it's a bit too hard.