#!/usr/bin/perl -lws
#
# possible options: -log -debug
#
require strict;

# ===== DATA STRUCTURES ====================

my @states = ('1','2');
my @voc = ('H','T');

my %init = ( $states[0] => 0.5 );
$init{$states[1]} = 1 - $init{$states[0]};

my %trans = ( 
    $states[0] => { $states[0] => 0.4 } ,
    $states[1] => { $states[0] => 0.9 } 
);
$trans{$_}{$states[1]} = 1 - $trans{$_}{$states[0]} foreach keys %trans;

my %emit = (
    $states[0] => { $voc[0] => 0.49 } ,
    $states[1] => { $voc[0] => 0.85 } 
);
$emit{$_}{$voc[1]} = 1 - $emit{$_}{$voc[0]} foreach keys %emit;

my $input = 'HTTHTTHHTTHTTTHHTHHTTHTTTTHTHHTHTHHTTTH';
my @input  = split //, $input;

if ($::debug) { 
    print "init:";
    print "$_ => $init{$_}" foreach keys %init ; 
    print "trans:";
    foreach my $row (keys %trans) {
        print " $row:";
        print "\t$_ => $trans{$row}{$_}" foreach (keys %{$trans{$row}}) ; 
    }
    print "emit:";
    foreach my $row (keys %emit) {
        print " $row:";
        print "\t$_ => $emit{$row}{$_}" foreach (keys %{$emit{$row}}) ; 
    }
}

# ===== INITIALISATION ====================

my $i = 1; # for debugging only

my %last = ();
my %new = ();

my $c = shift @input;

if ($::log) {
    $new{$_} = log($init{$_}) + log($emit{$_}{$c}) foreach (@states);
} else {
    $new{$_} = $init{$_} * $emit{$_}{$c} foreach (@states);
}

if ($::debug) {
    print '-' x 5, " i=$i ", '-' x 5;
    print "$_ => $new{$_}" foreach keys %new ; 
}

# ===== FORWARD ====================

my @bests = ();
my ($prev, $best, $max, $value, %col);

while ($c = shift @input) {
    
    %last=%new;
    %col=%new=();

    foreach (@states) {

        # ----- Searching for max -----
        $max = $::log ? -Inf : 0; 
        $best = 0;
        foreach $prev (@states) {

            if ($::log) {
                $value = $last{$prev} + log($trans{$prev}{$_});
            } else  {
                $value = $last{$prev} * $trans{$prev}{$_};
            }

            if ($max < $value) {
                $max = $value;
                $best = $prev;
            }
        }

        # ----- Update -----
        $col{$_} = $best;
        if ($::log) {
            $new{$_} = $max + log($emit{$_}{$c});
        } else {
            $new{$_} = $max * $emit{$_}{$c};
        }
    }

    push @bests, { %col } ;

    if ($::debug) { 
        print '-' x 5, ' i=', ++$i, ' ', '-' x 5;
        print "$_ => $new{$_}" foreach keys %new ; 
    }
}

if ($::debug) { 
    print '=' x 10, ' BESTS ', '=' x 10;
    $i = 1;
    foreach my $row (@bests) {
        print '-' x 5, ' i=', ++$i, ' ', '-' x 5;
        print "$_ => $row->{$_}" foreach keys %{$row} ; 
    }
    print '=' x 10;
}

# ===== BACKWARD ====================

# ----- Searching for last max -----
$max = $::log ? -Inf : 0; 
foreach (@states) {
    if ($max < $new{$_}) {
        $max = $new{$_};
        $best = $_;
    }
}

my $output=$best;
while( my $x = pop @bests) {
    $best = $x->{$best};
    $output = $best . $output;
}

# ===== RESULT ====================

print $input;
print $output;
