Anagram Nut Clusters

Wherein sometimes we say clever things and others we stay silent. We try to present the clever part but silence permeates the void.

THE WEEKLY CHALLENGE – PERL & RAKU #94

---

episode Eno:
“Sacramental Gut Run”

---

Task 1

Group Anagrams

Submitted by: Mohammad S Anwar

You are given an array of strings @S.

Write a script to group Anagrams together in any random order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

    Input: ("opt", "bat", "saw", "tab", "pot", "top", "was")
    Output: [ ("bat", "tab"),
              ("saw", "was"),
              ("top", "pot", "opt") ]

Example 2:

    Input: ("x")
    Output: [ ("x") ]

Method

A group of anagrams you say? A what of what?

I think the definition of an anagram in the text above, while nice (and important mind you), is in the end a little less useful to us than, say, adding a second sentence with some sort of rephrasing of the task might have been. I have to say that on first reading I couldn’t make heads or tails of what was actually being requested. Wait, what anagrams of what? Making random anagrams? Grouping them? From where again?

Only after some careful deconstructing of the examples it did become clear to me what was expected, so with that over and done with let’s have a go at that rephrase. How about:

“Given a list of strings, gather together any that are complete anagrams of each other and list each group in any order.”

Now doesn’t that make a little more sense? In the first example, “bat” and “tab” are anagrams, as are the pair “saw” and “was”, and the triplet “top”, “pot” and “opt”. These are then all presented as three lists. As for strings that have no letterwise compatriots, from the second example any strings without anagrams are just presented as a group of one. Very good. Now we can get started.

To do this we’ll only need to know which and how many of each letter compose the word, the order in the string is unimportant. I mean, they all get moved about anyway, right? The easiest way to go about this is to sort the letters alphabetically, and the count will be kept for us automatically by the repetitions of the letters themselves. For example we will convert the word “anagram” into “aaagmnr”. Any other anagram will convert to the same form, so if we use this as a hash key, we can keep the words that match as a list in the values.

It’s worth noting that hash keys, like the hashes themselves, don’t concern themselves much with physical size. I suppose if someone, like me perhaps, took this to some pathological extreme one could find an effect, but I suspect we’d be using truly enormous strings by the time we saw any difference, and that would only be attributable to the expense of allocating vast expanses of memory. Also any string can be used for a hash key; and with non-interpolating single quotes any character can be used, such as complete URLs, slashes and colons and all. Generally speaking (according to the rules of anagramming as I understand them), any capitalization, punctuation or other non-letter characters are not to be considered anyway, so I think we’ll go ahead and install a filter to strip any of these characters and qualities out before we start.

In permutation, the repositioning of the elements where no changes are made is still considered a valid permutation and must be counted. Similarly, we will consider identical words anagrams as well, discounting any inevitable derision such a failure to act would command from the notoriously meritocratic anagram community. We are not here to judge the quality of the anagrams, only to identify them.

PERL 5 SOLUTION

The solution works on creating a common hash key between anagram forms of a letter collection. We’ve installed a filter to remove non-alphabetical characters and to lowercase everything before we start comparing, so “cooks” and “Cook’s” are to considered equivalent.

[colincrain:~/PWC]$  perl grouping_anagrams.pl "Opt", "saw1", "po-t", "top", "wa's", "cooks", "Cook's"
saw was
opt pot top
cooks cooks`

The code:

use warnings;
use strict;
use feature ":5.26";

## ## ## ## ## MAIN:

## just some default data
@ARGV == 0 and @ARGV = ("Opt", "bat", "saw1", "tab", "po-t", "top", "wa's");

my @list;
for (@ARGV) {
    s/[^a-zA-Z]//g;
    push @list, lc $_;
}

my %letters;
for (@list) {
    my $str = join '', sort split //, $_;
    push $letters{$str}->@*, $_;
}

say "@$_" for values %letters;

raku solution

unit sub MAIN (*@input) ;

@input.elems == 0 and @input = "Opt", "bat", "saw1", "tab", "po-t", "top", "wa's";

@input .= map: { .lc; };
@input .= map: { S:g/// };

my %lets;
push %lets{ .comb.sort.join }, $_ for @input;

.say for values %lets;