import re
from itertools import product

ct = "Phhezn me dnngmcuk zol rlclyndofnh ndxpjc yokh bl bh lastpuja z sfsn nzqjrq jxr zdwy lcxryfpa!"
letters = [c for c in ct if c.isalpha()]
n = len(letters)

# English letter frequencies
FREQ = [8.167,1.492,2.782,4.253,12.702,2.228,2.015,6.094,6.966,0.153,0.772,4.025,2.406,
        6.749,7.507,1.929,0.095,5.987,6.327,9.056,2.758,0.978,2.360,0.150,1.974,0.074]

def chi2(seq, shift):
    counts = [0]*26
    for c in seq:
        counts[(ord(c.upper()) - 65 - shift) % 26] += 1
    tot = len(seq)
    return sum((counts[i] - FREQ[i]*tot/100)**2 / (FREQ[i]*tot/100) for i in range(26))

def ic(seq):
    counts = [0]*26
    for c in seq:
        counts[ord(c.upper()) - 65] += 1
    N = len(seq)
    return sum(k*(k-1) for k in counts) / (N*(N-1)) if N > 1 else 0

print('n =', n)
print('--- index of coincidence by key length ---')
best = []
for L in range(1, 16):
    cols = [letters[i::L] for i in range(L)]
    avg = sum(ic(c) for c in cols) / L
    best.append((avg, L))
    print(f'  L={L:2}  avgIC={avg:.4f}')

for avg, L in sorted(best, reverse=True)[:5]:
    cols = [letters[i::L] for i in range(L)]
    key = ''.join(chr(65 + min(range(26), key=lambda s: chi2(col, s))) for col in cols)
    # decrypt
    out, ki = [], 0
    for ch in ct:
        if ch.isalpha():
            k = ord(key[ki % L]) - 65
            base = 65 if ch.isupper() else 97
            out.append(chr((ord(ch) - base - k) % 26 + base)); ki += 1
        else:
            out.append(ch)
    print(f'\nL={L} IC={avg:.4f} key={key}\n  {"".join(out)}')
