A Word Game Solver in Common Lisp

I enjoy playing that game known as ``Wordle'' and chose to implement solvers thereof in Common Lisp,
Ada, and APL.  The core of such a solver exposes the same information available to the player of the
game in a nicer way.  In this Common Lisp implementation, the function CHECK-WORD accepts two words,
the word to guess and the current guess, and returns a vector of length five containing the symbolic
results for each position; the letter may not be present at all in the word to guess, an exact match
may be found, or the letter may be present in the word but at a different position; my solver splits
these cases into four symbolic results, and I knew ahead of time how the last case would be hardest.

This code may be used by entering the SUMMARIZE implementation into the COMMON-LISP-USER package and
then evaluating the solver with LOAD; the dictionary may be entered by using WORDLE:READ-DICTIONARY.

The implementation of CHECK-WORD uses easier methods to determine its results than may be natural to
a man, so careful attention was paid to ensure it regardless only betrays the same fair information.
A grey letter of the game in isolation only shows the absence of that letter in that position, which
is easy enough to use, but an implementation of CHECK-WORD word with total knowledge is only obvious
and reasonable, so long as it leak nothing; the CHECK-WORD data model will likely change in the APL.

The number of five letter words is finite, and small.  The solver accepts a dictionary from which it
takes its word to guess and its guesses.  The dictionary is trimmed after every invocation of CHECK-
WORD based on its result.  Clearly, if the letter be entirely absent, then every word containing the
letter may be removed; similarly, exact positional matches allow the dictionary to be trimmed of all
words without that letter in that position; the algorithm for the last case is greatly simplified by
ignoring the exact matches and maintains the possible range of counts for that letter, most commonly
uninteresting but occasionally useful; the final symbolic case merely notes which position lacks the
letter, and is good only in the case where all such letters have been found also in their positions,
and that case where no exact matches have been found but too many guesses for that letter were made.

I noticed and remembered some interesting additions to make as I wrote this, such as the map for the
case with present letters in unknown positions, and an exact letter count for exact matches too.  In
the case where a word with too many instances of a letter is guessed, the amount of that letter must
be known, and the exatch match carries optional data noting this if possible, whereas the other case
must carry an inclusive range.  Fiddling with this latter case was so very tedious, but not too bad.

Frustratingly, I tried to use the features of Common Lisp to shape the input dictionary to miss some
error cases, only to find it to be very slow in one implementation and yet not another; the original
form of the dictionary was an N-by-five array holding BASE-CHAR, but this was noticeably inefficient
for some reason, and I decided to provide an alternative form of the dictionary for the main solver:
a list of BASE-STRINGs, which was much faster in all tested implementations.  Knowing that ease with
which I may shape data in both APL and Ada, this was unpleasant and annoying to discover.  I'd tried
to optimize the data to avoid overhead, only to run into some manner of unseen overhead.  I know the
other two implementations won't have such problems, and the Ada in particular will be much easier to
restrict; I can't reliably get an array of only English letters, enforced by the language, in Common
Lisp, only BASE-CHAR, which requires me to check all characters in the array, manually.  Ada permits
such a trivial restriction, however, so I can rest easy knowing the language will enforce it for me.

Regardless, I know the Common Lisp and APL will be more pleasant than the Ada in a few ways, such as
that ease with which generic data structures are haphazardly defined and manipulated by the same few
functions; that Ada will require me to write names and loops for just about everything I seek to do.

I particularly enjoy how this solver uses no heuristics.  When I play the game, I must call forth my
vocabulary, and trim it by recalling those vague and inconsistent rules of English word formation to
help me.  A naive approach to a solver for this game would attempt to store those rules, and attempt
to generate words from nothing, changing its way as they be rejected or accepted, but that domain of
five letter words is so small so as to make such an approach obviously stupid with only a little bit
of thought.  The ability of a computer merely to ``memorize'' large domains invalidates the need for
such heuristics in many problems, and perhaps all of them.  Approaching every problem from this view
makes many utterly trivial.  The machine forms nothing resembling a thought, and because of this may
solve any iteration of this game both faster and more reliably than any man, ignoring random chance.

This implementation is inefficient in the respect that it repeatedly scans the dictionary during its
trimming, wastefully in some cases, but I think it to be generally unworthy of further optimization.

Programming this solver reminded me of the fun programming may hold, just a little, as I was lord of
the domain; sans intake of the dictionary from file, whose format I also controlled, no interactions
with other systems were needed; the shape of everything was mine to decide and mine alone, with only
that singular performance issue to bother me.  Programming with ignorance of the world is needed for
such fun, I think.  Parsers and similarly strict things are where such fun generally goes to perish.

Unlike other solvers, this one nicely has no ability to ruin enjoyment of the game for me or others.

Lastly, here is some code that may be used to view the solver in action followed by four runs in two
different implementations of Common Lisp; this TRACE output is given manual linebreaks in two cases:


(setq dictionary (wordle:convert-dictionary (wordle:read-dictionary ...)))

(format t "~A" (with-output-to-string (*trace-output*)
                 (unwind-protect (progn (trace wordle::check-word)
                                        (wordle:resolve dictionary))
                   (untrace wordle::check-word))))


Word: harun
colva
haber
harms
hartz
hardi
harry
harun
Seven guesses were needed.
  0: (WORDLE::CHECK-WORD "harun" "colva")
  0: WORDLE::CHECK-WORD returned
       #((:NONE #\c) (:NONE #\o) (:NONE #\l) (:NONE #\v) (:SOME #\a 6 1))
  0: (WORDLE::CHECK-WORD "harun" "haber")
  0: WORDLE::CHECK-WORD returned
       #((:HERE #\h) (:HERE #\a) (:NONE #\b) (:NONE #\e)
         (:SOME #\r 6 1 #(NIL NIL T T T)))
  0: (WORDLE::CHECK-WORD "harun" "harms")
  0: WORDLE::CHECK-WORD returned
       #((:HERE #\h) (:HERE #\a) (:HERE #\r) (:NONE #\m) (:NONE #\s))
  0: (WORDLE::CHECK-WORD "harun" "hartz")
  0: WORDLE::CHECK-WORD returned
       #((:HERE #\h) (:HERE #\a) (:HERE #\r) (:NONE #\t) (:NONE #\z))
  0: (WORDLE::CHECK-WORD "harun" "hardi")
  0: WORDLE::CHECK-WORD returned
       #((:HERE #\h) (:HERE #\a) (:HERE #\r) (:NONE #\d) (:NONE #\i))
  0: (WORDLE::CHECK-WORD "harun" "harry")
  0: WORDLE::CHECK-WORD returned
       #((:HERE #\h) (:HERE #\a) (:HERE #\r 1) (:MISS #\r) (:NONE #\y))


Word: roman
meran
orman
roman
Three guesses were needed.
  0: (WORDLE::CHECK-WORD "roman" "meran")
  0: WORDLE::CHECK-WORD returned
       #((:SOME #\m 6 1 #(T T T NIL NIL)) (:NONE #\e)
         (:SOME #\r 6 1 #(T T T NIL NIL)) (:HERE #\a) (:HERE #\n))
  0: (WORDLE::CHECK-WORD "roman" "orman")
  0: WORDLE::CHECK-WORD returned
       #((:SOME #\o 6 1 #(T T NIL NIL NIL)) (:SOME #\r 6 1 #(T T NIL NIL NIL))
         (:HERE #\m) (:HERE #\a) (:HERE #\n))


Word: padua
legal
borsa
ditka
nadja
padma
padda
padua
Seven guesses were needed.
1. Trace: (WORDLE::CHECK-WORD '"padua" '"legal")
1. Trace: WORDLE::CHECK-WORD ==> #((:NONE #\l) (:NONE #\e) (:NONE #\g) (:SOME #\a 6 1) (:NONE #\l))
1. Trace: (WORDLE::CHECK-WORD '"padua" '"borsa")
1. Trace: WORDLE::CHECK-WORD ==> #((:NONE #\b) (:NONE #\o) (:NONE #\r) (:NONE #\s) (:HERE #\a))
1. Trace: (WORDLE::CHECK-WORD '"padua" '"ditka")
1. Trace: WORDLE::CHECK-WORD ==> #((:SOME #\d 6 1 #(T T T T NIL))
                                   (:NONE #\i) (:NONE #\t) (:NONE #\k) (:HERE #\a))
1. Trace: (WORDLE::CHECK-WORD '"padua" '"nadja")
1. Trace: WORDLE::CHECK-WORD ==> #((:NONE #\n) (:HERE #\a) (:HERE #\d) (:NONE #\j) (:HERE #\a))
1. Trace: (WORDLE::CHECK-WORD '"padua" '"padma")
1. Trace: WORDLE::CHECK-WORD ==> #((:HERE #\p) (:HERE #\a) (:HERE #\d) (:NONE #\m) (:HERE #\a))
1. Trace: (WORDLE::CHECK-WORD '"padua" '"padda")
1. Trace: WORDLE::CHECK-WORD ==> #((:HERE #\p) (:HERE #\a) (:HERE #\d 1) (:MISS #\d) (:HERE #\a))


Word: cults
https
teams
rusts
nuits
fults
cults
Six guesses were needed.
1. Trace: (WORDLE::CHECK-WORD '"cults" '"https")
1. Trace: WORDLE::CHECK-WORD ==> #((:NONE #\h) (:SOME #\t 1 1) (:MISS #\t) (:NONE #\p) (:HERE #\s))
1. Trace: (WORDLE::CHECK-WORD '"cults" '"teams")
1. Trace: WORDLE::CHECK-WORD ==> #((:SOME #\t 6 1 #(T T T T NIL))
                                   (:NONE #\e) (:NONE #\a) (:NONE #\m) (:HERE #\s))
1. Trace: (WORDLE::CHECK-WORD '"cults" '"rusts")
1. Trace: WORDLE::CHECK-WORD ==> #((:NONE #\r) (:HERE #\u) (:MISS #\s) (:HERE #\t) (:HERE #\s 1))
1. Trace: (WORDLE::CHECK-WORD '"cults" '"nuits")
1. Trace: WORDLE::CHECK-WORD ==> #((:NONE #\n) (:HERE #\u) (:NONE #\i) (:HERE #\t) (:HERE #\s))
1. Trace: (WORDLE::CHECK-WORD '"cults" '"fults")
1. Trace: WORDLE::CHECK-WORD ==> #((:NONE #\f) (:HERE #\u) (:HERE #\l) (:HERE #\t) (:HERE #\s))
.