PWC 373 Task 2: Let's Dance to List Division

The task title reminded me of the song Let's Dance to Joy Division. Oddly applicable lyrics for a blog about programming: "But I worked something out last night that changed this little boy's brain, a small piece of advice that took 22 years in the make, and I will break it for you now. Please learn from my mistakes." And who doesn't love a wombat?

Task Description

You are given a list and a non-negative integer, $n. Write a script to divide the given list into $n equal parts. Return -1 if $n is more than the size of the list.

Example 1

Input: @list = ( 1,2,3,4,5), $n = 2
Output: ((1,2,3), (4,5))

• 5 / 2 = 2 remainder 1. The extra element goes into the first chunk.

Example 2

Input: @list = (1,2,3,4,5,6), $n = 3
Output: ((1,2), (3,4), (5,6))

• 6 / 3 = 2 remainder 0.

Example 3

Input: @list = (1,2,3), $n = 2
Output: ((1,2), (3))

Example 4

Input: @list = (1,2,3,4,5,6,7,8,9,10), $n = 5
Output: ((1,2), (3,4), (5,6), (7,8), (9,10))

Example 5

Input: @list = (1,2,3), $n = 4
Output: -1

Example 6

Input: @list = (72,57,89,55,36,84,10,95,99,35), $n = 7;
Output: ((72,57), (89,55), (36,84), (10), (95), (99), (35))

Elaboration

There's some simple modulo division here, and then a decision about what to do if it doesn't divide evenly into $n chunks. We could put the remainder into a chunk of its own, ignore the remainder, or we could distribute the leftovers in some way that feels balanced -- here, the specification implies that the bigger divisions should go at the front of the list.

Handling an invalid input (where $n is too big) by returning -1 instead of an array is a code smell. Having a function that returns different types of things is awkward to handle and error-prone. It would be more consistent to either throw an exception, or return an out-of-range value of the same type, such as an empty array or a null reference. But that wanker Kevin with his six months of Javascript experience got promoted to project manager for some reason <cough/>nepotism<cough> and that's the requirement we have.

This task has six examples, and usually we're given five. Is there some significance to this? Example 6 doesn't seem to add any new information beyond what we've already been given. But then we notice that the numbers could be ASCII characters, spelling "H9Y7$T?_c#". I'm pretty sure this is Kevin's password. Watch your back, Kevin.

To the CodeMobile, Robin!

sub listDivision($list, $n)
{
    my $size = @$list;
    return -1 if $n > $size;

    my $chunk = floor($size / $n);
    my $extra = $size % $n;
    my @answer;

    while ( $extra-- ) { push @answer, [ splice(@$list, 0, $chunk + 1) ]; }
    while ( @$list   ) { push @answer, [ splice(@$list, 0, $chunk    ) ]; }
    return \@answer;
}

The input parameters are an array and a number, which forces us to confront the way that Perl passes arguments as a flat list. Here, I've chosen to pass an array reference for $list instead of an array, which accomplishes two things: it removes the flat list problem to make it obvious which parameter is $n, and it's more efficient than passing a copy of the array. I could have also passed the parameters in the other order, but "project manager" Kevin said according to ChatGPT and Claude it had to be in this order, so yeah, that's that then.

Time to be serious. We dispense with the special case of returning -1 (more on that later). Then we calculate the quantities involved, and set up an array for producing the answer, initially empty.

The answer has two segments: a head part where there might be one extra element, and the tail part where the segments are of the calculated chunk size. One while loop ticks off the extra-sized chunks, and the second while loop completes the division.

To grab a group of contiguous elements from a list, the splice function seems like the obvious thing to do. Each splice is surrounded with [] so that the chunks are treated as array references. An alternative would have been to take an array slice, but that would introduce index variables for the range being sliced, which looks and feels more complicated and error-prone.

splice reduces the size of the list every time it's called, so the second while loop can use the size of $list as its condition. However, we are destroying $list as we go, so the calling function needs to be aware that the array it passed in is no longer valid. If it were important to keep the original list, a copy would need to be made either from the caller, or near the beginning of listDivision().

Let's think a moment about how to use this function. When it's called it could return either an array of arrays (references actually), or it could return a scalar -1. Here's how I wanted to write the script to use this function, using -n as a command-line option to get that parameter:

use GetOpt::Long;
my $N = 1;
GetOptions("n:i" => \$N);
my $div = listDivision([@ARGV], $N);
say showAofA($div);

where showAofA() is a function that formats the array of arrays into a parenthesized list of comma-separated lists, as in the examples.

However, $div isn't always a reference; sometimes it's a scalar -1. That throws up an ugly error about trying to use a scalar value as a reference. The way to check what's behind a variable in Perl is to use the ref function. It will give a string identifying the variable type, or, for a scalar, it will give an empty string. In perl, an empty string counts as false. So, to satisfy the requirement, the script needs to test whether ref($div) is empty:

say ( ref($div) ? showAofA($div) : $div );

What I probably should have done is change listDivision so that it consistently returns an array reference, but for the invalid case, throws an error. Variations on try/catch have been available as modules in Perl for decades, but it finally (see what I did there?) became official in version 5.38. That simplifies the usage of the function (if you consider try/catch simpler, which some consider a debatable topic).

try          { say showAofA( listDivision([@ARGV], $N) ); }
catch ( $e ) { say "-1" }

To make the function throw an exception, we only need to change the early return from the function into a die:

sub listDivision($list, $n)
{
    my $size = @$list;
    die "N out of range (must be <= $size)" if $n > $size;
    # [ ... ]

That's cleaner, but it slightly complicates the unit testing, because now we have to test for exceptions. The incantation is:

sub runTest
{
    use Test2::V0;
    use Test2::Tools::Exception;
    # [Test cases that should work
    is( listDivision([1,2,3], 1), [[1,2,3]], "One chunk");
    # [ ... ]
    # Test things that throw exceptions
    like ( dies { listDivision( [1,2,3], 4) }, qr/out of range/);

The dies function returns the exception string that results from trying to execute a code block, and like does a pattern match against the expected exception.

And finally, to tidy up a loose end, here's the showAofA() function.

sub showAofA($ref)
{
    return '('. join(',', map { '('.join(',', $_->@*).')' } $ref->@*) .')';
}

Let's take a bunch of punctuation out of that so that we can see the structure:

return ( join( map { join } ) ref )

$ref is a reference to an array of references; hence, $ref->@* is de-referencing it to yield a list of array references.

Each of those array references is then transformed by map. Inside the map {} block, $_ refers to one of the inner arrays, so we de-reference that ($_->@*) to get a list of numbers, which we will join into a comma-separated string. Wrap that with a pair of parentheses, and out of the map comes the inner lists formatted as needed.

Now each of the inner lists is a string. The outer join inserts commas to make it a list of lists, and finally we wrap the whole thing in parentheses to complete the string.