use strict;
use warnings;

sub shorten {
    my $tmp = shift;
    return substr($tmp,0,length($tmp)-1);
}

sub min {
    my $rv = shift;
    while (@_) {
        my $tmp = shift;
        $rv = $tmp if $tmp < $rv;
    }
    return $rv;
}

sub editDistance {
    my ($l, $lenL, $r, $lenR) = map { $_, length($_) } @_;

    return $lenR unless $lenL;
    return $lenL unless $lenR;

    if (substr($l,-1) eq substr($r,-1)) {
        return editDistance(shorten($l), shorten($r));
    }

    return 1 + min(
        editDistance($l,          shorten($r)), #insert
        editDistance(shorten($l), $r),          #remove
        editDistance(shorten($l), shorten($r))  #replace
    );
}

my @pairs = (
    [ "Sundayyy", "Saturday" ],
    [ "sunday", "saturday" ],
);
for my $ar (@pairs) {
    my ($str1, $str2) = @$ar;
    print editDistance($str1,$str2), " <$str1:$str2>\n";
}