Perl Weekly Challenge: I’ve got my back against the Turing machine…

Posted on by

In this post, I’m starting to go back and filling in the challenges I missed in 2024-2025 when my mother was hospitalized and dying. Perl Weekly Challenge 295‘s tasks were “Word Break” and “Jump Game”.

As I discovered when I actually made myself a spreadsheet of my music choices, I used Joni Mitchell’s Circle Game three separate times, so I decided to steer clear of that. I’ve played on “word” twice, so that left me with “break” and “jump”. I decided to pick Jump because it made me remember Junior year of high school…

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.

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

Approach

Probably because I just wrote PWC 374 using regular expressions, that’s the solution that popped into my head immediately. What I’ll do is use regular expressions to repeatedly remove strings from @words from $str until I’m left with either an empty string (which means the result is true) or a string which is not empty (the result is false).

Except… it just occurred to me that modifying the string like that could lead to false positives. What if I had the string "raperlrakuperlku"? If I remove perl twice and raku once, I’m left with "raku". But I still think I want to remove the strings, because I want to be able to determine if there’s left over characters that couldn’t have come from repeating one of the strings in @words. So what I’m going to do is replace the words in @words with spaces, so "raperlrakuperlku" would become "ra ku" and "sonsanddaughters" would become " and ", and then if the final string doesn’t match /\A\s*\z/, the result will be false.

Raku

Of course, in Raku I can’t use \A and \z, I have to use ^ and $.

sub wordBreak($str is copy, @words) {
  for @words -> $word {
    $str ~~ s:g/$word/ /;
  }
  $str ~~ /^\s*$/ ?? 'true' !! 'false';
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
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

Example 4:
Input: $str = 'raperlrakuperlku', @words = ("raku", "perl")
Output: false

Example 5:
Input: $str = 'thequickbrownfoxx', @words = ("the", "quick", "brown", "fox")
Output: false

Perl

sub wordBreak($str, @words) {
  for my $word (@words) {
    $str =~ s/$word/ /g;
  }
  $str =~ /\A\s*\z/ ? 'true' : 'false';
}

View the entire Perl script for this task on GitHub.

Python

Apparently in Python, I have to use ^ and $ as well. Also, because re.sub returns an unmodified subject string when the pattern isn’t matched, I needed to use re.subn, which returns a tuple of the result string and the number of substitutions made, which allows me to break out of my 

import re

def word_break(string, words):
  for word in words:
    string = re.sub(re.compile(word), " ", string)
  return 'true' if re.match(r'^\s*$', string) else 'false'

View the entire Python script for this task on GitHub.

Elixir

But Elixir let me use \A and \z!

def word_break(str, words) do
  str = Enum.map(words, &( Regex.compile!(&1)))
  |> Enum.reduce(str, fn pattern, str ->
    Regex.replace(pattern, str, " ")
  end)
  if Regex.match?(~r/\A\s*\z/, str), do: "true", else: "false"
end

View the entire Elixir script for this task on GitHub.

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

Jump 1 step from index 0, then 2 steps from index 1 to the last element.

Example 3

Input: @ints = (2, 0, 0, 4)
Output: -1

If you jump 2 steps or 1 step from index 0, both $ints[2] and $ints[1] are 0, so we can't take any more jumps.

Approach

Ok, this one had me confused for a long time. I finally realized the word “maximum” was the important thing to notice: when we start at element 0, 2 is not how far ahead we must jump, it is merely the maximum distance we may jump. So we can jump two spaces ahead, or one space ahead. Which means as long as we don’t hit any 0s, we will eventually get to the end of the array.

This winds up being a tree traversal problem: we have a tree of the number of steps we can take in each jump, and we need to traverse the tree to find the minimum number of jumps.

There are places we can bail out of the traversal: in the trivial case, where the array is one element long, it takes zero jumps to get to the end of the array—we’re already there. If at any point we encounter a value of 0 in the array element we’re looking at, we can bail on the branch of the tree we’re in, since we can’t go any further down it.

I’m also deciding to break up the recursion into its own function, might_as_well, so I can just call jump with the array of ints and let it handle the pre-recursion trivial case, and then kickstart the recursion with a jump count of one. The recursive function will grab the maximum number of steps we can take in a jump from the array, and then loop backwards from that maximum down to 1 and recursively explore each of the branches in the tree.

Raku

One thing I had to be aware of in each of the languages was how to loop backwards from a value down to 1. In Raku, there are two ways to do it: create a range 1 .. $max_steps and then reverse it, (1 .. $max_steps).reverse, or just use the infix … operator to generate a sequence of class Seq, $max_steps ... 1.

Note how, in line 6, if the number of steps our current position allows us to take would take us to the end of the array (or beyond), it doesn’t matter what value is in that element of the array. Even if it contains a 0, we’ll have arrived at the end of the array successfully, so we don’t need to check what the value is.

sub might_as_well($i, $jumps, @ints) {
  my $max_steps = @ints[$i];
  return $jumps if $i + $max_steps >= @ints.end;
  return -1     if $max_steps == 0; # dead end
  my @min_steps;
  for $max_steps ... 1 -> $j {
    my $steps = might_as_well($i + $j, $jumps+1, @ints);
    next if $steps == -1; # dead end
    @min_steps.push($steps);
  }
  @min_steps.elems ?? min(@min_steps) !! -1;
}

sub jump(@ints) {
  return 0 if @ints.elems == 1; # we're already at the end
  might_as_well(0, 1, @ints);
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: @ints = (2, 3, 1, 1, 4)
Output: 2

Example 2:
Input: @ints = (2, 3, 0, 4)
Output: 2

Example 3:
Input: @ints = (2, 0, 0, 4)
Output: -1

Example 4:
Input: @ints = (3, 0, 0, 4)
Output: 1

Example 5:
Input: @ints = (1, 2, 3, 4, 5)
Output: 3

Example 6:
Input: @ints = (0)
Output: 0

Perl

For Perl, to produce the backwards loop, we had to use the reverse function to reverse the range 1 .. $max_steps.

use List::AllUtils qw( min );

sub might_as_well($i, $jumps, @ints) {
  my $max_steps = $ints[$i];
  return $jumps if $i + $max_steps >= $#ints;
  return -1     if $max_steps == 0; # dead end
  my @min_steps;
  for my $j ( reverse 1 .. $max_steps ) {
    my $steps = might_as_well($i + $j, $jumps+1, @ints);
    next if $steps == -1; # dead end
    push @min_steps, $steps;
  }
  @min_steps ? min(@min_steps) : -1;
}

sub jump(@ints) {
  return 0 if @ints == 1; # we're already at the end
  might_as_well(0, 1, @ints);
}

View the entire Perl script for this task on GitHub.

Python

In Python, you use the builtin range() function with a step of -1 to produce the backwards loop. Note that range() does not produce the ending value, so instead of stopping at 1, we need to stop at 0.

def might_as_well(i, jumps, ints):
  max_steps = ints[i]
  if i + max_steps >= len(ints)-1: return jumps
  if max_steps == 0: return -1 # dead end
  min_steps = []
  for j in range(max_steps, 0, -1):
    steps = might_as_well(i + j, jumps+1, ints)
    if steps == -1: continue  # dead end
    min_steps.append(steps)
  return min(min_steps) if min_steps else -1

def jump(ints):
  if len(ints) == 1: return 0  # we're already at the end
  return might_as_well(0, 1, ints)

View the entire Python script for this task on GitHub.

Elixir

In Elixir, there’s no concept of returning from a function early, so what I’ve done is put Guards on function variations to just return from those functions with a value if certain conditions are met. For instance, if jump/1 is called with an array of length 1, we know that we don’t need to do any jumps to get to the end, so line 27 handles that. I modified might_as_well/3 to extract the max steps from ints and then call might_as_well/4 because that allowed me to place guards that handled being able to get to the end of the array (lines 4-5) and not having any steps to move forward (lines 7-8).

I could have put a cond do statement in might_as_well/3 to handle the conditions instead…

def might_as_well(i, jumps, ints) do
  max_steps = Enum.at(ints, i)
  cond do
    i + max_steps >= length(ints)-1 -> jumps
    
    max_steps == 0 -> -1 # dead end
    
    true ->
      min_steps = Enum.reduce(max_steps..1//-1, [],
        fn j, min_steps ->
          steps = might_as_well(i + j, jumps+1, ints)
          if steps == -1,
            do:   min_steps, # dead end
            else: min_steps ++ [steps]
        end)
      if length(min_steps) > 0, do: Enum.min(min_steps),
                              else: -1
  end
end

but I like the guards better. They feel more Elixir-like.

def might_as_well(i, max_steps, jumps, ints)
  when i + max_steps >= length(ints)-1, do: jumps

def might_as_well(_, max_steps, _, _)
  when max_steps == 0, do: -1 # dead end

def might_as_well(i, max_steps, jumps, ints) do
  min_steps = Enum.reduce(max_steps..1//-1, [],
    fn j, min_steps ->
      steps = might_as_well(i + j, jumps+1, ints)
      if steps == -1,
        do:   min_steps, # dead end
        else: min_steps ++ [steps]
    end)
  if length(min_steps) > 0, do: Enum.min(min_steps), else: -1
end

def might_as_well(i, jumps, ints) do
  max_steps = Enum.at(ints, i)
  might_as_well(i, max_steps, jumps, ints)
end

# we're already at the end
def jump(ints) when length(ints) == 1, do: 0

def jump(ints) do
  might_as_well(0, 1, ints)
end

View the entire Elixir script for this task on GitHub.

Here’s all my solutions in GitHub: https://github.com/packy/perlweeklychallenge-club/tree/challenge-295-packy-anderson/challenge-295/packy-anderson

Leave a Reply