TL;DR

E. Choroba tested my solution and found bugs.

In particular:

I ended up finding two bugs.

The first was about missing to calculate the right amount of minimum stickers needed. In the example:

• letter `a` appears twice, which means we need two `ab` stickers;
• letter `c` appears thrice, which means we need three `bc` stickers.

The solution is calculating the right amount by dividing the amount thatâ€™s needed by the amount thatâ€™s provided by each sticker. In Perl terms:

``````# check for a viable solution and set the bare minimum
my %minimum;
for my \$letter (keys(%needed)) {
my \$alternatives = \$provided{\$letter}
or return 0; # no viable source
if (scalar(keys(\$alternatives->%*)) == 1) { # one viable source only
my (\$word, \$units) = \$alternatives->%*;
my \$amount = int(\$needed{\$letter} / \$units)
+ (\$needed{\$letter} % \$units ? 1 : 0);
my \$amount = \$units;
\$minimum{\$word} = \$amount
if (! exists(\$minimum{\$word})) || (\$minimum{\$word} < \$amount);
}
}
``````

On the other hand, I already knew that there was at least another error. In theory, calculating the minimum etc. was not strictly needed, as the final step with the breadth-first search should have sufficed. Yet it didnâ€™t, so it had to have a bug too.

It turned out that I was wasting useful pieces of stickers while doing the search, i.e. I was only using specific parts without using the rest to cover for other letters needs. This required turning the algotithm a bit to first find out all words that can possibly advance a little towards a solution, then iterate over those words by taking complete advantage of all provided letters. In Raku terms:

``````sub complete-minimum (%minimum is copy, %needed is copy, %provided) {
my @queue = {needed => %needed, minimum => %minimum},;
while @queue {
my \$frame = @queue.shift;
my \$needed = \$frame<needed>;
my \$minimum = \$frame<minimum>;

my %words = \$needed.keys.map({ %provided{\$_}.keys }).flat.map({ \$_ => 1 });
for %words.keys -> \$source {
my %nmin  = %\$minimum;
%nmin{\$source}++;
my %nneed = %\$needed;
for %nneed.keys -> \$letter {
%nneed{\$letter} -= %provided{\$letter}{\$source} // 0;
%nneed{\$letter}:delete if %nneed{\$letter} <= 0;
}
return %nmin if %nneed.keys.elems == 0;
@queue.push: {needed => %nneed, minimum => %nmin};
}
}
return ();
}
``````

Thanks E. Choroba!

Comments? Octodon, , GitHub, Reddit, or drop me a line!