Skip to content

Instantly share code, notes, and snippets.


ovs-code/ Secret

Last active Dec 11, 2020
What would you like to do?
A basic (and slow) modulo chain search program
from collections import defaultdict
from pprint import pprint
state_list = '''
Alabama AL
Alaska AK
Arizona AZ
Arkansas AR
California CA
Colorado CO
Connecticut CT
Delaware DE
Florida FL
Georgia GA
Hawaii HI
Idaho ID
Illinois IL
Indiana IN
Iowa IA
Kansas KS
Kentucky KY
Louisiana LA
Maine ME
Maryland MD
Massachusetts MA
Michigan MI
Minnesota MN
Mississippi MS
Missouri MO
Montana MT
Nebraska NE
Nevada NV
New Hampshire NH
New Jersey NJ
New Mexico NM
New York NY
North Carolina NC
North Dakota ND
Ohio OH
Oklahoma OK
Oregon OR
Pennsylvania PA
Rhode Island RI
South Carolina SC
South Dakota SD
Tennessee TN
Texas TX
Utah UT
Vermont VT
Virginia VA
Washington WA
West Virginia WV
Wisconsin WI
Wyoming WY
states = [line.rsplit(maxsplit=1) for line in state_list.splitlines()]
numbers_by_abbr = defaultdict(set)
for name, abbr in states:
n = int(name[0]+name[-2:],36)
sets = list(numbers_by_abbr.values())
def find_mod_chain(sets, iterations=2, limit=None):
m = max(max(x)for x in sets)
if iterations==0:
# if the last iteration is reached, return the maximum number
return (m,)
if limit is None:
limit = m
best_chain = (limit, )
# if there are n sets the lowest possible modulo value without intersection is n
for i in range(len(sets), limit):
# apply modulo candidate i to each set
n = [{k % i for k in x} for x in sets]
# the resulting sets are disjoint if there are as many elements in the union as in all sets
if len(set.union(*n)) == sum(len(x) for x in n):
r = find_mod_chain(n, iterations - 1)
if r[-1] < best_chain[-1]:
best_chain = (i,) + r
return best_chain
def display_mod_chain(chain):
*c, m = chain
print('x', *c, sep='%')
print(f'Highest remaining value is {m}.')
display_mod_chain(find_mod_chain(sets, 5, 500))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment