Edit post

Title

### 加強版題目
有人話，呢題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

Content

Password

Edit post

Preview

Powered by Simple Blog