From 5bf4220266147c3c5f53ba1ba0b3ffc41b95b431 Mon Sep 17 00:00:00 2001 From: dcw Date: Sun, 24 Jan 2021 22:33:54 +0000 Subject: imported my solutions to this week's challenge.. task 1: trivial, task 2: only did the naive recursive form cos I got bogged down.. --- challenge-096/duncan-c-white/README | 71 ++++++++++++++----------- challenge-096/duncan-c-white/perl/ch-1.pl | 37 +++++++++++++ challenge-096/duncan-c-white/perl/ch-2.pl | 88 +++++++++++++++++++++++++++++++ 3 files changed, 165 insertions(+), 31 deletions(-) create mode 100755 challenge-096/duncan-c-white/perl/ch-1.pl create mode 100755 challenge-096/duncan-c-white/perl/ch-2.pl (limited to 'challenge-096') diff --git a/challenge-096/duncan-c-white/README b/challenge-096/duncan-c-white/README index b4f84102f4..332493400e 100644 --- a/challenge-096/duncan-c-white/README +++ b/challenge-096/duncan-c-white/README @@ -1,49 +1,58 @@ -Task 1: "Palindrome Number +Task 1: "Reverse Words -You are given a number $N. -Write a script to figure out if the given number is Palindrome. -Print 1 if true otherwise 0. +You are given a string $S. + +Write a script to reverse the order of words in the given string. The +string may contain leading/trailing spaces. The string may have more +than one space between words in the string. Print the result without +leading/trailing spaces and there should be only one space between words. Example 1: - Input: 1221 - Output: 1 + Input: $S = "The Weekly Challenge" + Output: "Challenge Weekly The" Example 2: - Input: -101 - Output: 0, since -101 and 101- are not the same. + Input: $S = " Perl and Raku are part of the same family " + Output: "family same the of part are Raku and Perl" +" + +My notes: looks straightforward. -Example 3: - Input: 90 - Output: 0 -" +Task 2: "Edit Distance -My notes: sounds trivial. N == join(reverse(split(N))) +You are given two strings $S1 and $S2. +Write a script to find out the minimum operations required to convert +$S1 into $S2. The operations can be insert, remove or replace a +character. Please check out +https://en.wikipedia.org/wiki/Edit_distance +for more information. -Task 2: "Demo Stack +Example 1: + + Input: $S1 = "kitten"; $S2 = "sitting" + Output: 3 -Write a script to demonstrate Stack operations like below: + Operation 1: replace 'k' with 's' + Operation 2: replace 'e' with 'i' + Operation 3: insert 'g' at the end -push($n) - add $n to the stack -pop() - remove the top element -top() - get the top element -min() - return the minimum element +Example 2: -Example: + Input: $S1 = "sunday"; $S2 = "monday" + Output: 2 -my $stack = Stack->new; -$stack->push(2); -$stack->push(-1); -$stack->push(0); -$stack->pop; # removes 0 -print $stack->top; # prints -1 -$stack->push(0); -print $stack->min; # prints -1 + Operation 1: replace 's' with 'm' + Operation 2: replace 'u' with 'o' " -My notes: ok so by "script" we mean "Perl class". Very easy to do, -but I wonder what ch-2.pl does - contains the above example I guess. -On second thought, let's inline the Stack module into ch-2.pl.. +My notes: reading the Wikipedia page, the naive recursive implementation +sounds good enough to me, even though it's hideously inefficent. +The various iterative versions sound clever, especially the one which +only stores two rows, but I can't be bothered. + +(note that there are several CPAN modules which do this, but solving a +Perl Challenge by "use Text::Levenshtein" seems like cheating). diff --git a/challenge-096/duncan-c-white/perl/ch-1.pl b/challenge-096/duncan-c-white/perl/ch-1.pl new file mode 100755 index 0000000000..0b8f9d2a58 --- /dev/null +++ b/challenge-096/duncan-c-white/perl/ch-1.pl @@ -0,0 +1,37 @@ +#!/usr/bin/perl +# +# Task 1: "Reverse Words +# +# You are given a string $S. +# +# Write a script to reverse the order of words in the given string. The +# string may contain leading/trailing spaces. The string may have more +# than one space between words in the string. Print the result without +# leading/trailing spaces and there should be only one space between words. +# +# Example 1: +# +# Input: $S = "The Weekly Challenge" +# Output: "Challenge Weekly The" +# +# Example 2: +# +# Input: $S = " Perl and Raku are part of the same family " +# Output: "family same the of part are Raku and Perl" +# " +# +# My notes: looks straightforward. +# + +use strict; +use warnings; +use feature 'say'; +use Data::Dumper; + +die "Usage: reverse-words S\n" if @ARGV==0; +my $s = join(' ', @ARGV); + +$s =~ s/^\s+//; +$s =~ s/\s+$//; +my @rw = reverse( split(/\s+/, $s ) ); +say join(' ', @rw); diff --git a/challenge-096/duncan-c-white/perl/ch-2.pl b/challenge-096/duncan-c-white/perl/ch-2.pl new file mode 100755 index 0000000000..90187b85cb --- /dev/null +++ b/challenge-096/duncan-c-white/perl/ch-2.pl @@ -0,0 +1,88 @@ +#!/usr/bin/perl +# +# Task 2: "Edit Distance +# +# You are given two strings $S1 and $S2. +# +# Write a script to find out the minimum operations required to convert +# $S1 into $S2. The operations can be insert, remove or replace a +# character. Please check out https://en.wikipedia.org/wiki/Edit_distance +# for more information. +# +# Example 1: +# +# Input: $S1 = "kitten"; $S2 = "sitting" +# Output: 3 +# +# Operation 1: replace 'k' with 's' +# Operation 2: replace 'e' with 'i' +# Operation 3: insert 'g' at the end +# +# Example 2: +# +# Input: $S1 = "sunday"; $S2 = "monday" +# Output: 2 +# +# Operation 1: replace 's' with 'm' +# Operation 2: replace 'u' with 'o' +# " +# +# My notes: reading the Wikipedia page, the naive recursive implementation +# sounds good enough to me, even though it's hideously inefficent. +# The various iterative versions sound clever, especially the one which +# only stores two rows, but I can't be bothered. +# +# (note that there are several CPAN modules which do this, but solving a +# Perl Challenge by "use Text::Levenshtein" seems like cheating). +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +use Function::Parameters; +use Data::Dumper; +use List::Util qw(min); + +my $debug=0; +die "Usage: edit-distance [--debug] A B\n" unless + GetOptions( "debug" => \$debug ) && @ARGV==2; +my( $a, $b ) = @ARGV; + +my $ed = lev($a, $b); +say $ed; + +# +# my $ed = lev($a, $b); +# Calculate and return the Levenshtein edit distance between $a and $b. +# Naive recursive implmentation, basically: +# len(a), if len(b)==0 +# len(b), if len(a)==0 +# lev(tail(a),tail(b), if a[0]==b[0] +# else 1 + min( +# lev(tail(a),b), +# lev(a,tail(b)), +# lev(tail(a),tail(b)) ) +# +fun lev( $a, $b ) +{ + return length($a) if length($b)==0; + + return length($b) if length($a)==0; + + # if a[0]==b[0]: lev(tail(a),tail(b) + if( substr($a,0,1) eq substr($b,0,1) ) + { + return lev( substr($a,1), substr($b,1) ); + } + + # 1 + min( + # lev(tail(a),b), + # lev(a,tail(b)), + # lev(tail(a),tail(b)) ) + return 1 + min( + lev(substr($a,1), $b), + lev($a,substr($b,1)), + lev(substr($a,1), substr($b,1)) + ); +} -- cgit