Code to solve Riddler Classic from 13 September 2019

states.py

#!/usr/bin/env python3

all_states = set(['AL', 'AK', 'AS', 'AZ', 'AR', 'CA', 'CO', 'CT', 'DE', 'DC',
                  'FM', 'FL', 'GA', 'GU', 'HI', 'ID', 'IL', 'IN', 'IA', 'KS',
                  'KY', 'LA', 'ME', 'MH', 'MD', 'MA', 'MI', 'MN', 'MS', 'MO',
                  'MT', 'NE', 'NV', 'NH', 'NJ', 'NM', 'NY', 'NC', 'ND', 'MP',
                  'OH', 'OK', 'OR', 'PW', 'PA', 'PR', 'RI', 'SC', 'SD', 'TN',
                  'TX', 'UT', 'VT', 'VI', 'VA', 'WA', 'WV', 'WI', 'WY', 'AE',
                  'AP', 'AA'])

all_states_except_military = all_states - set(['AE', 'AP', 'AA'])


def search(sofar, states, min_length):
    # sofar: string of states found so far
    # states: set of valid states remaining
    found = 0                   # have we found a valid string on this call?
    for st in states:           # for every valid state ...
        # remove the current state from the list of valid states
        states_remaining = states - set([st])
        if sofar == '':         # if the string is empty (if we just started)
            # then keep searching; the new string is the current state
            search(st, states_remaining, min_length)
            found = 1
        elif sofar[-1] == st[0]:  # otherwise, see if there's a match:
            # is the last letter of the string so far equal to the first
            # letter of the current state?
            # if so, add the second letter to the string and keep searching
            search(sofar + st[1], states_remaining, min_length)
            found = 1
    # if we found nothing and it's long enough, print it
    if found == 0 and len(sofar) >= min_length:
        print(sofar)


print("All states except military")
search('', all_states_except_military, 31)
print("All states including military")
search('', all_states, 34)