laurent_r

These are some answers to the Week 59 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a few hours. This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.

Task 1: Linked List Partition

You are given a linked list and a value k. Write a script to partition the linked list such that all nodes less than k come before nodes greater than or equal to k. Make sure you preserve the original relative order of the nodes in each of the two partitions.

For example:

Linked List: 1 → 4 → 3 → 2 → 5 → 2

k = 3

Expected Output: 1 → 2 → 2 → 4 → 3 → 5.

A linked list is a linear collection of data items, which are often called nodes, in which each data item holds a value (or several values) and a link to the next item of the collection. Each node points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence. Usually, each node contains some data and a reference (in other words, a link) to the next node in the sequence. This structure is very useful in low-level languages such as C, since it allows for easy insertion or removal of elements at any position in the sequence.

Now, both Perl and Raku make it possible to easily add or remove data items at any position in an array. Therefore, I do not see any reason to implement a low-level linked list in these languages. In the course of the two last Perl Weekly Challenges, I showed how a binary tree could be implemented as a simple flat array with an implicit data structure. It would be a regression to bend over backward and implement a linked-list in Perl or Raku. And it would be a case of over-engineering. In brief, I’ll use simple arrays for this task.

However, for the sake of completeness, I’ll show a brief implementation of actual linked lists in Perl. But I do not recommend using it.

Linked List Partition in Raku

The partition subroutine simply feeds two arrays with values less than k or values greater than or equal to k, and returns merged data in the proper order.

use v6;

sub partition ($k, @list) {
    my @before = grep {$_ < $k}, @list;
    my @after = grep {$_ >= $k}, @list;
    return |@before, |@after;
}

sub MAIN ($k, Str $list-str = "1 4 3 2 5 2") {
    my @list = $list-str.comb(/\d+/);
    my @result = partition $k, @list;
    say @result.join(" → ");
}

This displays the following output:

$ perl6 linked1.p6 3
1 → 2 → 2 → 4 → 3 → 5

$ perl6 linked1.p6  4 "3 5 4 5 8 7 9 2"
3 → 2 → 5 → 4 → 5 → 8 → 7 → 9

However, it can be made simpler and possibly slightly more efficient using the classify built-in function of Raku as shown in this very simple example:

use v6;

my $k = 3;
my @vals = <1 4 3 2 5 2>;
my %out = classify { $_ < $k ?? 'before' !! 'after'}, @vals;
say join " → ", |%out<before>, |%out<after>;

This duly prints the correct result:

$ perl6 linked2.p6
1 → 2 → 2 → 4 → 3 → 5

We could even reduce it to a Raku one-liner:

$ perl6 -e 'say join " ", (classify { $_ < 3 ?? "b" !! "a" }, <1 4 3 2 5 2>)<b a>'
1 2 2 4 3 5

Similarly, we could use the categorize method and an method-invocation syntax:

$ perl6 -e '<1 4 3 2 5 2>.categorize({ $_ < 3 ?? "b" !! "a" })<b a>.join(" ").say'
1 2 2 4 3 5

Linked List Partition in Perl

This is a Perl port of the first Raku solution above, with a partition subroutine to split the input into two arrays:

use strict;
use warnings;
use feature "say";

sub partition {
    my $k = shift;
    my @before = grep {$_ < $k} @_;
    my @after = grep {$_ >= $k} @_;
    return @before, @after;
}

my $k = shift;
my $list_str = shift // "1 4 3 2 5 2";
my @list = $list_str =~ /\d+/g;
my @result = partition $k, @list;
say join " → ", @result;

Two execution examples:

$ perl linked1.pl 3
1 → 2 → 2 → 4 → 3 → 5

$ perl linked1.pl 3 "1 4 3 4 5 6 7 2 1"
1 → 2 → 1 → 4 → 3 → 4 → 5 → 6 → 7

An Actual Linked List

As I said before, I really do not recommend the implementation of an actual linked list to solve this problem.

But, just in case you think that I balk at doing it because I don’t know how to do it, or more generally in the event that you would like to see how this could be implemented, this is one possible way to do it, using nested hashes:

use strict;
use warnings;
use feature qw/say/;
use Data::Dumper;

sub create_linked_list {
    my $input = shift;
    my $L;
    for my $val (reverse split / /, $input) {
        my $pt = { value => $val, next => $L };
        $L = $pt;
    }
    return $L;
}        

my $k = shift;
my $list_str = shift // "1 4 3 2 5 2";
my $list = create_linked_list $list_str; 
# say Dumper $list; 
my (@before, @after);
while (1) {
    last unless defined $list->{value};
    my $temp = $list->{value};
    if ($temp < $k) {
        push @before, $temp;
    } else {
        push @after, $temp;
    }
    $list = $list->{next}
}
say join " → ", @before, @after;

And this is a sample run:

$ perl  linked2.pl 3
1 → 2 → 2 → 4 → 3 → 5

But again, creating an actual linked list for the problem is, in my humble view, technological overkill.

Task 2: Bit Sum

Helper Function: for this task, you will most likely need a function f(a,b) which returns the count of different bits of binary representation of a and b.

For example, f(1,3) = 1, since:

Binary representation of 1 = 01

Binary representation of 3 = 11

There is only 1 different bit. Therefore the subroutine should return 1. Note that if one number is longer than the other in binary, the most significant bits of the smaller number are padded (i.e., they are assumed to be zeroes).

Script Output: your script should accept n positive numbers. Your script should sum the result of f(a,b) for every pair of numbers given.

For example, given 2, 3, 4, the output would be 6, since f(2,3) + f(2,4) + f(3,4) = 1 + 2 + 3 = 6

Bit Sum in Raku

In the compare subroutine, we just produce a binary string (eight digits) for each input number, split the binary string into arrays, loop through both arrays at the same time to compare the individual bits. And we use the combinations built-in method to build every pair of numbers:

use v6;

sub compare (UInt $m, UInt $n) {
    my @a = $m.fmt('%08b').comb;
    my @b = $n.fmt('%08b').comb;
    my $cnt = 0;
    for 0..7 -> $i {
        $cnt++ if @a[$i] != @b[$i];
    }
    return $cnt;
}
my $diff = 0;
for @*ARGS.combinations(2) -> $seq {
    $diff += compare +$seq[0], +$seq[1];
}

say $diff;

This program displays the following output:

$ perl6 bit_sum.p6 2 3 4
6
$ perl6 bit_sum.p6 32 64 137
10

Using the Raku built-in Z or zip operator can make the compare subroutine more compact:

sub compare (UInt $m, UInt $n) {
    my $cnt = 0;
    for $m.fmt('%08b').comb Z $n.fmt('%08b').comb -> [$l, $r] {
        $cnt++ if $l != $r;
    }
    return $cnt;
}

Bit Sum in Perl

This is a port to Perl of the first Raku solution above, with a compare subroutine to find out the number of different bits between two numbers. Since Perl doesn’t have a built-in combinations function, we just use two nested for loops to generate every pair of numbers:

use strict;
use warnings;
use feature "say";

sub compare {
    my ($m, $n) = @_;
    my @a = split //, sprintf "%08b", $m;
    my @b = split //, sprintf "%08b", $n;
    my $cnt = 0;
    for my $i (0..7) {
        $cnt++ if $a[$i] != $b[$i];
    }
    return $cnt;
}
my $diff = 0;
my @nums = @ARGV;
for my $i (0..$#nums) {
    for my $j (($i+1) .. $#nums) {
        $diff += compare $nums[$i], $nums[$j];
    }
}
say $diff;

Sample output:

$ perl bit_sum.pl 2 3 4
6

$ perl bit_sum.pl 32 64 137
10

Wrapping up

The next week Perl Weekly Challenge is due to start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on Sunday, May 17, 2020. And, please, also spread the word about the Perl Weekly Challenge if you can.