PWC 161 › Pangrams

This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

For this week’s second challenge, the task is to generate a pangram.

A pangram is simply a collection of words that contain every letter in the alphabet (English, in this case). A classic pangram example is:

the quick brown fox jumped over the lazy dog

Wikipedia

Algorithm

There are a lot of different ways to approach this problem, but I settled on a simple iterative approach in O(n²). It does not find the shortest, nor is it the fastest, but it does a pretty good job of both.

I also tried a bit mask approach on a 26-bit integer, but that was needlessly complicated and slower.

Perl code

 sub pangram {
    my @pangram;  # Pangram gets built here
    my %has;

    # Trade some space for time
    my %words = map { $_ => [ uniq split // ] } @_;

    while (keys %has < 26) {
        my %best = (word => undef, score => -26);

        for my $word (keys %words) {
            my $new = grep { !$has{$_} } @{$words{$word}};
            if ($new == 0) {
                delete $words{$word};
                next;
            }

            my $score = $new * 2 - length;
            %best = (word => $word, score => $score)
                if $score > $best{score};
        }

        # Put the best word in the @pangram
        push @pangram, $best{word};
        $has{$_} = 1 for @{$words{$best{word}}};
    }

    @pangram;
}

GitHub: perl/ch-2.pl

The calling syntax is simply pangram(@words) where @words is the dictionary. I read the dictionary from the file Mohammad checked into the git repository, but you can point it at any dictionary you like by giving the script a --dict=/path/to/dict.txt argument.

The script also takes a --min=length argument to filter out words below the specified minimum length. (Default is 4.)

Algorithm Remarks

We first do some housekeeping: the %has hash keeps track of the letters that we already have in our @pangram, built up over time. If $has{x} is false, we don’t have the letter x in our pangram, yet.

Then we make a hash of %words, and each word is mapped to an array ref of its unique characters. For example, ‘coffee’ would map to [ 'c', 'o', 'f', 'e' ]. Order doesn’t matter.

Each time through the main loop, we look for the %best word to add to the pangram. I have arbitrarily defined a heuristic of “new letters, minus existing letters”. We therefore tend to get words with a lot of new letters, without getting many duplicate letters.

This greedy method does not generate the shortest pangram, but rather a “pretty short” pangram in O(n²) time. Since we’re removing many words from %words on each iteration, the average time is significantly faster than n².