RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved array selection and grid shifting. (Note that this ends today.)

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

If I sort the array, I can just look at adjacent pairs of integers since they are all distinct

Lua needs a window function (I've borrowed the code from my PostScript libraries here, inspired originally by Raku's rotor, which can do chunking or sliding windows as needed).

function windows(a, size, offset)
   local out = {}
   for i = 1, #a - size + 1, offset do
      local w = {}
      for j = 0, size - 1 do
         if i + j <= #a then
            table.insert(w, a[i + j])
         end
      end
      table.insert(out, w)
   end
   return out
end

So first we sort the input, and set up the output list.

function minabsdiff(a)
   local b = a
   table.sort(b)
   local out = {}

I'll use a rolling minimum difference, so that I can do this in a single pass. It can be no higher than the difference between the first and last list entries.

   local mindiff = 1 + b[#b] - b[1]

Look at each adjacent pair, taking the difference.

   for _, c in ipairs(windows(b, 2, 1)) do
      local d = c[2] - c[1]

If this is lower than any difference I've seen before, clear the output list and reset the lowest difference.

      if d < mindiff then
         out = {}
         mindiff = d
      end

If this is the lowest difference, add this pair to the output list.

      if d == mindiff then
         table.insert(out, c)
      end
   end
   return out
end

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.

I'm afraid I took a bit of a short cut here. If I linearise the list into a single long concatenated row, shift it k times, and then split it back into the original geometry, I obtain the same effect without having to worry about implementing individual rules. Raku:

sub shiftgrid(@gi, $k0) {

Linearise gi into wi:

    my @wi;
    for @gi -> @x {
        @wi.append(@x);
    }

Calculate a working k from a parameter which could be far larger than the matrix's size. I will do all the shifts at once as a single operation.

    my $k = $k0 % @wi.elems;

The first part of the output list wo is the later portion of the input, which would wrap round.

    my @wo = @wi[@wi.elems - $k .. @wi.end];

That is followed by the earlier portion of the input, which is shifted from start to end.

    @wo.append(@wi[0 .. @wi.elems - $k - 1]);

Then wo is chunked back into the final output form based on the length of the first input row.

    @wo.rotor(@gi[0].elems).map({$_.Array}).Array;
}

Some languages don't have all these fiddly operations. PostScript: for example:

/shiftgrid {
    0 dict begin
    /k exch def

Flatten wi into gi.

    /gi exch def
    /wi gi {
        aload pop
    } map def
    /k k wi length mod def

Set up an output list.

    [

Slice of wi from split point to end, which comes as an array, but we can unwrap it and drop the individual values onto the stack.

        wi wi length k sub k getinterval aload pop

Slice of wi from start to split point, similarly.

        wi 0 wi length k sub getinterval aload pop

End the output list, and chunk it up with my rotor function. (Everything else here is core PostScript. aload doesn't get talked about much even by the standards of PostScript functions, but it's dead handy.)

    ] gi 0 get length 0 rotor
    end
} bind def

And some languages make it very easy, as in Rust:

fn shiftgrid(gi: Vec<Vec<u32>>, k0: usize) -> Vec<Vec<u32>> {

Flatten gi into wi.

    let wi = gi.concat();
    let k = k0 % wi.len();

Take the two slices and build them into a new vector.

   let wo = [wi[wi.len() - k..].to_vec(), wi[0..wi.len() - k].to_vec()]
        .to_vec()
        .concat();

Chunk it out again.

    wo.chunks(gi[0].len()).map(|x| x.to_vec()).collect::<Vec<_>>()
}

Full code on github.