DEV Community

Bob Lied
Bob Lied

Posted on

PWC 334 First We Do the Range Sum, Then We Take Manhattan

#perl #perlweeklychallenge #pwc

For your musical enjoyment, I recommend First We Take Manhattan (Leonard Cohen, 1988).

Task 1: Range Sum

Well, actually, first we do task 1, then we work on Manhattan.

You are given a list integers and pair of indices.
Write a script to return the sum of integers
between the given indices (inclusive).
Enter fullscreen mode Exit fullscreen mode
  • Example 1:
    • Input: @ints = (-2, 0, 3, -5, 2, -1), $x = 0, $y = 2
    • Output: 1
    • Elements between indices (0, 2) => (-2, 0, 3)
  • Example 2:
    • Input: @ints = (1, -2, 3, -4, 5), $x = 1, $y = 3
    • Output: -3
    • Elements between indices (1, 3) => (-2, 3, -4)

Knowing that array slices are a thing, and that Perl has a range operator (..), this is almost trivial. The sum comes from the List::Util module.

What happens if $x or $y is out of range? The array slice still yields values, but those values are undef. When we pass undef to sum0, we get a warning for every undef value. So untidy.

What happens if $x is greater than $y? The range operator in Perl doesn't do descending, for ... reasons. Although there's good logic why it's like that, it's one of the few places where Perl doesn't "do what I mean". Executive decision: swap the arguments to make it work.

sub rangeSum($x, $y, $ints)
{
    use List::Util qw/sum0/;
    if ( $x > $y ) { ($x,$y) = ($y, $x) }

    return sum0 map { $_ // 0 } $ints->@[$x .. $y];
}
Enter fullscreen mode Exit fullscreen mode

Notes:

  • Swapping can be done without a temporary variable.
  • $ints->@[$x..$y] is postfix syntax for an array slice, which I like. Traditional syntax would be @$ints[$x..$y].
  • $_ // 0 uses the // operator to yield 0 if $_ is undefined. This has been around quite a while now, but I still see a lot of defined($_)?$_:0. So untidy.
  • sum0, not sum because we want to handle the possibility of an empty list by returning 0.

Task 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|
Enter fullscreen mode Exit fullscreen mode

  • Example 1:

    • Input: $x = 3, $y = 4, @points ([1,2], [3,1], [2,4], [2,3])
    • Output: 2
    • Valid points: 3,1, 2,4
    • 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([2,5])

  • 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: 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, same distance. All tie, return the one with the lowest index: 0

Manhattan distance is the result of moving on a grid only left-to-right or up-and-down. It comes up a lot in Advent of Code problems, which reminds me that I still have problems 21 through 25 of last year to finish. The constraint that either the x or y coordinate must match means that only vertical and horizontal destination points are valid. Weird flex, but OK.

I'm going to tackle this problem in a literal way by examining each point in a loop.

sub nvp($x, $y, $point)
{
    my $minIndex;
    my $minDistance;
    for my ($i, $p)  (indexed reverse @$point)
    {
        next unless $p->[0] == $x || $p->[1] == $y;

        my $d = abs($x - $p->[0] + $y - $p->[1] );
        $minDistance //= $d;
        if ( $d <= $minDistance )
        {
            $minIndex = $i;
            $minDistance = $d;
        }
    }
    return $minIndex // -1;
}
Enter fullscreen mode Exit fullscreen mode

Notes:

  • The input parameter $point is a reference to an array of points, not the array itself. Passing a single reference is more efficient than passing an array, as it is in many languages.
  • my $minIndex is initially undefined. If it's still undefined at the end, it means we didn't find any valid points.
  • for my $(i,$p) (indexed ...) -- indexed conveniently gives us both the index and the value at the index.
  • The value at the index is a reference to a point, which is an [x,y] pair.
  • for ... (reverse @$point) -- We want the smallest index, so working backwards ends at smaller values.
  • next unless -- convenient syntax for asserting what must be true
  • $d = abs(...) -- In the calculation of the distance, the literal formula has two absolute values, but we only need to do it once, because either x-p[0] or y-p[1] must be zero.
  • $minDistance //= $d -- Initialize $minDistance the first time we see a valid point.
  • return $minIndex // -1 -- If we never saw a valid point, we want to return -1 instead of undef.

Top comments (0)