# RogerBW's Blog

The Weekly Challenge 270: Special Distribtions Position the Elements 26 May 2024

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

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) {
}
}
var xd = mutableSetOf<Int>()
for (x in xs) {
val c = a.map{ it[x] }.toList()
if (validator(c) == -1) {
}
}
xs.removeAll(xd)
return vr.filter{xs.contains(it.second)}.size
}
``````

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.