Valtion salaisten huoltotunneleiden salaiset pääsykoodit vuodettiin hakkeriryhmässä

bruijn.py

import itertools
import math
import multiprocessing
import random
import tqdm


# Via Wikipedia
def de_bruijn(alphabet, n: int) -> str:
    """de Bruijn sequence for alphabet k
    and subsequences of length n.
    """
    k = len(alphabet)

    a = [0] * k * n
    sequence = []

    def db(t, p):
        if t > n:
            if n % p == 0:
                sequence.extend(a[1 : p + 1])
        else:
            a[t] = a[t - p]
            db(t + 1, p)
            for j in range(a[t - p] + 1, k):
                a[t] = j
                db(t + 1, t)

    db(1, 1)
    return "".join(alphabet[i] for i in sequence)


keypad_pos = {
    "1": (0, 0),
    "2": (1, 0),
    "3": (2, 0),
    "4": (0, 1),
    "5": (1, 1),
    "6": (2, 1),
    "7": (0, 2),
    "8": (1, 2),
    "9": (2, 2),
    "0": (1, 3),
}


def compute_perm_goodness(perm):
    s = de_bruijn(perm, 4)
    dist_sq = 0
    last_pos = None
    for c in s:
        if not last_pos:
            last_pos = keypad_pos[c]
            continue
        curr_pos = keypad_pos[c]
        lx, ly = last_pos
        cx, cy = curr_pos
        dist_sq += (lx - cx) ** 2 + (ly - cy) ** 2
        last_pos = curr_pos
    return (perm, dist_sq)


def main():
    chs = "0123456789"
    perms = list(itertools.permutations(chs))
    random.shuffle(perms)

    n_perms = len(perms)  # factorial(len(chs))

    with multiprocessing.Pool() as pool:
        with tqdm.tqdm(perms, total=n_perms) as prog:
            best_perm = None
            best_dist = 1 << 32
            worst_dist = 0
            worst_perm = None
            for perm, dist_sq in pool.imap_unordered(
                compute_perm_goodness, prog, chunksize=150
            ):
                if dist_sq < best_dist:
                    best_dist = dist_sq
                    best_perm = perm
                    print("Good!", best_perm, math.sqrt(best_dist))
                elif dist_sq > worst_dist:
                    worst_dist = dist_sq
                    worst_perm = perm
                    print("Bad!", worst_perm, math.sqrt(worst_dist))
            print("Good --->", (best_perm, best_dist))
            print("Bad  --->", (worst_perm, worst_dist))


if __name__ == "__main__":
    main()