2024 US electoral college combinations

output.txt

swing states
PA 19
GA 16
NC 16
MI 15
AZ 11
WI 10
NV 6

Democrats (226 baseline)
277 PA[19],NC[16],GA[16] wins
276 PA[19],NC[16],MI[15] wins
272 PA[19],NC[16],AZ[11] wins
271 PA[19],NC[16],WI[10] wins
276 PA[19],GA[16],MI[15] wins
272 PA[19],GA[16],AZ[11] wins
271 PA[19],GA[16],WI[10] wins
271 PA[19],MI[15],AZ[11] wins
270 PA[19],MI[15],WI[10] wins
272 PA[19],AZ[11],WI[10],NV[6] wins
273 NC[16],GA[16],MI[15] wins
269 NC[16],GA[16],AZ[11] ties, plus an extra district in ME wins or one of NV,WI
268 NC[16],GA[16],WI[10] one short of tie, an extra district in ME would tie or one of NV wins
268 NC[16],MI[15],AZ[11] one short of tie, an extra district in ME would tie or one of NV,WI wins
273 NC[16],MI[15],WI[10],NV[6] wins
269 NC[16],AZ[11],WI[10],NV[6] ties, plus an extra district in ME wins
268 GA[16],MI[15],AZ[11] one short of tie, an extra district in ME would tie or one of NV,WI wins
273 GA[16],MI[15],WI[10],NV[6] wins
269 GA[16],AZ[11],WI[10],NV[6] ties, plus an extra district in ME wins
268 MI[15],AZ[11],WI[10],NV[6] one short of tie, an extra district in ME would tie

Republicans (219 baseline)
270 PA[19],NC[16],GA[16] wins
269 PA[19],NC[16],MI[15] ties, plus an extra district in NE wins or one of NV,WI,AZ
275 PA[19],NC[16],AZ[11],WI[10] wins
271 PA[19],NC[16],AZ[11],NV[6] wins
269 PA[19],GA[16],MI[15] ties, plus an extra district in NE wins or one of NV,WI,AZ
275 PA[19],GA[16],AZ[11],WI[10] wins
271 PA[19],GA[16],AZ[11],NV[6] wins
274 PA[19],MI[15],AZ[11],WI[10] wins
270 PA[19],MI[15],AZ[11],NV[6] wins
277 NC[16],GA[16],MI[15],AZ[11] wins
276 NC[16],GA[16],MI[15],WI[10] wins
272 NC[16],GA[16],MI[15],NV[6] wins
271 NC[16],MI[15],AZ[11],WI[10] wins
271 GA[16],MI[15],AZ[11],WI[10] wins

swingstates2024.py

#!/usr/bin/env python3

"""US electoral college, minimal winning combinations

Finds all of the winning, tied, and almost tied minimal combinations
of swing states in the 2024 US presidential election based on 7 swing states.

The US president is elected by the electoral college.

Our interest in one less than tied (268) arises from Nebraska (NE) and
Maine (ME) allocating 2 electors for their state wide result and
the remaining electors by the results of 3 or 2 districts respectively.
Baseline expectations are that the Democrats will win 1/2 districts in ME
and the Republicans 2/3 districts in NE. It may not be out of reach
for the Democrats to sweep Maine or for the Republicans to sweep Nebraska.

All other contributions to the baseline are from expected non-swing states
with winner take all allocations of electors.

This output is useful for understanding the combinative importance of given
swing states, particularly after some of them have projected results. Not
only can you cross out ruled out combinations, but can also cross-out
overly complex combinations that are superseded by simpler equivalents.

Further, you can also see when a swing state achieves combinatorial
uselessness. Nevada (NV) is particularly vulnerable to becoming useless
after some of its friends are projected, sorry Nevada.

The algorithm here is greedy. Larger states are preferred in building
combinations. But not too greedy, we stop upon reaching the tied threshold.

As combinations, order does not matter, so observe in the output how a
state drops off entirely after it has demonstrated its combinative usefulness.

A normal and recommended way to implement this kind of algorithm is
with recursion.

I wrote this as an exercise in not using recursion, which can have a
small performance benefit in some environments, but not in Python. The
other thing making performance irrelevant is the small number of swing states.
Perhaps there will be more when the USA carries the electoral college
into the galactic empire.

The horrible downside to not using recursion is that stacks have to be
managed manually.

We've got four active data structures and one key variable, the total
electoral votes (total).

The total variable is redundant, as the components of the current combination
are always tracked. Great opportunity for bugs, note the asserts to catch them.

The other four data structures are lists that are manipulated old-school in
a mutable fashion per party combinative computation. Each list member is a
tuple with [0] the vote count and [1] the state two letter ABREV

The list unused_stack is used as a stack of states that at a given time are
considered not used. The list order is smallest to largest, with .pop() being
a greedy grab of the biggest remaining.

The list sum_stack is a stack of states considered part of the sum at a given
time. Order is reversed here, from largest (first in, last out)
to smallest (first out, last in). When we get to our threshold, popping off
the last one added is assumed to take us back below threshold.

hold_q and long_hold_q are lists where a heap priority queue invariant
is preserved with functions from the heapq module. The states in these
have been part of the total at some point. The ones in hold_q could come back
into play soon, whereas the ones in long_hold_q have been used a lot and
are not coming back until a big state at the start of the combination is
dropped entirely.

The payoff of maintaining priority queue order for these queues comes
when heapq.merge() is able to be used to take advantage of their respective
ordering to perform a merge sort. I like the idea of showing we can live
without a bunch of invocations of quick-sort.

As the algorithm progresses, these combined length of these lists will
drop as the combinative usefulness of given US states is exhausted.

I imagine there is a cleaner way to implement this algorithm non-recursively.
Perhaps with less stacks and ordered queues.

In some environments, use of linked lists for stacks and queues may offer
some kinds of performance optimization. In an earlier version I enjoyed using
Python's collections.deque, though I ultimately converted to a random-access
list-only approach. Worth knowing about.

@author Mark Jenkins
"""

from heapq import merge, heappush, heappop

swing_states = {'PA': 19,
                'GA': 16,
                'NC': 16,
                'MI': 15,
                'AZ': 11,
                'WI': 10,
                'NV': 6,
}

print("swing states")
for state_name,votes in swing_states.items():
    print(state_name, votes)
print()

# Baseline assumptions are based on the-non swing states, most of which
# are winner take all, except for:
# * Maine (ME) where the Democrats are assumed to win statewide (2 electors)
#   and one of two districts
# * Nebraska (NE) where the Republicans are assume to win statewide
#   (2 electors) and two out of three districts
BASELINES = {
    226: "Democrats",
    219: "Republicans",
}

# Possible plus ones, it is somewhat possible that the Democrat ticket
# gets an extra district in Maine (ME) and somewhat possible for the
# Republican ticket to get an extra district in Nebraska
#
# These could break a tie or bring a position one short of tied up
PLUS_ONES = {
    "Democrats": "an extra district in ME",
    "Republicans": "an extra district in NE",
}

# check the swing state and baseline totals add up to the total electors
TOTAL_ELECTORS = sum(BASELINES.keys()) + sum(swing_states.values())

# divisibility by 2 asserted for the TIE_THRESHOLD concept
# without which there is no tie threshold, only winners and losers
assert TOTAL_ELECTORS == 538 and TOTAL_ELECTORS%2==0

TIE_THRESHOLD = TOTAL_ELECTORS //2
assert TIE_THRESHOLD == 269

def fully_pop_heap(heap):
    """Takes a list that is managed with the heapq module and
    yields heappop(heap) until empty

    This is destructive, empties the provided heap
    """
    while len(heap)>0:
        yield heappop(heap)

for baseline, party_name in BASELINES.items():
    print(party_name, "(%d baseline)" % baseline)

    unused_stack = list( sorted( (votes, state)
                                 for state,votes in swing_states.items()))
    long_hold_q = []
    sum_stack = []
    hold_q = []
    total = baseline
    while True: # breaking conditions are in the loop
        pair = unused_stack.pop()
        votes, state = pair
        sum_stack.append( pair )
        total+= votes
        if total >= (TIE_THRESHOLD-1):
            # check that total and sum_stack + baseline have been
            # kept consistent
            assert total == sum(votes for votes,state in sum_stack) + baseline

            if total > TIE_THRESHOLD:
                result = "wins"
            elif total == TIE_THRESHOLD:
                result = "ties, plus " + PLUS_ONES[party_name] + " wins"
                if len(unused_stack)>0:
                    result+= ' or one of ' + ','.join(
                        state for votes,state in unused_stack)
            else:
                result = "one short of tie, " + PLUS_ONES[party_name] \
                         + " would tie"
                if len(unused_stack)>0:
                    result+= ' or one of ' + ','.join(
                        state for votes,state in unused_stack) + " wins"
            print(total,
                  ','.join("%s[%d]" % (b,a) for a,b in sum_stack),
                  result)
            heappush(hold_q, sum_stack.pop() )
            total-=votes

        if len(unused_stack)==0:
            if ( len(sum_stack)==1 and
                 len(long_hold_q)==0 and
                 len(hold_q)==0 ):
                # termination condition
                break
                
            pair = sum_stack.pop()
            votes,state = pair
            total-= votes
            heappush(hold_q, pair)

            if len(sum_stack)==0:
                total = baseline
                unused_stack.extend( merge(
                    fully_pop_heap(long_hold_q), fully_pop_heap(hold_q) ))
                assert 0==len(hold_q) # cleared by fully_pop_heap
                assert 0==len(long_hold_q) # cleared by fully_pop_heap

            elif len(sum_stack)==1:
                total-= sum_stack.pop()[0] # votes
            else:
                pair = sum_stack.pop()
                heappush(long_hold_q, pair)
                total-= pair[0] # votes
            
            unused_stack.extend( merge( reversed(sum_stack),
                                        fully_pop_heap(hold_q) ))
            assert baseline == total - sum(a for a,b in sum_stack)
            total = baseline
            sum_stack.clear()
            assert 0==len(hold_q)
    print()