Task 1: 2D Array

You are given an array of integers and two integers $r amd $c.

Write a script to create two dimension array having $r rows and $c columns using the given array.

Example 1

Input: @ints = (1, 2, 3, 4), $r = 2, $c = 2
Output: ([1, 2], [3, 4])

Example 2

Input: @ints = (1, 2, 3), $r = 1, $c = 3
Output: ([1, 2, 3])

Example 3

Input: @ints = (1, 2, 3, 4), $r = 4, $c = 1
Output: ([1], [2], [3], [4])

Approach

Ok, this feels pretty straightforward: we need to loop over the input array and shift off the first $c values to make the first row, then the next $c values to make the next row, until we run out of values. So why are we even given $r to tell us how many rows we should get? I think it’s so we can do some input validation. I’m going to add some additional example cases and some messaging for when we’re provided the incorrect number of values.

For all my output, I’m borrowing the formatmatrix functions I used for PWC 271.

Raku

What wound up stymieing me for a while was how to return the error and the resulting array from the same function. When I tried returning ($error, @array), I’d wind up getting results like [[[1, 2], [3, 4]],] where the result array was the first element of an array. I finally decided to punt and just return the error in the result array, and I would check to see if the first element of the result array was a Str and, if so, print that instead of the array:

sub twoDarray(@ints, $r, $c) {
  if (@ints.elems != $r * $c) {
    return ["Unable to create a two-dimensional array with "
         ~ "$r rows and $c columns\nfrom a list of {@ints.elems} "
         ~ "integers; there must be {$r * $c} integers."];
  }
  my @arr;
  while (@ints) {
    my @row;
    @row.push( @ints.shift ) for 1 .. $c ;
    @arr.push(@row);
  }
  return @arr;
}

sub solution(@ints, $r, $c) {
  my $ints = '(' ~ @ints.join(', ') ~ ')';
  say "Input: \@ints = $ints, \$r = $r, \$c = $c";
  my @arr = twoDarray(@ints, $r, $c);
  if (@arr[0].isa("Str") ) {
    say "";
    say @arr[0];
  }
  else {
    say "Output: {formatMatrix(@arr)}";
  }
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
Example 1:
Input: @ints = (1, 2, 3, 4), $r = 2, $c = 2
Output: [
          [1, 2],
          [3, 4]
        ]

Example 2:
Input: @ints = (1, 2, 3), $r = 1, $c = 3
Output: [
          [1, 2, 3]
        ]

Example 3:
Input: @ints = (1, 2, 3, 4), $r = 4, $c = 1
Output: [
          [1],
          [2],
          [3],
          [4]
        ]

Example 4:
Input: @ints = (1, 2, 3, 4), $r = 3, $c = 1

Unable to create a two-dimensional array with 3 rows and 1 columns
from a list of 4 integers; there must be 3 integers.

Example 4:
Input: @ints = (1, 2, 3, 4), $r = 3, $c = 2

Unable to create a two-dimensional array with 3 rows and 2 columns
from a list of 4 integers; there must be 6 integers.

Perl

However, in Perl I decided to avoid the problem by just returning an arrayref.

sub twoDarray($ints, $r, $c) {
  if (scalar(@$ints) != $r * $c) {
    return "Unable to create a two-dimensional array with "
         . "$r rows and $c columns\nfrom a list of "
         . "@{[scalar @$ints]} integers; there must be "
         . "@{[$r * $c]} integers.";
  }
  my @arr;
  while (@$ints) {
    my @row;
    push @row, shift @$ints for 1 .. $c ;
    push @arr, \@row;
  }
  return undef, \@arr;
}

sub solution($ints, $r, $c) {
  my $int_list = '(' . join(', ', @$ints) . ')';
  say "Input: \@ints = $int_list, \$r = $r, \$c = $c";
  my ($err, $arr) = twoDarray($ints, $r, $c);
  if ($err) {
    say "";
    say $err;
  }
  else {
    say "Output: @{[ formatMatrix($arr) ]}";
  }
}

View the entire Perl script for this task on GitHub.

Python

The Python solution was fun, but not really much different from the Raku and Perl solutions. I just had to make sure I returned an empty array in the error case, or I got ValueError: too many values to unpack (expected 2) when I hit the last two examples.

def twoDarray(ints, r, c):
  if (len(ints) != r * c):
    return (
         "Unable to create a two-dimensional array with "
      + f"{r} rows and {c} columns\nfrom a list of {len(ints)} "
      + f"integers; there must be {r * c} integers.",
      []
    )
  arr = []
  while (ints):
    row = []
    for i in range(c):
      row.append( ints.pop(0) )
    arr.append(row)
  return None, arr

def solution(ints, r, c):
  int_list = '(' + int_join(", ", ints) + ')'
  print(f'Input: @ints = {int_list}, $r = {r}, $c = {c}')
  err, arr = twoDarray(ints, r, c)
  if err:
    print(f'\n{err}')
  else:
    print(f'Output: {formatMatrix(arr)}')

View the entire Python script for this task on GitHub.

Elixir

Elixir, however, is the winner here: the Enum.chunk_every/2 function does all the work. Also, I was able to split the error condition out into a guard (lines 4-12).

  def twoDarray(ints, r, c) when length(ints) != r * c do
    {
      "Unable to create a two-dimensional array with " <>
      "#{r} rows and #{c} columns\nfrom a list of " <>
      "#{length(ints)} integers; there must be #{r * c} " <>
      "integers.",
      []
    }
  end

  def twoDarray(ints, _, c) do
    { nil, Enum.chunk_every(ints, c) }
  end

  def solution(ints, r, c) do
    int_list = "(" <> Enum.join(ints, ", ") <> ")"
    IO.puts("Input: @ints = #{int_list}, $r = #{r}, $c = #{c}")
    {err, arr} = twoDarray(ints, r, c)
    if err do
      IO.puts("\n#{err}")
    else
      IO.inspect(arr)
      IO.puts("Output: " <> formatMatrix(arr) )
    end
  end

View the entire Elixir script for this task on GitHub.

Task 2: Total XOR

You are given an array of integers.

Write a script to return the sum of total XOR for every subset of given array.

Example 1

Input: @ints = (1, 3)
Output: 6

Subset [1],    total XOR = 1
Subset [3],    total XOR = 3
Subset [1, 3], total XOR => 1 XOR 3 => 2

Sum of total XOR => 1 + 3 + 2 => 6

Example 2

Input: @ints = (5, 1, 6)
Output: 28

Subset [5],       total XOR = 5
Subset [1],       total XOR = 1
Subset [6],       total XOR = 6
Subset [5, 1],    total XOR => 5 XOR 1 => 4
Subset [5, 6],    total XOR => 5 XOR 6 => 3
Subset [1, 6],    total XOR => 1 XOR 6 => 7
Subset [5, 1, 6], total XOR => 5 XOR 1 XOR 6 => 2

Sum of total XOR => 5 + 1 + 6 + 4 + 3 + 7 + 2 => 28

Example 3

Input: @ints = (3, 4, 5, 6, 7, 8)
Output: 480

Approach

Ok, let’s unpack this problem. It talks about “every subset of given array”, and that’s the Power Set of the array. Once we have the power set, we loop over the subsets in it and XOR the values together. The examples start by showing the single-element subsets, but the power set starts with the empty set. Fortunately, the empty set has no elements, and the XOR of no elements is 0.

Raku

I remember in Perl there’s a few modules for generating permutations of lists, but I don’t recall there being a handy module in Raku. Fortunately, rolling my own isn’t that hard using the .combinations method on the List class.

And for getting the XOR of each subset? I haven’t been able to say the words reduction metaoperator in a while! Every other time, we’ve been combining the reduction metaoperator ([ ]) wth addition (+) to achieve summing ([+]), but this time we’re using the metaoperator to repeatedly perform the XOR (+^) operator.

sub powerSet(@array) {
  return @array.combinations: 0 .. @array.elems;
}

sub totalXOR(@ints) {
  my $sum = 0;
  for powerSet(@ints) -> @s {
    $sum += [+^] @s;
  }
  return $sum;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: @ints = (1, 3)
Output: 6

Example 2:
Input: @ints = (5, 1, 6)
Output: 28

Example 3:
Input: @ints = (3, 4, 5, 6, 7, 8)
Output: 480

Perl

Things were even easier in Perl, because of Algorithm::Combinatorics‘s subset function and List::AllUtils‘ reduce function. The only snag I hit was when I first ran my script, I got Use of uninitialized value in addition (+) at perl/ch-2.pl line 10. Where was the undefined value? You guessed it: the empty set. So instead of

$sum += reduce { $a ^ $b } @$s;

I had to use the // (logical defined or) to fall back to a value of 0 if reduce returned an undef.

$sum += (reduce { $a ^ $b } @$s) // 0;

use Algorithm::Combinatorics qw( subsets );
use List::AllUtils qw( reduce );

sub totalXOR($ints) {
  my $sum = 0;
  for my $s ( subsets($ints) ) {
    $sum += (reduce { $a ^ $b } @$s) // 0;
  }
  return $sum;
}

View the entire Perl script for this task on GitHub.

Python

In Python, we need to import reduce from the functools module.

from functools import reduce

def powerSet(ints):
  return reduce(lambda r, i: r + [s + [i] for s in r], ints, [[]])

def totalXOR(ints):
  sum = 0
  for s in powerSet(ints):
    sum += reduce(lambda a, b: a ^ b, s, 0)
  return sum

View the entire Python script for this task on GitHub.

Elixir

In my Elixir solution, both of my functions use Enum.reduce/3 to do their work in much the same way the Python solution does. As usual, recursion replaces any looping.

  def powerSet([]), do: []

  def powerSet([i | rest]) do
    list = powerSet(rest)
    [[i] | Enum.reduce(list, list, &[[i | &1] | &2])]
  end

  def totalXOR([], sum), do: sum

  def totalXOR([set | rest], sum) do
    totalXOR(
      rest,
      sum + Enum.reduce(set, 0, &( Bitwise.bxor(&1, &2) ))
    )
  end

  def totalXOR(ints) do
    powerSet(ints) |> totalXOR(0)
  end

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-324/packy-anderson