#!/usr/bin/env python3

import re
import os
import sys
import random
from itertools import chain, product

testkey = 'q w e r'
message = 'ta kzxwgpdjtctpf prozif, d nop zs adpgidc agxjoin tn kdccom iokgintho, kzxwgpdjco zi moktmdjco ts proio tn da dcyzitprx ertkr poixtadpon dspoi d statpo dxzgap zs ptxo (ertkr xdf mowoam za pro ythoa agxjoi) dam kziiokpcf moktmon eroproi d ythoa agxjoi joczayn pz pro nop.'
sampledecrypt = 'ly dsourjwclqlje jxisbe, w hij sk ywjrbwq yrocibh lh dwqqig bidrbhlai, dsourjwcqi sb gidlgwcqi lk jxibi lh wy wqpsbljxo vxldx jibolywjih wkjib w klylji wosryj sk jloi (vxldx owe giuiyg sy jxi plaiy yrocib) wyg dsbbidjqe gidlgih vxijxib w plaiy yrocib ciqsyph js jxi hij.'
messagetarget = 'In computability theory, a set of natural numbers is called recursive, computable or decidable if there is an algorithm which terminates after a finite amount of time (which may depend on the given number) and correctly decides whether a given number belongs to the set.'.lower()
alpha = 'abcdefghijklmnopqrstuvwxyz'

'''
    we first need to generate the master key (e50) from the initial key
    seed the state (d) by concatenating the alphabet onto the key (all lowercase).
    state = asdfabcdefghijklmnopqrstuvwxyz
    loop through each letter of the alphabet.
    call that letter's index (1-indexed) a
    and call the letter itself b.
    find that letter's position (1-indexed) in the state, this is c.

    to update the state, we need to generate d_left and d_right.
    d_left is the first c chars of the current state
    d_right is the remainder of the chars (position c to the end)
    with all occurrences of b deleted.

    we update the state with the concatenation of d_left and d_right

    to encrypt, we operate char by char.
    we first get the index of the first occurrence of the plaintext char
    in the master key, add 20 to that index, and call it findval.
    the encrypted char is the findval'th character of e50
'''

def gen_e50(key):
    col_a = [i for i in range(1, 271)]  #
    col_b = list(alpha)                 # =char(A51+96)
    col_c = []                          # =FIND(B51,D50)
    col_d = []                          # =CONCAT(LEFT(D50,C51), SUBSTITUTE(MID(D50,C51+1, LEN(D50)), B51, ""))

    d50 = re.sub('[^a-z]', '', key.lower()[0:10]) + alpha
    for a in col_a[0:len(col_b)]:
        if a == 1:
            d_prev = d50
        else:
            d_prev = col_d[a-2]
        b = col_b[a-1]
        c = d_prev.find(b) + 1
        d_right = d_prev[c:len(d_prev)]
        d_right = re.sub(b, '', d_right)
        d_left = d_prev[0:c]
        d = d_left + d_right
        col_c.append(c)
        col_d.append(d)

    e50 = col_d[-1] + col_d[-1]
    return e50

def encryptchar(char, e50):
    # =IFERROR(MID($E$50, FIND(E51, $E$50)+20, 1), E51)
    if not char in e50:
        return char
    findval = e50.find(char) + 20
    return e50[findval]

def scoredecrypt(key):
    testpt = ''.join([encryptchar(char, gen_e50(key)) for char in message])
    score = 0
    for c in range(len(testpt)):
        if testpt[c] == messagetarget[c]:
            score += 1
    return score

assert gen_e50(testkey) == 'qwerabcdfghijklmnopstuvxyzqwerabcdfghijklmnopstuvxyz'
e50 = gen_e50(testkey)
testpt = ''.join([encryptchar(char, e50) for char in message])
assert testpt == sampledecrypt

key = list(' ' * 10)
scorehist = []
highscore = 0
while True:
    print(''.join(key) + ' ' + str(highscore) + '\t[', end='')
    progress = int((highscore / len(messagetarget)) * 100)
    print('=' * progress, end='')
    print(' ' * (100 - progress), end='')
    print(']')
    if highscore == len(messagetarget):
        print("WOW!!!!!!!!!!!!!!!!!!!")
        print(key)
        break
    if len(scorehist) > 2:
        if scorehist[-1] == scorehist [-2]:
            keyind = random.randint(0,9)
            alphind = random.randint(0, len(alpha)-1)
            # print("stuck - setting key index %s to alphabet index %s" % (keyind, alphind))
            key[keyind] = alpha[alphind]
    for k in range(len(key)):
        keyscore = {}
        for a in (alpha):
            key[k] = a
            score = scoredecrypt(''.join(key))
            keyscore[a] = score
        highscore = keyscore[max(keyscore, key=keyscore.get)]
        key[k] = max(keyscore, key=keyscore.get)
    scorehist.append((key, highscore))