Persistence Sort, In Which I Give Up and Use a Global 🌎

This is the second half of Week 238 in the Weekly Challenge. Previously, I programmed a running sum in Perl that wasn’t that difficult at all. I spent more time on cleaning things up and writing a pretty printer function so it looked good on the screen when it ran.

Today, things get real. We’re talking recursion, global variables, and nested sorting.

Whoa, boy.

Part Two: Sort For Your Life!

You are given an array of positive integers. Write a script to sort the given array in increasing order with respect to the count of steps required to obtain a single-digit number by multiplying its digits recursively for each array element. If any two numbers have the same count of steps, then print the smaller number first.

To truly understand this one, you need to see the examples. At least, I did.

This was one of those cases where a simple sort command wasn’t going to work. I’d have to sort by a custom function. Fine, let’s do that.

The solution I came up with was to first create a hash that stores the number of times the digits in a number need to be multiplied together to get to a single-digit number.

sub multiply_numbers_recursively {

    # Recursion Rocks

    my $number = shift();
    my $count  = shift();

    my @list_of_numbers = split(//, $number);
    return $count if scalar(@list_of_numbers) == 1;

    my $running_total = 1;
    map{ $running_total *= $_ } @list_of_numbers;

    return multiply_numbers_recursively($running_total, ++$count);
}

Ah, the glories of recursion! In my last write-up, I mentioned how much I love map{} and grep{}, but recursion is right up there, too.

This function keeps multiplying until you get down to the number you need, tracking the number of iterations in an accumulator named $count.

I split the number as if it were a string of characters to get a list of numbers. I went with “//”, but you can also use ‘undef’ or an empty string like ” there to do the same thing.

Having created this hash with all the information I need, I can run my custom sort and arrange the numbers in the correct order: first, by the number of multiplications, and secondarily in increasing value of the numbers.

sub persistence_sort {

    my @array = @{ shift() };

    foreach my $value( @array ) {
        my @array_of_numbers = split(//, $value);
        $steps{$value} = multiply_numbers_recursively($value, 0);
    }

    my @final_results = sort compare keys %steps;

    return @final_results;

}

sub compare {

    ## The two level sort function
    ## The reason I have a global variable.

    if($steps{$a} < $steps{$b}) {
        return -1;
    } elsif ($steps{$a} == $steps{$b}) {
        return 1 if $a > $b;
        return -1;
    } else {
        return 1
    }

}

persistence_sort() loops over the positive integers in the array that the program is given. It runs multiply_numbers_recursively() to do all the multiplying necessary of the individual digits in a number until their sum is less than 10. The number of rounds it took to get there is stored in the %steps hash.

Now, you can sort the keys of the hash by (1) how many rounds of multiplication it took and then, when the number of loops is equal for multiple values, (2) how big the original number is.

Gasp! The Horrors!

There is one ugly bit of business that this solution has, though. A global variable. %steps has to be global for this to work. I ran out of time to try to work it out with that. I have a feeling there’s a way to pass %steps into the sort that will make things get very ugly very quickly. Or, I’d have to include the sort function directly inside the sort command line.

Finally, I copied-and-pasted that pretty printer from the last exercise, wrote a bit of script to loop over the two sample arrays, and got back these results:

BEFORE: (15, 99, 1, 34)
AFTER: (1, 15, 34, 99)

BEFORE: (50, 25, 33, 22)
AFTER: (22, 33, 50, 25)

That’s nothing too fancy, but it gets the job done.

Again, the global variable bites back as I had to make sure to blank that out after each iteration:

## Test Values:
my @first  = (15, 99, 1, 34);
my @second = (50, 25, 33, 22);
my @tests = ( \@first, \@second );

## Runner:
foreach my $array_ref( @tests ) {

    print "BEFORE: ";
    pretty_print_array( $array_ref);

    my @results = persistence_sort( $array_ref );

    print "AFTER: ";
    pretty_print_array(\@results);

    print "\n";

    ## The price I pay for the global
    %steps = ();

}

When I didn’t restart the hash, it would continue to add in all the values from the next test. It sorts it correctly, at least, but that’s not what I was trying to do.

Next week, I’ll follow this up by using a GOTO statement!

You can find my final script on Github.