I've spotted this week as a great opportunity to test my own Quantum::Superpositions::Lazy module while doing some coding challenges. The module has just been released to CPAN this month and I'm eager to dogfood it as much as possible to ensure the quality. A little spoiler: the results are much better than expected. Read on to see why.
As always, here's the link to this week's tasks: https://perlweeklychallenge.org/blog/perl-weekly-challenge-074
Challenge #1: Majority element
An easy enough task on its own - we just have to find out if there's an element in the array that occurs more often than 50% of times. The actual equation given is over floor(size_of_list / 2) times, but that is irrelevant because even for uneven list it has to simply be above 50% and math will work the same. Why not make it easier with some quantum-like magic?
A superposition is more or less just a multi-value container. In my take on this, that container has also two important characteristics which are going to be very helpful:
- it handles weights and probabilities
- it has its own statistics module bundled up
So, how would you implement the task with no modules? Simple! Just grab the array, set up a hash to count the occurrences of elements, loop through the array and fill up the hash, get the biggest value from the hash and return its key if it passes the threshold.
No, wait, that seems a bit too imperative and "raw", let's think of something different. How about sorting the array so that the elements of same value are adjacent and then replacing the X adjacent elements with a single element containing the count and the value, sorting again by count and getting the first element's value?
That's certainly clever, but sounds like a lot more work for such a simple task. In the end, with the right tool, all you need is this:
my $list = superpos(@_);
my ($state) = $list->stats->most_probable->states->@*;
return $state->weight > 0.5 ? $state->value : -1;After creating the superposition from the input data, we can immediately access its most probable outcomes via the stats object. Superpositions automatically merge the outcomes of same value, summing their probabilities, so if one element is more frequent it will have a higher probability.
The $state value now contains the first of the states which have the same most probability. The result of the most_probable is not as an array but a new superposition object. Probabilities of its states will have a sum equal to the calculated probability they had in the original superposition. We actually don't need this object in this setup, so we can immediately call ->states->@* to get all of its states as an actual Perl array.
We don't even have to check the number of elements in this setup, since it's impossible for an element to have over 0.5 weight if both of them are more probable. But to be fair, this is the perfect example for the usage of Quantum::Superpositions::Lazy module, so it really shines here. Lets see how can it help in less optimal environment, in task #2.
Challenge #2: FNR (first non-repeating) character
The description here is rather unclear and the examples are counter-intuitive (because they seem more like last non-repeating rather than first), but thankfully it is quite known puzzle and it can be found on other pages as well. All we have to do is create substrings of an input string - from length 1 to full length - and for each of these strings, extract the first character that does not repeat in them. If all characters repeat, we are to use the hash character.
The outer part of the puzzle (the one with looping through substrings and concatenating output characters) is not interesting at all, so let's focus on the inner part, which is the non-repeating character extraction. In its nature, this task is quite similar to the first one, but also completely different, since we don't care about probabilities anymore, but rather about the occurrences - one or more, to be precise.
I wasn't sure if it's even worth it to use the superpositions module here, since it doesn't seem to fit at all. But one clever trick changed it all - we're going to abuse probabilities again, but this time in form of weights.
Internally, all the superposition probabilities are actually just weights, and the default weight is equal to 1. It is only in certain situations (statistical calculations being one of them) where the weights are transfered to probabilities, and it is done by setting a weight sum to a constant 1. Knowing that we can put all the letters into a superposition, and when we reach for them again, they will have their occurrences counted in their weight field:
my @split = split "", shift;
my $split_pos = superpos(@split);
my @non_repeating = grep { $_->weight == 1 } $split_pos->states->@*;We can immediately reduce the set of letters to just those that do not repeat - that's like two thirds of the task done by a simple method call. We can now entertain some of the task's requirements with a couple of if statements:
return "#" if @non_repeating == 0;
return (shift @non_repeating)->value if @non_repeating == 1;With this out of the way, it is time for icing on the cake - a place where we choose which non repeating character we want to use, if there are multiple. Since the task is named First non-repeating character I'm going to use List::Util::first and ignore the fact that the examples on PWC website want me to use the last character:
my $alternatives = superpos(@non_repeating);
return first { $_ eq $alternatives } @split;But wait, what happened here? A simple eq in a place where there should be basically a loop? How does it work?
This is another little place in which I found the module to be very handy. When we have a superposition at hand, it tries very hard to act as if it actually was in all these states at the same time (for Perl operators at least). For logical checks like the eq operator, it uses one of the reduction strategies implemented in it, which can be changed with some special subroutines. The default reduction strategy is any, which means that the eq will return true if any state from the superposition has a value that successfully compares using eq. This way we can "have our loop and skip it too".
How was your dog food?
Not bad for something that was not aimed to be anything but toy code (at first) and upgrade of Damian Conway's old module. I'm actually very happy with it and how it makes some tasks trivial. And we haven't even touched more goodies that are out there waiting to be used, like built in RNG which collapses multiple superpositions at once to produce a random result, or using them in mathematical or string calculations.
Comments? Suggestions? Send to bbrtj.pro@gmail.com
Published on 2020-08-22