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 -- 數數字與跳格子》之英文版。
Top comments (0)