This is my response to The Weekly Challenge #295.
$str, and list of words, @words.
true or false whether the given string
can be segmented into a space separated sequnce of one or more words from
the given list.
Input: $str = 'weeklychallenge', @words = ("challenge", "weekly")
Output: true
Input: $str = "perlrakuperl", @words = ("raku", "perl")
Output: true
Input: $str = "sonsanddaughters", @words = ("sons", "sand", "daughters")
Output: false
I have chosen to permutate the words, instead of segmenting the string.
The first try does not exactly work, hence the name.
File: word-broken
#! /usr/bin/env raku
unit sub MAIN ($str where $str.chars > 0, # [1]
*@words where @words.elems > 1, # [2]
:v(:$verbose));
for @words.permutations -> @permutation # [3]
{
my $permutation = @permutation.join; # [4]
say ": Testing '$permutation'" if $verbose;
if $permutation eq $str # [5]
{
say 'true'; # [5a]
exit; # [5b]
}
}
say 'false'; # [6]
[1] A string, with at least 1 character.
[2] A slurpy array for the words, with at least two of them.
[3] Use permutations to permutate
the input array.
See docs.raku.org/routine/permutations for more information about permutations.
[4] Glue the permutation list togeter as a single string.
[5] Do we have a match for the input string? If so report success [5a] and exit [5b].
[6] No match. Report failure.
Running it, with verbose mode:
$ ./word-broken -v weeklychallenge challenge weekly
: Testing 'challengeweekly'
: Testing 'weeklychallenge'
true
$ ./word-broken -v perlrakuperl raku perl
: Testing 'rakuperl'
: Testing 'perlraku'
false
$./word-broken -v sonsanddaughters sons sand daughters
: Testing 'sonssanddaughters'
: Testing 'sonsdaughterssand'
: Testing 'sandsonsdaughters'
: Testing 'sanddaughterssons'
: Testing 'daughterssonssand'
: Testing 'daughterssandsons'
false
The second example gave the wrong result.
The problem is that we (as in you, not me) ignored the «one or more words from the given list» part. Using a regex (really a substring) instead of string equality does the trick:
File: word-break
#! /usr/bin/env raku
unit sub MAIN ($str where $str.chars > 0,
*@words where @words.elems > 1,
:v(:$verbose));
for @words.permutations -> @permutation
{
my $permutation = @permutation.join;
say ": Testing '$permutation'" if $verbose;
if $str ~~ /$permutation/
{
say 'true';
exit;
}
}
say 'false';
Running it:
$ ./word-break weeklychallenge challenge weekly
true
$ ./word-break perlrakuperl raku perl
true
$ ./word-break sonsanddaughters sons sand daughters
false
Looking good.
With verbose mode:
$ ./word-break -v weeklychallenge challenge weekly
: Testing 'challengeweekly'
: Testing 'weeklychallenge'
true
$ ./word-break -v perlrakuperl raku perl
: Testing 'rakuperl'
true
$ ./word-break -v sonsanddaughters sons sand daughters
: Testing 'sonssanddaughters'
: Testing 'sonsdaughterssand'
: Testing 'sandsonsdaughters'
: Testing 'sanddaughterssons'
: Testing 'daughterssonssand'
: Testing 'daughterssandsons'
false
@ints.
$ints[$i] represents the maximum length of a forward jump from the index
$i. In case last element is unreachable then return -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.
Input: @ints = (2, 3, 0, 4)
Output: 2
Input: @ints = (2, 0, 0, 4)
Output: -1
#! /usr/bin/env raku
unit sub MAIN (*@ints where @ints.elems > 1 && all(@ints) ~~ UInt, # [1a]
:v(:$verbose));
my $target = @ints.end; # [2]
my @queue = ( { at => 0, jumps => 0 }, ); # [3]
while @queue.elems # [4]
{
my $current = @queue.shift; # [5]
my $steps = @ints[$current<at>]; # [6]
for 1 .. $steps -> $step # [7]
{
say ": At: $current<at> Steps: $step (of 1..$steps) \
Jumps: $current<jumps> " if $verbose;
if $current<at> + $step == $target # [8]
{
say ": At: $target (the target) Jumps: { $current<jumps> +1 }"
if $verbose;
say $current<jumps> + 1; # [9]
exit; # [9a]
}
@queue.push( { at => $current<at> + $step,
jumps => $current<jumps> +1 } ); # [10]
}
}
say -1; # [11]
[1] Ensure at least two elements, all of which are unsigned integers (the
UInt type).
[2] The index of the last element in the array; the target.
[3] We are looking for the shortest path (or rather; one of many equally short paths), so breadth first traversal and a queue is the thing. Then we can print the first match we find. Put the initial position in the queue; the position ("at") is the array index. We need the number of jumps ("jumps") for the result, so we store that as well.
[4] As long as we have unfinished business.
[5] Get the first element from the queue.
[6] Get the maximum number of steps we can take, by looking it up in the array.
[7] Iterate over the possible number of steps.
[8] Will we reach the target?
[9] If so, print the number of steps (add 1, as we are still at the previous position) and exit [9a]. Note that it is impossible to go beyond the target (as a previous iteration in [7] would have landed us squarely on it), so we do not have to check for that.
[10] Add the new position to the stack.
[11] If we reach this point, the stack is empty and we have not reached the target. Report the failure.
Running it:
$ ./jump-game 2 3 1 1 4
2
$ ./jump-game 2 3 0 4
2
$ ./jump-game 2 0 0 4
-1
Looking good.
With verbose mode:
$ ./jump-game -v 2 3 1 1 4
: At: 0 Steps: 1 (of 1..2) Jumps: 0
: At: 0 Steps: 2 (of 1..2) Jumps: 0
: At: 1 Steps: 1 (of 1..3) Jumps: 1
: At: 1 Steps: 2 (of 1..3) Jumps: 1
: At: 1 Steps: 3 (of 1..3) Jumps: 1
: At: 4 (the target) Jumps: 2
2
$ ./jump-game -v 2 3 0 4
: At: 0 Steps: 1 (of 1..2) Jumps: 0
: At: 0 Steps: 2 (of 1..2) Jumps: 0
: At: 1 Steps: 1 (of 1..3) Jumps: 1
: At: 1 Steps: 2 (of 1..3) Jumps: 1
: At: 3 (the target) Jumps: 2
2
$ ./jump-game -v 2 0 0 4
: At: 0 Steps: 1 (of 1..2) Jumps: 0
: At: 0 Steps: 2 (of 1..2) Jumps: 0
-1
And that's it.