PWC 342 Balance: And a 1, and a 2

Task 1: Balance String

Description

You are given a string made up of lowercase English letters and digits only.

Write a script to format the given string where no letter is followed by another letter and no digit is followed by another digit. If there are multiple valid rearrangements, always return the lexicographically smallest one. Return empty string if it is impossible to format the string.

Thoughts

This amounts to using the available characters from the string to create a new string where letters and digits alternate. The letters and digits should be sorted ascending, to satisfy the requirement to return the lexicographic minimum. Because digits sort before letters in ASCII, we should prefer to start with a digit if we can.

I will first create two lists, one of letters, and one of numbers. We can only create an alternating string if the the two lists are the same length, plus or minus one.

The skill required here is to have read, at some point, the documentation of the List::MoreUtils module, where there are functions for partitioning a list (part) and for combining two lists in an alternating fashion (mesh). Spending time reading module documentation for amusement used to be known as "nerdy"; nowadays I believe the terminology is "on the spectrum."

Let's go to the code

sub balance($str)
{
    use List::MoreUtils qw/part mesh/;

    my @p = part { index("0123456789", $_) >= 0  } sort split(//, $str);

    return "" if abs($p[0]->$#* - $p[1]->$#*) > 1;

    return  join "", grep { defined }
                (( $p[0]->$#* > $p[1]->$#* )
                      ? mesh($p[0]->@*, $p[1]->@*)
                      : mesh($p[1]->@*, $p[0]->@*));
}

Notes

• use ... /part mesh/ -- The parts most likely to get wrong will be delegated to well-tested code.
• sort split(//, $str) -- Convert the string into individual characters, and then sort in lexicographic order.
• index("0123456789", $_) >= 0 -- Test if a character is a digit. A regular expression could be used here ($_ =~ m/\d/), but I like to use simple operations if I can.
• @p = part {...} -- The part function will use the code to create lists for each partition, and return an array of list references. p[0] will be the letters, and p[1] will be the digits
• return "" if ... -- For this to work, the two lists must be the same length, plus or minus one.
• $p[0]->$#* -- this is the last index of the list referenced by $p[0], using post-fix syntax. I could have used @{$p[0]} to give the length of the array in scalar context. Either way, it's a lot of punctuation characters, and Perl's reputation for obscurity remains secure.

Now it's time to mesh the two lists together. We prefer to start with digits, so we will only start with letters if that list is longer.

• mesh($p[0]->@*, $p[1]->@*) -- There are two versions of mesh, one from the List::Util module, and this one from MoreUtils. The difference is that this one requires lists, not list references, so we have to de-reference. Once again, I'm choosing post-fix notation.

• ( $p[0]->$#* > $p[1]->$#* ) ? ... : ... -- Using a ternary operator here to select the order of meshing (recall the $p[0] is the letters and $p[1] is the digits). I only want to put letters first if that's necessary because there are more of them.

• grep {defined} -- mesh would like the two lists to be exactly the same length, but they may not be. In that case, mesh will helpfully fill in undef, which will not-helpfully create warnings about using undefined values, so let's remove them.

• join "", ... -- Finally, the answer, putting the individual characters back into a string.