RabbitFarm

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 is a good example of doing recursion in Prolog! Everything can be contained within a short recursive predicates.

At each recursive step we select a word form the list and see if it can be removed form the beginning of the final string. If we can whittle the final string down to the empty string then we know we have succeeded.

The rest of the code just wraps this predicate into a file.

Sample Run

$ gprolog --consult-file prolog/ch-1.p 
| ?- word_break(weeklychallenge, [challenge, weekly]). 
 
true ? 
 
yes 
| ?- word_break(perlrakuperl, [raku, perl]). 
 
true ? 
 
yes 
| ?- word_break(sonsanddaughter, [sons, sand, daughters]). 
 
no 
| ?-
    

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.

In some ways this has a very similar approach as part 1. That is, a recursive solution which explores all possible “jumps”.

When using the jump

Finally, let’s assemble our completed code into a single file.

Sample Run

$ gprolog prolog/ch-2.p 
| ?- findall(Moves, jump_game([2, 3, 1, 1, 4], 1, Moves), AllMoves), sort(AllMoves, AllMovesSorted), nth(1, AllMovesSorted, MinimumMoves). 
 
AllMoves = [4,3,2,3] 
AllMovesSorted = [2,3,4] 
MinimumMoves = 2 
 
yes 
| ?- findall(Moves, jump_game([2, 3, 0, 4], 1, Moves), AllMoves), sort(AllMoves, AllMovesSorted), nth(1, AllMovesSorted, MinimumMoves). 
 
AllMoves = [2] 
AllMovesSorted = [2] 
MinimumMoves = 2 
 
yes 
| ?- findall(Moves, jump_game([2, 0, 0, 4], 1, Moves), AllMoves), sort(AllMoves, AllMovesSorted), nth(1, AllMovesSorted, MinimumMoves). 
 
no 
| ?-
    

References

The Weekly Challenge 290
Generated Code

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.

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.

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.

Putting it all together...

The rest of the code just runs some simple tests.

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.

The rest of the code drives some tests.

Sample Run

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

References

The Weekly Challenge 295
Generated Code