加強版題目
有人話，呢題17進制，17個variable，問我知驚未。
ΑΒΓΔ
- ΕΖΗΘ
------
ΙΚΛΜ
+ ΝΞΟΠ
------
ΡΡΡΡΡ
加強版題目解法
我一個鐘搞掂左基本野(好叻叻豬牙)，再用少少時間去implement個multiprocessing。
#!/usr/bin/env pypy3
from multiprocessing import Pool, Queue
from contextlib import closing
from itertools import permutations
PPPPP = 88741
CF8Q = Queue()
def check_last_8(i):
if i[0] == 0 or i[4] == 0:
return 0
ΙΚΛΜ, ΝΞΟΠ = i[0] * 4913 + i[1] * 289 + i[2] * 17 + \
i[3], i[4] * 4913 + i[5] * 289 + i[6] * 17 + i[7]
if ΙΚΛΜ + ΝΞΟΠ == PPPPP:
return ΙΚΛΜ
return 0
def check_first_8(i, ΙΚΛΜ):
if i[0] == 0 or i[4] == 0:
return 0
ΑΒΓΔ, ΕΖΗΘ = i[0] * 4913 + i[1] * 289 + i[2] * 17 + \
i[3], i[4] * 4913 + i[5] * 289 + i[6] * 17 + i[7]
if ΑΒΓΔ - ΕΖΗΘ == ΙΚΛΜ:
return 1
def check_first_8_worker(queue):
while 1:
i, ΙΚΛΜ = queue.get()
for j in permutations(set(range(17)) - set(i) - {1}, 8):
if check_first_8(j, ΙΚΛΜ):
print(j, i)
if __name__ == '__main__':
the_pool = closing(Pool(64, check_first_8_worker, (CF8Q,)))
for i in permutations(set(range(17)) - {1}, 8):
ΙΚΛΜ = check_last_8(i)
if ΙΚΛΜ != 0:
CF8Q.put((i, ΙΚΛΜ,))
加強版答案驗證
將上面求一行output入落Digits?就ok了。
#!/usr/bin/env pypy3
from re import findall
PPPPP = 88741
def baseN(num, b, numerals="0123456789abcdefghijklmnopqrstuvwxyz"):
return ((num == 0) and numerals[0]) or (baseN(num // b, b, numerals).lstrip(numerals[0]) + numerals[num % b])
def verify(i):
ΑΒΓΔ, ΕΖΗΘ = i[0] * 4913 + i[1] * 289 + i[2] * 17 + \
i[3], i[4] * 4913 + i[5] * 289 + i[6] * 17 + i[7]
ΙΚΛΜ, ΝΞΟΠ = i[8] * 4913 + i[9] * 289 + i[10] * 17 + \
i[11], i[12] * 4913 + i[13] * 289 + i[14] * 17 + i[15]
print("{} - {} == {}? {}".format(baseN(ΑΒΓΔ, 17), baseN(ΕΖΗΘ, 17), baseN(ΙΚΛΜ, 17), ΑΒΓΔ - ΕΖΗΘ == ΙΚΛΜ))
print("{} + {} == {}? {}".format(baseN(ΙΚΛΜ, 17), baseN(ΝΞΟΠ, 17), baseN(PPPPP, 17), ΙΚΛΜ + ΝΞΟΠ == PPPPP))
if __name__ == "__main__":
verify([int(i) for i in findall("\d+", input("Digits? "))])
部份答案
(16, 13, 15, 0, 2, 5, 4, 11) (14, 8, 10, 6, 3, 9, 7, 12)
(16, 10, 4, 12, 2, 0, 15, 7) (14, 9, 6, 5, 3, 8, 11, 13)
(16, 15, 4, 0, 2, 5, 13, 11) (14, 9, 7, 6, 3, 8, 10, 12)
(16, 15, 13, 4, 2, 6, 0, 10) (14, 9, 12, 11, 3, 8, 5, 7)
(16, 15, 7, 0, 2, 5, 10, 11) (14, 9, 13, 6, 3, 8, 4, 12)
(16, 11, 5, 4, 2, 0, 13, 15) (14, 10, 8, 6, 3, 7, 9, 12)
(16, 15, 5, 0, 2, 4, 13, 11) (14, 10, 8, 6, 3, 7, 9, 12)
(16, 15, 13, 0, 2, 5, 4, 11) (14, 10, 8, 6, 3, 7, 9, 12)
(16, 15, 13, 0, 2, 4, 7, 9) (14, 11, 5, 8, 3, 6, 12, 10)
(16, 12, 8, 9, 2, 0, 15, 4) (14, 11, 10, 5, 3, 6, 7, 13)
(16, 12, 9, 4, 2, 0, 15, 8) (14, 11, 10, 13, 3, 6, 7, 5)
(16, 12, 5, 15, 2, 0, 9, 7) (14, 11, 13, 8, 3, 6, 4, 10)
./challenge.py 77.75s user 1.51s system 190% cpu 41.515 total
再快d？
- First 8p4 iterations can be reduced to 100 - 1.
- Last iterations may be reduced too.
- Therefore, first 16p8 iterations can be reduced to (10000 - 1) (in b17)
實驗：9字母版
好多string operation，好慢。但check_last_4同check_first_4夾埋call得560次。
#!/usr/bin/env python3
from collections import Counter
BASE = 10
WIDTH = 2
PPP = int('111', BASE)
def construct(*args):
digits = 0
for i in args:
digits *= BASE ** WIDTH
digits += i
return digits
def check_last_4(GH):
EF = PPP - GH
c = Counter()
c.update(str(construct(EF, GH)))
for i in c.items():
if i[0] == '1' or i[1] > 1:
return 0
return EF
def check_first_4(AB, EF):
CD = AB - EF
c = Counter()
c.update(str(construct(AB, CD, EF, GH)))
for i in c.items():
if i[0] == '1' or i[1] > 1:
return 0
return CD
if __name__ == '__main__':
for GH in range(20, BASE ** WIDTH):
EF = check_last_4(GH)
if EF == 0:
continue
for AB in range(EF + 20, BASE ** WIDTH):
CD = check_first_4(AB, EF)
if CD != 0 :
print(AB, CD, EF, GH, PPP)
17字母版
淨係改左EF GH果part，AB CD唔識改，同埋我唔識唔經str抽返d千位數百位數出黎，個program因為咁慢左少少。
#!/usr/bin/env pypy3
from string import digits, ascii_letters
from time import sleep
from multiprocessing import Pool, Queue, Lock
from itertools import permutations
from collections import Counter
# Configurable variables
# 32C64T machine runtime, 17: 2.7s, 18: 14s, 19: 2m, 20: 8m
PROCESSES = 128
BASE = 20 # 17 or up
# Don't change anything below this line
WIDTH = 4
BOUND = int('2034', BASE)
PPPPP = int('11111', BASE)
NUMERALS = digits + ascii_letters
CF8Q = Queue()
exit_lock = Lock()
def baseN(num):
return ((num == 0) and NUMERALS[0]) or (baseN(num // BASE).lstrip(NUMERALS[0]) + NUMERALS[num % BASE])
def check_last_8(ΝΞΟΠ):
ΙΚΛΜ = PPPPP - ΝΞΟΠ
c = Counter()
c.update(baseN(ΙΚΛΜ * (BASE ** WIDTH) + ΝΞΟΠ))
for i in c.items():
if i[0] == '1' or i[1] > 1:
return 0
return ΙΚΛΜ
def check_first_8(i, ΙΚΛΜ):
if i[0] == 0 or i[4] == 0:
return 0
ΑΒΓΔ, ΕΖΗΘ = i[0] * (BASE ** 3) + i[1] * (BASE ** 2) + i[2] * BASE + i[3], \
i[4] * (BASE ** 3) + i[5] * (BASE ** 2) + i[6] * BASE + i[7]
if ΑΒΓΔ - ΕΖΗΘ == ΙΚΛΜ:
return 1
def check_first_8_worker(queue):
while 1:
used_digits, ΙΚΛΜ = queue.get()
for j in permutations(set(range(BASE)) - set(used_digits) - {1}, 8):
if check_first_8(j, ΙΚΛΜ):
print(j, used_digits)
if queue.qsize() == 0:
try:
exit_lock.release()
except Exception as e:
pass
if __name__ == '__main__':
for ΝΞΟΠ in range(BOUND, BASE ** WIDTH):
ΙΚΛΜ = check_last_8(ΝΞΟΠ)
if ΙΚΛΜ != 0:
used_digits = [int(i, BASE) for i in baseN(ΙΚΛΜ * (BASE ** WIDTH) + ΝΞΟΠ)]
CF8Q.put((used_digits, ΙΚΛΜ,))
exit_lock.acquire()
pool = Pool(PROCESSES, check_first_8_worker, (CF8Q,))
exit_lock.acquire()
部份結果
(9, 12, 0, 4, 7, 8, 10, 16) [2, 3, 6, 5, 15, 14, 11, 13]
(10, 7, 16, 0, 8, 4, 9, 12) [2, 3, 6, 5, 15, 14, 11, 13]
(9, 16, 6, 4, 7, 13, 0, 11) [2, 3, 5, 10, 15, 14, 12, 8]
(10, 12, 7, 4, 8, 9, 0, 16) [2, 3, 6, 5, 15, 14, 11, 13]
(13, 7, 6, 9, 11, 4, 0, 16) [2, 3, 5, 10, 15, 14, 12, 8]
(8, 9, 0, 10, 6, 5, 12, 16) [2, 3, 4, 11, 15, 14, 13, 7]
(8, 12, 5, 10, 6, 9, 0, 16) [2, 3, 4, 11, 15, 14, 13, 7]
(10, 9, 0, 6, 8, 5, 12, 16) [2, 3, 4, 7, 15, 14, 13, 11]
(10, 12, 5, 6, 8, 9, 0, 16) [2, 3, 4, 7, 15, 14, 13, 11]
pypy3 ./eff.py 37.57s user 4.00s system 1534% cpu 2.708 total