RabbitFarm
2025-06-08
Two Dimensional XOR Not?
The examples used here are from the weekly challenge problem statement and demonstrate the working solution.
Part 1: 2D Array
You are given an array of integers and two integers $r and $c. Write a script to create two dimension array having $r rows and $c columns using the given array.
The core of the solution is contained in a main loop. The resulting code can be contained in a single file.
-
sub create_array{
my($i, $r, $c) = @_;
my @a = ();
for (0 .. $r - 1){
my $row = [];
for (0 .. $c - 1){
push @{$row}, shift @{$i};
}
push @a, $row;
}
return @a;
}
◇
-
Fragment referenced in 1.
Just to make sure things work as expected we’ll define a few short tests. The double chop is just a lazy way to make sure there aren’t any trailing commas in the output.
-
MAIN:{
my $s = q//;
$s .= q/(/;
do{
$s.= (q/[/ . join(q/, /, @{$_}) . q/], /);
} for create_array [1, 2, 3, 4], 2, 2;
chop $s;
chop $s;
$s .= q/)/;
say $s;
$s = q//;
$s .= q/(/;
do{
$s.= (q/[/ . join(q/, /, @{$_}) . q/], /);
} for create_array [1, 2, 3], 1, 3;
chop $s;
chop $s;
$s .= q/)/;
say $s;
$s = q//;
$s .= q/(/;
do{
$s.= (q/[/ . join(q/, /, @{$_}) . q/], /);
} for create_array [1, 2, 3, 4], 4, 1;
chop $s;
chop $s;
$s .= q/)/;
say $s;
}
◇
-
Fragment referenced in 1.
Sample Run
$ perl perl/ch-1.pl ([1, 2], [3, 4]) ([1, 2, 3]) ([1], [2], [3], [4])
Part 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.
This is another short one, but with a slightly more involved solution. We are going to compute the Power Set (set of all subsets) of the given array of integers and then for each of these sub-arrays compute and sum the XOR results.
The main section is just some basic tests.
-
MAIN:{
say calculate_total_xor 1, 3;
say calculate_total_xor 5, 1, 6;
say calculate_total_xor 3, 4, 5, 6, 7, 8;
}
◇
-
Fragment referenced in 4.
-
sub calculate_total_xor{
my $total = 0;
for my $a (power_set @_){
my $t = 0;
$t = eval join q/ ^ /, ($t, @{$a});
$total += $t;
}
return $total;
}
◇
-
Fragment referenced in 4.
The Power Set can be computed by using a binary counter. Let’s say we have N elements of the set. We start at 0 x N and continue to 1 x N. At each iteration we compose a subarray by including the ith element from the original array if the ith bit is set. Actually, we arent going to start at 0 x N because we want to exclude the empty set for the purposes of the later XOR computation.
-
sub power_set{
my @a = ();
for my $i (1 .. 2 ** @_- 1){
my @digits = ();
for my $j (0 .. @_ - 1){
push @digits, $_[$j] if 1 == ($i >> $j & 1);
}
push @a, \@digits;
}
return @a;
}
◇
-
Fragment referenced in 4.
Sample Run
$ perl perl/ch-2.pl 6 28 480
References
Power Set Defined
Power Set Calculcation (C++) from TWC 141
The Weekly Challenge 324
Generated Code
posted at: 12:36 by: Adam Russell | path: /perl | permanent link to this entry