There’s antimony, arsenic, aluminum, selenium,
And hydrogen and oxygen and nitrogen and rhenium,
And nickel, neodymium, neptunium, germanium,
And iron, americium, ruthenium, uranium…
This week’s challenge is all about ELEMENTS! (That’s Perl Weekly Challenge 270, of course…)
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.
Example 1
Input: $matrix = [ [1, 0, 0],
[0, 0, 1],
[1, 0, 0],
]
Output: 1
There is only one special position (1, 2) as $matrix[1][2] == 1
and all other elements in row 1 and column 2 are 0.
Example 2
Input: $matrix = [ [1, 0, 0],
[0, 1, 0],
[0, 0, 1],
]
Output: 3
Special positions are (0,0), (1, 1) and (2,2).
Approach
The matrix is stated to be binary, so the elements are all 1
or 0
. So we can safely say that there’s only one 1
in a row or a column if the sum of that row or column is 1
.
Raku
I thought about using someone else’s matrix math module to get the columns and rows, but I realized it was pretty easy to get the values in a row via @matrix[$i].values
, and with a little thought I realized I could get the values in a column by mapping the rows and pulling out the desired value for the column using @matrix.map: { .[$j] }
.
use Lingua::Conjunction;
sub sumRow(@matrix, $i) {
return [+] @matrix[$i].values;
}
sub sumCol(@matrix, $j) {
return [+] ( @matrix.map: { .[$j] } );
}
sub specialPositions(@matrix) {
my @special;
for @matrix.kv -> $i, @row {
for @row.kv -> $j, $value {
# not special unless = 1
next unless $value == 1;
# not special unless only 1 in row
next unless sumRow(@matrix, $i) == 1;
# not special unless only 1 in column
next unless sumCol(@matrix, $j) == 1;
# it's special!
@special.push( "($i, $j)" );
}
}
my $str = 'Special position[|s] [is|are] |list|';
return @special.elems, conjunction(@special, :$str, :alt<,>);
}
$ raku/ch-1.raku
Example 1:
Input: $matrix = [
[1, 0, 0],
[0, 0, 1],
[1, 0, 0]
]
Output: 1
Special position is (1, 2)
Example 2:
Input: $matrix = [
[1, 0, 0],
[0, 1, 0],
[0, 0, 1]
]
Output: 3
Special positions are (0, 0), (1, 1), and (2, 2)
View the entire Raku script for this task on GitHub.
Perl
Once I’d done the Raku version, the Perl version was easy. I mix passing arrays and array references so I don’t have to swap the order of the arguments in sumRow
and sumCol
, since array arguments need to be the last argument.
use List::Util qw( sum );
use Lingua::EN::Inflexion qw( wordlist );
sub sumRow($matrix, $i) {
return sum @{ $matrix->[$i] };
}
sub sumCol($matrix, $j) {
return sum map { $_->[$j] } @$matrix;
}
sub specialPositions(@matrix) {
my @special;
foreach my $i ( 0 .. $#matrix ) {
my @row = @{$matrix[$i]};
foreach my $j ( 0 .. $#row ) {
my $value = $row[$j];
# not special unless = 1
next unless $value == 1;
# not special unless only 1 in row
next unless sumRow(\@matrix, $i) == 1;
# not special unless only 1 in column
next unless sumCol(\@matrix, $j) == 1;
# it's special!
push @special, "($i, $j)";
}
}
my $list = wordlist(@special, { sep => ',' });
my $explain = 'Special position';
$explain .= (@special == 1) ? ' is ' : 's are ';
$explain .= $list;
return scalar(@special), $explain;
}
View the entire Perl script for this task on GitHub.
Python
It’s not as trivial to just break out of nested loops in Python as it is in Raku/Perl (it’s possible, but a bit unwieldy), so it was easier to just make it a big compound if
statement.
def sumRow(matrix, i):
return sum(matrix[i])
def sumCol(matrix, j):
return sum([ i[j] for i in matrix ])
def specialPositions(matrix):
special = []
for i, row in enumerate(matrix):
for j, value in enumerate(row):
# not special unless = 1
if (value == 1 and
# not special unless only 1 in row
sumRow(matrix, i) == 1 and
# not special unless only 1 in column
sumCol(matrix, j) == 1):
# it's special!
special.append( f"({i}, {j})" )
explain = 'Special position'
explain += ' is ' if len(special) == 1 else 's are '
explain += ', '.join(special)
return len(special), explain
View the entire Python script for this task on GitHub.
Elixir
Of course, immutability in Elixir winds up complicating my code. In order to append to the list of special elements, I need to constantly return the list as the value of the loops. But when I’m done with the loops, the list winds up looking like [[[], [], []], [[], [], ["(1, 2)"]], [[], [], []]]
, so I need to List.flatten/1
the list so I wind up with only the elements I’m interested in…
Fortunately, I think I’m finally getting a handle on Elixir’s pipe operator.
def sumRow(matrix, i) do
matrix
|> Enum.at(i)
|> Enum.sum
end
def sumCol(matrix, j) do
matrix
|> Enum.map(fn x -> Enum.at(x, j) end)
|> Enum.sum
end
def specialPositions(matrix) do
special = []
special = for i <- 0..length(matrix)-1 do
row = Enum.at(matrix, i)
for j <- 0..length(row)-1 do
value = Enum.at(row, j)
if value == 1 and
sumRow(matrix, i) == 1 and
sumCol(matrix, j) == 1 do
# it's special
special ++ [ "(#{i}, #{j})" ]
else
special
end
end
end
special = List.flatten(special)
{
length(special),
case length(special) do
1 -> "Special position is "
_ -> "Special positions are "
end <> Enum.join(special, ", ")
}
end
View the entire Elixir script for this task on GitHub.
Task 2: Equalize Array
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.
Example 1
Input: @ints = (4, 1), $x = 3 and $y = 2
Output: 9
Level 1: i=1, so $ints[1] += 1.
@ints = (4, 2)
Level 1: i=1, so $ints[1] += 1.
@ints = (4, 3)
Level 1: i=1, so $ints[1] += 1.
@ints = (4, 4)
We performed operation Level 1, 3 times.
So the total cost would be 3 x $x => 3 x 3 => 9
Example 2
Input: @ints = (2, 3, 3, 3, 5), $x = 2 and $y = 1
Output: 6
Level 2: i=0, j=1, so $ints[0] += 1 and $ints[1] += 1
@ints = (3, 4, 3, 3, 5)
Level 2: i=0, j=2, so $ints[0] += 1 and $ints[2] += 1
@ints = (4, 4, 4, 3, 5)
Level 2: i=0, j=3, so $ints[0] += 1 and $ints[3] += 1
@ints = (5, 4, 4, 4, 5)
Level 2: i=1, j=2, so $ints[1] += 1 and $ints[2] += 1
@ints = (5, 5, 5, 4, 5)
Level 1: i=3, so $ints[3] += 1
@ints = (5, 5, 5, 5, 5)
We performed operation Level 1, 1 time and Level 2, 4 times.
So the total cost would be (1 x $x) + (3 x $y) => (1 x 2) + (4 x 1) => 6
Approach
This one is interesting—repeatedly performing Level 1 operations will eventually yield the desired result, but the operation has (at least in the two examples provided) a higher cost associated with it than Level 2 operations. As long as the cost of Level 2 operations is less than twice the cost of Level 1 operations, it’s going to be more cost effective to use Level 2 operations when possible.
That said, the approach I think will be most effective is to take a pass over the integers and take note of the following pieces of information:
- What the maximum value is in the array
- A mapping of each unique value in the array to a list of indices where it occurs.
Then, we examine the map. If there are two values that can be incremented and $x * 2 > $y
, increment the lowest two of those values; otherwise, we pick the lowest remaining value and increment that. In either case, we update the map so we know where the values are, and the iterate until all the values in the array are at the maximum value.
Raku
sub fmtInts(@ints) {
return '@ints = (' ~ @ints.join(', ') ~ ')';
}
sub getNextIndex(%mapping) {
my $min = min(%mapping.keys); # note the current min val
my $i = min(%mapping{$min}.keys); # get the smallest index
%mapping{$min}{$i}:delete; # remove index from map
unless (%mapping{$min}.values) { # no more of this value
%mapping{$min}:delete; # remove value from map
}
return $i; # return the index
}
sub equalizeArray(@ints, $x, $y) {
# track how many of each op, and terminal value
my $max = -Inf;
my %mapping;
my @steps;
my ($L1, $L2) = (0, 0);
# loop over the array to determine max value
# and where the lower numbers are
for @ints.kv -> $i, $int {
$max = $int if ($int > $max);
%mapping{$int}{$i} = 1;
}
# we don't need to operate on values already at the max
%mapping{$max}:delete;
while (%mapping.keys) {
my $elems = %mapping.values».List.flat.elems;
if ($elems > 1 && $x <= $y * 2) {
# get the two indices
my $i = getNextIndex(%mapping);
my $j = getNextIndex(%mapping);
# increment the values
@ints[$i]++;
@ints[$j]++;
@steps.push(
"Level 2: i=$i, j=$j, so \$ints[$i] += 1 and " ~
"\$ints[$j] += 1\n" ~ fmtInts(@ints)
);
$L2++;
# if the numbers we incremented are less than the max,
# put them back in the mapping
%mapping{@ints[$i]}{$i} = 1 if (@ints[$i] < $max);
%mapping{@ints[$j]}{$j} = 1 if (@ints[$j] < $max);
}
else {
# get the index
my $i = getNextIndex(%mapping);
# increment the value
@ints[$i]++;
@steps.push(
"Level 1: i=$i, so \$ints[$i] += 1\n" ~
fmtInts(@ints)
);
$L1++;
# if the number we incremented is less than the max,
# put it back in the mapping
%mapping{@ints[$i]}{$i} = 1 if (@ints[$i] < $max);
}
}
my $cost = ($L1 * $x) + ($L2 * $y);
my @operations;
@operations.push(
"Level 1, $L1 " ~ ($L1 == 1 ?? 'time' !! 'times')
) if $L1;
@operations.push(
"Level 2, $L2 " ~ ($L2 == 1 ?? 'time' !! 'times')
) if $L2;
@steps.push(
'We performed operation ' ~ @operations.join(" and ") ~
"\nSo the total cost would be ($L1 × \$x) + ($L2 × \$y) => " ~
"($L1 × $x) + ($L2 × $y) => $cost"
);
return $cost, @steps.join("\n\n");
}
$ raku/ch-2.raku
Example 1:
Input: @ints = (4, 1), $x = 3 and $y = 2
Output: 9
Level 1: i=1, so $ints[1] += 1
@ints = (4, 2)
Level 1: i=1, so $ints[1] += 1
@ints = (4, 3)
Level 1: i=1, so $ints[1] += 1
@ints = (4, 4)
We performed operation Level 1, 3 times
So the total cost would be (3 × $x) + (0 × $y) => (3 × 3) + (0 × 2) => 9
Example 2:
Input: @ints = (2, 3, 3, 3, 5), $x = 2 and $y = 1
Output: 6
Level 2: i=0, j=1, so $ints[0] += 1 and $ints[1] += 1
@ints = (3, 4, 3, 3, 5)
Level 2: i=0, j=2, so $ints[0] += 1 and $ints[2] += 1
@ints = (4, 4, 4, 3, 5)
Level 2: i=3, j=0, so $ints[3] += 1 and $ints[0] += 1
@ints = (5, 4, 4, 4, 5)
Level 2: i=1, j=2, so $ints[1] += 1 and $ints[2] += 1
@ints = (5, 5, 5, 4, 5)
Level 1: i=3, so $ints[3] += 1
@ints = (5, 5, 5, 5, 5)
We performed operation Level 1, 1 time and Level 2, 4 times
So the total cost would be (1 × $x) + (4 × $y) => (1 × 2) + (4 × 1) => 6
View the entire Raku script for this task on GitHub.
Perl
use List::Util qw( min );
sub fmtInts(@ints) {
return '@ints = (' . join(', ', @ints) . ')';
}
sub getNextIndex($mapping) {
my $min = min(keys %$mapping); # note the current min val
my $i = min(keys %{$mapping->{$min}}); # get the smallest index
delete $mapping->{$min}{$i}; # remove index from map
unless (values %{$mapping->{$min}}) { # no more of this value
delete $mapping->{$min}; # remove value from map
}
return $i; # return the index
}
sub equalizeArray($ints, $x, $y) {
# track how many of each op, and terminal value
my $max = -Inf;
my %mapping;
my @steps;
my ($L1, $L2) = (0, 0);
# loop over the array to determine max value
# and where the lower numbers are
foreach my $i ( 0 .. $#{$ints} ) {
my $int = $ints->[$i];
$max = $int if ($int > $max);
$mapping{$int}{$i} = 1;
}
# we don't need to operate on values already at the max
delete $mapping{$max};
while (keys %mapping) {
my $elems = scalar(map { keys %$_ } values %mapping);
if ($elems > 1 && $x * 2 >= $y) {
# get the two indices
my $i = getNextIndex(\%mapping);
my $j = getNextIndex(\%mapping);
# increment the values
$ints->[$i]++;
$ints->[$j]++;
push @steps,
"Level 2: i=$i, j=$j, so \$ints[$i] += 1 and " .
"\$ints[$j] += 1\n" . fmtInts(@$ints);
$L2++;
# if the numbers we incremented are less than the max,
# put them back in the mapping
$mapping{$ints->[$i]}{$i} = 1 if ($ints->[$i] < $max);
$mapping{$ints->[$j]}{$j} = 1 if ($ints->[$j] < $max);
}
else {
# get the index
my $i = getNextIndex(\%mapping);
# increment the value
$ints->[$i]++;
push @steps, "Level 1: i=$i, so \$ints[$i] += 1\n" .
fmtInts(@$ints);
$L1++;
# if the number we incremented is less than the max,
# put it back in the mapping
$mapping{$ints->[$i]}{$i} = 1 if ($ints->[$i] < $max);
}
}
my $cost = ($L1 * $x) + ($L2 * $y);
my @operations;
push @operations, "Level 1, $L1 " . ($L1 == 1 ? 'time' : 'times')
if $L1;
push @operations, "Level 2, $L2 " . ($L2 == 1 ? 'time' : 'times')
if $L2;
push @steps,
'We performed operation ' . join(" and ", @operations) .
"\nSo the total cost would be ($L1 × \$x) + ($L2 × \$y) => " .
"($L1 × $x) + ($L2 × $y) => $cost";
return $cost, join("\n\n", @steps);
}
View the entire Perl script for this task on GitHub.
Python
import sys
def items_in_dict(d):
items = 0
for v, d2 in d.items():
for i in d2.keys():
items += 1
return items
def comma_join(arr):
return ', '.join(map(lambda i: str(i), arr))
def fmtInts(ints):
return f'@ints = ({comma_join(ints)})'
def setMap(mapping, intVal, i):
if mapping.get(intVal, None) is None:
mapping[intVal] = {}
mapping[intVal][i] = 1
def getNextIndex(mapping):
minVal = min(mapping.keys()) # note the current min val
i = min(mapping[minVal].keys()) # minimum index for that val
del mapping[minVal][i] # remove index from map
if not mapping[minVal].values(): # no more of this value
del mapping[minVal] # remove value from map
return i # return the index
def equalizeArray(ints, x, y):
# track how many of each op, and terminal value
maxVal = -1 * sys.maxsize
mapping = {}
steps = []
L1 = 0
L2 = 0
# loop over the array to determine max value
# and where the lower numbers are
for i, intVal in enumerate(ints):
if intVal > maxVal:
maxVal = intVal
setMap(mapping, intVal, i)
# we don't need to operate on values already at the max
del mapping[maxVal]
while mapping.keys():
if items_in_dict(mapping) > 1 and x * 2 >= y:
# get the two indices
i = getNextIndex(mapping)
j = getNextIndex(mapping)
# increment the values
ints[i] += 1
ints[j] += 1
steps.append(
f"Level 2: i={i}, j={j}, so $ints[{i}] += 1 and " +
f"$ints[{j}] += 1\n" + fmtInts(ints)
)
L2 += 1
# if the numbers we incremented are less than the max,
# put them back in the mapping
if ints[i] < maxVal:
setMap(mapping, ints[i], i)
if ints[j] < maxVal:
setMap(mapping, ints[j], j)
else:
# get the index
i = getNextIndex(mapping)
# increment the value
ints[i] += 1
steps.append(
f"Level 1: i={i}, so $ints[{i}] += 1\n" +
fmtInts(ints)
)
L1 += 1
# if the number we incremented is less than the max,
# put it back in the mapping
if ints[i] < maxVal:
setMap(mapping, ints[i], i)
cost = (L1 * x) + (L2 * y)
operations = []
if L1:
operations.append(
f"Level 1, {L1} " + ('time' if L1 == 1 else 'times')
)
if L2:
operations.append(
f"Level 2, {L2} " + ('time' if L2 == 1 else 'times')
)
steps.append(
'We performed operation ' + ' and '.join(operations) +
f"\nSo the total cost would be ({L1} × $x) + ({L2} × $y) => " +
f"({L1} × {x}) + ({L2} × {y}) => {cost}"
)
return cost, "\n\n".join(steps)
View the entire Python script for this task on GitHub.
Elixir
This one was a real challenge. One of them is that Elixir doesn’t really have arrays, it has linked lists, and most of the functions to modify lists expect you to operate on the entire list (or just retrieve, not modify, a value at an index using Enum.at/3
). So in order to modify a single value by index, we have to use Enum.with_index/2
. I came up with a function to accept a list and an index value that will increment the value at that index:
def incrementAt(ints, index) do
ints
|> Enum.with_index() # produces tuples of {value, index}
|> Enum.map(fn
{val, ^index} -> val + 1 # ^ matches on index
{val, _} -> val
end)
end
Similarly, the immutability of Elixir makes using my approach more difficult. I can’t just delete values from maps willy-nilly, so instead of a setMap
function to manipulate the map, I created addToMap/3
and removeFromMap/3
to perform more basic operations.
# get just the indices stored in the map of maps
defp indicesInMap(mapping) do
List.flatten( for i <- Map.values(mapping), do: Map.keys(i) )
end
def fmtInts(ints) do
"@ints = (" <> Enum.join(ints, ", ") <> ")"
end
def addToMap(mapping, intVal, i) do
submap = Map.put(Map.get(mapping, intVal, %{}), i, 1)
Map.put(mapping, intVal, submap)
end
def removeFromMap(mapping, intVal, i) do
submap = Map.delete(Map.get(mapping, intVal, %{}), i)
if submap == %{} do
Map.delete(mapping, intVal)
else
Map.put(mapping, intVal, submap)
end
end
# Increments a value in a list at a given index
def incrementAt(ints, index) do
ints
|> Enum.with_index() # produces tuples of {value, index}
|> Enum.map(fn
{val, ^index} -> val + 1 # ^ matches on index
{val, _} -> val
end)
end
# just remove the old value from the map
# if the new value is maxVal
def reMap(mapping, value, maxVal, index) when value == maxVal do
mapping |> removeFromMap(value - 1, index)
end
# if the number we incremented is less than the max,
# put it back in the mapping
def reMap(mapping, value, _, index) do
mapping
|> removeFromMap(value - 1, index)
|> addToMap(value, index)
end
# stopping case
defp equalize(params = %{indices: indices})
when length(indices) == 0, do: params
# level 2 case
defp equalize(params = %{indices: indices, x: x, y: y})
when length(indices) > 1 and x * 2 >= y do
{i, indices} = List.pop_at(indices, 0)
{j, _} = List.pop_at(indices, 0)
mapping = params[:mapping]
steps = params[:steps]
ints = params[:ints]
# increment the values
ints = incrementAt(ints, i)
ints = incrementAt(ints, j)
steps = steps ++ [
"Level 2: i=#{i}, j=#{j}, so $ints[#{i}] += 1 and " <>
"$ints[#{j}] += 1\n" <> fmtInts(ints)
]
params = %{params | L2: params[:L2] + 1}
mapping = reMap(mapping, Enum.at(ints, i), params[:maxVal], i)
mapping = reMap(mapping, Enum.at(ints, j), params[:maxVal], j)
params = %{params |
indices: indicesInMap(mapping),
mapping: mapping,
steps: steps,
ints: ints
}
equalize(params)
end
# level 1 case
defp equalize(params = %{indices: indices}) do
{i, _} = List.pop_at(indices, 0)
mapping = params[:mapping]
steps = params[:steps]
ints = params[:ints]
# increment the values
ints = incrementAt(ints, i)
steps = steps ++ [
"Level 1: i=#{i}, so $ints[#{i}] += 1\n" <>
fmtInts(ints)
]
params = %{params | L1: params[:L1] + 1}
mapping = reMap(mapping, Enum.at(ints, i), params[:maxVal], i)
params = %{params |
indices: indicesInMap(mapping),
mapping: mapping,
steps: steps,
ints: ints
}
equalize(params)
end
# once the list of ints is empty, return the results
defp makeMapping([], maxVal, mapping, _), do: {maxVal, mapping}
# process the first int off the list and recurse to
# process the rest
defp makeMapping([intVal | ints], maxVal, mapping, index) do
maxVal = Enum.max([intVal, maxVal])
mapping = addToMap(mapping, intVal, index)
makeMapping(ints, maxVal, mapping, index + 1)
end
defp inflectTimes(n) do
case n do
1 -> "time"
_ -> "times"
end
end
defp equalizeArray(ints, x, y) do
{maxVal, mapping} = makeMapping(ints, -1, %{}, 0)
# we don't need to operate on values already at the max
mapping = Map.delete(mapping, maxVal)
params = equalize(%{
indices: indicesInMap(mapping),
mapping: mapping,
maxVal: maxVal,
steps: [],
ints: ints,
L1: 0,
L2: 0,
x: x,
y: y,
})
steps = params[:steps]
l1 = params[:L1]
l2 = params[:L2]
cost = (l1 * x) + (l2 * y)
operations = if l1 > 0 do
[ "Level 1, #{l1} " <> inflectTimes(l1) ]
else
[]
end
operations = if l2 > 0 do
operations ++ [ "Level 2, #{l2} " <> inflectTimes(l2) ]
else
operations
end
steps = steps ++ [
"We performed operation " <>
Enum.join(operations, " and ") <>
"\nSo the total cost would be " <>
"(#{l1} × $x) + (#{l2} × $y) => " <>
"(#{l1} × #{x}) + (#{l2} × #{y}) => #{cost}"
]
{ cost, Enum.join(steps, "\n\n") }
end
I’m sure there’s a more Elixir-y way to accomplish this task by rethinking how I’m processing the data, but I’m saving that for a future exercise.
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-270/packy-anderson