Perl Weekly Challenge: Week 295
Challenge 1:
Word Break
You are given a string,
$str, and list of words,@words.Write a script to return
trueorfalsewhether the given string can be segmented into a space separated sequence 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 am still wondering if there is a cleverer way to solve this challenge but the one I came up with is pretty compact.
I assume the input will be in command-line parameters. The first will be $str and the rest will be
@words. The way to express this in Raku is like this:
MAIN($str, *@words)
But the problem is function parametes in Raku are immutable and, as we shall see, we will need to modify $str.
So my MAIN()signature just looks like this:
MAIN(*@words)
and the first line of that function is this:
my $str = @words.shift;
Now $str is mutable.
Then for each word in @words...
for @words -> $word {
...I just globally (the :g flag) delete it from $str.
$str ~~ s:g/$word//;
}
If after all words have been removed, the length of $str is less than 1 (or I could have said equals 0; don't
remember why I didn't.) we print True otherwise we print False.
say $str.chars < 1;
The Perl version works the same way but we don't need to worry about immutability.
my $str = shift;
my @words = @ARGV;
for my $word (@words) {
$str =~ s/$word//g;
}
Also because Perl didn't have a formal Boolean type until recently and even the experimental feature in the latest versions doesn't include printable representations of the truth values (yet?), we have to explicitly print true or false.
say length $str < 1 ? 'true' : 'false';
Challenge 2:
Jump Game
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
Once again we will assume that the input is being provided via command-line parameters.
We need to keep track of how far we can jump. This will initially be the first value in @ints. In hindsight
I should have given this a clearer name I think.
my $maxJumps = @ints[0];
We also need to know how many steps we can take with this jump before we need another one. This will also
initially be the first value in @ints.
my $step = @ints[0];
How many jumps we have actually taken.
my $jumps = 1;
Now for each index of @inta except the first (because we are already using that one) and
the last (because that is the goal)...
for 1 ..^ @ints.end -> $i {
If the current index plus the jump length from this index is greater than the current $maxJumps we
update the value of $maxJumps.
if $i + @ints[$i] > $maxJumps {
$maxJumps = $i + @ints[$i];
}
We decrement the value of $step.
$step--;
If $step is still greater than 0, we make another round of the loop.
If it is 0, we need a another jump.
if $step == 0 {
$jumps++;
If the current index is greater than the current value of $maxJumps you can't move
forward so we admit defeat, set the number of jumps to -1 and stop processing.
if $i >= $maxJumps {
$jumps = -1;
last;
}
Otherwise we reset $steps for the new jump;
$step = $maxJumps - $i;
}
}
Finally we can print how many jumps it took to reach the goal or -1 if we couldn't make it.
say $jumps;
And this is the Perl version.
my $maxJumps = $ints[0];
my $step = $ints[0];
my $jumps = 1;
for my $i (1 .. scalar @ints - 2) {
if ($i + $ints[$i] > $maxJumps) {
$maxJumps = $i + $ints[$i];
}
$step--;
if ($step == 0) {
$jumps++;
if ($i >= $maxJumps) {
$jumps = -1;
last;
}
$step = $maxJumps - $i;
}
}
say $jumps;