Perl Weekly Challenge: Week 334

Challenge 1:

Range Sum

You are given a list integers and pair of indices..

Write a script to return the sum of integers between the given indices (inclusive).

Example 1

Input: @ints = (-2, 0, 3, -5, 2, -1), $x = 0, $y = 2
Output: 1

Elements between indices (0, 2) => (-2, 0, 3)
Range Sum: (-2) + 0 + 3 => 1

Example 2

Input: @ints = (1, -2, 3, -4, 5), $x = 1, $y = 3
Output: -3

Elements between indices (1, 3) => (-2, 3, -4)
Range Sum: (-2) + 3 + (-4) => -3

Example 3

Input: @ints = (1, 0, 2, -1, 3), $x = 3, $y = 4
Output: 2

Elements between indices (3, 4) => (-1, 3)
Range Sum: (-1) + 3 => 2

Example 4

Input: @ints = (-5, 4, -3, 2, -1, 0), $x = 0, $y = 3
Output: -2

Elements between indices (0, 3) => (-5, 4, -3, 2)
Range Sum: (-5) + 4 + (-3) + 2 => -2

Example 5

Input: @ints = (-1, 0, 2, -3, -2, 1), $x = 0, $y = 2
Output: 1

Elements between indices (0, 2) => (-1, 0, 2)
Range Sum: (-1) + 0 + 2 => 1

This problem can be solved as a one-liner; here is the Raku version first. The code consists of two statements. The first is merely an alias so we don;t have to waste space writing @*ARGS several times. While we are at it, we also use ».Int to convert the command-line arguments (which are Strings) to numbers.

The input is taken from @*ARGS in the format @ints... $x $y So example 3 for instance would be 1 0 2 -1 3 3 4. The shell is a pain in the neck; you have to quote arguments like -1 or they are treated as switches. Instead of assigning to $x and $y we use the positional indices *-2 (second to last) and *-1 (last) directly to form a Range of elements in @a. This range is then .sum()ed and the result is printed with .say().

my @a = @*ARGS».Int; (@a[@a[*-2] .. @a[*-1]]).sum.say

(Full code on Github.)

The Perl version is also one line but a little bit longer because we don't have .sum() so we have to use a for-loop and accumulator, $s, instead.

my $s = 0, @a = @ARGV; for (@a[$a[-2] .. $a[-1]]) { $s+=$_ }; say $s

(Full code on Github.)

Challenge 2:

Nearest Valid Point

You are given current location as two integers: x and y. You are also given a list of points on the grid.

A point is considered valid if it shares either the same x-coordinate or the same y-coordinate as the current location.

Write a script to return the index of the valid point that has the smallest Manhattan distance to the current location. If multiple valid points are tied for the smallest distance, return the one with the lowest index. If no valid points exist, return -1.

The Manhattan distance between two points (x1, y1) and (x2, y2) is calculated as: |x1 - x2| + |y1 - y2|

Example 1

Input: $x = 3, $y = 4, @points ([1, 2], [3, 1], [2, 4], [2, 3])
Output: 2

Valid points: [3, 1] (same x), [2, 4] (same y)

Manhattan distances:
    [3, 1] => |3-3| + |4-1| = 3
    [2, 4] => |3-2| + |4-4| = 1

Closest valid point is [2, 4] at index 2.

Example 2

Input: $x = 2, $y = 5, @points ([3, 4], [2, 3], [1, 5], [2, 5])
Output: 3

Valid points: [2, 3], [1, 5], [2, 5]

Manhattan distances:
    [2, 3] => 2
    [1, 5] => 1
    [2, 5] => 0

Closest valid point is [2, 5] at index 3.

Example 3

Input: $x = 1, $y = 1, @points ([2, 2], [3, 3], [4, 4])
Output: -1

No point shares x or y with (1, 1).

Example 4

Input: $x = 0, $y = 0, @points ([0, 1], [1, 0], [0, 2], [2, 0])
Output: 0

Valid points: all of them

Manhattan distances:
    [0, 1] => 1
    [1, 0] => 1
    [0, 2] => 2
    [2, 0] => 2

Tie between index 0 and 1, pick the smaller index: 0

Example 5

Input: $x = 5, $y = 5, @points ([5, 6], [6, 5], [5, 4], [4, 5])
Output: 0

Valid points: all of them
    [5, 6] => 1
    [6, 5] => 1
    [5, 4] => 1
    [4, 5] => 1

All tie, return the one with the lowest index: 0

Within a few minutes, I had a really nice one line solution in Raku. The only problem is it was solving a different problem to the one actually being posed. People, you have to actually read the spec carefully before you start coding!

So the actual solution is a bit bigger but still quite traightforward I think. We take input from the command-line with $x and $y first followed by the points in the format x,y.

First we define two variables to hold the information we are going to need along the way; the smallest Manhattan distance seen so far and the (index of the) point with the smallest Manhattan distance. $smallestDistance is initialized to the largest possible value, namely infinity. $smallestPoint is initialized to -1 because without evidence to the contrary, we are going to assume a valid point has not been found.

my $smallestDistance = ∞;
my $smallestPoint = -1;

Now iterating through @points by index with .keys()...

for @points.keys -> $point {

We split each point that we got from the command-line into its x and y coordinates and convert them into integers.

    my ($x1, $y1) = @points[$point].split(',')».Int;

If either the x coordinate equals $x or the y coordinate equals $y, we have a valid point.

    if $x1 == $x || $y1 == $y {

We find the Manhattand distance between this poin and the one specified by $x,$y.

        my $distance = manhattanDistance($x, $y, $x1, $y1);

The Manhattan Distance is very simple to calculate. I could have done it inline but chose to make it into a separate function that looks like this, a straightforward translation of the formula given in the spec.

sub manhattanDistance($x, $y, $x1, $y1) {
    return ($x1 - $x).abs + ($y1 - $y).abs;
}

Back to MAIN(), if this Manhattan distance was smaller than the current smallest one, it becomes the new $smallestDistance. I originally had <= but this is wrong because the spec says if two points are equally distant, the earlier one is to be preferred. Also, the index of the current point becomes the new $smallestPoint.

        if $distance < $smallestDistance {
            $smallestDistance = $distance;
            $smallestPoint = $point;
        }
    }
}

Finally, we print the value of $smallestPoint.

say $smallestPoint;

(Full code on Github.)

This is the Perl version. It is pretty much the same as Raku.

sub manhattanDistance($x, $y, $x1, $y1) {
    return abs($x1 - $x) + abs($y1 - $y);
}

my ($x, $y, @points) = @ARGV;
my $smallestDistance = 'Inf';
my $smallestPoint = -1;

for my $point (keys @points) {
    my ($x1, $y1) = split /,/, $points[$point];

    if ($x1 == $x || $y1 == $y) {
        my $distance = manhattanDistance($x, $y, $x1, $y1);

        if ($distance < $smallestDistance) {
            $smallestDistance = $distance;
            $smallestPoint = $point;
        }
    }
}

say $smallestPoint;

(Full code on Github.)