RabbitFarm

2022-05-08

Bitwise AndSums and Skip Summations: Somewhat Complicated Uses of Map

The examples used here are from The Weekly Challenge problem statement and demonstrate the working solution.

Part 1

You are given a list of numbers. Write a script to calculate the sum of the bitwise & operator for all unique pairs.

Solution


use strict;
use warnings; 

sub sum_bitwise{
    my $sum = 0;
    for my $i (0 .. @_ - 2){
        my $x = $_[$i];
	map {$sum += ($x & $_)} @_[$i + 1 .. @_ - 1];
    }
    return $sum; 
}

MAIN:{
    print sum_bitwise(1, 2, 3) . "\n";  
    print sum_bitwise(2, 3, 4) . "\n";
}  

Sample Run


$ perl perl/ch-1.pl
3
2

Notes

Since most of the code for both parts of the challenge was fairly straightforward I thought it was worthwhile to concentrate on how I use map. In both cases are somewhat non-trivial. Here map is used in lieu of a nested loop. Effectively it is equivalent but the resulting code is more compact. The for loop iterates over the array of numbers. At each iteration the current number is saved as $x. We then need to work pairwise through the rest of the array. To do this we use map over the slice of the array representing the elements after $x. Within the for loop/map $sum is continuously updated with the bitwise & results as required.

Part 2

Given a list of numbers @n, generate the skip summations.


use strict;
use  warnings;

sub skip_summations{
    my @lines = ([@_]);
    for my $i (1 .. @_ - 1){
        my @skip = @{$lines[$i - 1]}[1 .. @{$lines[$i - 1]} - 1];
        my $line = [map {my $j = $_; $skip[$j] + unpack("%32I*", pack("I*", @skip[0 .. $j - 1]))} 0 .. @skip - 1];
        push @lines, $line;
    }
    return @lines;
}

MAIN:{
    for my $line (skip_summations(1, 2, 3, 4, 5)){
        print join(" ", @{$line}) . "\n";
    }
    print "\n";
    for my $line (skip_summations(1, 3, 5, 7, 9)){
        print join(" ", @{$line}) . "\n";
    }
}

Sample Run


$ perl perl/ch-2.pl
1 2 3 4 5
2 5 9 14
5 14 28
14 42
42

1 3 5 7 9
3 8 15 24
8 23 47
23 70
70

Notes

Again map is used in place of a nested loop. With the use of pack/unpack we further replace work that would take place inside yet another loop. While much more concise it is reasonable to concede a slight loss of readability, for the untrained eye anyway. The map in the code above works over a list of numbers representing array indices of the previously computed line of summations. For each element we get the slice of the array representing the ones before it and then use pack/unpack to get the sum which is then added to the current element. Each use of map here generates the next line and so we enclose the map in square brackets [] to place bthe results in an array reference which is the pushed onto the array of alllines to be returned.

References

Challenge 163

posted at: 13:52 by: Adam Russell | path: /perl | permanent link to this entry

The Weekly Challenge 163 (Prolog Solutions)

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

Part 1

You are given a list of numbers. Write a script to calculate the sum of the bitwise & operator for all unique pairs.

Solution


and(N, X, And):-
    And is N /\ X.
sum_and([], 0).
sum_and([H|T], SumAnd):-
    sum_and(T, Sum),
    maplist(and(H), T, Ands),
    sum_list(Ands, AndSum),
    SumAnd is Sum + AndSum.

Sample Run


$ gprolog --consult-file prolog/ch-1.p 
| ?- sum_and([1, 2, 3], SumAnd).

SumAnd = 3

yes
| ?- sum_and([2, 3, 4], SumAnd).   

SumAnd = 2

yes
| ?- sum_and([1, 2, 3], 99).    

no
| ?- sum_and([1, 2, 3], 3). 

yes

Notes

It is not too often you see the bitwise operators used in Prolog code! I am kind of a fan of the /\ operator, I mean, it even looks like an upper case 'A', right?

Other than the novelty of the bitwise and I found this task to be well suited for the use of maplist/3 for computing the pairwise and operations across the list of numbers. This is something of a "nested loop" in the sense that recursively the head of the list of numbers is removed and upon each recursive step the maplist is re-performed on the increasingly shorter list.

Part 2

Given a list of numbers, generate the skip summations.

Solution


skip_sum(Numbers, N, Sum):-
    append(Left, [N|_], Numbers),
    sum_list(Left, SumLeft),
    Sum is N + SumLeft.

skip_summations(Numbers, Summations):-
    skip_summations(Numbers, [Numbers], Summations).
skip_summations([], Summations, Summations).
skip_summations([_|T], SummationsAccum, Summations):-
    maplist(skip_sum(T), T, Sums),
    skip_summations(Sums, [Sums|SummationsAccum], Summations).

print_summation(S):-
    write(S),
    write(' ').
print_summations([]).
print_summations([H|T]):-
    print_summations(T),
    maplist(print_summation, H), nl.

Sample Run


$ gprolog --consult-file prolog/ch-2.p 
| ?- skip_summations([1, 2, 3, 4, 5], Summations), print_summations(Summations).
1 2 3 4 5 
2 5 9 14 
5 14 28 
14 42 
42 


Summations = [[],[42],[14,42],[5,14,28],[2,5,9,14],[1,2,3,4,5]] ? 

yes
| ?- skip_summations([1, 3, 5, 7, 9], Summations), print_summations(Summations).      
1 3 5 7 9 
3 8 15 24 
8 23 47 
23 70 
70 


Summations = [[],[70],[23,70],[8,23,47],[3,8,15,24],[1,3,5,7,9]] ? 

yes
| ?- skip_summations([1, 3, 5, 7, 9], [[],[70],[23,70],[8,23,47],[3,8,15,24],[1,3,5,27,9]]).

no
| ?- skip_summations([1, 3, 5, 7, 9], [[],[70],[23,70],[8,23,47],[3,8,15,24],[1,3,5,7,9]]). 

true ? 

yes

Notes

Much like the task above we use a maplist/3 within a recursive step. Here the maplist/3 is used to do the partial sums for each "line" of the output. There is also a maplist/2 used to print the output lines with a space between each element.

Satisfyingly, as shown above, the same code not only generates the skip summations but also validates them as well. This sort of intrinsic Prolog behavior brings joy!

References

Challenge 163

posted at: 13:52 by: Adam Russell | path: /prolog | permanent link to this entry