Perl Weekly Challenge: Some Grids

Posted on by

With Perl Weekly Challenge 354‘s tasks being “Min Abs Diff” and “Shift Grid”, I was a bit stuck for a musical theme. So I free-associated, and “grid” made me think of the cover of The Rolling Stones’ album, Some Girls. So let’s listen to that while we write some challenges1.

Task 1: Min Abs Diff

You are given an array of distinct integers.

Write a script to find all pairs of elements with the minimum absolute difference.

Rules (a,b):
1: a, b are from the given array.
2: a < b
3: b - a = min abs diff any two elements in the given array

Example 1

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

Example 2

Input: @ints = (10, 100, 20, 30)
Output: [10, 20], [20, 30]

Example 3

Input: @ints = (-5, -2, 0, 3)
Output: [-2, 0]

Example 4

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

Example 5

Input: @ints = (12, 5, 9, 1, 15)
Output: [9, 12], [12, 15]

Approach

Looking at the output, I see they’re all sorted, and I realized that as a first step we want to sort the list, because that means that the minimum distance between any two elements will be between an element and its immediate neighbors (because once they’re sorted, any element further from another element besides its immediate neighbors will, by definition, have larger differences).

Then, once we’ve got a sorted list, we can step through the list element by element and compute the differences. We can keep a variable to track the minimum difference, and we can assign a starting value of the largest possible difference: the difference between the first and last elements in the array.

Since there can be more than one instance of pairs with the minimum absolute difference, we want to maintain a list of pairs. When we find a pair that has the same difference as the current minimum, we add it to the list. When we find a pair that has a lower difference than the current minimum, we clear the list, add that pair to the new list, and reset the minimum to the current difference.

Raku

One of the things that I didn’t start doing until I got to the Elixir solution was assigning the representation of the pair to a local variable, and I came back and added it to the other solutions. In here, it’s the assignment on line 15. I did it in Elixir to make the line length shorter (my blog’s style doesn’t really display lines longer than 65 characters well), but I think it also makes the code a little more readable.

sub minAbsDiff(@ints) {
  # sort so minimum difference items are next to each other
  @ints = @ints.sort;
  # start with the largest possible difference
  my $min = abs(@ints[*-1] - @ints[0]);

  my @pairs;
  my $last = @ints.shift;

  for @ints -> $current {
    my $diff = abs($current - $last);
    my $pair = "[$last, $current]";
    if ($diff == $min) { # same diff, add to list
      @pairs.push($pair);
    }
    elsif ($diff < $min) { # start new list with this pair
      @pairs = ($pair);
      $min = $diff;
    }
    $last = $current;
  }
  return @pairs.join(', ');
}

View the entire Raku script for this task on GitHub.

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

Example 2:
Input: @ints = (10, 100, 20, 30)
Output: [10, 20], [20, 30]

Example 3:
Input: @ints = (-5, -2, 0, 3)
Output: [-2, 0]

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

Example 5:
Input: @ints = (12, 5, 9, 1, 15)
Output: [9, 12], [12, 15]

Perl

As always, you can tell Perl and Raku are sibling languages.

sub minAbsDiff(@ints) {
  # sort so minimum difference items are next to each other
  # ensure numeric sorting
  @ints = sort { $a <=> $b } @ints;
  # start with the largest possible difference
  my $min = abs($ints[-1] - $ints[0]);

  my @pairs;
  my $last = shift @ints;

  foreach my $current (@ints) {
    my $diff = abs($current - $last);
    my $pair = "[$last, $current]";
    if ($diff == $min) { # same diff, add to list
      push @pairs, $pair;
    }
    elsif ($diff < $min) { # start new list with this pair
      @pairs = ($pair);
      $min = $diff;
    }
    $last = $current;
  }
  return join(', ', @pairs);
}

View the entire Perl script for this task on GitHub.

Python

But even Python looks like a cousin to Perl and Raku.

def min_abs_diff(ints):
  # sort so minimum difference items are next to each other
  ints.sort()
  # start with the largest possible difference
  min_val = abs(ints[-1] - ints[0])

  pairs = []
  last = ints.pop(0)

  for current in ints:
    diff = abs(current - last)
    pair = f"[{last}, {current}]"
    if diff == min_val: # same diff, add to list
      pairs.append(pair)
    elif diff < min_val: # start new list with this pair
      pairs = [pair]
      min_val = diff
    last = current

  return ", ".join(pairs)

View the entire Python script for this task on GitHub.

Elixir

It’s Elixir that looks really different from the rest of the languages I use.

One of the things I love about Elixir is the emphasis on recursion. I may have been able to come up with a way to use Enum.map_reduce/3 to process each of the elements in the list, but it was really easy to just create a recursive min_abs_diff/4 that did everything I needed to.

Initially, in the cond do on lines 10-18 I was recursively calling min_abs_diff/4 for each condition and just returning the result

def min_abs_diff([current | ints], last, min_val, pairs) do
  diff = abs(current - last)
  pair = "[#{last}, #{current}]"
  cond do
    diff == min_val ->
      # same diff, add to list
      min_abs_diff(ints, current, min_val, pairs ++ [pair])
    diff < min_val ->
      # start new list with this pair
      min_abs_diff(ints, current, diff, [pair])
    true ->
      # process next pair
      min_abs_diff(ints, current, min_val, pairs)
  end
end

but I decided to refactor and have it assign a tuple of {min_val, pairs} so I could emphasize that those were the only things changing (or not changing) in that conditional, much the way I’m doing it in the non-recursive solutions in Raku, Perl, and Python.

def min_abs_diff([], _, _, pairs), do:
  pairs |> Enum.join(", ")

def min_abs_diff([current | ints], last, min_val, pairs) do
  diff = abs(current - last)
  pair = "[#{last}, #{current}]"
  { min_val, pairs } = cond do
    diff == min_val ->
      # same diff, add to list
      { min_val, pairs ++ [pair] }
    diff < min_val ->
      # start new list with this pair
      { diff, [pair] }
    true -> { min_val, pairs }
  end
  # process next pair
  min_abs_diff(ints, current, min_val, pairs)
end

def min_abs_diff(ints) do
  # sort so minimum difference items are next to each other
  ints = Enum.sort(ints)

  min_abs_diff(
    tl(ints),
    hd(ints),
    # start with the largest possible difference
    abs(Enum.at(ints,-1) - Enum.at(ints,0)),
    []
  )
end

View the entire Elixir script for this task on GitHub.

Task 2: Shift Grid

You are given m x n matrix and an integer, $k > 0.

Write a script to shift the given matrix $k times.

Each shift follow the rules:

Rule 1:
Element at grid[i][j] moves to grid[i][j + 1]
This means every element moves one step to the right within its row.

Rule 2:
Element at grid[i][n - 1] moves to grid[i + 1][0]
This handles the last column: elements in the last column of row i wrap to the first column of the next row (i+1).

Rule 3:
Element at grid[m - 1][n - 1] moves to grid[0][0]
This is the bottom-right corner: it wraps to the top-left corner.

Example 1

Input: @matrix = ([1, 2, 3],
                  [4, 5, 6],
                  [7, 8, 9],)
       $k = 1
Output: ([9, 1, 2],
         [3, 4, 5],
         [6, 7, 8],)

Rule 1: grid[i][j] -> grid[i][j+1] for j < n-1.

We take elements from the original grid at (i, j) and put them into new_grid[i][j+1].

From original:

(0,0): 1 -> new_grid[0][1] = 1
(0,1): 2 -> new_grid[0][2] = 2
(1,0): 4 -> new_grid[1][1] = 4
(1,1): 5 -> new_grid[1][2] = 5
(2,0): 7 -> new_grid[2][1] = 7
(2,1): 8 -> new_grid[2][2] = 8

New grid looks after Rule 1:

([?, 1, 2],
 [?, 4, 5],
 [?, 7, 8],)

Rule 2: grid[i][n-1] -> grid[i+1][0] for i < m-1.

Elements from original last column (except last row) go to next row's first column.

From original:

(0,2): 3 -> new_grid[1][0] = 3
(1,2): 6 -> new_grid[2][0] = 6

Now new grid after Rules 1 + 2:

([?, 1, 2],
 [3, 4, 5],
 [6, 7, 8],)

Rule 3: grid[m-1][n-1] -> grid[0][0].

Original (2,2): 9 -> new_grid[0][0] = 9.

Now new_grid is complete:

([9, 1, 2],
 [3, 4, 5],
 [6, 7, 8],)

Example 2

Input: @matrix = ([10, 20],
                  [30, 40],)
       $k = 1
Output: ([40, 10],
         [20, 30],)

Rule 1 (move right in same row if not last column):

(0,0): 10 -> new[0][1] = 10
(1,0): 30 -> new[1][1] = 30

After Rule 1:

([?, 10],
 [?, 30],)

Rule 2 (last col -> next row’s first col, except last row):

(0,1): 20 -> new[1][0] = 20

After Rule 2:

([?,  10],
 [20, 30],)

Rule 3 (bottom-right to top-left):

(1,1): 40 -> new[0][0] = 40

After Rule 3:

([40, 10],
 [20, 30],)

Example 3

Input: @matrix = ([1, 2],
                  [3, 4],
                  [5, 6],)
      $k = 1
Output: ([6, 1],
         [2, 3],
         [4, 5],)

Rule 1:
(0,0): 1 -> new[0][1] = 1
(1,0): 3 -> new[1][1] = 3
(2,0): 5 -> new[2][1] = 5

After Rule 1:
( [?, 1],
  [?, 3],
  [?, 5],)

Rule 2:
(0,1): 2 -> new[1][0] = 2
(1,1): 4 -> new[2][0] = 4

After Rule 2:
([?, 1],
 [2, 3],
 [4, 5],)

Rule 3:
(2,1): 6 -> new[0][0] = 6

After Rule 3:
([6, 1],
 [2, 3],
 [4, 5],)

Example 4

Input: @matrix = ([1, 2, 3],
                  [4, 5, 6],)
       $k = 5
Output: ([2, 3, 4],
         [5, 6, 1],)

Shift 1

Rule 1
1 -> (0,1)
2 -> (0,2)
4 -> (1,1)
5 -> (1,2)

Rule 2
3 -> (1,0) (last column of row 0)

Rule 3
6 -> (0,0) (bottom-right corner)

Result
[6, 1, 2]
[3, 4, 5]

----------------------------

Shift 2

Starting from the previous matrix:

[6, 1, 2]
[3, 4, 5]

Rule 1
6 -> (0,1)
1 -> (0,2)
3 -> (1,1)
4 -> (1,2)

Rule 2
2 -> (1,0)

Rule 3
5 -> (0,0)

Result
[5, 6, 1]
[2, 3, 4]

----------------------------

Shift 3

[5, 6, 1]
[2, 3, 4]

Rule 2: 1 -> (1,0)
Rule 3: 4 -> (0,0)

Others follow Rule 1

Result
[4, 5, 6]
[1, 2, 3]

----------------------------

Shift 4

[4, 5, 6]
[1, 2, 3]

Result
[3, 4, 5]
[6, 1, 2]

----------------------------

Shift 5
[3, 4, 5]
[6, 1, 2]

Result
[2, 3, 4]
[5, 6, 1]

Final Output (after k = 5 shifts)
([2, 3, 4],
 [5, 6, 1])

Example 5

Input: @matrix = ([1, 2, 3, 4])
       $k = 1
Output: ([4, 1, 2, 3])

Rule 1:
(0,0): 1 -> new[0][1] = 1
(0,1): 2 -> new[0][2] = 2
(0,2): 3 -> new[0][3] = 3

After Rule 1:
([?, 1, 2, 3])

Rule 2:
(0,3): 4 -> new[1][0] ??

Wait — but i=0, n-1=3, next row i+1=1 doesn’t exist (m=1).
So this is actually a special case where Rule 2 should not apply.
because m=1, so (0,3) goes by Rule 3 actually.

The rules say:
grid[i][j]     -> grid[i][j+1] for j < n-1.
grid[i][n-1]   -> grid[i+1][0] for i < m-1.
grid[m-1][n-1] -> grid[0][0].

For m = 1:
Elements (0,0),(0,1),(0,2) follow Rule 1 -> (0,1),(0,2),(0,3).
Element (0,3) is (m-1, n-1), so follows Rule 3 -> (0,0).

Actually, that means after Rule 1:
We put 1,2,3 in positions 1,2,3, leaving position 0 empty.
Then Rule 3 puts 4 in position 0.

So final directly:
[4, 1, 2, 3]

Approach

One of the things that I noticed when I was following along in the steps is that these rules wind up producing the exact same output as if you had done the following:

  • Transform the m x n matrix into an array of m * n elements, where the first n elements of the array are the first row of the array, the next n elements are the second row, and so on.
  • Pop the last element off the array and unshift it into the first element of the array, thus rotating/shifting the array one element to the right.
  • Re-transform the array back into an m x n matrix.

Raku

sub shiftGrid(@matrix, $k is copy) {
  # get the dimensions of the matrix
  my ($m, $n) = (@matrix.elems, @matrix[0].elems);

  # flatten the matrix
  my @flat = @matrix.flat;

  while ($k-- > 0) {
    @flat.unshift(@flat.pop()); # shift to the right
  }

  # re-matrix the array
  my @result;
  while ($m-- > 0) {
    @result.push(@flat[0..$n-1]);
    @flat.splice(0, $n);
  }

  return @result;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: @matrix = [ [1, 2, 3],
                   [4, 5, 6],
                   [7, 8, 9] ]
       $k = 1
Output: [ [9, 1, 2],
          [3, 4, 5],
          [6, 7, 8] ]

Example 2:
Input: @matrix = [ [10, 20],
                   [30, 40] ]
       $k = 1
Output: [ [40, 10],
          [20, 30] ]

Example 3:
Input: @matrix = [ [1, 2],
                   [3, 4],
                   [5, 6] ]
       $k = 1
Output: [ [6, 1],
          [2, 3],
          [4, 5] ]

Example 4:
Input: @matrix = [ [1, 2, 3],
                   [4, 5, 6] ]
       $k = 5
Output: [ [2, 3, 4],
          [5, 6, 1] ]

Example 5:
Input: @matrix = [ [1, 2, 3, 4] ]
       $k = 1
Output: [ [4, 1, 2, 3] ]

Perl

sub shiftGrid($matrix, $k) {
  # get the dimensions of the matrix
  my ($m, $n) = (scalar(@$matrix), scalar(@{$matrix->[0]}));

  # flatten the matrix
  my @flat = map { @{$_} } @$matrix;

  while ($k-- > 0) {
    unshift @flat, pop @flat; # shift to the right
  }

  # re-matrix the array
  my @result;
  while ($m-- > 0) {
    push @result, [ @flat[0..$n-1] ];
    splice @flat, 0, $n;
  }

  return \@result;
}

View the entire Perl script for this task on GitHub.

Python

def shift_grid(matrix, k):
  # get the dimensions of the matrix
  m, n = len(matrix), len(matrix[0])

  # flatten the matrix
  flat = sum(matrix, [])

  while k > 0:
    flat.insert(0, flat.pop()) # shift to the right
    k -= 1

  # re-matrix the array
  result = []
  while m > 0:
    result.append(flat[0:n])
    del flat[0:n]
    m -= 1

  return result

View the entire Python script for this task on GitHub.

Elixir

I realized when I got to the Elixir solution, I didn’t need the m dimension of the array; I could just rebuild the matrix by chunking every n elements.

Also, the easiest way to get the end of a list in Elixir is to reverse the list and grab the head of the list, so I combined that with a recursive function that also loops k times.

  def shift_right(array, k) when k <= 0, do: array

  def shift_right(array, k) do
    [head | tail] = Enum.reverse(array)
    shift_right([head | Enum.reverse(tail)], k-1)
  end

  def shift_grid(matrix, k) do
    # get the width of the matrix
    n = length(hd(matrix))

    # flatten the matrix
    flat = Enum.flat_map(matrix, fn x -> x end)

    # shift to the right
    flat = shift_right(flat, k)

    # re-matrix the array
    Enum.chunk_every(flat, n)
  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-354/packy-anderson

  1. This album has the distinction of ending with Shattered, which has my wife’s and my favorite lines in any Rolling Stones song. Hers is in verse 2—”I can’t give it away on 7th avenue”, and mine is just before the outro—”We’ve got rats on the west side, bed bugs uptown!” ↩︎

Leave a Reply