Jared Martin

PWC Task #1, Linked List

jaredor submission for Task #1

Partitioning an input array into a @lower and @upper array based on a pivot element, $k, and then recombining into an output array (@lower, @upper) is pretty easy, e.g.,

say join(' ', (grep { $_ < $k } @ARGV), (grep { $k <= $_ } @ARGV));

A linked list can be collapsed into an array easily enough, so the challenge here (for me) is to add a little extra in the handling that could be useful in the future (because I always steal from myself ;-)

So maybe the little extra is this: Once a link is made it won't be copied.

I started explaining everything and it started feeling like I was writing a very boring novel. Below I'll just stick to the link logic.

Details

Input

There is one command line option:

--k

Specify the pivot point, k, per the problem instructions. [REQUIRED]

The arguments are the elements of the chain, in order, from HEAD to TAIL, since I like to make things as easy for myself as possible.

Link Logic

After validation of input options and arguments, make the input linked list.

Making the input linked list is a simple loop with the right-to-left assignment associativity that perl does so well:

$ll_curpt = ( $ll_curpt->[1] = make_link $_ ) for @ARGV;

1. Make the link from the given list element, and then
2. assign that link to the link pointer of the current link,
   ( $ll_curpt->[1] = make_link $_ )
3. The returned result of an assignment is whatever was assigned, so capture that in parens and assign it as the new value to the pointer to the current link,
   $ll_curpt = ( *** )
4. ... and you're ready to start over with the next element in the list.

Once the linked list is completed, we drop the initial HEAD element. Because of the way the links are constructed, you drop with a pop:

$ll_input = pop @$ll_input;

This pattern will be repeated in the partitioning code that follows.

So immediately partition the linked list into a "less than" linked list and a "greater than or equal to" linked list based on the partitioning value, $k, given. The code has the same basic outline as before, but this time there are two pointers to the two linked lists and this time we are walking a linked list.

while (@$ll_input) {
   my $curr_ptr = $ll_input->[0] < $k ? \$lt_curpt : \$ge_curpt;
   $ll_input = ( $$curr_ptr = ( $$curr_ptr->[1] = $ll_input ) )->[1];
}

• Walking a linked list is a snap: Just go from link to link until the next link (as pointed to by the current input linked list pointer, $ll_input, is an empty array:
  while (@$ll_input) { *** }
• Decide which linked list will get the current input list based on the comparison to the pivot value, $k, note that this assignment takes a reference of the appropriate pointer.
      my $curr_ptr = $ll_input->[0] < $k ? \$lt_curpt : \$ge_curpt;
• On the following line the two assignments inside the outer parentheses are exactly like the two assignments when creating the input linked list above; however, since there is no link being made, but a link being reassigned, we use $ll_input instead of make_link $_:
      ( $$curr_ptr = ( $$curr_ptr->[1] = $ll_input ) )
• By happy circumstance, the returned result from those assignments is the $ll_input link itself, so reassign $ll_input to its following link; this is how the linked list is walked.
  $ll_input = ( *** )->[1];

The one thing that is "new" compared to the creation of the input list, is that we need to ensure our two new linked lists both end with an empty array. One of these lists always will, and the other won't. The easiest thing to do is to just set both properly. Both of the current pointers to the new linked lists are pointing to their last links, so the assignment is straightforward and simple:
( $lt_curpt->[1], $ge_curpt->[1] ) = ( NULL, NULL );

Output

Just like the problem description: Print out the partitioned link list data in order.

BTW, all the code ugliness above is mine, but for my ability to think along the lines of perl grammar, I owe a debt to Modern Perl, which is one of my faves.

PWC Task #2, Bit Sum

jaredor submission for Task #2

I'm going to talk about my first solution, which led to my second solution (linked above). I'm going to display the whole script since there's not much to it. All the magic comes from pack and unpack as well as a short and sweet explanation that tied it all together.

Details

First Version Code

#!/usr/bin/env perl

use v5.012;
use warnings;
use Config;
use List::Util qw(all sum);

die "This script requires one or more positive integer arguments."
  unless @ARGV;

die "Not all arguments to the script are positive integers."
  unless all { /\A [1-9] \d* \Z/xms } @ARGV;

my ( $LL, $NN ) =
  defined $Config{longlongsize}
  ? ( 8 * $Config{longlongsize}, 'Q' )
  : ( 8 * $Config{longsize}, 'L' );

my @nums = map { pack "${NN}", $_ } @ARGV;

my ( @diffbits, $num );
while ( $num = pop @nums ) {
        push @diffbits, unpack( "%${LL}b*", $num ^ $_ ) for @nums;
}
say @diffbits ? sum @diffbits : 0;

Input

Input is just positive integers given on the command line. Minimal validation is needed for this. I note that by saying "positive integer" zero must be excluded on input. In developing the code I should have allowed zero so I could have done quick tests, such as giving the single argument, 31, and getting 5 back. Instead I wound giving the two arguments 31 and 1 and getting 4 back. Only while writing this paragraph up did I realize I was needlessly adding to my cognitive load. Barely squeaked by ;-)

Details

Config Stuff

This is tacit admission that only positive integers that fit into the largest unsigned integer data type available will be considered. I could have weaseled out and gone with the safe choice of a 32-bit unsigned integer, but since I was restricting the problem domain, I figured I should make the effort to be maximally inclusive.

Transform Input

A one-liner explicitly packs each argument into a one-word unsigned integer and holds them all in an array.

Do the Diff

Perl's XOR returns a word that captures the different bits of its two arguments. Since the arguments are the same length there is no need to pad anything. The last example in the unpack documentation is exactly the checksum we need. We go through the array of packed integers in an "N choose 2" double loop, with each pass adding to the checksum array.

Output

The checksum array is summed and printed at the end. The only special case is if there was only one integer given for input: There can be no bit difference with only one integer, so the result returned must be zero.

Nagging Guilt

As I was cleaning up this code, it reduced down so much that I thought maybe I should make it work for indefinitely large positive integers. Fortunately, perl has the bigint library, so I decided to give it a go.

• A bigint integer handles basic mathematical operations easily, but
• it does not do what you want when handing a bigint integer to pack
• I had to write a small subroutine, num2bitstr, to convert an arbitrarily large integer into packed chunks of unsigned integers that were concatenated into a bit string. It wasn't until I got to this point that I realized that I didn't have to have the overall bit string be the binary representation of the input number: Just as long as the "chunks" of the number were converted to binary in a consistent way, the checksum of the XOR would be the same.
• Gratifyingly, the XOR on different sized bit strings works as you would desire: as if the deficit length of the short bit string was padded with 0-bits.

I would have loved to turn a bigint integer into a bit string in one go instead of iteratively. If anyone knows how, let me know please.