Perl Weekly Challenge: Missing Absolute Distance

Posted on by

To work on Perl Weekly Challenge 327 I must be MAD, you say? MAD? MAD?!?!

Are we there yet?
I’m tired
I’m hungry
How far?
My nose is snotty
Need to move my body
Gotta use the potty
Better stop the car!

Task 1: Missing Integers

You are given an array of n integers.

Write a script to find all the missing integers in the range 1..n in the given array.

Example 1

Input: @ints = (1, 2, 1, 3, 2, 5)
Output: (4, 6)

The given array has 6 elements.
So we are looking for integers in the range 1..6 in the given array.
The missing integers: (4, 6)

Example 2

Input: @ints = (1, 1, 1)
Output: (2, 3)

Example 3

Input: @ints = (2, 2, 1)
Output: (3)

Approach

This is a set based exercise. We don’t care about how many times any of the integers appear in the input array of n integers, we only care whether or not any of the integers in the range 1..n don’t exist in it. We make a set of the integers, then loop from 1..n to check if any are missing.

Raku

In Raku, there’s a Set class that will do that work for us. And because I love using Raku’s fancy unicode aliasing, I’m using the ∉ operator as well.

sub missingInts(@ints) {
  my $set = @ints.Set;
  my @missing;
  for 1 .. @ints.elems -> $i {
    @missing.push($i) if $i ∉ $set;
  }
  return @missing;
}

View the entire Raku script for this task on GitHub.

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

Example 2:
Input: @ints = (1, 1, 1)
Output: (2, 3)

Example 3:
Input: @ints = (2, 2, 1)
Output: (3)

Perl

Perl doesn’t have sets, but it’s easy do do the same thing with a hash:

sub missingInts(@ints) {
  my %set = map { $_ => 1} @ints;
  my @missing;
  foreach my $i ( 1 .. scalar(@ints) ) {
    push @missing, $i unless exists $set{$i};
  }
  return @missing;
}

View the entire Perl script for this task on GitHub.

Python

But Python does have sets.

def missingInts(ints):
  intSet = set(ints)
  missing = []
  for i in range(1, len(ints)+1):
    if i not in intSet:
      missing.append(i)
  return missing

View the entire Python script for this task on GitHub.

Elixir

And so does Elixir. 

defp map_reduce_func(i, {set, missing}) do
  {i,
    if not MapSet.member?(set, i) do
      {set, missing ++ [i]}
    else
      {set, missing}
    end
  }
end

def missingInts(ints) do
  {_, {_, missing}} =
    1..length(ints)
    |> Enum.map_reduce(
         { MapSet.new(ints), [] },
         &map_reduce_func/2
       )
  missing
end

View the entire Elixir script for this task on GitHub.

Task 2: MAD

You are given an array of distinct integers.

Write a script to find all pairs of elements with minimum absolute difference (MAD) of any two elements.

Example 1

Input: @ints = (4, 1, 2, 3)
Output: [1,2], [2,3], [3,4]

The minimum absolute difference is 1.
Pairs with MAD: [1,2], [2,3], [3,4]

Example 2

Input: @ints = (1, 3, 7, 11, 15)
Output: [1,3]

Example 3

Input: @ints = (1, 5, 3, 8)
Output: [1,3], [3,5]

Approach

Ok, calculating the absolute difference between two integers x and y is easy, it’s ⎮x - y⎮. So what we want to do is get all the possible pairs (I see a nested loop), compute the absolute difference for each pair in order, and compare it with whatever the minimum absolute difference was up until that point. If it’s the same as the previous minimum, we add the pair to a list. If it’s smaller than the previous minimum, we clear the list, make this the new minimum and add the pair to the new list.

Raku

At first, I thought about looping over the array with indexes, but then I realized I was going to have to get the values from the indexes, and I could just as easily accomplish what I wanted by shifting off an element in the outer loop and then just looping over the remaining elements in the inner loop. When I shifted the last element off the list in the final pass through the outer loop, there would be nothing left for the inner loop and that would just be a no-op.

sub MAD(@ints) {
  my @mad;
  # let's make the biggest int our starting minimum
  my $min = max @ints;
  while (my $x = @ints.shift) {
    for @ints -> $y {
      my $diff = abs($x - $y);
      next if $diff > $min; # too big!
      if ($diff < $min) { # we found a new min!
        $min = $diff; # set the new minimum
        @mad = ();    # clear the old list
      }
      # make sure we put the numbers on the list
      # with the smaller integer first
      @mad.push([sort $x, $y]);
    }
  }
  # and return the list with the pairs sorted as well
  return @mad.sort({ $^a[0] cmp $^b[0] });
}

View the entire Raku script for this task on GitHub.

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

Example 2:
Input: @ints = (1, 3, 7, 11, 15)
Output: [1,3]

Example 3:
Input: @ints = (1, 5, 3, 8)
Output: [1,3], [3,5]

Perl

Again, there isn’t much different about the Perl implementation. We just need to import a max function so I can set my initial minimum.

use List::AllUtils qw( max );

sub MAD(@ints) {
  my @mad;
  # let's make the biggest int our starting minimum
  my $min = max @ints;
  while (my $x = shift @ints) {
    foreach my $y ( @ints ) {
      my $diff = abs($x - $y);
      next if $diff > $min; # too big!
      if ($diff < $min) { # we found a new min!
        $min = $diff; # set the new minimum
        @mad = ();    # clear the old list
      }
      # make sure we put the numbers on the list
      # with the smaller integer first
      push @mad, [sort $x, $y];
    }
  }
  # and return the list with the pairs sorted as well
  return sort { $a->[0] <=> $b->[0] } @mad;
}

View the entire Perl script for this task on GitHub.

Python

What bit me with the Python solution initially is that I didn’t indent lines 15-17 enough, so they weren’t inside the if block on line 11. One might say that’s why I ought to be using 4-space indentation like Guido intended. Personally, I prefer having block delimiters that aren’t whitespace dependent. If I wanted so much significant whitespace, I’d use SNOBOL.

def MAD(ints):
  mad = []
  # let's make the biggest int our starting minimum
  minDiff = max(ints)
  x = ints.pop(0) # get the first value for x
  while ints:
    for y in ints:
      diff = abs(x - y)
      if diff <= minDiff:  # not too big!
        if diff < minDiff: # we found a new min!
          minDiff = diff   # set the new minimum
          mad = []         # clear the old list
        # make sure we put the numbers on the list
        # with the smaller integer first
        mad.append(sorted([x, y]))
    x = ints.pop(0) # get the next value for x
  # and return the list with the pairs sorted as well
  return sorted(mad, key=lambda x: x[0])

View the entire Python script for this task on GitHub.

Elixir

In Elixir, I’m using a mix of two ways to iterate a list: for the outer loop, I’m using a function where I pass a list as a parameter and use Elixir’s [head | tail] syntax to grab the first element off the list and leave the remaining elements in their own list (line 22). Then, for the inner loop, I’m using Enum.map_reduce/3 to loop over the remaining elements without modifying them and using a private function to modify minDiff and madList as needed. Then I’m making a recursive call on line 26 which will pull off the next value for x and repeat the whole process.

defp map_reduce_func(y, {x, minDiff, madList}) do
  diff = abs(x - y)
  {minDiff, madList} = cond do
    diff > minDiff ->
      {minDiff, madList} # no change
    diff == minDiff ->
      # add [x,y] to the current list
      {minDiff, madList ++ [ Enum.sort([x, y]) ]}
    diff < minDiff ->
      # we found a new min!
      # make [x,y] the start of new list
      {diff, [ Enum.sort([x, y]) ]}
  end
  {y, {x, minDiff, madList}}
end

def mad([], _, madList), do: madList

def mad([x | ints], minDiff, madList) do
  {_, {_, minDiff, madList}} = Enum.map_reduce(
    ints, {x, minDiff, madList}, &map_reduce_func/2
  )
  mad(ints, minDiff, madList)
end

def mad(ints) do
  # return the list with the pairs sorted as well
  mad(ints, Enum.max(ints), [])
  |> Enum.sort(&(List.first(&1) <= List.first(&2)))
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-327/packy-anderson

One thought on “Perl Weekly Challenge: Missing Absolute Distance”

  1. Pingback: Perl Weekly Challenge: It MUST be nice! | Packy’s Place

Comments are closed.