#! /usr/bin/perl
##========================================================================
## Name:
## Date:
##========================================================================

use strict;                  

my @score;			# Matrix to hold scores
my (@up, @left, @diag);		# For memoization
my $gapPenalty = -2;		# gap penalty
my $matchScore = +1;		# match score
my $mismatchScore = -1; 	# mismatch score

##========================================================================
##
## Subroutine reward() gives the match/mismatch reward/penalty
##
##========================================================================
sub reward {
    my ($base1, $base2) = @_;
    return ($base1 eq $base2) ? $matchScore : $mismatchScore;
}

##========================================================================
##
## Subroutine max() computes the maximum of any number of parameters
## The first term is used to hold the greatest term as we search
##
##========================================================================
sub max {
    my ($first_most, @rest) = @_;
    foreach my $x (@rest) {
        $first_most = $x if ($x > $first_most);
    }
    return $first_most;
}

##========================================================================
##
## Subroutine fillMatrix() fills the scoring matrix and returns the
## numerical similarity of its arguments.
## Note that it does not compute the alignment
##
##========================================================================
sub fillMatrix {
    my ($sequence1, $sequence2) = @_;
##
## Initialize the score matrices
##
    foreach my $i (0..length($sequence1)) {
	$score[0][$i] = $i * $gapPenalty;
	$score[$i][0] = $i * $gapPenalty;
    }

##
## Fill the rest of the matrix
##
    foreach my $i (1..length($sequence1)) {
        foreach my $j (1..length($sequence2)) {
	    # This is where you have to fill in some stuff
	    $up[$i][$j] = 0;
	    $left[$i][$j] = 0;
	    $diag[$i][$j] = 0;
	    $score[$i][$j] = max($i, $j, 1, 2, 3);
	    if($j == max($i, $j)){
		$up[$i][$j] = 1;
	    }
	    if($j == max($i, $j)){
		$left[$i][$j] = 1;
	    }
        }
    }

    #
    # Here we print the score matrix, just so you can see it.
    # 
    foreach my $i (1..length($sequence1)) {
        foreach my $j (1..length($sequence2)) {
	    print($score[$i][$j]." ");
        }
	print("\n");
    }



    return ( $score[length($sequence1)][length($sequence2)]);
}

##========================================================================
##
## Subroutine getAlignment() assumes the scoring matrix has been filled.
## It takes two strings as arguments and returns a list of the same two
## strings with gap symbols inserted to achieve the best-scoring alignment.
##
##========================================================================
sub getAlignment {
    my ($sequence1, $sequence2) = @_;
    my ($seq1Length, $seq2Length) = (length($sequence1), length($sequence2));
    return ( "-"x$seq2Length, $sequence2) if ( $seq1Length == 0);
    return ( $sequence1, "-"x$seq1Length) if ( $seq2Length == 0);

    # Otherwise, what should you do, perhaps recursively?
}


##
## Here begins the main perl program.
##
## The curly braces make this an example of a naked block; the my variables
## will be lexically local to this block.
##
##========================================================================
{
    my $sequence1 = <STDIN>; chomp($sequence1);
    my $sequence2 = <STDIN>; chomp($sequence2);
    print "Similarity score: ", fillMatrix($sequence1, $sequence2), "\n";
    print "Alignment: \n";
    foreach my $x (getAlignment($sequence1, $sequence2)) {
        print $x, "\n";
    }
}