# Challenge 59 - Lists and Binary XOR

This is Perl Weekly Challenge 059. I wasn’t too jazzed about the tasks in 58, but this one intrigued me from first glance.

### TASK #1 › Linked List

Reviewed by Ryan Thompson You are given a linked list and a value

k. Write a script to partition the linked list such that all nodes less thankcome before nodes greater than or equal tok. 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= 3Expected Output:

1 → 2 → 2 → 4 → 3 → 5

First, an assertion: *All behaviors we would require from a linked list are behaviors that come with Perl’s arrays.* `push`

and `pop`

are `shift`

and `unshift`

come from linked list, and if the pointer to the list head is undef, that means the list is empty. (Or, of course, we lost track of our pointers.)

So, as long as we use the above methods, we can treat a standard Perl array as a linked list. I mean, I *might* pull out my `Node`

code and make a “real” linked list, but I assert that this is more covering yourself than actually useful. So…

```
#!/usr/bin/env perl
use strict;
use warnings;
use utf8;
use feature qw{ postderef say signatures state switch };
no warnings qw{ experimental };
my $k = 3;
my $input = [ 1, 4, 3, 2, 5, 2 ];
say display_ll($input);
my $output = task_1( $k, $input );
say display_ll($output);
sub task_1 ( $k, $array ) {
my $output = [];
my @below ;
my @above ;
while ( $array->@* ) {
my $l = shift $array->@*;
if ( $l < $k ) {
push @below, $l;
next;
}
push @above, $l;
}
push $output->@*, @below, @above;
return $output;
}
sub display_ll($array) {
return join ' -> ', $array->@*;
}
# 1 -> 4 -> 3 -> 2 -> 5 -> 2
# 1 -> 2 -> 2 -> 4 -> 3 -> 5
```

A pure linked-list version exists and has been pushed as a solution. I will likely blog on it later.

### TASK #2 › Bit Sum

Reviewed by Ryan Thompson

Helper FunctionFor this task, you will most likely need a functionf(a,b)which returns the count of different bits of binary representation ofaandb.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 OutputYou 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

There are two cool parts of this one, the **helper function** and the **script output**, as listed above.

You can go a *long* while in programming and not do a lot of what people assume programmers do. I’ve only done things with trees and graphs and a few other *real Computer Science* things in toy/challenge code, but with the higher-level languages I routinely work in, this is rarely necessary. Largely, the need for them was abstracted away years before I got there, and I got there decades ago.

Bitwise operators are things I’ve known existed in Perl since close to when I started, and have I ever had need for them? I don’t *think* so? Not until now, at least.

#### And on to the Truth Tables

`&`

is **bitwise and**, meaning that, if for each space, both bits are true, the result is true.

```
i j i&j
0 0 0
0 1 0
1 0 0
1 1 1
```

`|`

is **bitwise or**, meaning that, if for each space, any bit is true, the result is true.

```
i j i|j
0 0 0
0 1 1
1 0 1
1 1 1
```

Finally (for this blog; there’s many more, such as **NAND**), `^`

is **bitwise exclusive or**, meaning that, if for each space, the bits disagree, the result is true.

```
i j i^j
0 0 0
0 1 1
1 0 1
1 1 0
```

This is *exactly* what is needed for this problem. Well, with some help.

Such as a string representation so we work in terms of ones and zeros.

And summation and splitting might be nice.

And those I do in Perl so much more often.

```
# back to front:
# $i ^ $j - XOR, which is $i or $j but not $i and $j
# sprintf - make a string representation of a
# binary number of the result
# split // - turn '00001111' into [0,0,0,0,1,1,1,1]
# sum - add all the numbers in the array together
sub f ( $i, $j ) {
return sum split //, sprintf '%b', $i ^ $j;
}
```

This crams a lot of power into one line, at the potential cost of readability, but gives us a count of the bitwise difference between two numbers.

(Also, worth saying, the challenge says `f(a,b)`

, but because `sort`

has convinced me to never use `$a`

and `$b`

in my code, I use `$i`

and `$j`

.)

(FORTRAN, I’m told, has implicit typing based on the variable name. Variables starting `'I'..'N'`

were integers unless explicitly declared something else. This, not `i`

meaning `index`

, is why it is so common to do things like `for(i=0;i<10;i++) {...}`

, although it certainly helps. This is also why **“GOD is real, unless declared integer”**)

And now we’re working with the Script Output part of the problem, which specifies that not only are we going to do `1,3`

, but `2,3,4`

and possibly other, longer arrays, and that `2,3,4`

means `[2,3],[2,4],[3,4]`

.

This looks like a job for **CPAN!**.

Because, sure, I *could* pull out and modify my permutations code, and that would be the most portable solution, but Algorithm::Combinatorics exists, so why not use it?

I discovered it by reading an article from Fedora Magazine about Perl that I felt I had to review, and so if it wasn’t as easy as `use Algorithm::Combinatorics qw{combinations}`

, I might’ve rolled my own, but since it’s there?

So, we’re returning `0`

for small arrays, only getting to work with arrays of 2 or more. There’s only one combination you can have with an array of 2 values, but if it saves us a special case, let’s go for it.

```
sub f2 ( @array ) {
return 0 if scalar @array < 2;
my $sum = 0;
for my $combo ( combinations( \@array, 2 ) ) {
my $f = f( $combo->@* );
$sum += $f;
}
return $sum;
}
```

The whole thing:

```
#!/usr/bin/env perl
use strict;
use warnings;
use utf8;
use feature qw{ postderef say signatures state switch };
no warnings qw{ experimental };
use List::Util qw{ sum };
use Algorithm::Combinatorics 'combinations';
use JSON;
my $json = JSON->new->canonical->allow_nonref;
say f2();
say f2(1);
say f2( 1, 3 );
say f2( 2, 3, 4 );
say f2( 2, 3, 4, 5 );
say f2( 99,101 );
sub f2 ( @array ) {
return 0 if scalar @array < 2;
my $sum = 0;
for my $combo ( combinations( \@array, 2 ) ) {
my $f = f( $combo->@* );
$sum += $f;
}
return $sum;
}
sub f ( $i, $j ) {
return sum split //, sprintf '%b', $i ^ $j;
}
```

And the output:

```
# say f2();
0
# say f2(1);
0
# say f2( 1, 3 );
1
# say f2( 2, 3, 4 );
6
# say f2( 2, 3, 4, 5 );
12
# say f2( 99,101 );
2
```

### End Note

I don’t want to say more until I know more, but best of luck to some of my favorite members of the Perl family, irishpebbles and Ptolemarch.