#!/usr/local/bin/perl 


#========================   STEP 1   =========================#
# 	Objectives:
# 	Take two sequences as input string 
# 	compare their length 
#	convert the strings into arrays
#=======================================================================#

#Assign two sequences in two different variables ( seq1 and seq2 )


# Get the length of each sequence and assign them in two different variables


# Optional - (print the sequence with their corresponding length)


# using the max and min subroutine ( supplied ) identify the longer seq and the shorter seq
# and assign the length accordingly in two different variable


# Convert the sequences into arrays. 

# Optional - print the arrays.


#========================  STEP 2 =========================#
# 	Objectives:
# 	Build the matrix i.e. two dimensional array. 
# 	Initialize the matrix
#=======================================================================#

# Initialize the matrix
	
#Traverse through the matrix
		# if the cell is (0,0) assign 0																	S(0,0) = 0;
		# if the cell is S(i,0) where the value of i is >=1 but <n then assign iw        	S(i,0) = iw, 1<= i <n
		# if the cell is S(0,j) where the value of j is >=1 but <m then assign jw			S(0,j) = jw, 1<= j <m


# Optional - with the Print_Array subroutine (supplied) print the initialized array
#Print_Array(@main_array);
	
# Optional - with the Print_Array subroutine (supplied) print the initialized array

#========================   STEP 3     =========================#
# 	Objectives:
#	Fill the matrix
# 	While filling keep pointer to that cell for future trace back
#=======================================================================#

# Traverse through the matrix - starting from the 1st row and column since the 0th row and col is already filled with 0s
		
	# For the current cell, declare three variables to assign the diagonal value, vertical value and horizontal value
		
		# Assign the diagonal value for the current cell
		# Two options for the diagonal value 
		# if the corresponding nucleotides are same then {S i-1, j-1+ M i,j }  where M i,j  = 1
		# else {S i-1, j-1+ M i,j }  where M i,j  = 0

		# Assign the vertical value S i-1, j+ w
		
		# Assign the horizontal value S i, j-1 + w
		
		# Using the max subroutine get the maximum value of the three and assign the value to the current cell.

		# If the max value is the diagonal value then the key for the hash will be the current cell coordinate and 'D' will be the value
		# If the max value is the vertical value then the key for the hash will be the current cell coordinate and 'V' will be the value
		# If the max value is the Horizontal value then the key for the hash will be the current cell coordinate and 'H' will be the value

# At the end of  traversing the matrix will be filled with values and a separate hash table will be built which will have cell coordinate as hash
# and pointers as values

# Optional 	- using the supplied Print_Array function print the filled array 
#				- Print the hash table to check how does it look

#========================      STEP 4      =========================#
# 	Objectives:
#	Trace back the alignment path
# 	While tracing back generate the actual alignment
#=======================================================================#

# Assign the lower right corner cell as the current cell to begin trace back

# While the current cell is not the upper left corner cell 

	# for the current cell ( start with the lower right corner cell )
		
		# if the pointer is diagonal step back one cell diagonally and re assign the current cell accordingly
		# Assign the corresponding column nucleotide in the first array declared to hold the aligned sequence
		# Assign the corresponding row nucleotide in the second array declared to hold the aligned sequence
		
		# elsif the pointer is vertical then step back one cell row wise and re assign the current cell accordingly.
		# Assign gap sign in the first array declared to hold the aligned sequence
		# Assign the corresponding row nucleotide in the second array declared to hold the aligned sequence

		# else ( the pointer must be a vertical one) step back one cell column wise and re assign the current cell accordingly.
		# Assign the corresponding column nucleotide in the first array declared to hold the aligned sequence
		# Assign gap sign in the second array declared to hold the aligned sequence

# At the end of the loop two arrays are filled with nucleotides and gap signs, however the sequence is from right to left
# since we started from the lower right corner cell and ended at upper left corner cell 

# Reverse both the arrays using the in built reverse function. 

# Print both arrays separated by new line -- Got your Alignment !!


#======================== Subroutines ==================================# 

# subroutine to calculate the maximum
sub max 
{
    my $max = shift(@_);    # shift removes the first value from @_
    
    foreach my $val (@_) 
    {
	    if($max < $val)
	    {
        	$max = $val;
    	}
    }
    return $max;
}

#subroutine to calculate minimum
sub min 
{
    my $min = shift(@_);    # shift removes the first value from @_
    
    foreach my $val (@_) 
    {
	    if($min > $val)
	    {
        	$min = $val;
    	}
    }
    return $min;
}

# subroutine to print the array
sub Print_Array
{
	(@array) =@_;

    for $i ( 0 .. $#array ) 
    {
        for $j ( 0 .. $#{$array[$i]} ) 
        {    
	        print $array[$i][$j]," ";
        }        
        print "\n";
    }
}