Na blogu od jakiegoś czasu cicho i spokojnie. Czytelników nigdy nie miałem zbyt wielu, a nowe wpisy pojawiają się teraz rzadko, bo wciągnął nas kołowrotek rodzinnego życia. Od ostatniego wpisu zdążyłem przeczytać dwie książki mojego ulubionego Pratchetta, ale ja dziś nie o tym.
Ja dziś o słówkach.
Zabawy ze słówkami to jeden z moich ulubionych "pchełkowych" tematów - dane są powszechnie dostępne, nieskomplikowane, no i można z nimi zrobić całkiem sporo interesujących operacji.
Tzn. interesujących dla mnie. Bo Czytelnik, rzecz jasna, zaśnie w okolicach czwartego akapitu. Ale w końcu to mój blog jest. O czym to ja...
A no właśnie. Słowa. W języku polskim jest około 2.7 milionów słów dopuszczalnych w Scrabble (albo w Literakach - różnice są niewielkie). Dziś spróbujemy zobaczyć jakie są możliwości anagramowania na tym, całkiem pokaźnym, zbiorze wyrazów.
Zaczniemy od załadowania słówek do tabe... nie, źle mówię. Zaczniemy od pobrania listy słówek z Internetu. Na stronie www.sjp.pl można znaleźć (w sekcji "więcej", pod hasłem "lista słów do gier") spakowany plik tekstowy slowa-win.txt, w którym każde słowo znajduje się w osobnej linijce - czyli format wręcz wymarzony do wczytania do tabeli.
Oprócz tego potrzebna nam będzie również tabela, którą utworzymy sobie na darmowej wersji SQL Servera (wersja Express do pobrania ze strony Microsoftu, proszę sobie poguglać).
Zakładając, że mamy już plik slowa-win.txt oraz zainstalowany SQL Server, zabieramy się do roboty. Najpierw tworzymy sobie nową, pustą bazę danych: prawomysz na Databases, klikamy New Database, nadajemy nazwę, zatwierdzamy ustawienia domyślne. Potem tworzymy w tej bazie nową, pustą tabelę: prawomysz na Tables w naszej nowo utworzonej bazie, potem klikamy New Table (ewentualnie Table... jeżeli mamy wersję SQL Servera 2014), tworzymy w tabeli jedną jedyną kolumnę o nazwie "slowo", typ danych to nvarchar(15), ustawiamy tą kolumnę na Primary Key, zapisujemy tabelę pod nazwą "slowa", gotowe.
Kolejny krok to wczytanie słówek z pliku tekstowego do naszej nowo utworzonej tabeli. Metod jest kilka (na szybkiego przychodzą mi do głowy co najmniej cztery), najprościej i najszybciej skorzystać z BULK INSERT, o tak:
BULK INSERT dbo.slowa
FROM 'C:\Users\ewa\Documents\slowa-win.txt'
WITH (CODEPAGE = '1250')
Operacja powinna zająć kilkanaście sekund (na domowym laptopie: 27 sekund), w efekcie mamy tabelę z 2709883 słowami. Stronę kodową ustawiamy na 1250, bo takie kodowanie polskich znaków zastosowano na stronie sjp.pl.
Żeby pobawić się w anagramowanie, dobrze byłoby jeszcze utworzyć w naszej tabeli dodatkową kolumnę, która będzie przechowywać wszystkie litery danego słowa, ale w postaci posortowanej alfabetycznie. A więc dla słowa "dupa" litery to "adpu", a dla "kołowrotek" - "ekkłooortw". Dzięki temu łatwo będzie sprawdzić, czy z liter danego słowa da się ułożyć inne słowo, a jeżeli tak, to jakie. Metoda jest prymitywna, ale do naszych potrzeb w zupełności wystarczy.
W tym celu najpierw tworzymy dodatkową kolumnę w tabeli "slowa" (kolumnę nazwałem "litery"). Typ danych to również NVARCHAR(15).
Żeby tę nową kolumnę wypełnić danymi, napiszemy sobie funkcję, która z dowolnego słowa zwróci nam litery tego słowa posortowane alfabetycznie:
CREATE FUNCTION [dbo].[litery]
(@s NVARCHAR(15))
RETURNS NVARCHAR(15) AS BEGIN
DECLARE @retval NVARCHAR(15) = '', @i INT = 1
DECLARE @t TABLE(s NCHAR(1) NOT NULL)
WHILE @i<=len(@s) BEGIN
INSERT @t SELECT substring(@s, @i, 1)
SET @i+=1
END
SELECT @retval += s FROM @t ORDER BY s
RETURN @retval
END
Teraz trzeba wykonać operację właściwą, czyli wypełnić kolumnę litery odpowiednimi wartościami:
UPDATE slowa SET litery = dbo.litery(slowo)
Powyższa operacja zajmie około 25 minut. A dokładniej 24 minuty i 55 sekund na "dużym" serwerze z setką gigabajtów pamięci operacyjnej i dwoma sześciordzeniowymi procesorami Xeon, ewentualnie 27 minut i 16 sekund na domowym laptopie z czterowątkowym i7, dyskiem SSD i 8GB pamięci. Czas wykonania jest tak długi, ponieważ serwer musi wywołać naszą kiepsko zoptymalizowaną funkcję ponad 2.7 milionów razy, ale ponieważ jest to operacja jednokrotna, idziemy na kawę i po niecałej półgodzinie mamy dla każdego słowa wyliczone jego litery.
Teraz zaczyna się najciekawsze, czyli zabawy z anagramami. Zaczniemy od znalezienia odpowiedzi na następujące pytanie: jaka jest największa ilość anagramów możliwych do utworzenia z tego samego zestawu liter?
Rozwiązanie jest proste:
SELECT TOP 10
litery,
count(*) ile
FROM
slowa
GROUP BY
litery
ORDER BY
2 DESC
W wyniku dostaniemy dziesięć najbardziej "anagramowalnych" zestawów liter, wraz z ilością anagramów możliwych do utworzenia z każdego z nich. Okazuje się, że tylko jeden z nich pozwala na utworzenie aż trzynastu różnych anagramów. Zestaw ten to "akmor". Z pięciu liter: a, k, m, o, r, można utworzyć aż trzynaście słówek, i jest to jedyny taki zestaw. A jakie to słówka?
SELECT
slowo
FROM
slowa
WHERE
litery = 'akmor'
Wynik (lekko przeformatowany dla lepszej czytelności) to:
kamor, karmo, karom, komar, makro, marko, mokra, morka, okarm, rakom, ramko.
Nie jest źle - z tych trzynastu słówek nie znam tylko jednego (nie mam pojęcia co to jest "kamor" - sprawdzę sobie później).
Ponadto dowiadujemy się też, że zestawy, z których można utworzyć dwanaście anagramów (a więc tylko o jeden mniej od rekordzisty), jest aż sześć: eiklnow, aeikmnorwy, aeikprs, aeiklnp, aekmnort, aaikmnor. Wyrazy, które z tych zestawów można uzyskać, pozostawiam do odkrycia Czytelnikowi.
Pójdźmy dalej. Nasz słownik zawiera wyrazy o maksymalnej długości piętnaście liter (bo plansza do Literaków, jak też do Scrabble, ma piętnaście pól w każdą stronę). Sprawdźmy jak wygląda sprawa z anagramami piętnastoliterowymi:
SELECT TOP 10
litery,
count(*) ile
FROM
slowa
WHERE
len(slowo) = 15
GROUP BY
litery
ORDER BY
2 DESC
Okazuje się, że są trzy takie zestawy, z których można zbudować sześć anagramów (tzn. po sześć z każdego zestawu). Są to: aadeeiinnooprsw, aaeiiklmnnoswyz, acdeeiinnopsuzz.
Słówka z liter aadeeiinnooprsw to: niedoprasowanie, nieodprasowanie, nieodseparowani, niepoadresowani, niepodrasowanie, niesparodiowane.
Słówka z liter aaeiiklmnnoswyz to: niekaszlowanymi, nieszaklowanymi, nieszkalowanymi, nieszlakowanymi, niewykaszlaniom, niewyszkalaniom.
Wreszcie słówka z liter acdeeiinnopsuzz to: niedopuszczanie, niedopuszczenia, nieodpuszczanie, nieodpuszczenia, niepoduszczanie, niepoduszczenia.
Jak widać, we wszystkich bez wyjątku przypadkach mamy do czynienia z przedrostkiem "nie". Spróbujmy znaleźć "najpłodniejszy" anagram piętnastoliterowy bez tego przedrostka:
SELECT TOP 100
litery,
count(*) ile
FROM
slowa
WHERE
len(slowo) = 15
and slowo not like 'nie%'
GROUP BY
litery
ORDER BY
2 DESC
Okazuje się, że jest aż trzynaście zestawów liter nie zawierających jednocześnie "n", "i" oraz "e", z których można zrobić cztery anagramy. Przykład: aaabłopprsśwyyz (słówka z tego zestawu: powypraszałabyś, przypasowałabyś, wypaproszałabyś, poszarpywałabyś)
Spróbujmy teraz znaleźć "najpłodniejsze" zestawy zawierające przynajmniej po jednej z samogłosek "a", "e", "i", "o", "u", "y":
SELECT TOP 100
litery,
count(*) ile
FROM
slowa
WHERE
slowo like '%a%'
and slowo like '%e%'
and slowo like '%i%'
and slowo like '%o%'
and slowo like '%u%'
and slowo like '%y%'
GROUP BY
litery
ORDER BY
2 DESC
Okazuje sie, że są tylko trzy zestawy dające pięć anagramów. Są to: aeiikmnnoruwy, aeimnnorstuwyz, abeiimnnouwy. Anagramy z zestawu aeimnnorstuwyz to: niemusztrowany, nieszturmowany, nieszutrowanym, niesznurowatym, niezmustrowany.
Jak widać, znów wcięło nam się owo nieszczęsne "nie". Spróbujmy je wyeliminować:
SELECT TOP 100
litery,
count(*) ile
FROM
slowa
WHERE
slowo like '%a%'
and slowo like '%e%'
and slowo like '%i%'
and slowo like '%o%'
and slowo like '%u%'
and slowo like '%y%'
and slowo not like 'nie%'
GROUP BY
litery
ORDER BY
2 DESC
Dostaniemy piętnaście zestawów dających maksymalnie trzy anagramy.
Spróbujmy teraz z ogonkami. Czy są jakieś anagramy zawierające jednocześnie ą i ę?
Otóż tak. Jest osiem takich zestawów, dających maksymalnie trzy anagramy: ąęipt, aąęinprstz, aaącdęjoprzz, ącdęnorz, ącdęgiilno, aącdeęijnopstu, ącęmz, ącęhnrstz.
A gdyby tak poszukać anagramów z literami "ż" i ź"?
SELECT TOP 100
litery,
count(*) ile
FROM
slowa
WHERE
slowo like '%ż%'
and slowo like '%ź%'
GROUP BY
litery
ORDER BY
2 DESC
Są trzy zestawy generujące maksymalnie trzy anagramy: cddeeijoźż, ddeejoźż, ddejmoyźż. Przykładowy zestaw anagramów z zestawu ddejmoyźż to: dojedźmyż, odejdźmyż, odjedźmyż.
Na koniec jeszcze poszukajmy anagramów z zestawu nie zawierającego żadnej z liter naszego zwycięskiego, trzynastoanagramowego zestawu z początku wpisu (czyli akmor):
SELECT TOP 100
litery,
count(*) ile
FROM
slowa
WHERE
slowo not like '%a'
and slowo not like '%k%'
and slowo not like '%m%'
and slowo not like '%o%'
and slowo not like '%r%'
GROUP BY
litery
ORDER BY
2 DESC
Wynik? Jeden zestaw dający osiem anagramów: eilntu. Anagramy te to: tuleni, tuneli, inletu, intelu, lutein, lutnie, tleniu, utleni.
Jak widać możliwości są całkiem spore, aczkolwiek to tylko wierzchołek góry lodowej. Zagadnienie napocząłem od najbardziej trywialnej strony, jednak być może zachęciłem chociaż trzynaście setnych Czytelnika do podjęcia dalszej zabawy słówkami 😉
Ksssddzzzzzz zwoje w mózgownicy mi się przepaliły….