The New York Times recently launched some new word puzzles, one of which is Spelling Bee. In this game, seven letters are arranged in a honeycomb lattice, with one letter in the center. The goal is to identify as many words that meet the following criteria: The word must be at least four letters long. The word must include the central letter. The word cannot include any letter beyond the seven given letters. Note that letters can be repeated. For example, the words GAME and AMALGAM are both acceptable words. Four-letter words are worth 1 point each, while five-letter words are worth 5 points, six-letter words are worth 6 points, seven-letter words are worth 7 points, etc. Words that use all of the seven letters in the honeycomb are known as “pangrams” and earn 7 bonus points (in addition to the points for the length of the word).
Which seven-letter honeycomb results in the highest possible game score? To be a valid choice of seven letters, no letter can be repeated, it must not contain the letter S (that would be too easy) and there must be at least one pangram.
Solution
This is a computational problem, so I’ll let the code mostly speak for itself. A brute-force approach is feasible because there are “only” about 56,000 possible bees. The requirement that there be at least one pangram is what really constrains that number down from the millions that otherwise would be possible. There are about 8,000 sets of seven letters that yield pangrams (call these pangram-sets), and we only need to determine the words that are generable from each of them. Our approach, then, is to find all pangram-sets, and then to assign to each of them a list of all the words that can be formed from its letters. Finally, for each pangram-set we score the seven bees that can be made from it, and we report the over-all winner.
The code and output is supplied below. The winning bee, which produces 693 words for a score of 4,036, has letters AEGINRT, with R in the center.
The Python coding was interesting to me (not a software person) partly because it was an exercise in managing the differences among three different data-structures that are collections of items: lists, tuples, and sets. Lists are ordered, alterable, and quickly addressable by index but not by member. Sets are unordered, immutable, and non-redundant, but quickly addressable by member (if you want to know whether an item is a member of a collection, a set is way speedier than a list). Tuples are ordered, immutable, quickly addressable by index but not by member, and able to serve as keys in dictionary objects (as are “frozen sets”). This task involved switching among the three as necessary for performance, logic, and programmical correctness.
# Find the highest possible score for the NYT Spelling Bee game, using a supplied
# word list as the dictionary. Runs in 23.6sec in pypy (a fast way to run
# python code) on an older PC.
wordsFile = "538Words.txt"
# Return sorted list of distinct letters in the word
def lettersIn(word):
letters = []
for letter in word:
if not letter in letters:
letters.append(letter)
letters.sort()
return letters
# Get list of bee-possible words
wordsList = []
with open(wordsFile,'r') as wordsFile:
for word in wordsFile:
word = word[:-1] # pare trainling newline character
letters = lettersIn(word)
if len(word) >= 4 and len(letters) <=7 and not 's' in word:
wordsList.append(word)
# Scan word list for words with 7 distinct letters; these can be pangrams, and every
# bee uses a set of letters that has a pangram.
pangramTuples = []
for word in wordsList:
letters = tuple(lettersIn(word))
if len(letters) == 7 and not letters in pangramTuples:
pangramTuples.append(letters)
hiveWordLists = {} # dict from pangram letter-tuple to list of words made from the letters
pangramSets = [] # this will let us use the issubset() method to test if a word can be made
for pangramTuple in pangramTuples:
hiveWordLists[pangramTuple] = []
pangramSets.append(set(pangramTuple))
# This takes the bulk of run time
for word in wordsList:
letters = set(lettersIn(word))
for i in range(len(pangramSets)):
if letters.issubset(pangramSets[i]):
hiveWordLists[pangramTuples[i]].append(word)
# Score a bee: words are worth their length plus 7 for a pangram
def score(pangramTuple,centerLetter):
s = 0
for word in hiveWordLists[pangramTuple]:
if centerLetter in word:
s += len(word)
if len(lettersIn(word)) == 7:
s += 7
return s
# Score all bees, i.e., all pangram 7-tuples and all choices of center letter
highestSoFar = [0,[]]
for pangramTuple in pangramTuples:
for centerLetter in pangramTuple:
s = score(pangramTuple,centerLetter)
if s > highestSoFar[0]:
highestSoFar = [s,[pangramTuple,centerLetter]]
# Report results
print 'Maximum score is', highestSoFar[0], 'for the bee [(letters), center letter]:'
print highestSoFar[1]
words = hiveWordLists[tuple(highestSoFar[1][0])]
print 'This bee has ', len(words), 'words:'
answerList = []
for word in words:
if highestSoFar[1][1] in word:
answerList.append(word)
for i in range(len(answerList)):
if len(lettersIn(answerList[i])) == 7:
print answerList[i].upper(), "",
else:
print answerList[i], "",
if ((i+1)/7.0).is_integer():
print ""
print ""
# The output:
# Maximum score is 4036 for the bee [(letters), center letter]:
# [('a', 'e', 'g', 'i', 'n', 'r', 't'), 'r']
# This bee has 693 words:
# aerate AERATING aerie aerier agar ager agger
# aggregate AGGREGATING aginner agrarian agree agreeing agria
# aigret aigrette airer airier airing airn airt
# airting anear anearing anergia angaria anger angering
# angrier anteater antiair antiar antiarin antra antre
# area areae arena arenite arete argent ARGENTINE
# ARGENTITE arginine aria arietta ariette arraign arraigning
# arrange arranger arranging arrant arrear arrearage artier
# atria attainer attar attire attiring attrite eager
# eagerer eagre earing earn earner earning earring
# eater eerie eerier eger eggar egger egret
# engager engineer engineering engirt engrain engraining enrage
# enraging enter entera enterer entering entertain entertainer
# ENTERTAINING entire entrain entrainer ENTRAINING entrant entreat
# ENTREATING entree ergate erne errant errata erring
# etagere eterne gager gagger gainer gaiter ganger
# gangrene gangrening garage garaging garget garner garnering
# garnet garni GARNIERITE garret garring garter GARTERING
# gear gearing genera generate GENERATING genre gerent
# getter gettering ginger gingering ginner ginnier girn
# girning girt girting gittern gnar gnarr gnarring
# GNATTIER grain grainer grainier graining gran grana
# grange granger granita GRANITE grannie grant grantee
# granter granting grat grate grater gratin GRATINE
# GRATINEE GRATINEEING grating great greaten GREATENING greater
# gree greegree greeing green greener greengage greenie
# greenier greening greet greeter greeting gregarine greige
# grig grigri grin grinner grinning grit grittier
# gritting igniter inaner inerrant inert inertia inertiae
# ingrain ingraining INGRATE INGRATIATE ingratiating inner integer
# INTEGRATE INTEGRATING intenerate INTENERATING inter INTERAGE INTERGANG
# intern interne internee interning INTERREGNA interring intertie
# intrant intreat INTREATING intrigant irate irater iring
# irrigate irrigating irritant irritate irritating iterant iterate
# ITERATING itinerant itinerate ITINERATING nagger naggier naira
# narine narrate narrater narrating natter NATTERING nattier
# near nearer nearing neater negater netter nettier
# nigger niter niterie nitrate nitrating nitre nitrite
# nittier raga rage ragee raggee ragging ragi
# raging ragtag raia rain rainier raining ranee
# rang range ranger rangier ranging rani rant
# ranter ranting rare rarer raring ratan ratatat
# rate rater ratine rating ratite rattan ratteen
# ratten rattener RATTENING ratter rattier ratting reagent
# reaggregate REAGGREGATING reagin rear rearer rearing rearrange
# rearranging reata reattain REATTAINING reearn reearning reengage
# reengaging reengineer reengineering reenter reentering reentrant regain
# regainer regaining regatta regear regearing regenerate REGENERATING
# regent reggae regina reginae regna regnant regrant
# REGRANTING regrate REGRATING regreen regreening regreet regreeting
# regret regretter regretting reign reigning reignite reigniting
# rein reining reinitiate REINITIATING REINTEGRATE REINTEGRATING reinter
# reinterring reiterate REITERATING renege reneger reneging renig
# renigging renin renitent rennet rennin rent rente
# renter rentier renting reran rerig rerigging retag
# RETAGGING retain retainer RETAINING retarget RETARGETING rete
# retear RETEARING retene retia retiarii retie retina
# retinae retine retinene retinite retint retinting retirant
# retire retiree retirer retiring retrain RETRAINING retreat
# retreatant retreater RETREATING retting riant riata rigger
# rigging ring ringent ringer ringgit ringing rinning
# rite ritter tagger tagrag tanager TANGERINE TANGIER
# tanner tantara tantra tare targe target TARGETING
# taring tarn tarre tarrier tarring tart tartan
# tartana tartar tarter tarting tartrate tatar tater
# tatter TATTERING tattier tear tearer tearier TEARING
# teenager teener teenier teeter teetering tenner tenter
# tentering tentier terai terete terga tergite tern
# ternate terne terra terrae terrain terrane terraria
# terreen terrene terret terrier terrine territ tertian
# tetra tetter tiara tier tiering tiger tinier
# tinner tinnier tinter tire tiring titer titrant
# titrate titrating titre titter titterer tittering tragi
# train trainee trainer training trait treat treater
# TREATING tree treeing treen tret triage triaging
# triene triennia trier trig trigger triggering trigging
# trine trining trinitarian trite triter
# [Finished in 23.6s]