# Viterbi Algorithm
# Christopher Zelazo (A10863450)

import math
import sys

# Pull from sources
with open("observations.txt") as f:
    observations = f.read().split(' ')

with open("initialStateDistribution.txt") as f:
    stateDistros = [line.rstrip() for line in f]

with open("emissionMatrix.txt") as f:
    emmissions = [[line.split()[0], line.split()[1]] for line in f]

with open("transitionMatrix.txt") as f:
    transitions = [line.rstrip().split(' ') for line in f]

lstar = [None] * 26
sstar = [None] * 45000
alphabet = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
            'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
message = ""

def viterbi(s, t):
    mathsLS = lstar[:]      # Does Python pass by reference? IDK YOLO
    pi = float(stateDistros[s])
    b = float(emmissions[s][int(observations[t])])
    max = -sys.float_info.max

    if t != 0:
        for i in range(26):
            a = float(transitions[s][i])
            next = mathsLS[i] + math.log(a)

            if next > max: max = next

    else:
        max = math.log(pi)

    mathsLS[s] = (max + math.log(b))
    return mathsLS

for (idx, t) in enumerate(observations):

    # Starlight, starbright
    for s in range(26):
        lstar = viterbi(s, int(t))[:]

    # Take it back now y'all
    likelyIdx = 0
    for i in range(26):
        i_val = lstar[i]
        likely_val = lstar[likelyIdx]

        likelyIdx = i if (i_val > likely_val) else likelyIdx

    # print likelyIdx

    sstar[idx] = likelyIdx

    # if idx % 1000 == 0 :
    #   print lstar

print lstar

# print output
for (idx, s) in enumerate(sstar):
    if idx != 0:
        if sstar[idx-1] == s:
            continue

    message += alphabet[int(s)]

print message