# Smith-Waterman  Algorithm
# call: perl SW_exercise.pl AAUGCCAUUGACGG CAGCCUCGCUUAG


# usage statement
die "usage: $0 <sequence 1> <sequence 2>\n" unless @ARGV == 2;

# get sequences from command line
$seq1=shift;
$seq2=shift;

# scoring scheme
my $MATCH    =  1;     # +1 for letters that match
my $MISMATCH = -(1/3); # - (1/3) for letters that mismatch
my $GAP      = -(4/3); # - (1 + 1/3) for any gap


# initialization
my @matrix;
$matrix[0][0]{score}   = 0;
$matrix[0][0]{pointer} = "*";
for(my $j = 1; $j <= length($seq1); $j++) {
    $matrix[0][$j]{score}   = 0;
    $matrix[0][$j]{pointer} = "*";
}
for (my $i = 1; $i <= length($seq2); $i++) {
    $matrix[$i][0]{score}   = 0;
    $matrix[$i][0]{pointer} = "*";
}

# fill
my $max_i     = 0;
my $max_j     = 0;
my $max_score = 0;

for(my $i = 1; $i <= length($seq2); $i++) {
    for(my $j = 1; $j <= length($seq1); $j++) {
        my ($diagonal_score, $left_score, $up_score);
        
        # calculate match/mismatch score
        my $letter1 = substr($seq1, $j-1, 1);
        my $letter2 = substr($seq2, $i-1, 1);       
        if ($letter1 eq $letter2) {
            $diagonal_score = $matrix[$i-1][$j-1]{score} + $MATCH;
        }
        else {
            #### save in $diagonal_score the score in the diagonal cell plus the penalty for the mismatch ### FILL IN ###### 
        }
        
        # calculate gap scores and save them in the $up_score and $left_score variables(unweighted linear mode) ### FILL IN #####
        
        
        ########################################################################
        # if $diagonal_score, $up_score and $left_score are ALL equal or lower than 0 
		# save in the current cell 0 as score and * as pointer and then move to the next cell
        
        if ($diagonal_score <= 0 and $up_score <= 0 and $left_score <= 0) {
            $matrix[$i][$j]{score}   = 0;
            $matrix[$i][$j]{pointer} = "*";
            next; # terminate this iteration of the loop
        }
        
        # choose best score
        if ($diagonal_score >= $up_score) {
            if ($diagonal_score >= $left_score) {
                $matrix[$i][$j]{score}   = ### save in this cell the value stored in $diagonal_Score ### FILL IN ####
                $matrix[$i][$j]{pointer} = ### save in this cell the value "d" (diagonal pointer) ### FILL IN ####
            }
            else {
				### save in this cell the value stored in $left_Score ### FILL IN ####
				### save in this cell the value "l" (left pointer) ### FILL IN ####
            }
        } else {
            if ($up_score >= $left_score) {
 				### save in this cell the value stored in $up_Score ### FILL IN ####
				### save in this cell the value "u" (up pointer) ### FILL IN ####               
            }
            else {
				### save in this cell the value stored in $left_Score ### FILL IN ####
				### save in this cell the value "l" (left pointer) ### FILL IN ####

            }
        }
        
        # set maximum score
        if ($matrix[$i][$j]{score} > $max_score) {
            $max_i     = $i;
            $max_j     = $j;
            $max_score = $matrix[$i][$j]{score};
        }
    }
}

############# PRINT THE SEQUENCES and the length of the sequences ### FILL IN (OPT) ###

############# PRINT THE MATRICES #######   FILL IN (OPT) ##############################

############# PRINT MAX SCORE (value, row index, column index ) ### FILL IN (OPT) #####

# trace-back 

my $align1 = "";
my $align2 = "";

my $j = $max_j;
my $i = $max_i;

while (1) {
    last if $matrix[$i][$j]{pointer} eq "*";
    
    if ($matrix[$i][$j]{pointer} eq "d") {
        $align1 .= substr($seq1, $j-1, 1);
        $align2 .= substr($seq2, $i-1, 1);
        $i--; $j--;
    }
    elsif ($matrix[$i][$j]{pointer} eq "l") {
		#### add the current simbol in $seq1 (use substr starting from the position $j-1) to $align1 ### FILL IN ###
		#### add a GAP symbol - to $align2 ##### FILL IN #############
		#### decrement the value stored in $j of 1 ### FILL IN #######
    }
    elsif ($matrix[$i][$j]{pointer} eq "u") {
		#### add a GAP symbol - to $align1 ##### FILL IN #############
		#### add the current simbol in $seq2 (use substr starting from the position $i-1) to $align2 ### FILL IN ###
		#### decrement the value stored in $i of 1 ### FILL IN #######
    }   
}

$align1 = reverse $align1;
$align2 = reverse $align2;
print "$align1\n";
print "$align2\n";