diff options
| -rw-r--r-- | challenge-096/cheok-yin-fung/perl/ch-1.pl | 10 | ||||
| -rw-r--r-- | challenge-096/cheok-yin-fung/perl/ch-2.pl | 155 |
2 files changed, 165 insertions, 0 deletions
diff --git a/challenge-096/cheok-yin-fung/perl/ch-1.pl b/challenge-096/cheok-yin-fung/perl/ch-1.pl new file mode 100644 index 0000000000..5ff9bce20c --- /dev/null +++ b/challenge-096/cheok-yin-fung/perl/ch-1.pl @@ -0,0 +1,10 @@ +# The Weekly Challenge 096 +# Usage: +# $ perl ch-1.pl "the weekly challenge" +# challenge weekly the + +$_ = $ARGV[0]; +s/(\s)+/ /g ; +@a = reverse split / /, $_; +print join " ", @a; +print "\n" diff --git a/challenge-096/cheok-yin-fung/perl/ch-2.pl b/challenge-096/cheok-yin-fung/perl/ch-2.pl new file mode 100644 index 0000000000..c8be2a822c --- /dev/null +++ b/challenge-096/cheok-yin-fung/perl/ch-2.pl @@ -0,0 +1,155 @@ +use strict; +no warnings; +use experimental 'switch'; + +my $S1 = $ARGV[0] ? $ARGV[0] : "sunday"; +die "Please input two parameters. " if (!$ARGV[1] && $ARGV[0]); +my $S2 = $ARGV[1] ? $ARGV[1] : "monday"; + +print "$S1 -> $S2\n\n"; + +edit_dis($S1, $S2); + +sub edit_dis { + my $d; + my $op_d; + my $pre_d; + my @A = ( '|' , (split //, $_[0])); # "|" is a dummy variable + my @B = ( '|' , (split //, $_[1])); + my $n = scalar @A; + my $m = scalar @B; + + $d->[0][0] = 0; + $op_d->[0][0] = undef; + $pre_d->[0][0] = undef; + + for my $i (1..$n-1) { + $d->[$i][0] = $i; + $op_d->[$i][0] = "insert"; + $pre_d->[$i][0] = [$i-1, 0]; + } + + for my $j (1..$m-1) { + $d->[0][$j] = $j; + $op_d->[0][$j] = "insert"; + $pre_d->[0][$j] = [0,$j-1]; + } + + for my $j (0..$m-1) { + for my $i (0..$n-1) { + my $op; + my $pre; + #1st step: check match/mismatch + if ($A[$i] eq $B[$j]) { + $op = "match"; + if ($i > 0 && $j > 0) { + $d->[$i][$j] = $d->[$i-1][$j-1]; + $pre = [$i-1, $j-1]; + } elsif ($i>0) { + $d->[$i][$j] = $d->[$i-1][$j]; + $pre = [$i-1, $j]; + } elsif ($j>0) { + $d->[$i][$j] = $d->[$i][$j-1]; + $pre = [$i, $j-1]; + } else { + $d->[$i][$j] = 0; + $pre = undef; + } + } else { + $op = "replace"; + if ($i != 0 && $j != 0) { + $d->[$i][$j] = $d->[$i-1][$j-1] + 1; + $pre = [$i-1, $j-1]; + } + elsif ($i > 0) { + $op = "delete"; + $d->[$i][$j] = $d->[$i-1][$j] + 1; + $pre = [$i-1, $j]; + } + elsif ($j > 0) { + $op = "insert"; + $d->[$i][$j] = $d->[$i][$j-1] + 1; + $pre = [$i, $j-1]; + } + else { + $op = "ID"; + $d->[$i][$j] = 1; + $pre = undef; + } + } + + # 2nd step: check if "insert" is efficient + if ($j > 0 && $d->[$i][$j] > $d->[$i][$j-1]+1) { + $op = "insert"; + $d->[$i][$j] = $d->[$i][$j-1]+1; + $pre = [$i, $j-1]; + } + + # 3rd step check if "delete" is efficient + if ($i > 0 && $d->[$i][$j] > $d->[$i-1][$j]+1) { + $op = "delete"; + $d->[$i][$j] = $d->[$i-1][$j]+1; + $pre = [$i-1, $j]; + } + + $op_d->[$i][$j] = $op; + $pre_d->[$i][$j] = $pre; + + } + } + + print "Edit distance: ", $d->[$n-1][$m-1], "\n\n"; + + + my @seq_op; + my @abcA_op; + my @abcB_op; + my $sA = $n-1; + my $sB = $m-1; + while ($sA >= 0 && $sB >= 0 && defined $pre_d->[$sA][$sB]) { + if ($op_d->[$sA][$sB] ne "match") { + unshift @seq_op, $op_d->[$sA][$sB]; + unshift @abcA_op, $sA; + unshift @abcB_op, $sB; + } + ($sA,$sB) = @{$pre_d->[$sA][$sB]}; + } + + if ( scalar @seq_op == 0 ) {print "same word\n"; exit;} + + for my $k (0..$#seq_op) { + print "Operation ",$k+1,": "; + given ($seq_op[$k]) { + when (/replace/) { + print "replace the \'$A[$abcA_op[$k]]\' by \'$B[$abcB_op[$k]]\'"; + } + when (/insert/) { + if ($A[$abcA_op[$k]] ne "|") { + my $bef; + $bef = ($abcA_op[$k] <= $abcB_op[$k]) ? "after" : "before"; + print "insert \'$B[$abcB_op[$k]]\' $bef the \'$A[$abcA_op[$k]]\'"; + } + else { + print "insert \'$B[$abcB_op[$k]]\' at the front"; + } + } + when (/delete/) { + if ($B[$abcB_op[$k]] ne "|") { + my $bef; + $bef = ($abcA_op[$k] => $abcB_op[$k]) ? "after" : "before"; + print "delete the \'$A[$abcA_op[$k]]\' $bef the \'$B[$abcB_op[$k]]\'"; + } + else { + print "delete the \'$A[$abcA_op[$k]]\' at the front."; + } + } + }; + print "\n"; + + } + print "\nDONE!\n"; + return $d->[$n-1][$m-1]; + +} + + |