Last active
October 24, 2020 14:42
-
-
Save hdf/32044dacbac102268347c376a7c732be to your computer and use it in GitHub Desktop.
My solution(s) to John Conway's 10 Digit number puzzle: (https://www.quantamagazine.org/three-math-puzzles-inspired-by-john-horton-conway-20201015/)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import string | |
from sys import argv, stderr | |
from time import time | |
def spinner_f(): | |
while True: | |
for c in '|/-\\': | |
yield c | |
spinner = spinner_f() | |
def assemblies(m, base): | |
n = len(m) | |
indices = [0 for i in range(n)] | |
s = time() | |
while True: | |
c = '' | |
f = False | |
u = set() | |
for i in range(n): | |
t = m[i][indices[i]] | |
ct = c + t | |
if t in u or int(ct, base) % (i + 1) != 0 or (ct == '0'): | |
f = True | |
break | |
c = ct | |
u.add(t) | |
e = time() | |
if e >= s + 0.1: # throttle spinner display | |
print(next(spinner), end='\b', flush=True, file=stderr) | |
s = e | |
if not f: | |
yield (c, u) # return valid numbers and their used digits, that will be used to ensure that all digits are used only once | |
# find the rightmost array that has more elements left after the current element in that array | |
nxt = n - 1 | |
while (nxt >= 0 and (indices[nxt] + 1 >= len(m[nxt]))): | |
nxt -= 1 | |
if (nxt < 0): # no more combinations left | |
return | |
indices[nxt] += 1 | |
# for all arrays to the right of this array current index again points to first element | |
for i in range(nxt + 1, n): | |
indices[i] = 0 | |
def conway(size=10, base=10): # Calculate John Conway's number puzzle, up to base 36 | |
ds = list(string.digits + string.ascii_lowercase)[0:base] | |
m = [] | |
b = {} | |
for i in range(size): | |
t = [] | |
m.append([]) | |
a = list(assemblies(m[:-1], base)) | |
# populate m, that holds the matrix of valid numbers per digit | |
for i2 in range(base): | |
for n, u in a: | |
if ds[i2] not in u and int(n + ds[i2], base) % (i + 1) == 0 and n + ds[i2] not in t and not (i == 0 and i2 == 0): | |
if ds[i2] not in m[i]: | |
m[i].append(ds[i2]) | |
t.append(n + ds[i2]) # this is a list of valid numbers until this digit | |
# clear out the invalid from m, to greatly reduce the search space | |
tl = len(t) | |
for i2 in range(i): | |
b[i2] = set(m[i2]) | |
for i3 in range(tl): | |
b[i2].discard(t[i3][i2]) | |
for e in b[i2]: | |
m[i2].remove(e) | |
return sorted(t) | |
if __name__ == "__main__": | |
if len(argv) < 2: | |
print('usage: conway.py [digits [base]]\n' + | |
' digits: \trange: \t2-base, default: 10 \tHow long should the number be?\n' + | |
' base: \trange: \t2-36, \tdefault: 10 \tWhat number base to use?\n') | |
print('Solution(s):', list(conway(*[int(p) for p in argv[1:]]))) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import sys, itertools | |
def conway(size=2): | |
for n in itertools.permutations([str(i) for i in range(10)], r = size): | |
f = False | |
for i in range(1, size+1): | |
#print(''.join(n[0:i]), '%', i, '=', n[0] != '0' and int(''.join(n[0:i])) % i == 0) | |
if n[0] == '0' or int(''.join(n[0:i])) % i != 0: | |
f = True | |
break | |
if not f: | |
yield ''.join(n) | |
print(list(conway(int(sys.argv[1]) if len(sys.argv) > 1 else 10))) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import string | |
from sys import argv | |
from itertools import permutations | |
from math import factorial | |
from time import time | |
def conway(size=10, base=10): # Calculate John Conway's number puzzle, up to base 36 | |
p = int(factorial(base) / factorial(base-size)) | |
c = 0 | |
b = time() | |
s = b | |
for n in permutations(list(string.digits + string.ascii_lowercase)[0:base], r = size): | |
f = False | |
c += 1 | |
for i in range(1, size+1): | |
t = time() | |
if t >= s + 0.1: # throttle status display | |
print(str(round(c/p*100, 2)) + '% (' + str(c) + '/' + str(p) + | |
') ETC: ' + str(round(p * (t - b) / c - (t - b), 1)) + 's \t' + | |
''.join(n[0:i]) + ' % ' + str(i) + ': ' + str(n[0] != '0' and int(''.join(n[0:i]), base) % i == 0), | |
end = '\t\t\t\t\r', flush = True) | |
s = t | |
if n[0] == '0' or int(''.join(n[0:i]), base) % i != 0: # skip if starts with 0 or is not divisible | |
f = True | |
break | |
if not f: | |
yield ''.join(n) | |
if __name__ == "__main__": | |
if len(argv) < 2: | |
print('usage: conway36.py [digits [base]]\n' + | |
' digits: \trange: \t2-base, default: 10 \tHow long should the number be?\n' + | |
' base: \trange: \t2-36, \tdefault: 10 \tWhat number base to use?\n') | |
print('Solution(s):', list(conway(*[int(p) for p in argv[1:]])), '\t\t\t\t\t\t') |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import string | |
from sys import argv | |
from itertools import permutations, chain | |
from multiprocessing import Pool | |
from functools import partial | |
def part(ds, size, base, h, hs, t): | |
ret = [] | |
header = h[t] | |
for n in permutations([e for e in ds if e not in header], r = size - hs): | |
n = header + n | |
f = False | |
for i in range(1, size+1): | |
if int(''.join(n[0:i]), base) % i != 0: # skip if not divisible | |
f = True | |
break | |
if not f: | |
ret.append(''.join(n)) | |
#print('Thread:', t, 'Header:', ''.join(header), 'Returned:', ret) | |
return ret | |
def conway(size=10, base=10, hs=2): # Calculate John Conway's number puzzle, up to base 36 | |
ds = list(string.digits + string.ascii_lowercase)[0:base] | |
if size - hs < 0: | |
hs = size | |
h = [n for n in permutations(ds, r=hs) if n[0] != '0'] # hs is the size of the header (h is header) | |
with Pool() as pool: | |
f = partial(part, ds, size, base, h, hs) | |
return sorted(chain(*pool.map(f, range(len(h))))) | |
if __name__ == "__main__": | |
if len(argv) < 2: | |
print('usage: conway36p.py [digits [base [granularity]]]\n' + | |
' digits: \trange: \t1-base, default: 10 \tHow long should the number be?\n' + | |
' base: \trange: \t2-36, \tdefault: 10 \tWhat number base to use?\n' + | |
' granularity: \trange: \t1-base, default: 2 \tHow many digits to use as header for threads?\n') | |
print('Solution(s):', conway(*[int(p) for p in argv[1:]])) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import string | |
from sys import argv | |
from itertools import permutations | |
def check(n, base): | |
s = len(n) | |
while s > 0: | |
if int(n[0:s], base) % s != 0: | |
return False | |
s -= 1 | |
return True | |
def conway(size=10, base=10): # Calculate John Conway's number puzzle, up to base 36 | |
ds = list(string.digits + string.ascii_lowercase)[0:base] | |
return sorted([int(''.join(n), base) for n in permutations(ds, r=size) if n[0] != '0' and check(''.join(n), base)]) | |
if __name__ == "__main__": | |
if len(argv) < 2: | |
print('usage: conway36s.py [digits [base]]\n' + | |
' digits: \trange: \t2-base, default: 10 \tHow long should the number be?\n' + | |
' base: \trange: \t2-36, \tdefault: 10 \tWhat number base to use?\n') | |
print('Solution(s):', conway(*[int(p) for p in argv[1:]])) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment