RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved tree searches. (Note that this ends today.)

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 sequence of one or more words from the given list.

I used my standard breadth-first search pattern: given a queue entry consisting initially of the given string, try each candidate word against it, and if it's a match put the remainder of the string into the queue.

Raku:

sub wordbreak($a, @words) {

Initialise the queue.

    my @queue = [$a];

Pull off the first entry.

    while @queue.elems > 0 {
        my $remnant = @queue.shift;

If it's empty, we have a full match.

        if $remnant.chars == 0 {
            return True;
        }

Otherwise, try each word and queue the remainder if it's a match. (Does Raku have an easy way if saying "if the result of this function is not zero, counting nil as not zero"? This is more involved than I feel it should be.)

        for @words -> $candidate {
            with $remnant.index($candidate) -> $ix {
                if $ix == 0 {
                    @queue.push(substr($remnant, $candidate.chars));
                }
            }
        }
    }

If the queue has become empty, the loop ends, indicating that there's no match.

    False;
}

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.

After part 1 was thinking in terms of another BFS, and I wrote that version first, but this doesn't need the full scaffolding that goes along with that.

In each scanning pass, here is the set of locations I've reached in the previous move (starting with the first entry in the list), and there is populated as the set of locations I could reach from all of those. So in example 2, I start with

[2, 3, 0, 4]

with only index 0 (value 2) in the here set. From there I flag up indices 0 + 1 = 1 to 0 + 2 = 2 as reachable after one move.

On the next pass there becomes here and the move count is now 2. Index 1 flags 1 + 0 = 1 to 1 + 3 = 4; index 2 with a value of 0 flags nothing. Index 3, the goal, is now flagged, so we return the move count.

To spot the degenerate case with no solutions, if there is unpopulated at the end of a pass we haven't reached any new locations and so abandon the attempt.

Crystal:

def jumpgame(a)

Store the goal value.

  target = a.size - 1

Initialise move counter and here set.

  moves = 0
  here = Set(Int32).new
  here.add(0)

Loop infinitely.

  while true

Increment the move counter and initialise a new empty output set.

    moves += 1
    there = Set(Int32).new

For each position here, for each point it can reach, set the value in there.

    here.each do |n|
      (n+1).upto([n + a[n], target].min).each do |i|
        there.add(i)
      end
    end

No new points? Goal is unreachable.

    if there.size == 0
      return -1
    end

Reached the goal? Return the move count.

    if there.includes?(target)
      return moves
    end

Otherwise set up the next here and continue.

    here = there
  end
end

Full code on github.