Jump, but Don't Break the Game (PWC 295)

These are my solutions in Perl
for Challenge 295 Tasks 1 and 2 of The Weekly Challenge - Perl and Raku.

Summary

Task 1: Word Break.
A simple regular expression, built from the word list, delivers the solution. Very short, very nice.

Task 2: Jump Game
Implementing an unspectacular 'breadth first search' (BFS) algorithm.

Task 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 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

We need to recognize words from the input word list in the string, making sure that after each recognized word, another word from the list begins.

That means we are checking whether the string is a sequence of one or more words from the list.
Wait a second...! Checking 'one or more' occurrences of something in a string?
What could be easier than using a regular expression for that?
The 'one or more' part directly translates to a + quantifier.

And the pattern? We form it as a list of alternatives, using the '|' character do separate the choices.

Then, we only have to match the string against our pattern:

use v5.36;

sub word_break( $str, $words ) {
    my $pattern = join "|", $words->@*;
    return $str =~ /^($pattern)+$/;
}

That was an easy one.

Task 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

Now this one requires some 'real programming'(tm).

First, let's get clear about the game mechanics. The description says:

$ints[$i] represents the maximum length of a forward jump from the index $i.

If we take $ints[$i] == 3 as an example, that means that we can choose to jump to $i+1, $i+2 or $i+3 in that move.
For each of those, the next move continues with the number that we find there.

Trying all possible combinations from the first entry in the list is like building a tree of possible paths. The root node is $int[0]. From there, there is one outgoing branch for every possible jump from there.

To find the 'shortest path' to the last entry, we need to find the shortest path in that tree that leads to a node with the index value of the last entry.

Finding the shortest path in a tree is typically done using a 'breadth first search' (or 'BFS') algorithm. All of the nodes on the same level ('breadth') are checked before any nodes on higher levels. So if one fulfils the end condition (here: it's the index of the last entry in the list), it's garanteed that there are no shorter paths.

A BFS algorithm is not difficult to set up:
We use a queue for the nodes to check.
For the queue entries, we use two-element anonymous arrays, containing the index value, and the length of the path that was needed to reach that node. That makes it easy to return the correct result once we find the shortest path.

We initialize our queue with the index of the first number in the list (which is 0, of course), and the number of jumps needed to get there (0, too!).
This represents the starting point of our tree.

Then we loop over the entries in the queue.
For each entry, we check whether it meets the end condition, and return the path length if it does. Done.

If we haven't reached the last entry yet, we add the next level of possible moves to the queue, making sure we don't add jumps that end beyond the end of the list.
The path length for these new queue entries is one higher than the one that we have so far.

If the queue runs empty, there is no possible path that reaches the last entry. We return the -1 as we should in that case.

use v5.36;

sub jump_game( @ints ) {
    my ( $index, $n_jumps ) = ( 0, 0 );
    my @queue = ( [ $index, $n_jumps ] );
    while ( @queue ) {
        my ( $index, $n_jumps ) = ( shift @queue )->@*;
        return $n_jumps
            if $index == $#ints;
        push @queue,
            map [ $_, $n_jumps + 1 ],
                grep $index <= $#ints,
                    reverse $index + 1 .. $index + $ints[$index];
    }
    return -1;
}

This BFS does not need a 'visited' structure to avoid running into circles. As we only move forward in the list, we don't need to fear running into that problem at all.

I have also created a solution using the Algorithm::Functional::BFS module from CPAN. It hides all the mechanics of the BFS algorithm and uses a functional approach: there are code blocks handed in to the search function, for checking whether a node meets the the end criteria, and for getting the list of successor nodes for a node. These are the only two variable parts of the algorithm.

In fact I found that the code is not significantly shorter when I use that module, because we need to supply the code blocks as parameters, and also set some parameters. So I am quite ok with having written it myself.

Thank you for the challenge!

Find the complete source code for both tasks, including tests and alternative solution implementations, on Github.