RabbitFarm

2024-11-24

Jump into a Word Game

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

Part 1: Word Break

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.

This can be brute forced rather easily: just try every concatenated combination from the list and see if we get a match. It is not too much work to add a bit more efficiency though. Our approach will be:

  1. Put the list of words into a hash keyed by the first letter.
  2. Start with the first letter of the string, find a match in the hash.
  3. Remove the word from the string and move onto the next letter.
  4. Repeat until, if possible, all parts of the string are found in the list.

Since there may be many words which start with the same letter we will use a recursive implementation which will make sure to check each of them.

Here’s how we construct the hash of words keyed by their first letter. Nothing especially clever, just an ordinary loop over the words.

⟨create hash 1 ⟩≡


my $h = {};
do{
my $c = substr $_, 0, 1;
push @{$h->{$c}}, $_;
} for @{$words};
◇

Fragment referenced in 3.

Defines: $h 2, 3.

The biggest chunk of word is here in this subroutine, where we recursively explore all possibilities of matching words. If at any point we find all components of the string we return true. In cases where the string cannot be composed of words from the list then the recursion just simply ends and, by default, returns undef.

⟨find breaks 2 ⟩≡


sub find_breaks{
my($s, $h) = @_;
return true if $s eq q//;
my $c = substr $s, 0, 1;
my $words = $h->{$c};
do{
$s = substr $s, length $_;
return find_breaks($s, $h);
} for @{$words};
}
◇

Fragment referenced in 4.

Uses: $h 1.

Here’s a subroutine which co-ordinates everything: invokes the hash construction and recursion. The boolean function is used to make sure something nicely printable is returned.

⟨word break: co-ordinates hash creation and the recursive search 3 ⟩≡


sub word_break{
my($s, $words) = @_;
⟨create hash 1 ⟩
return boolean(find_breaks $s, $h);
}
◇

Fragment referenced in 4.

Uses: $h 1.

Putting it all together...

"ch-1.pl" 4≡


⟨preamble 5 ⟩
⟨find breaks 2 ⟩
⟨word break: co-ordinates hash creation and the recursive search 3 ⟩
⟨main 6 ⟩
◇

⟨preamble 5 ⟩≡


use v5.40;
use boolean;
◇

Fragment referenced in 4, 9.

The rest of the code just runs some simple tests.

⟨main 6 ⟩≡


MAIN:{
say word_break q/weeklychallenge/, [q/challenge/, q/weekly/];
say word_break q/perlrakuperl/, [q/raku/, q/perl/];
say word_break q/sonsanddaughters/,[q/sons/, q/sand/, q/daughters/];
}
◇

Fragment referenced in 4.

Sample Run
$ perl perl/ch-1.pl 
1 
1 
0

Part 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.

We always start at the array index 0. From there we can recursively explore the possible paths that may be taken. Keep in mind that at each step $i we can only move as many as $ints[$i] positions.

In many ways this is similar to the first part of this week’s challenge!

If at any point we detect we have reached list’s end then we save the number of moves made. At the end we sort the list of moves and return the smallest number of moves. If this list is empty then we return -1.

⟨loop over our hand and remove 7 ⟩≡


sub jump{
my($l, $i, $counter, $moves) = @_;
my $m = $l->[$i];
if($i + $m >= @{$l} - 1){
push @{$moves}, $counter + 1;
}
else{
do{
jump($l, $i + $_, $counter + 1, $moves);
} for 1 .. $m;
}
}
◇

Fragment referenced in 9.

Defines: $i Never used, $l Never used.

Uses: $moves 8.

⟨jump game: co-ordinates the recursive search 8 ⟩≡


sub jump_game{
my $moves = [];
jump [@_], 0, 0, $moves;
return -1 if 0 == @{$moves};
return (sort {$a <=> $b} @{$moves})[0];
}
◇

Fragment referenced in 9.

Defines: $moves 7.

The rest of the code drives some tests.

"ch-2.pl" 9≡


⟨preamble 5 ⟩
⟨loop over our hand and remove 7 ⟩
⟨jump game: co-ordinates the recursive search 8 ⟩
⟨main 10 ⟩
◇

⟨main 10 ⟩≡


MAIN:{
say jump_game 2, 3, 1, 1, 4;
say jump_game 2, 3, 0, 4;
say jump_game 2, 0, 0, 4;
}
◇

Fragment referenced in 9.

Sample Run
$ perl perl/ch-2.pl 
2 
2 
-1

References

The Weekly Challenge 295
Generated Code

posted at: 19:22 by: Adam Russell | path: /perl | permanent link to this entry