Perl Weekly Challenge: Elements are Special

Posted on by

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