Perl Weekly Challenge 295.
My solutions (task 1 and task 2 ) to the The Weekly Challenge - 295.
Task 1: Word Break
Submitted by: Mohammad Sajid Anwar
You are given a string, $str, and list of words, @words.
Write a script to return true or false whether the given string can be
segmented into a space separated sequnce of one or more words from the given list.
Example 1
Input: $str = 'weeklychallenge', @words = ("challenge", "weekly")
Output: true
Example 2
Input: $str = "perlrakuperl", @words = ("raku", "perl")
Output: true
Example 3
Input: $str = "sonsanddaughters", @words = ("sons", "sand", "daughters")
Output: false
I can build a regular expression anchored at the beginning and the end and that allows any number of repetitions of any of the words in between. The matching operator would then take charge of recursion and backtracking, yielding a one-liner:
Example 1:
perl -E '
my ($s,@w)=@ARGV;$w=join "|", @w; say "String: $s, words: @w -> ", $s=~/^($w)*$/?"True":"False";
' weeklychallenge challenge weekly
Results:
String: weeklychallenge, words: challenge weekly -> True
Example 2:
perl -E '
my ($s,@w)=@ARGV;$w=join "|", @w; say "String: $s, words: @w -> ", $s=~/^($w)*$/?"True":"False";
' perlrakuperl raku perl
Results:
String: perlrakuperl, words: raku perl -> True
Example 3:
perl -E '
my ($s,@w)=@ARGV;$w=join "|", @w; say "String: $s, words: @w -> ", $s=~/^($w)*$/?"True":"False";
' sonsanddaughters sons sand daughters
Results:
String: sonsanddaughters, words: sons sand daughters -> False
The corresponding full code is:
1 # Perl weekly challenge 295
2 # Task 1: Word Break
3 #
4 # See https://wlmb.github.io/2024/11/11/PWC295/#task-1-word-break
5 use v5.36;
6 die <<~"FIN" unless @ARGV>=2;
7 Usage: $0 S W1 W2...
8 to find if string can be separated into one or more of the words
9 from the list W1 W2...
10 FIN
11 my ($string, @words)=@ARGV;
12 my $words=join '|', @words;
13 say "String: $string, words: @words -> ", $string=~/^(\s*$words\s*)*$/?"True":"False";
Examples:
./ch-1.pl weeklychallenge challenge weekly
./ch-1.pl perlrakuperl raku perl
./ch-1.pl sonsanddaughters sons sand daughters
Output: false
Results:
String: weeklychallenge, words: challenge weekly -> True
String: perlrakuperl, words: raku perl -> True
String: sonsanddaughters, words: sons sand daughters -> False
Notice that the code above allows spaces in the input strings and allows regular expressions instead of literal words as inputs, as in:
./ch-1.pl "weekly challenge" challenge weekly
./ch-1.pl 'weeklychallenge' 'w.*y' 'ch.*e'
Results:
String: weekly challenge, words: challenge weekly -> True
String: weeklychallenge, words: 'w.*y' 'ch.*e' -> True
Task 2: Jump Game
Submitted by: Mohammad Sajid Anwar
You are given an array of integers, @ints.
Write a script to find the minimum number of jumps to reach the last element.
$ints[$i] represents the maximum length of a forward jump from the index $i.
In case last element is unreachable then return -1.
Example 1
Input: @ints = (2, 3, 1, 1, 4)
Output: 2
Jump 1 step from index 0 then 3 steps from index 1 to the last element.
Example 2
Input: @ints = (2, 3, 0, 4)
Output: 2
Example 3
Input: @ints = (2, 0, 0, 4)
Output: -1
I can do a recursive procedure, trying out all possible first steps and recursing over the remaining list. I use memoize to avoid repetitions. If the list has only one element, I have arrived at the end and the answer is 0. If
Example 1:
perl -MMemoize -MList::Util=min -E '
memoize "f"; say "@ARGV -> ",f(@ARGV)//-1;sub f(@l){return 0 if @l<=1;my $s;for (1..$l[0])
{my $c=f(@l[$_..@l-1]);if(defined $c){$s=1+$c unless defined $s;$s=min($s,1+$c);}}return $s;}
' 2 3 1 1 4
Results:
2 3 1 1 4 -> 2
Example 2:
perl -MMemoize -MList::Util=min -E '
memoize "f"; say "@ARGV -> ",f(@ARGV)//-1;sub f(@l){return 0 if @l<=1;my $s;for (1..$l[0])
{my $c=f(@l[$_..@l-1]);if(defined $c){$s=1+$c unless defined $s;$s=min($s,1+$c);}}return $s;}
' 2 3 0 4
Output: 2
Results:
2 3 0 4 -> 2
Example 3:
perl -MMemoize -MList::Util=min -E '
memoize "f"; say "@ARGV -> ",f(@ARGV)//-1;sub f(@l){return 0 if @l<=1;my $s;for (1..$l[0])
{my $c=f(@l[$_..@l-1]);if(defined $c){$s=1+$c unless defined $s;$s=min($s,1+$c);}}return $s;}
' 2 0 0 4
Results:
2 0 0 4 -> -1
The full code follows
1 # Perl weekly challenge 295
2 # Task 2: Jump Game
3 #
4 # See https://wlmb.github.io/2024/11/11/PWC295/#task-2-jump-game
5 use v5.36;
6 use Memoize;
7 use List::Util qw(min);
8 die <<~"FIN" unless @ARGV;
9 Usage: $0 N0 N1 ... Nm
10 to find the minimum number of jumps to reach Nm starting from N0.
11 Ni is the maximum size of jumps from site i.
12 FIN
13 memoize "jump_game";
14 say "@ARGV -> ",jump_game(@ARGV)//-1;
15 sub jump_game(@list){
16 return 0 if @list<=1; # arrived?
17 my $steps;
18 for (1..min($list[0], @list-1)){ # Try to jump. Avoid going beyond the end
19 my $current=jump_game(@list[$_..@list-1]); # and play on remaining list
20 if(defined $current){ # success?
21 $steps = 1 + $current unless defined $steps; # initialize required steps
22 $steps = min($steps, 1 + $current); # choose shortest route
23 }
24 }
25 return $steps;
26 }
Examples:
./ch-2.pl 2 3 1 1 4
./ch-2.pl 2 3 0 4
./ch-2.pl 2 0 0 4
Results:
2 3 1 1 4 -> 2
2 3 0 4 -> 2
2 0 0 4 -> -1
Memozation is important for large inputs. For instance, the example below finds the result (3) in 0.01s with memoization and 7.3s without, 730 times slower.
time ./ch-2.pl 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
/;
Written on November 11, 2024