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