1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19
20. 20
21. 21
22. 22
23. 23
24. 24
25. 25
26. 26
27. 27
28. 28
29. 29
30. 30
31. 31
32. 32
33. 33
34. 34
35. 35
36. 36
37. 37
38. 38
39. 39
40. 40
41. 41
42. 42
43. 43
44. 44
45. 45
46. 46
47. 47
48. 48
49. 49
50. 50
51. 51
52. 52
53. 53
54. 54
55. 55
56. 56
57. 57
58. 58
59. 59
60. 60
61. 61
62. 62
63. 63
64. 64
65. 65
66. 66
67. 67
68. 68
69. 69
70. 70
71. 71
72. 72
73. 73
74. 74
75. 75
76. 76
77. 77
78. 78
79. 79
80. 80
81. 81
82. 82
83. 83

import collections
import math
import random
# import matplotlib.pyplot as plt

# alphabet size
with open('data/alphabet.csv') as f:
    A = f.read()[:-1].split(',')
    m = len(A)
    char2idx = {A[i]: i for i in range(m)}
with open('data/letter_probabilities.csv') as f:
    P = list(map(float, f.read().split(',')))
with open('data/letter_transition_matrix.csv') as f:
    M = list(map(lambda l: list(map(float, l.split(','))), f.readlines()))
with open('data/sample/plaintext.txt') as f:
    truetext = [char2idx[c] for c in f.read()]

def kl(p, q):
    return sum(p[i] * math.log((p[i] + 1e-9) / (q[i] + 1e-9)) for i in range(len(p)))

def p(y, f):
    return math.log(P[f[y[0]]]) + sum(math.log(M[f[y[k]]][f[y[k - 1]]] + 1e-9) for k in range(1, len(y)))

def decode(ciphertext: str, has_breakpoint: bool) -> str:
    # with open(ciphertext) as f:
    y = [char2idx[c] for c in ciphertext]
    cnts = [0] * m
    for u in y:
        cnts[u] += 1
    x = list(range(m))
    logli = []
    iters = 50000
    T = 50
    acc = 0
    prev = collections.deque()
    accrate = []
    decacc = []
    for i in range(iters):
        if i % 100 == 0:
            print(i)
        swap = random.sample(range(m), 2)
        xnew = x.copy()
        xnew[swap[0]],xnew[swap[1]] = xnew[swap[1]],xnew[swap[0]]
        logli.append(p(y, x))
        a = min(0, p(y, xnew) - p(y, x))
        if a > 0 or random.random() < math.exp(a):
            x = xnew
            acc += 1
            prev.append(1)
        else:
            prev.append(0)
        if len(prev) > T:
            acc -= prev[0]
            prev.popleft()
        accrate.append(acc / len(prev))
        decacc.append(sum(truetext[i] == x[y[i]] for i in range(len(y))) / len(y))
        llps = [0]*m
        for c in range(m):
            llps[x[c]] = cnts[c] / len(y)
        # print(i, p(y, x), decacc[-1], kl(llps, P))
    # print(-sum(u * math.log2(u + 1e-9) for u in llps), -sum(u * math.log2(u + 1e-9) for u in P))


    # plt.xlabel('Iterations')
    # plt.ylabel('Log likelihood')
    # plt.plot(range(iters), logli)
    # plt.savefig('logli.png')
    # plt.close()
    # plt.xlabel('Iterations')
    # plt.ylabel(f'Acceptance rate over past {T} iterations')
    # plt.plot(range(iters), accrate)
    # plt.savefig('accrate.png')
    # plt.close()
    # plt.xlabel('Iterations')
    # plt.ylabel('Decoding accuracy (first 500 chars)')
    # plt.plot(range(iters), decacc)
    # plt.savefig('decacc-mid.png')

    plaintext = ''.join(A[x[u]] for u in y)
    return plaintext

with open("cipher") as f:
    print(decode(f.read()[:-1], False))