Perl Weekly Challenge: SUMone tell me what makes a point VALID?

Posted on by

No music this week, I’m just jumping into the tasks, “Range Sum” and “Nearest Valid Point”. So let’s dive into Perl Weekly Challenge 334.

Task 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

Approach

In many languages, we can get the elements we want by doing an array slice.

Raku

sub rangeSum(@ints, $x, $y) {
  return @ints[$x..$y].sum;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
Example 1:
Input: @ints = (-2, 0, 3, -5, 2, -1), $x = 0, $y = 2
Output: 1

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

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

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

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

Perl

In Perl, I put the list last because the language wants the “slurpy” parameter to be last in the list.

use List::AllUtils qw( sum );

sub rangeSum($x, $y, @ints) {
  return sum @ints[$x..$y];
}

View the entire Perl script for this task on GitHub.

Python

In Python, the element at the end of the range in an array slice is not included in the slice, so we need to go one element beyond…

def range_sum(ints, x, y):
  return sum(ints[x:y+1])

View the entire Python script for this task on GitHub.

Elixir

In Elixir, we use Enum.slice/2 and Enum.sum/1.

  def range_sum(ints, x, y) do
    Enum.slice(ints, x..y) |> Enum.sum
  end

View the entire Elixir script for this task on GitHub.

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: | x 1 − x 2 | + | y 1 − y 2 |

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

Approach

One thing that’s good to note: don’t just jump into an implementation without completely understanding the requirements. When I first read the problem, I thought “Oh, I can grep through @points to yield a @valid array…” but then I realized that the output is the index in the original array of the point with the smallest distance, so I needed to maintain the original indices. Fortunately, we can use a hash to indicate whether the point at a particular index is “valid”, and later when we want to test to see if that index is in the hash, there’s an easy function to quickly do that, rather than having to search the hash for each index.

So, we loop through the list of points, and if a point is “valid”, we put that index into a hash of valid indices as the hash key. Then we check to see if any of the points were valid; if none were, we can bail early.

Then we loop through the list of points again, skipping the “invalid” ones, and calculate the Manhattan Distance for each point from our given x, y point. We then use that distance as the key in a new distance hash, and the value for the key is a list of indices that produced that distance. The advantage of this is we’re able to list out the keys and take the minimum value (this is the minimum distance), and since we’re looping through the indices in order, the first element of the array at that distance is the result we’re looking for.

Raku

These solutions are longer than they absolutely need to be because I’m producing the explanatory text used in the examples. I also created functions manhattanDistance and formatPoint to abstract away some of the visual confusion of dealing with arrays; we’re able to see that abs(@a[0] - @b[0]) + abs(@a[1] - @b[1]) produces the distance between the two points a and b, but then when it’s actually getting used, we just see the call to manhattanDistance (though I wind up calling formatPoint way more often).

sub manhattanDistance(@a, @b) {
  return (
    abs(@a[0] - @b[0]) + abs(@a[1] - @b[1]),
    "|@a[0] - @b[0]| + |@a[1] - @b[1]|"
  );
}

sub formatPoint(@p) {
  return "[@p[0], @p[1]]";
}

sub NVP($x, $y, @points) {
  my $explanation;

  # find the "valid" points
  my %valid;
  for 0 .. @points.end -> $i {
    next unless @points[$i][0] == $x || @points[$i][1] == $y;
    %valid{$i} = 1;
  }
  unless (%valid) {
    return (-1, "No point shares x or y with ($x, $y).");
  }
  if (%valid.elems == @points.elems) {
    $explanation = 'Valid points: all of them';
  }
  else {
    $explanation = 'Valid points: ' ~ @points[%valid.keys]
            .map({ formatPoint($_) }).join(", ");
  }

  # now find the distances from the valid points to (x,y)
  $explanation ~= "\n\nManhattan distances:\n";
  my %dist;
  for 0 .. @points.end -> $i {
    next unless %valid{$i}:exists;
    my ($d, $e) = manhattanDistance([$x, $y], @points[$i]); 
    $explanation ~= "    " ~ formatPoint(@points[$i])
                 ~  " => $e => $d\n";
    %dist{ $d }.push($i); # add the index to a list for this dist
  }

  # the minimum key in the %dist hash is the minimum distance
  my $min = min(%dist.keys);

  # pick the lowest index from the min distance array
  my $i = %dist{$min}[0];

  if (%dist{$min}.elems == 1) { # only one min distance
    $explanation ~= "\nClosest valid point is "
                 ~  formatPoint(@points[$i]) ~ " at index $i.";
  }
  elsif (%dist{$min}.elems < %valid.elems) {
    $explanation ~= "\nTie between index "
                 ~  %dist{$min}.join(" and ")
                 ~ ", pick the smaller index: $i.";
  }
  else {
    $explanation ~= "\nAll tie, return the one with "
                 ~  "the lowest index: $i.";
  }

  return ($i, $explanation);
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: $x = 3, $y = 4, @points ([1, 2], [3, 1], [2, 4], [2, 3])
Output: 2

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

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: [1, 5], [2, 5], [2, 3]

Manhattan distances:
    [2, 3] => |2 - 2| + |5 - 3| => 2
    [1, 5] => |2 - 1| + |5 - 5| => 1
    [2, 5] => |2 - 2| + |5 - 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] => |0 - 0| + |0 - 1| => 1
    [1, 0] => |0 - 1| + |0 - 0| => 1
    [0, 2] => |0 - 0| + |0 - 2| => 2
    [2, 0] => |0 - 2| + |0 - 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

Manhattan distances:
    [5, 6] => |5 - 5| + |5 - 6| => 1
    [6, 5] => |5 - 6| + |5 - 5| => 1
    [5, 4] => |5 - 5| + |5 - 4| => 1
    [4, 5] => |5 - 4| + |5 - 5| => 1

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

Perl

This solution is very much like the Raku solution. For some reason, I decided to used the $$var method of dereferencing a value instead of $var->, possibly because I feel it looks cleaner when it’s being interpolated in a string. But $$var[0] is the same as $var->[0].

use List::AllUtils qw( min );

sub manhattanDistance($a, $b) {
  return (
    abs($$a[0] - $$b[0]) + abs($$a[1] - $$b[1]),
    "|$$a[0] - $$b[0]| + |$$a[1] - $$b[1]|"
  );
}

sub formatPoint($p) {
  return "[$$p[0], $$p[1]]";
}

sub NVP($x, $y, @points) {
  my $explanation;

  # find the "valid" points
  my %valid;
  for my $i (0 .. $#points) {
    next unless $points[$i][0] == $x || $points[$i][1] == $y;
    $valid{$i} = 1;
  }
  unless (%valid) {
    return (-1, "No point shares x or y with ($x, $y).");
  }
  if (scalar(%valid) == scalar(@points)) {
    $explanation = 'Valid points: all of them';
  }
  else {
    $explanation = 'Valid points: ' . join(", ",
      map { formatPoint($_) } @points[keys %valid]
    );
  }

  # now find the distances from the valid points to (x,y)
  $explanation .= "\n\nManhattan distances:\n";
  my %dist;
  for my $i (0 .. $#points) {
    next unless exists $valid{$i};
    my ($d, $e) = manhattanDistance([$x, $y], $points[$i]); 
    $explanation .= "    " . formatPoint($points[$i])
                 .  " => $e => $d\n";
    # add the index to a list for this dist
    push @{ $dist{ $d } }, $i;
  }

  # the minimum key in the %dist hash is the minimum distance
  my $min = min(keys %dist);

  # pick the lowest index from the min distance array
  my $i = @{$dist{$min}}[0];

  if (@{$dist{$min}} == 1) { # only one min distance
    $explanation .= "\nClosest valid point is "
                 .  formatPoint($points[$i]) . " at index $i.";
  }
  elsif (@{$dist{$min}} < scalar(keys %valid)) {
    $explanation .= "\nTie between index "
                 .  join(" and ", @{$dist{$min}})
                 . ", pick the smaller index: $i.";
  }
  else {
    $explanation .= "\nAll tie, return the one with "
                 .  "the lowest index: $i.";
  }

  return ($i, $explanation);
}

View the entire Perl script for this task on GitHub.

Python

Not much to say about the Python version. It’s using a Counter in place of a dict so we get the ability to get a 0 value for elements not in the set; and I’ve never used dict.setdefault() before. It’s necessary because, unlike Raku and Perl, you can’t just autovivify a list in an array element just by pushing something onto it.

from collections import Counter

def manhattan_distance(a, b):
  return (
    abs(a[0] - b[0]) + abs(a[1] - b[1]),
    f'|{a[0]} - {b[0]}| + |{a[1]} - {b[1]}|'
  )

def format_point(p):
  return f'[{p[0]}, {p[1]}]'

def nvp(x, y, points):
  explanation = ''

  # find the "valid" points
  valid = Counter()
  for i in range(len(points)):
    if points[i][0] == x or points[i][1] == y:
      valid[i] = 1
  if len(valid) == 0:
    return (-1, f'No point shares x or y with ({x}, {y}).')

  if (len(valid) == len(points)):
    explanation = 'Valid points: all of them'
  else:
    vpoints = [ format_point(points[i]) for i in valid.keys() ]
    explanation = 'Valid points: ' + ', '.join(vpoints)

  # now find the distances from the valid points to (x,y)
  explanation += '\n\nManhattan distances:\n'
  dist = {}
  for i in range(len(points)):
    if valid[i]:
      d, e = manhattan_distance([x, y], points[i]) 
      explanation += (
        "    " + format_point(points[i]) + f' => {e} => {d}\n'
      )
      # add the index to a list for this distance
      # get the existing list in d, default to empty list
      l = dist.setdefault(d, [])
      l.append(i)

  # the minimum key in the dist dict is the minimum distance
  min_val = min(dist.keys())

  # pick the lowest index from the min distance array
  i = dist[min_val][0]

  if len(dist[min_val]) == 1:  # only one min distance
    explanation += (
      '\nClosest valid point is ' + format_point(points[i]) +
      f' at index {i}.'
    )
  elif len(dist[min_val]) < len(valid):
    tie_list = [ str(n) for n in dist[min_val] ]
    explanation += (
      '\nTie between index ' + ' and '.join(tie_list) +
      f', pick the smaller index: {i}.'
    )
  else:
    explanation += (
      f'\nAll tie, return the one with the lowest index: {i}.'
    )

  return (i, explanation)

View the entire Python script for this task on GitHub.

Elixir

In Elixir, I split the nvp function into two parts, an initial nvp/3 that can bail early if there are no valid points, and an nvp/4 form that will compute the distance and generate the explanations.

One of the things that kept tripping me was the index range needing to end at length(points)-1, so I made a one-line helper function to abstract that away and I only needed to remember it once.

def manhattan_distance(a, b) do
  {
    abs(Enum.at(a,0) - Enum.at(b,0)) +
    abs(Enum.at(a,1) - Enum.at(b,1)),
    "|#{Enum.at(a,0)} - #{Enum.at(b,0)}| + " <>
    "|#{Enum.at(a,1)} - #{Enum.at(b,1)}|"
  }
end

def format_point(p) do
  "[#{Enum.at(p, 0)}, #{Enum.at(p, 1)}]"
end

def is_valid(x, y, p) do
  Enum.at(p,0) == x or Enum.at(p,1) == y
end

def range(points), do: 0..length(points)-1

def nvp(x, y, points, valid) do
  explanation = cond do
    map_size(valid) == length(points) ->
      "Valid points: all of them"
    true ->
      vpoints = Map.keys(valid)
             |> Enum.map(fn i -> Enum.at(points, i) end)
             |> Enum.map(fn p -> format_point(p) end)
      "Valid points: " <> Enum.join(vpoints, ", ")
  end

  # now find the distances from the valid points to (x,y)
  explanation = explanation <> "\n\nManhattan distances:\n"
  {_, {dist, explanation}} = Enum.map_reduce(
    range(points), {%{}, explanation},
    fn i, {dist, explanation} ->
      {dist, explanation} = if Map.get(valid, i) do
        {d, e} = manhattan_distance([x, y], Enum.at(points,i))
        explanation = explanation <> "    " <>
                      format_point(Enum.at(points,i)) <>
                      " => #{e} => #{d}\n"
        # add the index to a list for this distance
        # get the existing list in d, default to empty list
        dist = Map.put(dist, d, Map.get(dist, d, []) ++ [i])
        {dist, explanation}
      else
        {dist, explanation}
      end
      {i, {dist, explanation}}
    end
  )

  # the minimum key in the dist map is the minimum distance
  min_val = Enum.min(Map.keys(dist))

  # label the minimum value list so its easier to use
  min_list = Map.get(dist, min_val)

  # pick the lowest index from the min distance array
  i = Enum.at(min_list, 0)

  explanation = explanation <> "\n" <> cond do
    length(min_list) == 1 ->
      point = format_point(Enum.at(points,i))
      "Closest valid point is #{point} at index #{i}."
    length(min_list) < map_size(valid) ->
      tie_list = Enum.join(min_list, " and ")
      "Tie between index #{tie_list}, " <>
      "pick the smaller index: #{i}."
    true ->
      "All tie, return the one with the lowest index: #{i}."
  end

  {i, explanation}
end

def nvp(x, y, points) do
  # find the "valid" points
  {_, valid} = Enum.map_reduce(
    range(points), %{},
    fn i, valid ->
      valid = if is_valid(x, y, Enum.at(points, i)) do
        Map.put(valid, i, 1)
      else
        valid
      end
      {i, valid}
    end
  )

  if map_size(valid) == 0 do
    { -1, "No point shares x or y with (#{x}, #{y})." }
  else
    nvp(x, y, points, valid)
  end
end

View the entire Elixir script for this task on GitHub.

Here’s all my solutions in GItHub: https://github.com/packy/perlweeklychallenge-club/tree/master/challenge-334/packy-anderson