Perl Weekly Challenge 91, Part 2

Challenge

You are given an array of positive numbers @N, where [the] 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.

It’s clear what is meant, as long as you don’t look at the examples. The second example has @N = (2,1,1,0,2) and it claims the result is 0, as $N [0] == 2 (so we jump to index 2), $N [2] == 1 (so we jump to index 3), and $N [3] == 0 — which means we don’t progress any further.

But what really should happen is that demons fly out of your nose. 0 is not a positive integer; this example doesn’t satisfy the precondition, so anything may happen.

Algorithm Overview

First, we read the input, and put it into an integer.

Then we take a pointer, and initialize it to 0. Then, as long as the pointer is less than @N - 1, that is, if it is still pointing to somewhere in the array, and that somewhere isn’t the last element of the array, we add whatever number the pointer is pointing add to the pointer. Note that this loop must terminate, as we keep adding positive integers to it.

And the end of the loop, the pointer either points to the last element of the array, or to past the end of the array. So, in the former case, we print 1, else we print 0.

Solution

Perl

while (<>) {
    my @N = /[0-9]+/g;
    die "Not all positive integers" if grep {/[^0-9]/ || !$_} @N;
    my $index = 0;
    while ($index < @N - 1) {
        $index += $N [$index];
    }
    say $index == $#N ? 1 : 0;
}

Note much to say about this — this is a straightforward translation of the overview described above. $#N is index of the last element of @N.

Find the complete program on GitHub.

Node.js

We start of by reading the all the input, which we then split on newlines. We then split each line on white space (which results into having an array) — and we make each element numeric by using unary +. Finally, we call the method hop with each array of numbers:

  require      ("fs")
. readFileSync (0)               // Read all.
. toString     ()                // Turn it into a string.
. split        ("\n")            // Split on newlines.
. filter       (_ => _ . length) // Filter out empty lines.
. map          (_ => _ . split (/\s+/)   // Split on whitespace.
                       . map (_ => +_))  // And numify the parts.
. map          (_ => hop (_))
;

The hop method works similar as the loop in the Perl solution: start at position 0, and as long as we’re not at the last element, or outside the array, add the current value. At the end of the loop, check whether we’re at the last element, or over:

function hop (array) {
    let i;
    for (i = 0; i < array . length - 1; i += array [i]) {}
    process . stdout . write (i == (array . length - 1) ? "1\n" : "0\n");
}

Find the complete program on GitHub.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s