######## compile word to dfa

alphabet = 'abcdefghijklmnopqrstuvwxyz'

def bitstoint(bs):
    n = 0
    for b in reversed(bs):
        n = 2*n + b
    return n

def compile_word_to_dfa_that_matches_it_as_substring(word):
    """

    The state of the automaton must tell, for each i, whether the
    input so far ends in word[:i].

    If the input so far ends in word[:i], and the next character is
    indeed word[i], then the input so far ends in word[:i+1];
    otherwise it doesn't.

    As an exception to this rule, if the input so far ends in word,
    then this will forever be the state of the automaton.
    """
    assert set(word) <= set(alphabet)
    N = 2**(len(word) + 1)  # all states are 0 <= s < N; (s & (1 << i)) is valid for 0 <= i <= len(word)
    def transition(s, c):
        if s == N-1:
            return N-1  # accepting state
        if s & (1 << (len(word)-1)) and word[-1] == c:
            return N-1
        return 1 + 2*bitstoint([
            int(s & (1 << i) and word[i] == c)
            for i in range(len(word))
        ])
            
    transition_matrices = {
        c: [[int(transition(i, c) == j) for j in range(N)] for i in range(N)]
        for c in alphabet
    }
    initial_state = 1
    final_state = N-1
    return (transition_matrices, initial_state, final_state)

######## (optional: optimize the dfa)


######## probability calculation

import numpy as np

def calculate_acceptance_probability(dfa, q, t):
    transition_matrices, initial_state, final_state = dfa
    Aq = sum([np.array(transition_matrices[c])*q[c] for c in alphabet]).transpose()
    N = Aq.shape[0]
    v = np.array([int(i == initial_state) for i in range(N)])
    for _ in range(t):
        v = np.dot(Aq, v)
    return v[final_state]

######## demo

word = 'joel'  # the 4 letter word
t = 8          # the total number of letters

dfa = compile_word_to_dfa_that_matches_it_as_substring(word)
q = {c: 1/len(alphabet) for c in alphabet}
answer = calculate_acceptance_probability(dfa, q, t)

print(f"The accepted stackexchange answer: {5/26**4}")
print(f"The exact answer with automaton: {answer}")


""" demo output

box% python -i main.py 
The accepted stackexchange answer: 1.094149364518049e-05
The exact answer with automaton: 1.094148885652915e-05
>>>

"""