The Break Game

Weekly Challenge 295

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Word Break

Task

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.

My solution

With TWC, I tend to think about how I would solve it on my commute home on Monday. I thought of the example of a string of winwine and the words win and wine, and also the string of winewin. There doesn't seem to be a deterministic way of seeing what word I should match first.

A few days later, I had a genius idea that I was actually solving the wrong problem. A much easier solution was to use regular expressions to see if one or more words matched the string s.

And that's what I wrote. I use re.escape in Python, and quotemeta in Perl to escape any special meta-characters in the words list.

def word_break(s: str, words: list) -> bool:
    pattern = '^(' + '|'.join(map(re.escape, words)) + ')+$'

    return True if re.search(pattern, s) else False

Examples

$ ./ch-1.py weeklychallenge challenge weekly
true

$ ./ch-1.py perlrakuperl raku perl
true

$ ./ch-1.py sonsanddaughters sons sand daughters
false

Task 2: Jump Game

Task

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.

My solution

When completing these tasks, I also use TDD, something I don't do in my day job. If the test fails, usually there is either an obvious error or something a little more tricky. This task was one of later. Lots of debugging ensued.

I know both Python and Perl have excellent built in debugging tools, but I'm still a fan of use a copious amount of print statements.

For this task, I have a recursive function called jump_game. It takes two parameters: ints is the list of integers (starting with the complete list), and moves which starts at one.

If the first integer is 0, I return None (undef in Python) as no further move is possible. I then iterate - with a variable i -from the value of int[0] to 1. If this value is greater than or equal to one less than the length of list, we have a solution and I return moves. For other values, I call the function again removing the i first values, and incrementing moves by one.

I have a min_moves variable to ensure we return the minimum number of moves for all the iterations.

def jump_game(ints: list, moves=1) -> int:
    min_moves = None
    for i in range(ints[0], 0, -1):
        if i >= len(ints)-1:
            return moves

        if ints[i] == 0:
            continue

        m = jump_game(ints[i:], moves+1)
        if m is not None and (min_moves is None or min_moves > m):
            min_moves = m

    return min_moves

What was my bug, you ask? I was checking for i >= len(ints) instead of i >= len(ints)-1.

Examples

$ ./ch-2.py 2 3 1 1 4
2

$ ./ch-2.py 2 3 0 4
2

$ ./ch-2.py 2 0 0 4
-1