diff options
author | Jesse Luehrs <doy@tozt.net> | 2012-11-19 03:21:07 -0600 |
---|---|---|
committer | Jesse Luehrs <doy@tozt.net> | 2012-11-19 03:21:07 -0600 |
commit | 68f306c0367700abbc1093af6c493292bc76d99f (patch) | |
tree | a4b283daea1712a998ca9f69d6d80295e32e4cfa | |
parent | 705deaf4444a5200e1646b0fb58b5794c7296b81 (diff) | |
download | rosalind-68f306c0367700abbc1093af6c493292bc76d99f.tar.gz rosalind-68f306c0367700abbc1093af6c493292bc76d99f.zip |
another solution
-rw-r--r-- | EDTA.pl | 48 |
1 files changed, 48 insertions, 0 deletions
@@ -0,0 +1,48 @@ +#!/usr/bin/env perl +use strict; +use warnings; +use 5.016; + +use List::Util 'min'; +use Memoize; + +chomp(my $str1 = <>); +chomp(my $str2 = <>); + +my ($distance, $aligned1, $aligned2) = align($str1, $str2); +say $distance; +say $aligned1; +say $aligned2; + +sub align { + my ($str1, $str2) = @_; + + return (length($str2), ('-' x length($str2)), $str2) if !length($str1); + return (length($str1), $str1, ('-' x length($str1))) if !length($str2); + + my @delete = align(substr($str1, 1), $str2); + $delete[0]++; + $delete[1] = substr($str1, 0, 1) . $delete[1]; + $delete[2] = '-' . $delete[2]; + + my @insert = align($str1, substr($str2, 1)); + $insert[0]++; + $insert[1] = '-' . $insert[1]; + $insert[2] = substr($str2, 0, 1) . $insert[2]; + + my @substitute = align(substr($str1, 1), substr($str2, 1)); + $substitute[0]++ if substr($str1, 0, 1) ne substr($str2, 0, 1); + $substitute[1] = substr($str1, 0, 1) . $substitute[1]; + $substitute[2] = substr($str2, 0, 1) . $substitute[2]; + + if ($delete[0] <= $insert[0] && $delete[0] <= $substitute[0]) { + return @delete; + } + elsif ($insert[0] <= $delete[0] && $insert[0] <= $substitute[0]) { + return @insert; + } + else { + return @substitute; + } +} +BEGIN { memoize('align') }; |