Pchełki Python: oszukujemy w Literaki

https://xpil.eu/jjt6 📋

Żeby nie zebrać po gębie, zanim przejdę do meritum dzisiejszego wpisu, żądnych krwi graczy w Literaki od razu informuję, że podczas gry nie stosuję żadnych "dopalaczy". Napisałem sobie ten kod wyłącznie jako wprawkę do nauki programowania.

Pokazywałem już na tym blogu kilkukrotnie w jaki sposób wyszukiwać anagramy za pomocą komputera; wtedy jednak robiłem to głównie za pomocą SQL-a, co może nawet jest zabawne i działa, ale jednak wymaga dostępu do serwera SQL, a więc trochę jakby strzelanie z armaty do much. Można prościej.

Ponieważ ostatnimi czasy jakoś mi się tak ułożyło zawodowo, że piszę więcej w Pythonie niż w SQL, pokażę dziś jak napisać sobie niewielkiego acz skutecznego oszusta do gry w Literaki / Scrabble.

De facto najczęstsze kombo, które mi się ostatnio przytrafia, to pisanie kodu w Pythonie, który generuje dynamiczne zapytania SQL, które są następnie wykonywane tu i ówdzie. Ale o tym może kiedy indziej.

Założenia są następujące: mamy na stojaku maksymalnie siedem liter, w tym maksymalnie dwa blanki. Na planszy coś już może leżeć, więc będziemy szukać słówek maksymalnie ośmioliterowych, no chyba że ktoś będzie próbował dopasować do więcej niż jednej litery już na planszy, wtedy być może szukamy dziewięcio- albo nawet dziesięcioliterówek.

Słownik polskich wyrazów można ściągnąć ze strony sjp.pl, stąd konkretnie: https://sjp.pl/sl/growy/. Po rozpakowaniu pliku zip dostajemy plik slowa.txt z ponad 3.1 milionami słówek (wszystkie odmiany wszystkich słów dopuszczalnych w Literakach), jedno słowo na linię, zakodowane w UTF-8 (polskie ogonki).

Skrypt powinien działać następująco: najpierw zapytać o skład stojaka (plus ewentualnie 1-2 litery na planszy); jeżeli mamy blanki, oznaczamy je kropkami. Na przykład jeżeli stojak jest "żćńół blank blank", podajemy na wejście "żćńół..". Pukamy enter i dostajemy listę możliwych do ułożenia słów, poczynając od najdłuższych. Następnie skrypt znów pyta o zawartość stojaka i tak do usranej. Chcielibyśmy też, żeby całość biegała względnie szybko, a także - ponieważ jestem leniwy - żeby kod nie zajmował więcej niż 100 linii.

Ten ostatni warunek dopisałem sprawdziwszy uprzednio ile linii zajmuje mój kod. Okazuje się, że 99 🙂

Dzisiejszy wpis będzie zrobiony krok po kroku - jeżeli, Czytelniku, interesuje Cię wyłącznie końcowy wynik, przewiń sobie na sam dół. Dla całej reszty - zaczynamy.

Ogólny pomysł jest następujący: najpierw wczytamy sobie listę słów z pliku, potem dla każdego słowa wygenerujemy hasz, rozumiany tutaj jako ciąg liter tego słowa poukładanych alfabetycznie (np. dla słowa "dupa" będzie to "adpu", a dla słów "korba", "robak" i "barok" haszem będzie "abkor").

Czujny Czytelnik zauważy, że nazywanie takiego przekształcenia "haszem" trąci o bluźnierstwo, ponieważ metoda zasadniczo gwarantuje kolizje, a hasze z założenia powinny być jak najbardziej bezkolizyjne. Jednak ponieważ kod mam już gotowy i nie chce mi się go teraz zmieniać, zostawiamy jak jest.

Czyli tak: dla każdego słowa w pliku words.txt wyliczamy jego hasz. Następnie grupujemy te hasze w postaci słownika haszów, gdzie każdy hasz ma listę słówek, które można zeń uzyskać. Na przykład dla wyżej wymienionych korby, baroku i robaka element takiego słownika będzie wyglądał następująco:

{"abkort": ["barok","korba","robak"]}

Dzięki temu możemy teraz zrobić analogiczny trick z danymi wejściowymi tj. stojakiem: policzyć hasz literek ze stojaka, plus hasze wszystkich podciągów tych literek, bo przecież nie będziemy wyszukiwać wyłącznie słów o maksymalnej długości - a następnie sprawdzić które z nich istnieją w słowniku haszów, i jeżeli znajdziemy trafienie, wypisujemy skojarzone z danym haszem słówka.

Aha, no i jeszcze te nieszczęsne blanki. Jeżeli na stojaku jest blank lub dwa, musimy to również uwzględnić. A więc wygenerujemy sobie listę wszystkich możliwych haszów wraz z blankami (w najgorszym przypadku dwóch blanków będziemy mieli 32x32=1024 razy więcej haszów do sprawdzenia) a dalej tak samo.

Nieoptymalnie?

Zgadza się. Bardzo nieoptymalnie. Eleganciej byłoby pewnie zbudować sobie jakieś drzewo i później po nim śmigać. Ale dla danych tej wielkości, jaką reprezentują nasz słownik i stojak, takie podejście w zupełności wystarczy.

Zaczniemy sobie od napisania funkcji, która wygeneruje nam wszystkie możliwe podciągi zadanego tekstu, nie krótsze niż dwie litery (bo w grach słownych nie układa się przecież wyrazów jednoliterowych):

def generuj_podciągi(s):
    podciągi = set()
    n = len(s)

    for długość in range(2, n + 1):
        for indeksy in combinations(range(n), długość):
            podciąg = ''.join(s[i] for i in indeksy)
            podciągi.add(podciąg)

    return list(podciągi)

Sprawdźmy, czy działa:

p1=generuj_podciągi("koń")
p2=generuj_podciągi("słoń")
print(p1)
print(p2)

Wynik:

['ko', 'koń', 'kń', 'oń']
['so', 'łoń', 'oń', 'słoń', 'soń', 'sło', 'sł', 'łń', 'ło', 'słń', 'sń']

Jak widać funkcja poprawnie wypluła nam wszystkie podciągi zadanych słów. Oczywiście przy dłuższych słowach liczba elementów na wyjściu rośnie do kwadratu:

p=generuj_podciągi("chłopstwa")
print(p)
exit(0)

Wynik:

['co', 'cops', 'psta', 'hsw', 'cłot', 'cha', 'cłstwa', 'cow', 'cłtw', 'hopt', 'hłopsw', 'hpa', 'cotwa', 'ca', 'cłwa', 'hpst', 'łwa', 'osta', 'chos', 'cłopsw', 'chłopsw', 'op', 'ops', 'hstw', 'hstwa', 'łstwa', 'łosa', 'cłoptw', 'choa', 'łoa', 'chps', 'chłpt', 'chłow', 'swa', 'cłosa', 'chłpswa', 'chtwa', 'łot', 'hłptwa', 'host', 'cłosta', 'chopstw', 'hopwa', 'łoptw', 'chta', 'hłowa', 'hłst', 'cpstwa', 'cłopsta', 'chłostwa', 'chpwa', 'copswa', 'pt', 'łota', 'opsta', 'cłopt', 'ch', 'cłp', 'cowa', 'łopstwa', 'łopsw', 'pa', 'łpstwa', 'hłopwa', 'łpst', 'chłost', 'chłopswa', 'chłosta', 'łt', 'cpswa', 'cłostwa', 'costw', 'chłpst', 'chłw', 'hłow', 'chłosw', 'cpsw', 'hłoa', 'łosw', 'cpsta', 'cłpsa', 'ps', 'copwa', 'coptwa', 'cosa', 'hopst', 'chopt', 'chptw', 'chłostw', 'cpsa', 'chpsta', 'łstw', 'chłopta', 'copstwa', 'cłsa', 'hpsta', 'łowa', 'cła', 'hopsa', 'chłtw', 'hoswa', 'cpwa', 'hotw', 'hłt', 'cłstw', 'pswa', 'hłosw', 'chopsw', 'coa', 'łpw', 'chpt', 'chopsa', 'cłswa', 'cotw', 'chopstwa', 'optwa', 'hłpswa', 'ptwa', 'łopt', 'chwa', 'chst', 'łopwa', 'hosw', 'twa', 'hos', 'hptw', 'łpsw', 'cht', 'cptwa', 'łopst', 'chpstwa', 'choswa', 'otwa', 'hłpstwa', 'hłoswa', 'ctw', 'ht', 'hłos', 'hłostwa', 'chpsa', 'osw', 'copta', 'cłostw', 'chłpta', 'cłsw', 'ow', 'cho', 'hpstwa', 'chłsta', 'owa', 'łsta', 'cł', 'cłopst', 'stw', 'chłoswa', 'łost', 'osa', 'chopw', 'chotwa', 'copstw', 'hłsw', 'hłpw', 'cosw', 'chłsw', 'hps', 'cłpstw', 'chłt', 'hopswa', 'chłpsta', 'hpsw', 'cpst', 'cłopw', 'chłopstwa', 'htw', 'hosa', 'hłopsa', 'coptw', 'ct', 'otw', 'cłopwa', 'copsa', 'chłptw', 'hłwa', 'hłopa', 'cpta', 'ostwa', 'cpstw', 'cpw', 'hta', 'cłopstw', 'wa', 'copsw', 'hłpsta', 'chpst', 'hłps', 'hostw', 'chopta', 'cłpa', 'chopst', 'chłpw', 'pw', 'cos', 'chs', 'cłopsa', 'hłoptwa', 'cłtwa', 'cłopswa', 'hwa', 'cłosw', 'optw', 'cłw', 'hłta', 'hpwa', 'opstwa', 'chłopsa', 'hłpsa', 'copst', 'cłpt', 'opswa', 'cłt', 'pwa', 'łopsa', 'chostw', 'hsa', 'hłtw', 'cstwa', 'hłpta', 'ha', 'copw', 'cłos', 'łostwa', 'cłops', 'hłotw', 'hłostw', 'łop', 'opsw', 'chłowa', 'hst', 'tw', 'ło', 'hopsta', 'chłopstw', 'chsta', 'cs', 'oswa', 'cost', 'łopsta', 'hłpst', 'łps', 'chłoptw', 'hp', 'chłops', 'opta', 'chłoptwa', 'chot', 'hłstw', 'cłpswa', 'csta', 'hłs', 'copt', 'łptw', 'cłpst', 'copsta', 'hłopt', 'chłopwa', 'cłptwa', 'chłota', 'łops', 'cłoptwa', 'opst', 'hpta', 'opwa', 'cptw', 'hswa', 'hłptw', 'chosta', 'hłp', 'chptwa', 'chostwa', 'cłop', 'łopa', 'hłota', 'cłotw', 'łopta', 'chowa', 'chłpstwa', 'cta', 'chłst', 'cop', 'hptwa', 'chłpsa', 'cstw', 'ctwa', 'sta', 'hoptw', 'łopswa', 'hłpt', 'chopa', 'hpstw', 'hłoptw', 'costa', 'hs', 'hopa', 'hłstwa', 'hłw', 'cłost', 'chłpsw', 'łosta', 'cłoswa', 'cłpsta', 'chw', 'chsw', 'łtw', 'cswa', 'psw', 'łopw', 'hosta', 'cłpta', 'chłopw', 'chłstwa', 'chła', 'chow', 'hłopstw', 'łotwa', 'cłow', 'łsw', 'łos', 'hłswa', 'hpswa', 'ostw', 'hłopstwa', 'łpsta', 'cw', 'sa', 'chstw', 'hłopst', 'łta', 'cłota', 'łswa', 'hłtwa', 'hło', 'chłwa', 'chłps', 'łpa', 'pstw', 'cłsta', 'cłptw', 'cłpwa', 'chłos', 'pstwa', 'chopswa', 'ta', 'chop', 'chopwa', 'chosa', 'os', 'chłpstw', 'chłsa', 'łst', 'hłpsw', 'cłs', 'chłstw', 'htwa', 'cps', 'chłotw', 'łpta', 'hw', 'hłot', 'chłpwa', 'csw', 'hot', 'chtw', 'cło', 'chpa', 'how', 'hopw', 'hłosa', 'choptwa', 'cst', 'chłopsta', 'chpw', 'ot', 'hłopw', 'chpswa', 'łotw', 'łw', 'chłotwa', 'hł', 'łp', 'chłtwa', 'chotw', 'cota', 'cłopta', 'hopsw', 'hopta', 'chłosa', 'łpt', 'ptw', 'chpta', 'cłpw', 'chsa', 'ost', 'hłopta', 'hłotwa', 'cłst', 'cłpstwa', 'stwa', 'łoswa', 'chstwa', 'csa', 'cłopa', 'hop', 'sw', 'hpt', 'chłswa', 'hoa', 'chops', 'cpt', 'łsa', 'łpstw', 'łopstw', 'hłop', 'cwa', 'łostw', 'chłopa', 'hopstwa', 'chłop', 'chłptwa', 'chłot', 'hpw', 'opa', 'hłsta', 'hops', 'cpa', 'chł', 'łpswa', 'chłopt', 'chost', 'copa', 'chosw', 'hła', 'hłosta', 'chłta', 'chłp', 'cłowa', 'cłps', 'łpwa', 'cot', 'chp', 'hłpa', 'chłpa', 'hpsa', 'ho', 'hopstw', 'cłotwa', 'hotwa', 'cłopstwa', 'chłoa', 'chło', 'łoptwa', 'hłopsta', 'howa', 'oa', 'psa', 'hoptwa', 'cłpsw', 'chpstw', 'hota', 'opw', 'łpsa', 'opt', 'cłta', 'coswa', 'hłops', 'ota', 'łow', 'st', 'łs', 'pst', 'hłost', 'chota', 'opstw', 'cp', 'hostwa', 'łtwa', 'hłpwa', 'chłopst', 'costwa', 'chłs', 'ła', 'pta', 'hłpstw', 'chswa', 'hsta', 'cłoa', 'hłopswa', 'łptwa', 'hłsa', 'chopsta', 'chpsw', 'opsa', 'choptw']

Następnie napiszemy sobie funkcję, która dla zadanego tekstu z blankami zwróci listę wszystkich możliwych zastąpień tych blanków literami:

def zastąp_blanki(tekst):
    if "." not in tekst:
        return [tekst]

    alfabet = 'aąbcćdeęfghijklłmnńoóprsśtuwxyzźż'
    if tekst.count(".") == 2:
        zastąpienia = []
        for znak1 in alfabet:
            for znak2 in alfabet:
                zastąpienia.append(tekst.replace(
                    ".", znak1, 1).replace(".", znak2, 1))
        return zastąpienia

    else:
        return [tekst.replace(".", znak) for znak in alfabet]

Sprawdźmy, czy działa:

print(zastąp_blanki("ko."))
print(zastąp_blanki("sł.."))

Pierwszy test zwraca ['koa', 'koą', 'kob', 'koc', 'koć', 'kod', 'koe', 'koę', 'kof', 'kog', 'koh', 'koi', 'koj', 'kok', 'kol', 'koł', 'kom', 'kon', 'koń', 'koo', 'koó', 'kop', 'kor', 'kos', 'koś', 'kot', 'kou', 'kow', 'kox', 'koy', 'koz', 'koź', 'koż'] a drugi listę bardzo długą, zaczynającą się od ['słaa', 'słaą', 'słab', 'słac', 'słać', 'sład', 'słae', 'słaę', 'słaf', 'słag', 'słah', 'słai', 'słaj', 'słak', 'słal', 'słał', 'słam', 'słan', 'słań', 'słao', 'słaó', 'słap', 'słar', 'słas', 'słaś', 'słat', 'słau', 'sław', 'słax', 'słay', 'słaz', 'słaź', 'słaż', 'słąa', 'słąą', 'słąb', 'słąc', 'słąć', 'słąd', 'słąe', 'słąę', 'słąf', 'słąg', 'słąh', 'słąi', 'słąj', 'słąk', 'słąl', 'słął', 'słąm', 'słąn', 'słąń', 'słąo', 'słąó', 'słąp', 'słąr', 'słąs', 'słąś', 'słąt', 'słąu', 'słąw', 'słąx', 'słąy', 'słąz', 'słąź', 'słąż', 'słba', 'słbą', 'słbb', 'słbc', 'słbć', 'słbd', 'słbe', 'słbę', 'słbf', 'słbg', ... a kończącą na ..., 'słżu', 'słżw', 'słżx', 'słży', 'słżz', 'słżź', 'słżż']. I tak, owszem, słoń jest na tej liście jakby ktoś się pytał 🙂

Kolejnym krokiem będzie napisanie funkcji, która zwraca nam hasz tekstu. Wprawdzie to jest tylko jedna linijka, ale być może w przyszłości będziemy chcieli owo haszowanie zoptymalizować, więc mamy zaczątek:

def hasz_tekstu(tekst):
    return ''.join(sorted(tekst))

I oczywiście sprawdzamy czy działa:

print([hasz_tekstu(słowo) for słowo in ["koń", "słoń", "dupa", "barok", "korba", "robak"]])

Wynik: ['koń', 'osłń', 'adpu', 'abkor', 'abkor', 'abkor'] - działa!

Przy okazji "abkor, abkor, abkor" brzmi prawie jak "hator, hator, hator", kojarzy ktoś?

Następna funkcja, którą sobie napiszemy, a która w końcu zacznie używać tego, co już napisaliśmy wcześniej, to funkcja, która dla zadanego słowa wygeneruje wszystkie możliwe hasze, jakie da się utworzyć z liter tego słowa, z uwzględnieniem blanków:

def generuj_hasze(tekst):
    podciągi = generuj_podciągi(tekst)

    hasze = set()
    for podciąg in podciągi:
        bezblanków = zastąp_blanki(podciąg)
        for słowo in bezblanków:
            hasz_słowa = hasz_tekstu(słowo)
            hasze.add(hasz_słowa)

    return hasze

Testujemy:

print(generuj_hasze("koń"))
print(generuj_hasze("sł.ń"))

Pierwszy test zwraca nam {'ko', 'kń', 'oń', 'koń'}

Drugi zaś: `

{'osń', 'csł', 'fs', 'ksń', 'stłń', 'zł', 'kń', 'jłń', 'ns', 'sńś', 'hń', 'ołń', 'sęłń', 'nłń', 'jsł', 'słś', 'syłń', 'rń', 'słź', 'sx', 'sw', 'hłń', 'jsłń', 'dsł', 'ps', 'osłń', 'cń', 'js', 'oń', 'ań', 'yń', 'cs', 'szń', 'isń', 'ksł', 'uł', 'hsłń', 'młń', 'xł', 'ełń', 'ułń', 'os', 'pń', 'eń', 'ńń', 'nsń', 'słńś', 'ks', 'łź', 'pł', 'bs', 'cłń', 'ćłń', 'es', 'sę', 'cł', 'is', 'dł', 'tł', 'mń', 'tń', 'sół', 'isłń', 'sxł', 'tłń', 'asł', 'uń', 'sąłń', 'słłń', 'rsń', 'jsń', 'rs', 'asłń', 'słńż', 'gsł', 'włń', 'nń', 'csłń', 'bń', 'fsł', 'suł', 'sął', 'psł', 'sz', 'sńń', 'swń', 'nł', 'zń', 'bł', 'ss', 'sxłń', 'ńż', 'nsł', 'rsł', 'ssń', 'hs', 'wł', 'suń', 'sęł', 'jł', 'łńń', 'słń', 'słż', 'oł', 'psń', 'ds', 'só', 'dsń', 'ńś', 'łńź', 'csń', 'sćłń', 'gł', 'lsłń', 'jń', 'wń', 'dń', 'błń', 'sułń', 'fń', 'złń', 'dsłń', 'stł', 'lł', 'sł', 'ił', 'ółń', 'lsń', 'msłń', 'fłń', 'sńż', 'sń', 'ćń', 'słńź', 'iń', 'fł', 'mł', 'ął', 'sęń', 'ssłń', 'są', 'dłń', 'lsł', 'szł', 'ksłń', 'szłń', 'płń', 'sś', 'ms', 'ół', 'asń', 'yłń', 'esł', 'ęń', 'swłń', 'głń', 'sóń', 'łłń', 'esń', 'psłń', 'ls', 'lń', 'nsłń', 'bsł', 'rsłń', 'su', 'iłń', 'fsłń', 'isł', 'ćł', 'sąń', 'łńż', 'gń', 'xń', 'ał', 'hsł', 'łż', 'kł', 'esłń', 'sćł', 'ęł', 'słł', 'msń', 'sć', 'łń', 'swł', 'gs', 'xłń', 'bsłń', 'słńń', 'óń', 'rłń', 'fsń', 'ęłń', 'lłń', 'sćń', 'ałń', 'sy', 'eł', 'st', 'sź', 'rł', 'hł', 'ssł', 'bsń', 'hsń', 'sółń', 'osł', 'łł', 'sył', 'msł', 'as', 'łńś', 'ąłń', 'sńź', 'syń', 'ńź', 'stń', 'sż', 'ył', 'ąń', 'kłń', 'sxń', 'gsń', 'łś', 'gsłń'}

Zauważamy przy okazji, że polskie ogonki nie są poprawnie sortowane - zamiast tego trafiają zawsze na koniec. Normalnie można by się do tego przyczepić, ale ponieważ sortowanie takie jest spójne w obrębie całego skryptu, nie zakłóca nam to logiki działania - chodzi bowiem wyłącznie o to, żeby hasz dla zadanego zestawu liter był zawsze ten sam, nawet jeżeli sortowanie jest popsute.

Kolejna funkcja to zbudowanie słownika haszów, a więc wyciągnięcie z pliku slowa.txt każdego słowa i przyporządkowanie mu jego haszu, następnie zgrupowanie słówek według wspólnych haszów:

def zbuduj_słownik_haszów(nazwa_pliku):
    słownik_haszów = {}
    with open(nazwa_pliku, 'r', encoding='utf-8') as plik:
        for linia in plik:
            słowo = linia.strip()
            hasz_słowa = hasz_tekstu(słowo)
            if hasz_słowa not in słownik_haszów:
                słownik_haszów[hasz_słowa] = []
            słownik_haszów[hasz_słowa].append(słowo)
    return słownik_haszów

Sprawdzamy, czy działa:

s=zbuduj_słownik_haszów("slowka/slowa.txt")
print(s)
exit(0)

Uwaga: jeżeli chcesz to przetestować u siebie, być może musisz zmienić nazwę pliku - u mnie wszystkie skrypty siedzą każdy w swoim folderze, stąd prefiks "slowka/" - u Ciebie może być nieco inaczej.

Wynik:

Duuuuuuużo tekstu, zaczynającego się od: {'aa': ['aa'], 'aaa': ['aaa'], 'aabclorsy': ['aalborscy'], 'aaabklors': ['aalborska'], 'aabklorsą': ['aalborską'], 'aabiklors': ['aalborski'], 'aabchiklors': ['aalborskich'], 'aabeiklors': ['aalborskie'], 'aabegikloors': ['aalborskiego'], 'aabeijklors': ['aalborskiej'], 'aabeiklmorsu': ['aalborskiemu'], 'aabiklmors': ['aalborskim'], 'aabiiklmors': ['aalborskimi'], 'aabkloors': ['aalborsko'], 'aabklorsu': ['aalborsku'], 'aaanoorw': ['aaronowa'], 'aanoorwą': ['aaronową'], 'aaenoorw': ['aaronowe'], 'aaegnooorw': ['aaronowego'], 'aaejnoorw': ['aaronowej'], 'aaemnooruw': ['aaronowemu'], 'aainoorw': ['aaronowi', 'aroniowa'], 'aanoorwy': ['aaronowy'], 'aachnoorwy': ['aaronowych'], 'aamnoorwy': ['aaronowym'], 'aaimnoorwy': ['aaronowymi'], 'aabce': ['abace'], 'aabci': ['abaci'], 'aabcei': ['abacie'],

Widać, że grupowanie słówek według haszów działa jak należy, na przykład tutaj: 'aabdnno': ['abandon', 'bandano', 'nadobna'] - jeden hasz, trzy słówka.

No dobra. Na tym etapie mamy już chyba wszystkie wymagane funkcje, możemy teraz zbudować logikę główną aplikacji:

def szukamy(słownik_haszów):
    dane_wejściowe = input(
        "Wpisz co masz na stojaku. Blank zastąp kropką. (Ctrl-C aby zakończyć): ")

    hasze_wejściowe = generuj_hasze(dane_wejściowe)

    znalezione_słowa = set()
    for hasz in hasze_wejściowe:
        if hasz in słownik_haszów:
            znalezione_słowa.update(słownik_haszów[hasz])

    if znalezione_słowa:
        znalezione_słowa = list(znalezione_słowa)
        znalezione_słowa.sort(key=len, reverse=True)
        print("Pasujące słowa:", ', '.join(znalezione_słowa))
    else:
        print("Nic nie pasuje.")

Testujemy:

sh=zbuduj_słownik_haszów("slowka/slowa.txt")
szukamy(sh)

Wynik:

Wpisz co masz na stojaku. Blank zastąp kropką. (Ctrl-C aby zakończyć): sł.ń
Pasujące słowa: słań, słoń, słyń, sił, sań, suń, łań, sał, ił, oń, se, eł, si, su, as, os, ts, es, są, ós, eń

Działa! Ale trzeba by to jeszcze obrzucić jakąś zewnętrzną pętelką, żeby nie czekać każdorazowo na wczytanie wszystkich słów z pliku oraz wyliczenie wszystkich haszów. Ponadto owo wyliczanie haszów również nie musi być wykonywane za każdym razem - przecież plik slowa.txt jest statyczny, więc po cholerę marnować drogocenne cykle procesora za każdym razem?

def main():
    nazwa_pliku = r'slowka/policzone_hasze.pkl'
    if os.path.exists(nazwa_pliku):
        with open(nazwa_pliku, 'rb') as plik:
            słownik_haszów = pickle.load(plik)
    else:
        słownik_haszów = zbuduj_słownik_haszów("slowka/slowa.txt")
        with open(nazwa_pliku, 'wb') as plik:
            pickle.dump(słownik_haszów, plik)

    while True:
        szukamy(słownik_haszów)

Oczywiście żeby to wszystko zadziałało, potrzebujemy zaimportować parę drobiazgów:

import pickle
import os
from itertools import combinations

Biblioteka pickle umożliwia zapisanie zmiennej do pliku a także późniejszy jej odczyt. W tym przypadku przy pierwszym uruchomieniu skryptu wyliczamy a następnie zapisujemy hasze wszystkich 3.1 milionów słówek ze słownika do pliku policzone_hasze.pkl, a przy kolejnych uruchomieniach wystarczy wczytać te hasze z tego właśnie pliku, co w tym konkretnym przypadku zaoszczędza nam ładnych parę sekund czekania na pojawienie się pierwszego zapytania o stojak.

Oczywiście na samym końcu musimy jeszcze dodać sakramentalne:

if __name__ == '__main__':
    main()

Et voila!

Cały skrypt wygląda tak:

import pickle
import os
from itertools import combinations


def generuj_podciągi(s):
    podciągi = set()
    n = len(s)

    for długość in range(2, n + 1):
        for indeksy in combinations(range(n), długość):
            podciąg = ''.join(s[i] for i in indeksy)
            podciągi.add(podciąg)

    return list(podciągi)


def zastąp_blanki(tekst):
    if "." not in tekst:
        return [tekst]

    alfabet = 'aąbcćdeęfghijklłmnńoóprsśtuwxyzźż'
    if tekst.count(".") == 2:
        zastąpienia = []
        for znak1 in alfabet:
            for znak2 in alfabet:
                zastąpienia.append(tekst.replace(
                    ".", znak1, 1).replace(".", znak2, 1))
        return zastąpienia

    else:
        return [tekst.replace(".", znak) for znak in alfabet]


def hasz_tekstu(tekst):
    return ''.join(sorted(tekst))


def generuj_hasze(tekst):
    podciągi = generuj_podciągi(tekst)

    hasze = set()
    for podciąg in podciągi:
        bezblanków = zastąp_blanki(podciąg)
        for słowo in bezblanków:
            hasz_słowa = hasz_tekstu(słowo)
            hasze.add(hasz_słowa)

    return hasze


def zbuduj_słownik_haszów(nazwa_pliku):
    słownik_haszów = {}
    with open(nazwa_pliku, 'r', encoding='utf-8') as plik:
        for linia in plik:
            słowo = linia.strip()
            hasz_słowa = hasz_tekstu(słowo)
            if hasz_słowa not in słownik_haszów:
                słownik_haszów[hasz_słowa] = []
            słownik_haszów[hasz_słowa].append(słowo)
    return słownik_haszów


def szukamy(słownik_haszów):
    dane_wejściowe = input(
        "Wpisz co masz na stojaku. Blank zastąp kropką. (Ctrl-C aby zakończyć): ")

    hasze_wejściowe = generuj_hasze(dane_wejściowe)

    znalezione_słowa = set()
    for hasz in hasze_wejściowe:
        if hasz in słownik_haszów:
            znalezione_słowa.update(słownik_haszów[hasz])

    if znalezione_słowa:
        znalezione_słowa = list(znalezione_słowa)
        znalezione_słowa.sort(key=len, reverse=True)
        print("Pasujące słowa:", ', '.join(znalezione_słowa))
    else:
        print("Nic nie pasuje.")


def main():
    nazwa_pliku = r'slowka/policzone_hasze.pkl'
    if os.path.exists(nazwa_pliku):
        with open(nazwa_pliku, 'rb') as plik:
            słownik_haszów = pickle.load(plik)
    else:
        słownik_haszów = zbuduj_słownik_haszów("slowka/slowa.txt")
        with open(nazwa_pliku, 'wb') as plik:
            pickle.dump(słownik_haszów, plik)

    while True:
        szukamy(słownik_haszów)


if __name__ == '__main__':
    main()

Na moim starutkim i7 oczekiwanie na pierwszy prompt to okolice pięciu sekund jeżeli hasze są już wcześniej policzone i zapisane w pliku .pkl, w przeciwnym przypadku około 12 sekund (czyli dodatkowe siedem sekund na odczytanie pliku words.txt i policzenie/zapisanie haszów do pliku .pkl). Natomiast potem samo szukanie anagramów leci praktycznie w czasie rzeczywistym, o ile oczywiście będziemy trzymać się początkowych założeń, że na stojaku jest nie więcej niż 7 liter, w tym maksymalnie dwa blanki. Zauważalne opóźnienia zaczynają pojawiać się w okolicach stojaków dziesięcioliterowych, ale tylko w przypadku podania dwóch blanków. Jeżeli blanków nie ma (lub jest tylko jeden), skrypt działa bez widocznych opóźnień nawet dla stojaków szesnastoliterowych, co jest już kompletną bzdurą, bo plansza ma przecież "tylko" 15x15 pól.

Mógłbym się jeszcze pobawić w formatowanie wyników, żeby ładniej wyglądały na ekranie. Na przykład pogrupowanie ich według długości słowa, albo podświetlanie liter z blanków.

Mógłbym spróbować zaimplementować automatyczną aktualizację słownika z sieci.

Ale już mi się nie chce.

https://xpil.eu/jjt6 📋