Solving Perl Weekly Challenge 091 -- Count numbers and Jump game.
Tags: raku
Published: 2020-12-18 08:08:53

---
tags: raku
title: Solving Perl Weekly Challenge 091 -- Count numbers and Jump game.
published: yes
---

## 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][wikipedia-rle-encoding].

Here is a solution using that naive solution in Raku.

```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`.

[wikipedia-rle-encoding]: https://en.wikipedia.org/wiki/Run-length_encoding

## 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 -- 數數字與跳格子][gugod-blog-pwc-091]》之英文版。


[gugod-blog-pwc-091]: https://gugod.org/2020/12/pwc-091/
[pwc-091]: https://perlweeklychallenge.org/blog/perl-weekly-challenge-091/