#!/usr/local/bin/python


states = ('Rainy', 'Sunny')

observations = ('walk', 'shop', 'clean')

start_probability = {'Rainy': 0.6, 'Sunny': 0.4}

transition_probability = {
   'Rainy' : {'Rainy': 0.7, 'Sunny': 0.3},
   'Sunny' : {'Rainy': 0.4, 'Sunny': 0.6},
   }

emission_probability = {
   'Rainy' : {'walk': 0.1, 'shop': 0.4, 'clean': 0.5},
   'Sunny' : {'walk': 0.6, 'shop': 0.3, 'clean': 0.1},
   }
def forward_viterbi(y, X, sp, tp, ep):
   T = {}
   for state in X:
       ##          prob.      V. path  V. prob.
       T[state] = (sp[state], [state], sp[state])
   for output in y:
       U = {}
       for next_state in X:
           total = 0
           argmax = None
           valmax = 0
           for source_state in X:
               (prob, v_path, v_prob) = T[source_state]
               p = ep[source_state][output] * tp[source_state][next_state]
               prob *= p
               v_prob *= p
               total += prob
               if v_prob > valmax:
                   argmax = v_path + [next_state]
                   valmax = v_prob
           U[next_state] = (total, argmax, valmax)
       T = U
   ## apply sum/max to the final states:
   total = 0
   argmax = None
   valmax = 0
   for state in X:
       (prob, v_path, v_prob) = T[state]
       total += prob
       if v_prob > valmax:
           argmax = v_path
           valmax = v_prob
   return (total, argmax, valmax)
def example():
   return forward_viterbi(observations,
                          states,
                          start_probability,
                          transition_probability,
                          emission_probability)
print example()