riddler_township.py

import itertools

riddler_township = {}
total_population = 0
for shire_number in range(1, 11):
    shire_population = shire_number * 10 + 1
    total_population += shire_population
    majority = shire_population // 2 + 1
    electors = shire_number + 2
    riddler_township[electors] = majority

total_electors = sum(riddler_township.keys())
electors_required_to_win = total_electors // 2 + 1
print("total population: {0}".format(total_population))
print("total electors: {0}".format(total_electors))
print("total electors required to win: {0}".format(electors_required_to_win))

# itertools.combinations gives all combinations of the values of a list,
# so in this case, gives us a list of all possible combinations of electors.
# This only works because each shire has a unique number of electors, allowing
# the number of electors to be the key in the dictionary; however, it would
# be trivial to have the key be a tuple of shire identifier and number of
# electors, and get the possible combinations of electors using the tuple.
elector_combinations = []
for r in range(len(riddler_township) + 1):
    elector_combinations += list(itertools.combinations(riddler_township.keys(), r))

results = {}
for elector_combination in elector_combinations:
    elector_total = sum(elector_combination)
    if (elector_total >= electors_required_to_win):
        vote_total = 0
        for elector_value in list(elector_combination):
            vote_total += riddler_township[elector_value]
        results[elector_combination] = (elector_total, vote_total)

# items() returns a key-value tuple, so the 1 element of the tuple
# is the value of the dictionary, consisting of tuple containing
# elector total as the 0 element and vote total as the 1 element.
# sorted() returns a list, so the 0th element of the list must have
# the lowest popular vote total.
sorted_results = sorted(results.items(), key=lambda x: x[1][1])
lowest_popular_vote = sorted_results[0][1][1]
print("lowest number of popular votes required to win: {0} (popular vote percentage: {1:.2%})".format(lowest_popular_vote, lowest_popular_vote / total_population))

print("")
print("all winning combinations")
print("========================")
for sorted_result in sorted_results:
    print("popular votes: {0}, electoral votes: {1}, shires won: {2}".format(sorted_result[1][1], sorted_result[1][0], sorted_result[0]))