# Problem Set 5: Financing a Presidential Campaign
# Name: 
# Collaborators:
# Time:
#

# --- a list(tuple) of states ---
# each state is represented by a dictionary
# key 'name' contains the name of the state
# key 'pop' contains the total population of the state
# key 'evotes' contains the number of electoral votes 

state_list=(
    {'evotes':3, 'name':'Wyoming', 'pop':515004},
    {'evotes':21, 'name':'Pennsylvania', 'pop':12440621},   
    {'evotes':6, 'name':'Arkansas', 'pop':2810872},
    {'evotes':13, 'name':'Virginia', 'pop':7642884},
    {'evotes':31, 'name': 'New York', 'pop': 19306183},
    {'evotes':3, 'name':'South Dakota', 'pop':781919},
    {'evotes':7, 'name':'Iowa', 'pop':2982085},
    {'evotes':10, 'name':'Minnesota', 'pop':5167101},
    {'evotes':17, 'name':'Michigan', 'pop':10095643},
    {'evotes':34, 'name':'Texas', 'pop':23507783},
    {'evotes':15, 'name':'New Jersey', 'pop':8724560},
    {'evotes':11, 'name':'Washington', 'pop':6395798},
    {'evotes':4, 'name':'Hawaii', 'pop':1285498},
    {'evotes':6, 'name':'Kansas', 'pop':2764075},
    {'evotes':55, 'name': 'California', 'pop': 36457549},
    {'evotes':5, 'name':'Nevada', 'pop':2495529},
    {'evotes':21, 'name':'Illinois', 'pop':12831970},
    {'evotes':7, 'name':'Connecticut', 'pop':3504809},
    {'evotes':15, 'name':'Georgia', 'pop':9363941},
    {'evotes':7, 'name':'Oregon', 'pop':3700758},
    {'evotes':5, 'name':'Utah', 'pop':2550063},
    {'evotes':11, 'name':'Indiana', 'pop':6313520},
    {'evotes':10, 'name':'Wisconsin', 'pop':5556506},
    {'evotes':10, 'name':'Maryland', 'pop':5615727},
    {'evotes':27, 'name': 'Florida', 'pop': 18089888},
)



# Problem 1: Utility functions
# A)
def total_pop(states):
    """
    Takes a list of dictionaries of states as a parameter. Computes
    and returns the total population as an integer.
    """
    # ... your code goes here ...

# B)
def total_evotes(states):
    """
    Takes a list of dictionaries of states as a parameter. Computes
    and returns the total number of electoral votes as an integer.
    """
    # ... your code goes here ...

# C)
def cheapest_evotes(states):
    """
    Takes a list of dictionaries of states as a parameter. Finds and
    returns the dictionary corresponding to the state with smallest
    population per electoral vote.
    """
    # ... your code goes here ...


# Problem 2: Exhaustive enumeration
def finance_campaign_ee(budget, free_states): 
    """
    Takes a budget, in dollars, and a list of available states, as a
    list of dictionaries.

    Computes and returns the list of states that maximizes the total
    number of electoral votes such that these states can be acquired
    on the budget. Returns an empty list if no states can be acquired.
    """
    cheap_states=[]
    for s in free_states:
        if s['pop'] <= budget:
            cheap_states.append(s)

    # Base case
    if len(cheap_states)==0:
        res_list=[]
    # Recursive case
    else:
        curr_state=cheap_states[0]
        other_states=cheap_states[1:]

        inc_states=finance_campaign_ee( budget-curr_state['pop'],
                                         other_states)
        inc_states.append(curr_state)
        inc_evotes=total_evotes(inc_states)

        excl_states=finance_campaign_ee( budget, other_states )
        excl_evotes=total_evotes(excl_states)

        # ... your code goes here ...
            
    return res_list

def print_finance_campaign_ee(budget, free_states):
    """
    Pretty-prints the output of finance_campaign_ee() and (TODO)
    prints the amount of time it took to do the computation.
    """
    states = finance_campaign_ee(budget, free_states)
    
    print "States where to run the campaign:"
    if len(states) == 0:
        print " No satisfactory solutions found",
    else:
        print ", ".join([s['name'] for s in states])
    print "Total number of electoral votes acquired:", total_evotes(states)
    print "Total budget required:", total_pop(states)


# Problem 3: Branch and bound
def finance_campaign_bb(budget, free_states):
    """
    Takes a budget, in dollars, and a list of available states, as a
    list of dictionaries.

    Computes and returns the list of states that maximizes the total
    number of electoral votes such that these states can be acquired
    on the budget. Returns an empty list if no states can be acquired.
    """
    # ... your code goes here...