Solving Perl Weekly Challenge 091 -- Count numbers and Jump game.

TASK #1 › Count Number

Submitted by: Mohammad S Anwar

You are given a positive number $N.

Write a script to count number and display as you read it.

Example 1:

Input: $N = 1122234
Output: 21321314

as we read "two 1 three 2 one 3 one 4"

Example 2:

Input: $N = 2333445
Output: 12332415

as we read "one 2 three 3 two 4 one 5"

Example 3:

Input: $N = 12345
Output: 1112131415

as we read "one 1 one 2 one 3 one 4 one 5"

Solution #1 › Count Number

A naive solution that follows the gist of the question would be taking each digits of $N, count the print the number of occurences of that digit, followed by the digit itself. If the input looks like XXYYZZZ, the output shall be 2X1Y3Z. This is what's known as Run-length encoding.

Here is a solution using that naive solution in Raku.

sub MAIN (Int $N) {

    # [1]
    my @chars = $N.comb;

    my Str $out;
    my $i = 0;
    my $j = 0;

    # [2] invariant: @chars[$i..$j] eq (@chars[$i] x ($j - $i))
    while $j < @chars.elems {
        $j++ while $j < @chars.elems && @chars[$i] eq @chars[$j];

        $out ~= ($j - $i) ~ @chars[$i];

        $i = $j;
    }

    say $out;
}

At [1], .comb subroutine first converts the integer $N to string then take each characters from that string. The list of characters is storen in the @chars on the left-hand side.

At [2], there is a inner loop for that finds $j as large as possible without violating @chars[$i] eq @chars[$j]. In other word, inside the body block of the outher loop, all characters indexed by the number ranged $i..$j are the same. Hence the expression $j - $i is the number of occurnces of character @chars[$i].

The rest of code is just gradually building the output string $out.

TASK #2 › Jump Game

Submitted by: Mohammad S Anwar

You are given an array of positive numbers @N, where value at each index determines how far you are allowed to jump further.

Write a script to decide if you can jump to the last index. Print 1 if you are able to reach the last index otherwise 0.

Example 1:

Input: @N = (1, 2, 1, 2)
Output: 1

as we jump one place from index 0 and then twoe places from index 1 to reach the last index.

Example 2:

Input: @N = (2,1,1,0,2)
Output: 0

it is impossible to reach the last index. as we jump two places from index 0 to reach index 2, followed by one place jump from index 2 to reach the index 3. once you reached the index 3, you can't go any further because you can only jump 0 position further.

Solution #2 › Jump Game

A naive solution would be just trying all posibilties with BFS or DFS.

Another non-naive(?) solution based on dynamic programming would be to solve sub-problems of the tail part of @N, the gradually solve a bigger subproblem, eventually the whole problem. Here's that algorithm implemented in Raku.

sub play-jump-game (@N) {

    # [1]: $reachable[$i] = solution of the sub-problem: $i .. @N.end
    my Bool @reachable = @N.map({ False });
    @reachable[ @reachable.end ] = True;

    # [2]: Solve the lightly bigger sub-problem each time
    for @N.end-1 ... 0 -> $i {
        my $maxjump = @N[$i];

        # [3]: Take 1 jump, see if I land on a pad that's known to reachable to the end
        @reachable[$i] = any( @reachable[$i+1 .. min($i+$maxjump, @reachable.end)]).Bool;
    }

    say '@N = ' ~ @N.raku;
    say @reachable[0] ?? 1 !! 0;
}

At [1], we define a boolean array @reachable for the answer of subproblems and let @reachable[$i] be True if and only if there is a way to jump from position $i to the end. Based on such definition, the last element of @reachable must be True.

At [2], we start a loop processing all the way back from the second last position. If any one of those jumpable target are known to be reachable, that means te current position must also be able reachable. The line at [3] does the boolean check of a small range within @reachable.

After such loop, the answer is inside @reachable[0].

本文為《解 Perl Weekly Challenge 091 -- 數數字與跳格子》之英文版。