Charlton's Blog

Esoteric Programming Lesson #1: “A to Z”

Vol. 1, Issue #1 in the "Daniel Fucking Nerd-Sniped Me" Series.

Published: Dec 27, 2021
Category: Programming
Tags:

Preface

My friend Daniel would like to find the set of English words that include an ‘a’ before a ‘z’, like ‘amazon’ or ‘authorize’. I would like to teach him a thing or two about regular expressions. Thus, our mutual self-interests collided.

For the purpose of this lesson, we will search only for words that begin with an ‘a’, and have zero or more alphabetical characters before the occurrence of at least one ‘z’. Words with non-alphabetical characters (such as spaces or hypens) between the a-z match are excluded, and matches are case-insensitive.

Examples of invalid words include:

For this exercise, I’ll be using a wordlist (words.txt) that I downloaded from this url.

Notes on Regular Expressions (Regex)

Regular expressions are a common facility for describing arbitrarily complex pattern matching operations on strings.

Because searching through strings is such a frequent necessity in programming, most languages implement some kind of regular expression engine/parser. In fact, many languages implement similar or compatible dialects of regular expression syntax, often allowing programmers to re-use the expressions themselves between different language implementations.

Regular expression implementations typically run in linear time (O(n)), though naive implementations can be O(n^2) or worse. As with most high-performance string matching algorithms, classic regex implementations construct deterministic finite state machines based on the expression, which then run the match routine against the input string on a character-by-character basis.

In contrast with other DFA-based string matching algorithms (such as Aho-Corasick), regular expression algorithms can match against an infinite set of arbitrary patterns (expressed as regex) rather than a finite set of predefined search strings.

Regular expressions are commonly used for tasks like:

We can describe our pattern-matching rules from earlier using regular expression syntax as follows:

(?i)^a[a-z]*z

Bonus:

In Ruby

Let’s begin with Ruby.

File.open("words.txt").grep(/(?i)^a[a-z]*z/).each {|w| puts w}

Here’s the runtime:

0.20s user 0.04s system 101% cpu 0.236 total

In JavaScript

Next up is JavaScript, per Dan’s request. I’ve implemented these solutions using Node.js, but they could be adapted to run in a browser.

My first Node-based solution looks like so:

const fs = require('fs');

fs.readFile('words.txt', function(e, l) {
    if(e) throw e;

    l.toString().split('\n').map(function(w){
        /(?i)^a[a-z]*z/.test(w) ? console.log(w) : null;
    });
});

On average, its runtime sits around the following:

0.54s user 0.07s system 107% cpu 0.570 total

This approach seems decent, but we can improve it further!

In our original version, the entire 4.7 MB wordlist has to be loaded into memory before any matching can take place. This has a few drawbacks:

In Node, we can refactor the first version of our code to take advantage of streams, which provide the benefits I had just described.

const fs = require('fs')

async function printWords(f) {
  for await (const c of f) {
    c.toString().split('\n').map(function(w){
        /(?i)^a[a-z]*z/.test(w) ? console.log(w) : null;
    });
  }
}

printWords(fs.createReadStream('words.txt'));

Along with improving the efficiency of our program’s memory use, this technique also realizes a fairly significant gain in execution time:

0.43s user 0.03s system 102% cpu 0.453 total

With Grep

grep is a command-line tool that allows you to filter the contents of text files based on matching rules.

We can invoke grep with the regular expression we created earlier:

grep -P '(?i)^a[a-z]*z' words.txt 

This tool is written in C, and is quite fast:

0.02s user 0.01s system 98% cpu 0.023 total

The Matches

And now, the bit that you’ve been waiting for:

abastardize
abaze
abbozzo
Abenezra
Abiezer
Abkhaz
Abkhazia
Abkhazian
ablaze
ableeze
abnormalize
abnormalized
abnormalizing
abolitionize
abolitionized
abolitionizing
Abourezk
abrazite
abrazitic
abrazo
abrazos
Abruzzi
absolutization
absolutize
aburabozu
abuzz
academization
academize
academized
academizing
accessorize
accessorized
accessorizing
acclimatizable
acclimatization
acclimatizations
acclimatize
acclimatized
acclimatizer
acclimatizes
acclimatizing
acculturize
acculturized
acculturizing
accustomize
accustomized
accustomizing
acetalization
acetalize
acetazolamide
acethydrazide
acetylaminobenzene
acetylbenzene
acetylbenzoate
acetylbenzoic
acetylcarbazole
acetylhydrazine
acetylizable
acetylization
acetylize
acetylized
acetylizer
acetylizing
acetylphenylhydrazine
acetize
acetobenzoic
acetonization
acetonize
Achakzai
Achaz
Achillize
achromatizable
achromatization
achromatize
achromatized
achromatizing
acidize
acidized
acidizing
acylamidobenzene
acraze
acronymize
acronymized
acronymizing
Actinozoa
actinozoal
actinozoan
actinozoon
actionize
actionized
actionizing
activize
activized
activizing
actualization
actualizations
actualize
actualized
actualizes
actualizing
Adaize
adazzle
Adeliza
adenization
adffroze
adffrozen
adfreeze
adfreezing
adfroze
adfrozen
ADIZ
admortization
Adnopoz
adonize
adonized
adonizing
adoze
adrenalectomize
adrenalectomized
adrenalectomizing
adrenalize
adulterize
adverbialize
advertizable
advertize
advertized
advertizement
advertizer
advertizes
advertizing
adz
adze
adzer
adzes
Adzharia
Adzharistan
adzooks
aerosolization
aerosolize
aerosolized
aerosolizing
aestheticize
Africanization
Africanize
Africanized
Africanizing
Afrikanerize
Afzelia
Agassiz
agatize
agatized
agatizes
agatizing
Agaz
agaze
agazed
agenize
agenized
agenizes
agenizing
agglutinize
aggrandizable
aggrandize
aggrandized
aggrandizement
aggrandizements
aggrandizer
aggrandizers
aggrandizes
aggrandizing
aglaozonia
agnize
agnized
agnizes
agnizing
Agnotozoic
agonize
agonized
agonizedly
agonizer
agonizes
agonizing
agonizingly
agonizingness
agrarianize
Agromyza
agromyzid
Agromyzidae
Ahaz
Ahaziah
Ahiezer
Ahimaaz
Ahuzzath
Ahvaz
Ahwaz
aizle
Aizoaceae
aizoaceous
Aizoon
ajimez
akazga
akazgin
akazgine
akhundzada
Akhziv
Aladdinize
Alagez
Alagoz
alazor
Albeniz
albitization
albizia
albizias
Albizzia
albizzias
Albniz
albronze
albumeniizer
albumenization
albumenize
albumenized
albumenizer
albumenizing
albuminization
albuminize
albuminized
albuminizing
alcalizate
Alcalzar
alcarraza
Alcatraz
alcazaba
Alcazar
alcazars
alcazava
alchemize
alchemized
alchemizing
alcoholizable
alcoholization
alcoholize
alcoholized
alcoholizing
aldazin
aldazine
aldolization
aldolize
aldolized
aldolizing
alecize
alefzero
alephzero
alezan
alferez
Alfonzo
algazel
algebraization
algebraize
algebraized
algebraizing
algebrization
alguazil
Alhazen
alienize
Aliza
alizarate
alizari
alizarin
alizarine
alizarins
alkalinization
alkalinize
alkalinized
alkalinizes
alkalinizing
alkalizable
alkalizate
alkalization
alkalize
alkalized
alkalizer
alkalizes
alkalizing
alkylbenzenesulfonate
alkylbenzenesulfonates
alkylize
allegorization
allegorize
allegorized
allegorizer
allegorizing
allez
allez-vous-en
allochezia
allomerization
allomerize
allomerized
allomerizing
allotropize
Allouez
allozooid
almuerzo
Alonzo
alphabetization
alphabetize
alphabetized
alphabetizer
alphabetizers
alphabetizes
alphabetizing
Alpheratz
AlrZc
altazimuth
alternize
alteza
altezza
alumetize
aluminize
aluminized
aluminizes
aluminizing
Alvarez
alveloz
Alzada
alzheimer
amalgamatize
amalgamization
amalgamize
amaze
amazed
amazedly
amazedness
amazeful
amazement
amazements
amazer
amazers
amazes
amazia
Amaziah
Amazilia
amazing
amazingly
Amazon
Amazona
Amazonas
Amazonia
Amazonian
Amazonis
Amazonism
amazonite
Amazonomachia
amazons
amazon's
amazonstone
Amazulu
Ameizoeira
Americanization
Americanize
Americanized
Americanizer
americanizes
Americanizing
amidoazo
amidoazobenzene
amidoazobenzol
amidothiazole
amidrazone
aminization
aminize
aminoazo
aminoazobenzene
aminobenzaldehyde
aminobenzamide
aminobenzene
aminobenzine
aminobenzoic
aminotriazole
Amizilis
ammonization
ammonolyze
ammonolyzed
ammonolyzing
amoralize
amorphozoa
amortizable
amortization
amortizations
amortize
amortized
amortizement
amortizes
amortizing
Amphizoidae
amuze
amuzzle
amzel
anabaptize
anabaptized
anabaptizing
anabibazon
anabolize
anacephalize
anachronize
anaesthetization
anaesthetize
anaesthetized
anaesthetizer
anaesthetizing
anagrammatization
anagrammatize
anagrammatized
anagrammatizing
analgize
analyzability
analyzable
analyzation
analyze
analyzed
analyzer
analyzers
analyzes
analyzing
analogize
analogized
analogizing
anapaganize
anarchize
Anasazi
Anasazis
anathematization
anathematize
anathematized
anathematizer
anathematizes
anathematizing
anathemize
anatomizable
anatomization
anatomize
anatomized
anatomizer
anatomizes
anatomizing
Anaxagorize
anazoturia
Andizhan
anematize
anematized
anematizing
anesthetization
anesthetize
anesthetized
anesthetizer
anesthetizes
anesthetizing
Anezeh
angelicize
angelize
angelized
angelizing
angiostomize
Angledozer
Anglicanize
Anglicization
Anglicize
Anglicized
anglicizes
Anglicizing
angularization
angularize
anhydridization
anhydridize
anhydrization
anhydrize
animalization
animalize
animalized
animalizing
animize
animized
annalize
annualize
annualized
Annunziata
anodization
anodize
anodized
anodizes
anodizing
antagonizable
antagonization
antagonize
antagonized
antagonizer
antagonizes
antagonizing
antherozoid
antherozoidal
antherozooid
antherozooidal
Antholyza
anthologize
anthologized
anthologizer
anthologizes
anthologizing
Anthozoa
anthozoan
anthozoic
anthozooid
anthozoon
anthracitization
anthropomorphization
anthropomorphize
anthropomorphized
anthropomorphizing
anthropophagize
Anthropozoic
antiantienzyme
antibenzaldoxime
anticatalyzer
anticentralization
anticize
antienzymatic
antienzyme
antienzymic
antifertilizer
antifeudalization
antifreeze
antifreezes
antifreezing
antimechanization
antimodernization
antimonopolization
antinationalization
antioxidizer
antioxidizing
antiozonant
antipathize
antipopularization
antiprotozoal
antiquarianize
antisensitizer
antisensitizing
antisepticize
antisepticized
antisepticizing
antiseptize
antistrophize
antitheologizing
antithesize
antizealot
antizymic
antizymotic
antizoea
antozone
antozonite
Anza
Anzac
Anzanian
Anzanite
Anzengruber
Anzio
Anzovin
ANZUS
apaesthetize
apathize
apesthetize
aphanozygous
aphetize
aphidozer
aphizog
aphorize
aphorized
aphorizer
aphorizes
aphorizing
aphrizite
Apiezon
apoenzyme
apologize
apologized
apologizer
apologizers
apologizes
apologizing
apostacize
apostatize
apostatized
apostatizes
apostatizing
apostolize
apostrophize
apostrophized
apostrophizes
apostrophizing
apothegmatize
apotheosize
apotheosized
apotheosizing
apozem
apozema
apozemical
apozymase
Appenzell
appetize
appetized
appetizement
appetizer
appetizers
appetizing
appetizingly
apprizal
apprize
apprized
apprizement
apprizer
apprizers
apprizes
apprizing
aprendiz
aquotization
aquotize
Arabianize
Arabicize
Arabize
arabized
arabizes
arabizing
Aramaicize
aranzada
arborization
arborize
arborized
arborizes
arborizing
Archaeozoic
archaize
archaized
archaizer
archaizes
archaizing
archcozener
Archeozoic
archizoic
arcticize
arcticized
arcticizing
Arenzville
Arezzini
Arezzo
Argentinize
Aryanization
Arianize
Aryanize
Aryanized
Arianizer
Aryanizing
arienzo
arithmetization
arithmetizations
arithmetize
arithmetized
arithmetizes
Ariz
Ariz.
Arizona
Arizonan
arizonans
Arizonian
arizonians
arizonite
Armenize
Arminianize
Arminianizer
armozeen
armozine
armsize
aromatization
aromatize
aromatized
aromatizer
aromatizing
arretez
arrhizal
arrhizous
arroz
arrtez
arsenicize
arsenization
arsenobenzene
arsenobenzol
arsonvalization
arterialization
arterialize
arterialized
arterializing
Arthrozoa
arthrozoan
arthrozoic
artificialize
artilize
artize
Artzybasheff
Artzybashev
Arzachel
arzan
Arzava
Arzawa
arzrunite
arzun
asbestinize
Ascenez
Ascidiozoa
ascidiozooid
asepticize
asepticized
asepticizing
asexualization
asexualize
asexualized
asexualizing
Ashchenaz
Ashkenaz
Ashkenazi
Ashkenazic
Ashkenazim
Asiaticization
Asiaticize
Asiatize
asyzygetic
aspheterize
asseize
asservilize
Assyrianize
assize
assized
assizement
assizer
assizes
assizing
assoilzie
astatize
astatized
astatizer
astatizing
Asterozoa
astigmatizer
astrologize
astronomize
Asz
atazir
atheize
atheizer
atheticize
athetize
athetized
athetizing
atmolyzation
atmolyze
atmolyzer
atomization
atomize
atomized
atomizer
atomizers
atomizes
atomizing
atrazine
atrazines
atropinization
atropinize
Atticize
Atticized
Atticizing
attitudinize
attitudinized
attitudinizer
attitudinizes
attitudinizing
auctorizate
Aunjetitz
Aurangzeb
Aurungzeb
Auschwitz
austenitize
austenitized
austenitizing
Austerlitz
Australianize
Austrianize
authorizable
authorization
authorizations
authorization's
authorize
authorized
authorizer
authorizers
authorizes
authorizing
autocatalyze
autodepolymerization
autohybridization
autohypnotization
autoimmunization
autoimmunize
autoimmunized
autoimmunizing
autoionization
autolyzate
autolyze
autolyzed
autolyzes
autolyzing
automatization
automatize
automatized
automatizes
automatizing
autonomize
autoracemization
autoschediaze
autosensitization
autosensitized
autostandardization
autotyphization
autotomize
autotomized
autotomizing
autoxidizability
autoxidizable
autoxidize
autoxidizer
autozooid
Auzout
aveloz
avestruz
avianization
avianize
avianized
avianizes
avianizing
Avitzur
avizandum
avunculize
axiomatization
axiomatizations
axiomatization's
axiomatize
axiomatized
axiomatizes
axiomatizing
AZ
az-
aza-
azadirachta
azadrachta
azafran
azafrin
Azal
Azalea
Azaleah
azaleamum
azaleas
azalea's
Azalia
Azan
Azana
Azande
azans
Azar
Azarcon
Azaria
Azariah
azarole
Azarria
azaserine
azathioprine
Azazel
Azbine
azedarac
azedarach
Azeglio
Azeito
azelaic
azelate
Azelea
Azelfafage
azeotrope
azeotropy
azeotropic
azeotropism
Azerbaidzhan
Azerbaijan
Azerbaijanese
Azerbaijani
Azerbaijanian
Azerbaijanis
Azeria
Azha
Azide
azides
azido
aziethane
azygo-
Azygobranchia
Azygobranchiata
azygobranchiate
azygomatous
azygos
azygoses
azygosperm
azygospore
azygote
azygous
Azikiwe
Azilian
Azilian-tardenoisian
azilut
azyme
Azimech
azimene
azimethylene
azimide
azimin
azimine
azimino
aziminobenzene
azymite
azymous
azimuth
azimuthal
azimuthally
azimuths
azimuth's
azine
azines
azinphosmethyl
aziola
Aziza
azlactone
Azle
azlon
azlons
Aznavour
azo
azo-
azobacter
azobenzene
azobenzil
azobenzoic
azobenzol
azoblack
azoch
azocyanide
azocyclic
azocochineal
azocoralline
azocorinth
azodicarboxylic
azodiphenyl
azodisulphonic
azoeosin
azoerythrin
Azof
azofy
azofication
azofier
azoflavine
azoformamide
azoformic
azogallein
azogreen
azogrenadine
azohumic
azoic
azoimide
azoisobutyronitrile
azole
azoles
azolitmin
Azolla
azomethine
azon
azonal
azonaphthalene
azonic
azonium
azons
azoology
azo-orange
azo-orchil
azo-orseilline
azoospermia
azoparaffin
azophen
azophenetole
azophenyl
azophenylene
azophenine
azophenol
Azophi
azophosphin
azophosphore
azoprotein
Azor
Azores
Azorian
Azorin
azorite
azorubine
azosulphine
azosulphonic
azotaemia
azotate
azote
azotea
azoted
azotemia
azotemias
azotemic
azotenesis
azotes
azotetrazole
azoth
azothionium
azoths
azotic
azotin
azotine
azotise
azotised
azotises
azotising
azotite
azotize
azotized
azotizes
azotizing
Azotobacter
Azotobacterieae
azotoluene
azotometer
azotorrhea
azotorrhoea
Azotos
azotous
azoturia
azoturias
Azov
azovernine
azox
azoxazole
azoxy
azoxyanisole
azoxybenzene
azoxybenzoic
azoxime
azoxynaphthalene
azoxine
azoxyphenetole
azoxytoluidine
azoxonium
Azpurua
Azrael
Azral
Azriel
Aztec
Azteca
Aztecan
aztecs
azthionium
Azuela
Azuero
azulejo
azulejos
azulene
azuline
azulite
azulmic
azumbre
azure
azurean
azure-blazoned
azure-blue
azure-canopied
azure-circled
azure-colored
azured
azure-domed
azure-eyed
azure-footed
azure-inlaid
azure-mantled
azureness
azureous
azure-penciled
azure-plumed
azures
azure-tinted
azure-vaulted
azure-veined
azury
azurine
azurite
azurites
azurmalachite
azurous
Azusa