RabbitFarm

2025-06-08

The Weekly Challenge 324 (Prolog Solutions)

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.

Our solution is short and will be contained in a single file that has the following structure.

"ch-1.p" 1≡


⟨create two dimensional array 2 ⟩
◇

We’ll use a straightforward recursive approach.

⟨create two dimensional array 2 ⟩≡


create_array(_, 0, _, []).
create_array(L, Rows, Columns, [Row|T]) :-
create_row(L, Columns, Row, L1),
R is Rows - 1,
create_array(L1, R, Columns, T).

create_row(L, 0, [], L).
create_row([H|T], Columns, [H|Row], L) :-
C is Columns - 1,
create_row(T, C, Row, L).
◇

Fragment referenced in 1.

Sample Run
$ gprolog --consult-file prolog/ch-1.p 
| ?- create_array([1, 2, 3, 4], 2, 2, TwoDArray). 
 
TwoDArray = [[1,2],[3,4]] ? 
 
yes 
| ?- create_array([1, 2, 3], 1, 3, TwoDArray). 
 
TwoDArray = [[1,2,3]] ? 
 
yes 
| ?- create_array([1, 2, 3, 4], 4, 1, TwoDArray). 
 
TwoDArray = [[1],[2],[3],[4]] ? 
 
yes 
| ?-

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.

GNU Prolog has a sublist/2 predicate which will generate all needed subsets on backtracking. We’ll use this inside of a findall/3. The code required is fairly small, although we’ll define a couple of small utility predicates.

"ch-2.p" 3≡


⟨subtotal 6 ⟩
⟨compute total xor 4 ⟩
⟨combine xors 5 ⟩
◇

⟨compute total xor 4 ⟩≡


total_xor(L, Total):-
findall(S, (
sublist(S, L),
\+ S = []
), SubLists),
maplist(combine, SubLists, Combined),
maplist(subtotal, Combined, SubTotals),
sum_list(SubTotals, Total).
◇

Fragment referenced in 3.

⟨combine xors 5 ⟩≡


combine([], 0).
combine([H|T], Combined):-
combine(T, Combined1),
Combined = xor(H, Combined1).
◇

Fragment referenced in 3.

⟨subtotal 6 ⟩≡


subtotal(Combined, X):-
X is Combined.
◇

Fragment referenced in 3.

Sample Run
$ gprolog --consult-file prolog/ch-2.p 
| ?- total_xor([1, 3], Total). 
 
Total = 6 
 
yes 
| ?- total_xor([5, 1, 6], Total). 
 
Total = 28 
 
yes 
| ?- total_xor([3, 4, 5, 6, 7, 8], Total). 
 
Total = 480 
 
yes 
| ?-

References

The Weekly Challenge 324
Generated Code

posted at: 14:40 by: Adam Russell | path: /prolog | permanent link to this entry

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.

"ch-1.pl" 1≡


use v5.40;
⟨create 2d array 2 ⟩
⟨main 3 ⟩
◇

⟨create 2d array 2 ⟩≡


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 3 ⟩≡


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.

"ch-2.pl" 4≡


use v5.40;
⟨power set calculation 7 ⟩
⟨calculate the total XOR 6 ⟩
⟨main 5 ⟩
◇

The main section is just some basic tests.

⟨main 5 ⟩≡


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.

⟨calculate the total XOR 6 ⟩≡


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.

⟨power set calculation 7 ⟩≡


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