Who Took My Cheese?

Wherein, perplexed, we notice something by its absence, and move Heaven and Earth to find out what it was…

THE WEEKLY CHALLENGE – PERL & RAKU #154 TAsk 1

---

“There is always something missing that torments me.“

— Camille Claudel

---

Missing Permutation

Submitted by: Mohammad S Anwar

You are given possible permutations of the string 'PERL'.

PELR, PREL, PERL, PRLE, PLER, PLRE, EPRL, EPLR, ERPL,
ERLP, ELPR, ELRP, RPEL, RPLE, REPL, RELP, RLPE, RLEP,
LPER, LPRE, LEPR, LRPE, LREP

Write a script to find any permutations missing from the list.

ANALYSIS

This task serves as a good exercise, modeling a data-analysis problem that one could reasonably come across in the wild: given an incomplete data set, to find the point or points that aren’t there.

To look for the missing piece of a puzzle isn’t necessarily a straightforward task. First off, to find something it’s generally better to start off knowing exactly what it is you’re looking for. If you can’t explicitly do that, however, the next-best place to start would then be to find out all the possible things that could be. Then you can compare what you have against what should be there, and find those things you should have but don’t.

In other words, you can’t find Waldo if you have no idea what he looks like. And if he slips out the back whilst you’re looking for God-knows-who? Then he’s in the wind, a ghost. And that cannot be allowed to happen.

We must find Waldo, and we must stop him. He knows what he did.

So how do we do that?

The idea, as we said before, is to make a systematic examination of what you have against what you expect, and spot the difference. We could do this by making two pools of data and removing common items from each until something is left over.

A systematic progression like this is tedious but it will work. The task, then, becomes to do this as efficiently as possible.

METHOD

Hashes in Perl are very fast, and constant in their lookup time. For all intents and purposes, the scale of the hash being accessed does not matter. So if we structure the input as keys in a hash, we can later check the hash for those keys in constant time. Furthermore, because the lookup cost is constant, there is no advantage to winnowing the lookup pool as we go; this won’t shorten the access time in any meaningful way. In fact it will only slow things down if we pause to do the deletions, so we leave the hash alone.

So the next step is to generate the permutations. I toyed briefly with the idea of creating a routine for this task, and almost reached for some old code to blow the dust off and possibly update. But then I decided if I was jut going to use my own implementation of Knuth’s Algorithm L, then what was the reasoning not to use someone else’s version of the same archetype? So I did the proper thing snd pulled in a combinatorics module to provide the means.

This I think was in the spirit of the task: here is a specific data set with some unknown element missing. It’s large enough that performing the task manually would be a bother. So the solution to our problem is to hard-code a quick tool to find the answer for us and move on.

This, then, I what we have.

PERL 5 SOLUTION

Given a large pool of data as a list, we first map it to keys in a hash. The associated values are inconsequential, so we save a little space and don’t even define them. Then using the Algorithm::Combinatorics module we break the string “PERL” into a 4 character array and pass this on to permutations(), which returns us an iterator that presents a new permutation every time we call it.

Then inside a loop we rejoin each permutation array into a proper string and perform a lookup to see whether a hash key for it exists. If so, we move on to the next, but if not we’ve found our missing piece of data. We know from the start that we need 24 possibilities but we only have 23, so once we’ve found our missing word: “LERP”, we exit the loop and with it the end of the script.

There’s no explicit need to exit after the first missing word, and if we had reason to believe more data was lost we could simply remove the last call from the loop and search through the whole set. But here that would only waste a little time so instead we cut and run.

use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';
use Algorithm::Combinatorics qw( permutations );

my @pool = qw(  PELR  PREL  PERL  PRLE  PLER  
                PLRE  EPRL  EPLR  ERPL  ERLP  
                ELPR  ELRP  RPEL  RPLE  REPL  
                RELP  RLPE  RLEP  LPER  LPRE  
                LEPR  LRPE  LREP    );
                
my %pool = map { $_ => undef } @pool;

my $iter = permutations( [split //, 'PERL'] );

while ( my $p = $iter->next ) {
    my $perm = join '', $p->@*;
    next if exists $pool{$perm};
    say $perm;
    last;
}

Raku Solution

In Raku, as is so often the case, the syntax tightens up nicely. After placing the input strings into a Bag data type, we then simply output the result of a chain of four functions on the word “PERL” as compared to the items in the bag.

At the beginning of the chain we divide the string into an array of characters, and then generate a list of permutation arrays, which we follow-up by reassembling back into strings. Finally a grep filter on this list of rearrangements allows only words not found in the original pool, as cross-referenced using the Bag.

This data flow very closely matches the original phrasing of the request: to find the string that’s missing from the input values.

unit sub MAIN () ;

my @pool = qw<  PELR  PREL  PERL  PRLE  PLER  
                PLRE  EPRL  EPLR  ERPL  ERLP  
                ELPR  ELRP  RPEL  RPLE  REPL  
                RELP  RLPE  RLEP  LPER  LPRE  
                LEPR  LRPE  LREP  >; 
my %pool =  @pool.Bag;

.say for
<PERL>  .comb
        .permutations
        .map({$_.join}) 
        .grep({ %pool{$_}:!exists })