The weekly challenge 334 - Task 2: Nearest Valid Point

  1 #!/usr/bin/env perl
  2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-334/#TASK2
  3 #
  4 # Task 2: Nearest Valid Point
  5 # ===========================
  6 #
  7 # You are given current location as two integers: x and y. You are also given a
  8 # list of points on the grid.
  9 #
 10 # A point is considered valid if it shares either the same x-coordinate or the
 11 # same y-coordinate as the current location.
 12 #
 13 # Write a script to return the index of the valid point that has the smallest
 14 # Manhattan distance to the current location. If multiple valid points are tied
 15 # for the smallest distance, return the one with the lowest index. If no valid
 16 # points exist, return -1.
 17 #
 18 ####  The Manhattan distance between two points (x1, y1) and (x2, y2) is
 19 ####  calculated as: |x1 - x2| + |y1 - y2|
 20 #
 21 #
 22 ## Example 1
 23 ##
 24 ## Input: $x = 3, $y = 4, @points ([1, 2], [3, 1], [2, 4], [2, 3])
 25 ## Output: 2
 26 ##
 27 ## Valid points: [3, 1] (same x), [2, 4] (same y)
 28 ##
 29 ## Manhattan distances:
 30 ##     [3, 1] => |3-3| + |4-1| = 3
 31 ##     [2, 4] => |3-2| + |4-4| = 1
 32 ##
 33 ## Closest valid point is [2, 4] at index 2.
 34 #
 35 #
 36 ## Example 2
 37 ##
 38 ## Input: $x = 2, $y = 5, @points ([3, 4], [2, 3], [1, 5], [2, 5])
 39 ## Output: 3
 40 ##
 41 ## Valid points: [2, 3], [1, 5], [2, 5]
 42 ##
 43 ## Manhattan distances:
 44 ##     [2, 3] => 2
 45 ##     [1, 5] => 1
 46 ##     [2, 5] => 0
 47 ##
 48 ## Closest valid point is [2, 5] at index 3.
 49 #
 50 #
 51 ## Example 3
 52 ##
 53 ## Input: $x = 1, $y = 1, @points ([2, 2], [3, 3], [4, 4])
 54 ## Output: -1
 55 ##
 56 ## No point shares x or y with (1, 1).
 57 #
 58 #
 59 ## Example 4
 60 ##
 61 ## Input: $x = 0, $y = 0, @points ([0, 1], [1, 0], [0, 2], [2, 0])
 62 ## Output: 0
 63 ##
 64 ## Valid points: all of them
 65 ##
 66 ## Manhattan distances:
 67 ##     [0, 1] => 1
 68 ##     [1, 0] => 1
 69 ##     [0, 2] => 2
 70 ##     [2, 0] => 2
 71 ##
 72 ## Tie between index 0 and 1, pick the smaller index: 0
 73 #
 74 #
 75 ## Example 5
 76 ##
 77 ## Input: $x = 5, $y = 5, @points ([5, 6], [6, 5], [5, 4], [4, 5])
 78 ## Output: 0
 79 ##
 80 ## Valid points: all of them
 81 ##     [5, 6] => 1
 82 ##     [6, 5] => 1
 83 ##     [5, 4] => 1
 84 ##     [4, 5] => 1
 85 ##
 86 ## All tie, return the one with the lowest index: 0
 87 #
 88 ############################################################
 89 ##
 90 ## discussion
 91 ##
 92 ############################################################
 93 #
 94 # We just walk the array of points from the first element to the
 95 # last, calculating the Manhattan distance for all valid points.
 96 # If we have a new lowest distance, we keep track of both the
 97 # distance and the index. By initializing both values to -1, we
 98 # have a perfect way to make sure we can keep track of whether we
 99 # found any valid points so far and return -1 if we don't find any.
100 
101 use v5.36;
102 
103 nearest_valid_point( 3, 4, ([1, 2], [3, 1], [2, 4], [2, 3]) );
104 nearest_valid_point( 2, 5, ([3, 4], [2, 3], [1, 5], [2, 5]) );
105 nearest_valid_point( 1, 1, ([2, 2], [3, 3], [4, 4]) );
106 nearest_valid_point( 0, 0, ([0, 1], [1, 0], [0, 2], [2, 0]) );
107 nearest_valid_point( 5, 5, ([5, 6], [6, 5], [5, 4], [4, 5]) );
108 
109 sub nearest_valid_point( $x, $y, @points ) {
110     say "Input: $x, $y, (" . join(", ", map { "[$_->[0], $_->[1]]" } @points) . ")";
111     my $index = -1;
112     my $dist = -1;
113     foreach my $i (0..$#points) {
114         my $tmp_dist;
115         if($x == $points[$i]->[0]) {
116             my $d = abs($y - $points[$i]->[1]);
117             if($dist == -1 || $dist > $d) {
118                 $dist = $d;
119                 $index = $i;
120             }
121         } elsif ($y == $points[$i]->[1]) {
122             my $d = abs($x - $points[$i]->[0]);
123             if($dist == -1 || $dist > $d) {
124                 $dist = $d;
125                 $index = $i;
126             }
127         } else {
128             # neither $x nor $y match the point we're looking at, skip it
129         }
130     }
131     say "Output: $index";
132 }
133