Preface...
A few dozen of lines of codes earlier...
As a coding exercise, we will examine a game where, given a wall of text and a randomly selected word from the text, the goal is to guess the word by attempting to guess individual letters. Example:
Given the text: Having reached the end of my poor sinner's life, my hair now white, I prepare to leave on this parchment my testimony as to the wondrous and terrible events.
and assuming we select the word prepare, the goal is to produce the word prepare as a solution after a series of attempts. Each attempt involves choosing a letter, asking about its positions in the selected word and getting a response:
- Q: where is the letter L located in the word?
- A: it is located at positions P<0>, P<1>,... P<n>
The performance of the solution will be measured by the number of attempts - the less attempts, the better.
From now on, by the term selected word we will mean the word that was selected at the start and which we will try to guess. In order to design a solution, we will note down a few important observations and assumptions:
- the text will include some items that we do not need at all in our analysis, like commas, dots, spaces and the like
- we will ignore the case - the words Prepare and prepare will just be the same word
- we will treat the words as they appear, without an attempt to alter them to be present tense infinitives - the words prepare and prepared will be different words
- we assume that the selected word actually exists in the text
- the length of the selected word is known at the start
Approach to guessing
We will take letter frequency based approach: based on the frequency of the appearance of individual letters in the text, we will try to guess the word starting from the letters most frequently used in the text and continue towards the less frequently used. So, high level, we will guess the selected word by executing these steps:
- Based on the input wall of text, prepare a list of letters sorted by the number of their appearance in the text, descending
- Narrow down the words that can be considered as possible solutions based on the length of the selected word
- Make an attempt using the first untried letter from the list
- Narrow down the list of words considered based on the attempt's response (that is, the positions of the letter in the selected word)
- If we narrowed the words considered to just one word, that's our solution; otherwise, continue the execution from step 3
This procedure can be implemented in Python as:
from random import choice
from functools import partial, reduce
# These are the characters that we will ignore during the analysis of the text
charsToRemove = ',.–\n()"'
def _removeChars(s, charsToRemove):
if len(charsToRemove) == 0:
return s
else:
return _removeChars(s.replace(charsToRemove[0:1], ''), charsToRemove[1:])
def _removeSpaces(s):
return s.replace(' ', '')
# This function returns a list of unique, lower case words resulting from
# the input wall of text.
def words(txt):
return list(set(_removeChars(txt.lower(), charsToRemove).split(' ')))
# This function returns a list of characters sorted by number of their occurrence
# in the text, descending.
def charsSortedByFreq(text):
sortedTuples = sorted(_charFreq(text).items(), key = lambda i : i[1], reverse=True)
chars, frequencies = zip(*sortedTuples)
return chars
def _charFreq(txt):
freq = dict()
for c in list(_removeSpaces(_removeChars(txt.lower(), charsToRemove))):
freq[c] = freq.get(c, 0) + 1
return freq
# This function returns a list of indexes marking the occurrences of character c
# in string s. Examples:
# s = 'determine', c = e -> [1, 3, 8]
# s = 'determine', c = p -> []
def findAllCharsInString(s, c):
def _findAllCharsInString(s, c, offset, res):
index = s.find(c, offset)
if index == -1:
return res
else:
res.append(index)
return _findAllCharsInString(s, c, offset + index + 1, res)
return _findAllCharsInString(s, c, 0, [])
# Each time a character is guessed, we want to adjust the words considered by leaving
# in only the words where the guessed character is at the same positions as in the word
# we are trying to guess.
# NOTE: the guessed character can be a miss and then the positions are empty list and no
# adjustment takes place.
def narrowWordsConsidered(wordsConsidered, guessedChar, guessedCharPositions):
def _predicateFn(word):
return all(map(lambda x: word[x:x+1] == guessedChar, guessedCharPositions))
return list(filter(lambda word: _predicateFn(word), wordsConsidered))
# The goal: given a wall of text, the length of a word W from the text and a cue function that we can use
# to determine the positions of a character in W, we will find out what W is.
# First, we take into account only the words whose length is the same as of the word to be guessed.
# Then, we try guessing the characters by simply going through the frequency list. Each time we do it,
# we narrow the words considered. Ultimately, there will be just one item in the words considered
# and that's the word we are looking for.
# The reductions list is only used to record how the list of the words considered shrinks with each step.
def guess(text, wordLen, cueFn):
reductions = []
wordsConsidered = list(filter(lambda k: len(k) == wordLen, words(text)))
reductions.append(len(wordsConsidered))
for c in charsSortedByFreq(text):
wordsConsidered = narrowWordsConsidered(wordsConsidered, c, cueFn(c))
reductions.append(len(wordsConsidered))
if len(wordsConsidered) == 1:
return wordsConsidered[0], reductions
def repeatAndSaveResults(text, repetitions):
summary = []
fullResults = []
for k in range(repetitions):
word = choice(words(text))
cueFn = partial(findAllCharsInString, word)
_, reductions = guess(text, len(word), cueFn)
summary.append(len(reductions))
fullResults.append(reductions)
resultsString = reduce(lambda x, y: str(x) + ',' + str(y), summary)
with open('summary.csv', 'w') as summaryFile, open('reductions.csv', 'w') as reductionsFile:
summaryFile.write(resultsString)
for row in fullResults:
rowStr = reduce(lambda x, y: str(x) + ',' + str(y), row)
reductionsFile.write(rowStr)
reductionsFile.write('\n')
if __name__ == '__main__':
text = """
Bogaty warszawski kupiec Stanisław Wokulski zakochuje się w zubożałej arystokratce Izabeli Łęckiej. Aby być jej godnym, postanawia powiększyć swój majątek, dlatego wyrusza na tzw. „wojnę bułgarską”. Zajmuje się tam aprowizacją armii rosyjskiej, na czym zbija fortunę. Powraca do Warszawy, po czym wchodzi w układy finansowe z ojcem Izabeli, Tomaszem (m.in. wykupuje jego weksle). Próbuje też zdobyć serce ukochanej, ofiarowując znaczne sumy na organizowaną przez nią kwestę charytatywną. Dla niej jednak gest Wokulskiego jest tylko objawem niezdrowych ambicji nowobogackiego nuworysza. Stanisław pragnie jak najczęściej widywać się z Izabelą, dlatego wkrada się w łaski warszawskiej arystokracji, udzielając im korzystnych pożyczek. Kupuje też klacz, którą wystawia do wyścigów konnych. Na torze spotyka barona Krzeszowskiego, który zachowuje się niegrzecznie w stosunku do Izabeli. Wokulski wykorzystując pretekst (przypadkowe popchnięcie), wyzywa go na pojedynek, w wyniku którego Krzeszowski zostaje ranny. Kilka tygodni potem Tomasz Łęcki zaprasza Wokulskiego na obiad, na którym mają poruszyć sprawy finansowe. Podczas posiłku obecna jest i Izabela, która stara się traktować gościa jak najuprzejmiej, proponuje mu nawet wspólny wyjazd do Paryża. Rozmawia też ze Stanisławem o włoskim aktorze Rossim (w którym jest zadurzona), ubolewając nad chłodnym jego przyjęciem przez warszawian. Wokulski, chcąc sprawić Łęckiej przyjemność, opłaca publiczność w teatrze, która gotuje Włochowi owacje. W tym samym czasie Tomasz Łęcki zmuszony jest sprzedać swoją kamienicę. Wokulski kupuje ją przez podstawionego Żyda – Szlangbauma, zawyżając cenę. Jednocześnie wysyła swojego przyjaciela i subiekta Ignacego Rzeckiego, by obejrzał nowy nabytek. Rzecki poznaje lokatorów, wśród których jest Helena Stawska – piękna, młoda kobieta, porzucona przez męża. Postanawia zeswatać ze sobą Stanisława i Helenę. Wokulski, będąc świadkiem flirtu Łęckiej i jej kuzyna Starskiego podejmuje decyzję o wyjeździe do Paryża.
Wokulski spotyka się ze swoim przyjacielem, Rosjaninem Suzinem, z którym robi interesy. W swoim hotelowym apartamencie przyjmuje interesantów, wśród których jest prof. Geist – genialny wynalazca, niedoceniany przez swoich kolegów. Proponuje mu wspólną pracę nad cudownym wynalazkiem – metalem lżejszym od powietrza. Stanisław jest rozdarty pomiędzy uczuciem do Łęckiej a swoją naukową pasją. Postanawia zostać we Francji, lecz kiedy dostaje list od prezesowej Zasławskiej (poznanej arystokratki, kiedyś nieszczęśliwie zakochanej w jego stryju), w którym prezesowa pisze o rodzącym się uczuciu Izabeli do niego, natychmiast wraca do kraju. Przybywa do Zasławka (będącego posiadłością prezesowej Zasławskiej), w którym spędza wakacje cała warszawska śmietanka towarzyska (Izabela przybędzie niebawem). Wśród nich jest piękna, młoda i bogata wdowa, pani Wąsowska, która próbuje uwieść Wokulskiego. Ten pozostaje jednak wierny swej miłości. Kiedy przybywa Izabela, Stanisław wyznaje jej swoją miłość. Łęcka robi mu nadzieję na wzajemność, po czym wyjeżdża. Mija pół roku. Wokulski bywa coraz częściej u Łęckich. Przez lokalną arystokrację jest postrzegany jako przyszły mąż Izabeli. Za namową Rzeckiego odwiedza panią Stawską, która zakochuje się w nim. Kobieta nie podejmuje jednak żadnych kroków, gdyż wie doskonale, że Stanisław jest zapatrzony w Izabelę. Tymczasem Izabela decyduje się wyjść za Wokulskiego (usilnie namawiana przez rodzinę), którego majątek wydaje się jedynym gwarantem jej dostatniego życia. Namawia jednak Stanisława, żeby porzucił kupiectwo i nabył majątek ziemski. Posłuszny jej radom, Wokulski sprzedaje sklep i wycofuje swoje kapitały z handlu. W chwili oświadczyn Stanisław daje Izabeli medalion, w który oprawił cudowny metal – podarek od prof. Geista. W kilka dni potem narzeczeni wyruszają pociągiem do Krakowa – w odwiedziny do ciotki Izabeli, Hortensji. W trakcie jazdy Izabela rozmawia po angielsku z kuzynem Starskim. Flirtuje z nim i ujawnia, że zgubiła medalion od Wokulskiego. Przy rozmowie obecny jest narzeczony, ale Łęcka jest przekonana, że nie zna on angielskiego. Tymczasem Wokulski w ciągu roku ich znajomości nauczył się tego języka i poznaje prawdę o podarunku i braku afektu. W trakcie tej podróży łuski spadają mu z oczu, nareszcie widzi Izabelę taką, jaka jest naprawdę. Otumaniony wysiada z wagonu i próbuje popełnić samobójstwo. Ratuje go Wysocki – dróżnik kolejowy, któremu kiedyś Stach pomógł. Wraca do Warszawy i zamyka się w swoim mieszkaniu. Popada w letarg. Po pewnym czasie dostaje zaproszenie od pani Wąsowskiej, która próbuje go nakłonić do powrotu do Izabeli. Daremnie. Wokulski odbywa ostatnią rozmowę ze swoim przyjacielem Rzeckim i niespodziewanie znika. Przyjaciele próbują go odszukać. Po pewnym czasie przychodzi wiadomość z Zasławia – Wokulski był tam widziany w okolicach ruin zamku, zaraz przed tym, jak z niewiadomych przyczyn zostały wysadzone w powietrze. Tymczasem umiera schorowany Rzecki. Cały interes Wokulskiego przechodzi w ręce kupców żydowskich. Izabela Łęcka, tracąc szansę na zamążpójście, wyjeżdża z zamiarem wstąpienia do klasztoru.
W powieści Lalka znajduje się rozdział poświęcony procesowi o kradzież lalki, rzeczywistej lalki dziecinnej. Otóż taki proces miał miejsce w Wiedniu. A ponieważ fakt ten wywołał w moim umyśle skrystalizowanie się, sklejenie się całej powieści, więc przez wdzięczność użyłem wyrazu Lalka za tytuł.
Pracuje jako subiekt w sklepie Mincla, a potem Wokulskiego, bardzo się przyjaźni z przełożonymi. Pracuje z wielkim uczuciem, przy tym jest niezwykle skromny i oddany swojemu zajęciu, jednak zupełnie nie umie poradzić sobie w życiu. Po sprzedaży sklepu jest spychany na drugi plan i nieustannie kontrolowany. Nie umie dojść do wniosku, że jego życiowe ideały legły w gruzach. Ostatecznie umiera w wielce symbolicznej scenie w swoim miejscu pracy, które tak ukochał. Był starym idealistą, który okazał się nie przystawać do czasów w których żył. Przez zamieszczenie w powieści „Pamiętnika starego subiekta” staje się drugim pierwszoplanowym narratorem utworu.
Małżeństwo żyjące w separacji, której powodem była prawdopodobnie tragiczna śmierć córeczki. Baronowa, której udało się zgromadzić dość pokaźny majątek, mieszka w kamienicy Łęckich, mimo że nie czuje się tam dobrze (dokuczają jej sąsiedzi, lekceważy dozorca). Ma sentyment do mieszkania, gdyż znajduje się tam ulubiony pokój córki, który pozostał niezmieniony od jej śmierci. Jest zgryźliwą histeryczką, niemal nigdy nie opuszcza mieszkania, dręczy służbę, a jej ulubionym zajęciem jest pisanie złośliwych anonimów. W końcowej części utworu baronowa kupuje kamienicę i usuwa z niej większość lokatorów. Baron z kolei to lekkoduch, wydający krocie na karciane długi i wyścigi konne. Ruina finansowa zmusza go w końcu do pogodzenia się z żoną i zamieszkania razem.
To rodzina reprezentująca solidne mieszczaństwo pochodzenia niemieckiego. Jeszcze ich babka nie znała słowa po polsku, zresztą pomiędzy braćmi Franzem i Janem trwa spór o przynależność narodową. Utrzymują się, prowadząc sklep galanteryjny, którego obroty systematycznie powiększają, z pokolenia na pokolenie. Kiedy ostatni z Minclów umiera, jego majątek przejmuje żona, która z kolei wnosi sklep w posagu Wokulskiemu. Ciepło w swoim pamiętniku wspomina ich Rzecki, który pracował u nich jako subiekt. Praca ta, była dla młodego Ignacego prawdziwą szkołą życia.
"""
uniqueWords = words(text)
print('Total number of unique words: ' + str(len(uniqueWords)))
# randomly choose a word
word = choice(uniqueWords)
print(word)
# cue function will always work on the word w, but will be called with varying character as a paremeter in consecutive calls
cueFn = partial(findAllCharsInString, word)
guessedWord, reductions = guess(text, len(word), cueFn)
print('Guessed the word ' + guessedWord + ' after ' + str(len(reductions)) + ' reductions.')
# Repeat the same 300 times and record the reduction results in a file
repeatAndSaveResults(text, 300)
This piece of code runs 300 guesses in order to capture some statistics. It produces two output files:
- summary.csv - contains the numbers of attempts it took each time to guess the word
- reductions.csv - shows how quickly the list of the words considered was getting narrowed down before the word was finally guessed
Results
If we feed these statistics into R, we can get the following:
80% of words can be guessed within 12 attempts:
The process of narrowing down the words considered can be visualised as:
Something worth noting is that in some cases we have just a handful of words under consideration, but we are not very lucky with guessing any letters. These are the stragglers that we would like to get rid of and optimize the solution that way, so that it does not go beyond ~20 attempts so often.
That's where we can introduce some heuristics. What we can notice is, if the list of words considered is relatively small, say below 5 words, then maybe it does not make sense to keep trying the most frequently used letters. Maybe we would be better off trying only the letters that actually exist in these 2, 3 or 4 words that we are still considering (and that have not been tried before). So, in other words, under some threshold (say, less than 5 words) we want to change the tactics and guess by using the untried letters from the words, instead of keep on using the letter frequency list.
The choice of 5 words as the threshold is not random - it is based on the generated chart and the actual data from reductions.csv.
Improved results after implementing the heuristic
80% of words can be guessed within 9 attempts:
And in fact our new solution eliminated a number of executions that used 20+ attempts, so the hypothesis and the heuristic approach chosen was correct:
Takeaways
We had an initial solution whose performance was not bad, but we wanted to see if it can be improved. Instead of trying blindly to do some sort of optimization in the code, we looked at the statistics and we noticed that the solution squanders some of the attempts - in the executions that had 20+ attempts the list of words considered was not being narrowed down at all for about 10 last, consecutive attempts.
Our goal was to optimize this very part of it and get rid of the stragglers. We took an heuristic approach to achieve it and we tuned it based on the observations (to set the word count as < 5). Finally, we were able to find the solutions for 80% of cases within 9 attemps, whereas our baseline was 12.
This whole cycle shows the importance of the quantitative approach: just like in mechanics, physics or chemistry, we developed a way to measure the outcome and we used statistics to get us on track of proposing and evaluating an optimization.
The example also shows the expressiveness and density of Python: the final solution without comments is just 110 lines long. The R script that draws the chart is just 16 lines long.
Resources
The complete code for the optimized solution (with heuristic) along with the code in R to produce the statistics can be found on GitHub: https://github.com/pgorak/word-guess
