Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
121 lines (93 sloc) 4.07 KB
import json
import pandas as pd
import os
def winnerloser(results):
'''Return ('gop', 'dem') if GOP won, else return ('dem', 'gop').'''
demevs = sum(result['evs'] for state, result in results.items()
if result['dem'] - result['gop'] > 0)
gopevs = sum(result['evs'] for state, result in results.items()
if result['gop'] - result['dem'] > 0)
return ('gop', 'dem') if gopevs > demevs else ('dem', 'gop')
def loststates(results):
'''Return list of states lost by loser.'''
winner, loser = winnerloser(results)
return {state: result for state, result in results.items()
if result[winner] > result[loser]}
def evsreqd(results, total=538):
'''Returns number of addional EVs required by loser to change outcome.'''
lost = sum(result['evs'] for state, result in loststates(results).items())
won = total - lost
reqd = total//2 + 1 - won
return reqd
def findflips(results):
'''
Determine states to which one would need to relocate the smallest possible
number of voters for the losing party to change the electoral college
winner (assuming no one changes their vote).
'''
winner, loser = winnerloser(results)
items = [(state, result[winner] - result[loser] + 1, result['evs'])
for state, result in loststates(results).items()]
flips, _ = complementaryknapsack(items, evsreqd(results))
return flips
def printresults(flips, loser='Democrats'):
for flip in flips:
print('Move {} {} to {} for {} EVs'.format(flip[1], loser, flip[0],
flip[2]))
print('Total of {} people for {} EVs'.format(
sum(flip[1] for flip in flips), sum(flip[2] for flip in flips)))
def complementaryknapsack(items, W):
'''
Solve complementary knapsack problem for an iterable of items and knapsack
capacity W. Each item is a (label, value, weight) triple.
Returns the items selected and their total value.
The complementary knapsack selection is the subset of items that minimizes
the total value of the knapsack while exceeding its capacity.
See http://stackoverflow.com/a/7950524/409879.
'''
Wtot = sum(weight for label, value, weight in items)
picks, _ = knapsack(items, Wtot - W)
complement = [(label, value, weight) for label, value, weight in items
if label not in [labelp for labelp, _, _ in picks]]
complementvalue = sum(value for label, value, weight in complement)
return complement, complementvalue
def knapsack(items, W):
'''
Solve knapsack problem for an iterable of items and knapsack capacity W.
Each item is a (label, value, weight) triple.
Returns the items selected and their total value.
The knapsack selection is the subset of items that maximizes the total
value of the knapsack without exceeding its capacity.
'''
items = list(items)
n = len(items)
# A[i, x] stores the solution to the optimal knapsack problem for items
# 1..i inclusive, given a knapsack of capacity x. The items are labelled 1
# to n, but A also stores optimal values for the empty set of items (i = 0)
# and a zero capacity knapsack (W = 0), which are of course all zero.
A = [[0] * (W+1) for _ in range(n+1)]
# Populate the array A from bottom up
for i in range(1, n+1):
# The value and weight of the ith item in items (-1 handles Python's
# 0-indexed arrays).
vi = items[i-1][1]
wi = items[i-1][2]
for x in range(0, W+1):
if wi <= x:
A[i][x] = max(A[i-1][x], A[i-1][x-wi] + vi)
else:
A[i][x] = A[i-1][x]
w = W
picks = []
for j in range(n, 0, -1):
if (A[j][w] != A[j-1][w]):
w -= items[j-1][2]
picks.append(items[j-1])
return picks, A[n][W]
def csv2json(csvpath):
head, ext = os.path.splitext(csvpath)
results = pd.read_csv(csvpath, index_col=0)
results.to_json(head + '.json', orient='index')
def getresults(jsonpath):
with open(jsonpath) as f:
return json.load(f)