Perl Weekly Challenge 129: Add Linked Lists

Input: L1 = 1 -> 2 -> 3
       L2 = 3 -> 2 -> 1
Output: 4 -> 4 -> 4

Input: L1 = 1 -> 2 -> 3 -> 4 -> 5
       L2 =           6 -> 5 -> 5
Output:     1 -> 3 -> 0 -> 0 -> 0

This challenge had me almost throw up in disgust. Linked list? Seriously? In Perl (and many other modern languagues), most things for which you might want to use a linked list, arrays will work very well. There are some problems for which linked lists work very well, and arrays won't — just take a look at Advent of Code, might manages to construct such a challenge most years.

For this challenge, using linked list is just, uhm, silly to say it mildly. Using linked list to add two numbers is about as useful as writing a novel with using the letter e. (This has been done in the past, but we don't see the top-10 reading list being flooded with e-free novels).

To add insult to the injury, our linked lists run from most significant digit to least, but addition goes from least significant digit to most, meaning we have to process a linked list back to front. How stupid is that?

Then there is the hint. Which starts with feel free to come up with your own unique way to deal with the task. And then has a list of things it expects to be done. Which is it? Are we free to come up with our unique way, or are we to do the expected things?

And the things it expects to be done raise questions. We're to take a method which takes a list of numbers, and then returns a list. Right. Useful.

Also, a method to add a new member. But where? At the end? The beginning? In the middle? After a given member, given a pointer to it? The latter is the only useful for linked lists, and about the only reason to use a linked list over an array (and then only if we have tons of elements, and do tons of insertions).

We'll just treat the hint as confusing rubbish, and ignore it.

First, we create two subroutines, n2ll which takes a number, and turns it into a linked list (using recursion), and ll2n, which takes a linked list and turns it into a single number (again, using recursion):

sub n2ll ($num) {$num =~ /./ ? [my $x = $&, n2ll ($')] : []}
sub ll2n ($ll)  {@$ll ? $$ll [0] . ll2n ($$ll [1]) : ""}

Sure, this uses $& and $', which can performance issues, but since we have a use linked lists to add two numbers, we're clearly not interested in performance in anyway.

Next, a method to add the content of two lists, which returns the sum as a linked list. We do this by flatting the lists into numbers, adding them (as big integers), and turning the result into a linked list again. (I just couldn't bother following a 18-step formula which does the work of a 1-character operator):

sub add ($ll1, $ll2) {use bigint; n2ll (0 + ll2n ($ll1) + ll2n ($ll2))}

Now we are ready to read in the data. We assume the input consists of two lines: one number/list per line. This may be given as a number, or in the digit/arrow format from the examples: we ignore anything which isn't a digit:

my $f_ll = n2ll <> =~ s/[^0-9]+//gr;
my $s_ll = n2ll <> =~ s/[^0-9]+//gr;

Add them:

my $sum_ll = add ($f_ll, $s_ll);

And we can now pretty print them by turning the list into a number, splitting that into characters, then joining the characters by arrows:

say join " -> " => split // => ll2n $sum_ll;

Find the full program on GitHub.