Peter
Peter Campbell Smith

Abecedarian words
and pangrams

Weekly challenge 161 — 18 April 2022

Week 161 - 18 Apr 2022

Task 2

Task — Pangrams

A pangram is a sentence or phrase that uses every letter in the English alphabet at least once.

Using the provided dictionary generate at least one pangram.

Your pangram does not have to be a syntactically valid English sentence (doing so would require far more work, and a dictionary of nouns, verbs, adjectives, adverbs, and conjunctions). Also note that repeated letters, and even repeated words, are permitted.

Examples


Perhaps the most well known pangram is:
The quick brown fox jumps over the lazy dog

Analysis

The approach I used to creating pangrams was to choose a random word from the dictionary as my pangram's first word. I then chose more random words from the dictionary, and added each of them to my pangram if they contained a letter I didn't already have. And once I had all 26 letters I stopped.

This works well, and my submission delivers a sample of 10 results.

I then wondered how close I could get to the shortest (fewest words or letters). I ran through my algorithm 10 000 times and it's clear that it can get down to 8 words and 60ish letters. The best I did after just a few tries is:

tributary shipwrecked mollifying gavels gazes frequents 
jerky exhaling
8 words, 63 letters

The 'quick brown fox' pangram has 9 words but only 35 letters, so I thought a better algorithm might be one that prefers shorter words. Limiting the word length to 5 gave:

rowdy clix bang newt quick huffs zest ohm video 
opera jell
11 words, 48 letters

I think that's not bad for a fairly simplistic algorithm (though I'm a little dubious about 'clix'.)

Try it 

Try running the script with any input:



example: 5

Script


#!/usr/bin/perl

# Peter Campbell Smith - 2022-04-18
# PWC 161 task 2

use v5.28;
use strict;
use warnings;
use utf8;

my ($dictionary, $done, $k, $last_word, $num_letter, $num_letters, $num_words, $ord_a, $pangram, $word,
    $num_chars, @best_words, @best_chars, $tries, @words);

# fetch dictionary
$dictionary = `curl -s -L https://github.com/manwar/perlweeklychallenge-club/raw/master/data/dictionary.txt`;

while ($dictionary =~ m|(.*?)\n|g) {
    $word = lc($1);
    chomp($word);
    push @words, lc($word);
}
$last_word = scalar @words;

$done = 2 ** 26 - 1;    # bitmap if all 26 letters have been found
$ord_a = ord('a');

# make 10 'random' pangrams
say qq[--- 10 random pangrams ---];

for $k (1 .. 10) {  
    ($pangram, $num_words, $num_letters) = pangram();
    say qq[\nPangram $k:\n$pangram\n$num_words words, $num_letters letters];
}

# find the fewest words and letters from lots of tries
$tries = 10000;
say qq[\n--- Fewest words and letters from $tries tries ---];

@best_words = ('', 1000, 1000);
@best_chars = ('', 1000, 1000);

for $k (1 .. $tries) {
    ($pangram, $num_words, $num_letters) = pangram();
    if ($num_words < $best_words[1]) {
        @best_words = ($pangram, $num_words, $num_letters);
    }
    if ($num_letters < $best_chars[2]) {
        @best_chars = ($pangram, $num_words, $num_letters);
    }
}

say qq[\nLeast words:\n$best_words[0]\n$best_words[1] words, $best_words[2] letters];
say qq[\nLeast letters:\n$best_chars[0]\n$best_chars[1] words, $best_chars[2] letters];
    
sub pangram {

    my ($bit, $letter, $num_chars, $num_words, $pangram, $pattern, 
        $target, $word, @letters);
    
    # generates a 'random' pangram
    
    # initialise
    $target = 0;            # bitmap so far 
    $pangram = '';
    
    # loop over random words
    while ($word = $words[int(rand($last_word))]) {
        
        # split word into letters
        @letters = split(//, $word);
#       next if $#letters > 4;   # see blog about this line
        
        # create bitmap of this word
        $pattern = 0;
        for $letter (@letters) {
            $bit = ord($letter) - $ord_a;
            $pattern |= 2 ** $bit;
        }
        
        # if this word has letter(s) we don't have, add it to the pangram
        if ($pattern & ~ $target) {
            $pangram .= $word . ' ';
            $target |= $pattern;
            $num_words ++;
            $num_chars += $#letters + 1;
        }
        
        # have we got them all yet?
        last if $target == $done;
    }
    return($pangram, $num_words, $num_chars);
}

Output

--- 10 random pangrams ---

Pangram 1:
lithium uninformative corkscrewed proudly swigging juveniles biology expose lizards tranquilizing 
10 words, 88 letters

Pangram 2:
authoring ramifications philanthropic bani plunges nosebleed betray wired executed yank junipers eloquently overworks snooze 
14 words, 111 letters

Pangram 3:
plod irks warms cessations game harebrained reimbursed evolve grossly cupful justify liquefying inexplicably hazes 
14 words, 101 letters

Pangram 4:
televises pores actresses seconds wages baboons beaching bestiality because frequented randomly storekeepers zippering extraordinarily judiciously 
15 words, 132 letters

Pangram 5:
plural summarizes prominence scabs trios merchandised interviewed flaky sharking rejoice inquest lexicons 
12 words, 94 letters

Pangram 6:
trailers permanence counterclockwise asphyxiation brocaded compelling jangles waterfront cavities plaque lizards 
11 words, 102 letters

Pangram 7:
axes fillet greases fairness faraway impair presidents pinked extinction robust hobnobbing violate eloquence friezes jabbered 
15 words, 111 letters

Pangram 8:
humored blur recycles ripeness laxative fleeter validating slakes touchdown equanimity interjected brazier 
12 words, 95 letters

Pangram 9:
psych indoctrinates outdistances dummy survey profited griefs weest slanders marquees xxi matchbook jackknifing agonize 
14 words, 106 letters

Pangram 10:
protections convenient lubricate hims hay characterized gushing drinker extrapolating fluent winning judiciously squeezing 
13 words, 110 letters

--- Fewest words and letters from 10000 tries ---

Least words:
objectively chloroformed scripting equivalents waterfront paddock exile pasteurizing 
8 words, 77 letters

Least letters:
precise botany levee extinguishes sizable swamp bedrock after judo squats 
10 words, 64 letters

The content of this website which has been created by
Peter Campbell Smith is hereby placed in the public domain