Task — Nearest valid point

You are given a 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|.

Examples

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

Analysis

Many US cities are built on a square grid pattern, so the definition of Manhattan Distance is the walking (or driving) distance between two intersections. I believe that older cities have typically 8 blocks per mile in each direction, and newer ones have 6 - although there are doubtless many exceptions.

However, square blocks don't work well for fitting in buildings - you end up with a hole in the middle - so often the blocks are divided into smaller sub-blocks in one direction or the other - see Chicago for example.

Manhattan is somwhat unusual in that the north-south city block length is generally much greater than the east-west length, and the north-south block sizes also vary somewhat. Also, the avenues - the north-south streets - are angled about 30 degrees east of north, to match the orientation of Manhattan Island, with the east-west streets similarly tilted.

So 'Manhattan distance' is not a very accurate measure of distance in Manhattan if x and y are measured in blocks!

That said, the challenge as stated is not hard: it's only necessary to check each point's Manhattan distance (mhd) from the origin point and find the first one with the shortest mhd.

Try it 

Try running the script with any input:

Your $x, $y =

example: 3, 4

Your @points =

example: [1, 2], [3, 1], [2, 4], [2, 3]

⤡

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2025-08-11
use utf8;     # Week 334 - task 2 - Nearest valid point
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

nearest_valid_point(3, 4, [[1, 2], [3, 1], [2, 4], [2, 3]]);
nearest_valid_point(2, 5, [[3, 4], [2, 3], [1, 5], [2, 5]]);
nearest_valid_point(1, 1, [[2, 2], [3, 3], [4, 4]]);
nearest_valid_point(0, 0, [[0, 1], [1, 0], [0, 2], [2, 0]]);
nearest_valid_point(5, 5, [[5, 6], [6, 5], [5, 4], [4, 5]]);

sub nearest_valid_point {
    
    my ($x, $y, $px, $py, $point, $points, $best, $mhd, $winner, $point_list, $index);
    
    # initialise
    ($x, $y, $points) = @_;
    $best = 1e10;
    
    # loop over points
    for $index (0 .. scalar(@$points) - 1) {
        ($px, $py) = @{$points->[$index]};
        $point_list .= qq{[$px, $py], }; 
        
        # check validity
        if    ($px == $x) { $mhd = abs($py - $y) }
        elsif ($py == $y) { $mhd = abs($px - $x) }
        else              { next }  
        
        # is this the winner?
        if ($mhd < $best) {
            $best = $mhd;
            $winner = qq{index = $index, coords = [$px, $py], distance = $mhd};
        }
    }
    
    say qq[\nInput:  \$x = $x, \$y = $y, \@points = ] . substr($point_list, 0, -2);
    say qq[Output: ] . (defined($winner) ? $winner : '-1');
}

Output

Input:  $x = 3, $y = 4, @points = [1, 2], [3, 1], [2, 4],
   [2, 3]
Output: index = 2, coords = [2, 4], distance = 1

Input:  $x = 2, $y = 5, @points = [3, 4], [2, 3], [1, 5],
   [2, 5]
Output: index = 3, coords = [2, 5], distance = 0

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

Input:  $x = 0, $y = 0, @points = [0, 1], [1, 0], [0, 2],
   [2, 0]
Output: index = 0, coords = [0, 1], distance = 1

Input:  $x = 5, $y = 5, @points = [5, 6], [6, 5], [5, 4],
   [4, 5]
Output: index = 0, coords = [5, 6], distance = 1