RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved searching matrices and raising array elements. (Note that this ends today.)

Task 1: Special Positions

You are given a m x n binary matrix.

Write a script to return the number of special positions in the given binary matrix.

A position (i, j) is called special if $matrix[i][j] == 1 and all other elements in the row i and column j are 0.

I got whimsical on this one.

The simplistic approach would obviously be to scan for 1s and then scan each row and column in which the occurred.

Instead, I validate rows to get a list of potential (x, y) points, then validate columns for each of the x values to see which ones are still valid. Then iterate the list of points and count the ones with valid x.

The "full" version needs something like a tuple to act as a set key. For languages that don't offer this (Perl, PostScript, Lua) I put the (y, x) pairs in a list instead, but since the order doesn't matter a set feels like a more appropriate structure for the purpose.

Perl:

The validator answers "is this sequence all zeroes except for a 1, and if so where is the 1".

sub validator($a0) {
  my @a = sort @{$a0};
  my $l = scalar @a;
  if ($a[0] == 0 && $a[$l - 2] == 0 && $a[$l - 1] == 1) {
    foreach my $i (0 .. $l - 1) {
      if ($a0->[$i]== 1) {
        return $i;
      }
    }
  }
  return -1;
}

sub specialpositions($a) {
  my @vr = ();
  my %xs = ();

Validate each row, and store the potential special position (if any) and the x value.

  while (my ($y, $row) = each @{$a}) {
    my $x = validator($row);
    if ($x > -1) {
      push @vr, [$y, $x];
      $xs{$x} = 1;
    }
  }

Check each column that has a potential special position and delete the ones that don't.

  foreach my $x (keys %xs) {
    keys @{$a};
    my @c = (map {$_->[$x]} @{$a});
    if (validator(\@c) == -1) {
      delete $xs{$x};
    }
  }

Read back the list of positions, and count them.

  return scalar grep {exists $xs{$_->[1]}} @vr;
}

Kotlin, with the set keyed on a Pair (and with its built-in list searcher, shared with Scala, JavaScript and Python):

fun validator(a0: List<Int>): Int {
    val a = a0.sorted()
    val l = a.size
    if (a[0] == 0 && a[l - 2] == 0 && a[l - 1] == 1) {
        return a0.indexOf(1)
    } else {
        return -1
    }
}

fun specialpositions(a: List<List<Int>>): Int {
    var vr = mutableSetOf<Pair<Int, Int>>()
    var xs = mutableSetOf<Int>()
    a.forEachIndexed{y, row ->
                         val x = validator(row)
                     if (x > -1) {
                         vr.add(Pair(y, x))
                         xs.add(x)
                     }
    }
    var xd = mutableSetOf<Int>()
    for (x in xs) {
        val c = a.map{ it[x] }.toList()
        if (validator(c) == -1) {
            xd.add(x)
        }
    }
    xs.removeAll(xd)
    return vr.filter{xs.contains(it.second)}.size
}

Task 2: Distribute Elements

You are give an array of integers, @ints and two integers, $x and $y.

Write a script to execute one of the two options:

Level 1: Pick an index i of the given array and do $ints[i] += 1

Level 2: Pick two different indices i,j and do $ints[i] +=1 and $ints[j] += 1.

You are allowed to perform as many levels as you want to make every elements in the given array equal. There is cost attach for each level, for Level 1, the cost is $x and $y for Level 2.

In the end return the minimum cost to get the work done.

I feel sure there should be a quicker way to do this without the full search routine. Ah well. I haven't done DFS in Scala or Crystal before. Even if there is an awful lot of sorting.

Some optimisations are to prune any path that's produced a cost higher than the previously-found minimum cost, or that increments values beyond the highest existing value.

Crystal:

A queue entry:

struct Op
  property a, cost

  def initialize(@a : Array(Int32), @cost : Int32)
  end
end

def equalizearray(a0 : Array(Int32), x : Int32, y : Int32) : Int32?
  a = a0.sort
  limit = a[-1]

Initialise the queue and minimum cost.

  queue = Deque(Op).new
  queue.push(Op.new(a, 0))
  mc : Int32 | Nil = nil

Loop through the queue.

  while queue.size > 0
    op = queue.shift

If the cost is already at least as high as the minimum cost, we don't care about this branch whether it's complete or not.

    if !mc || mc > op.cost

If the branch is complete, store the new minimum cost.

      if op.a[0] == op.a[-1]
        mc = op.cost
      else

"Level 1": add 1 to the lowest number in this copy of the array, and make sure it's no higher than the limit.

        p = op.a.dup
        p[0] += 1
        if p[0] <= limit

If so, sort and produce a new queue entry.

          p = p.sort
          queue.push(Op.new(p, op.cost + x))

If that worked, try the "Level 2" operation as well.

          q = op.a.dup
          q[0] += 1
          q[1] += 1
          if q[1] <= limit
            q = q.sort
            queue.push(Op.new(q, op.cost + y))
          end
        end
      end
    end
  end
  mc
end

Full code on github.