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.