| 15 November 2024 | Challenge 295 |
Jumping Words
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 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
Solution
Joining the (meta-quoted) words into a regex alternation leads basically to a two statement solution for this task:
use strict;
use warnings;
sub word_break {
my $str = shift;
my $words = join '|', map "\Q$_\E", @_;
$str =~ /^(?:$words)*$/;
}
See the full solution to task 1.
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
Solution
If $ints[0] >= $#ints, we may jump to the last element with a single jump.
Then, if $ints[0] == 0, we are stuck and there is no solution.
In all other cases we perform all the possible jumps in the range 1 .. $ints[0], replay the game from every new starting position, find the minimum required steps for each position and add one for the final solution.
Using \(\infty\) for no solution and map this to -1 afterwards.
use strict;
use warnings;
use List::Util 'min';
use Memoize;
memoize('jump_game');
sub jump_game {
return 1 if $_[0] >= $#_;
return 'inf' if $_[0] == 0;
1 + min map jump_game(@_[$_ .. $#_]), 1 .. $_[0];
}
See the full solution to task 2.
If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.