Tajemnicza funkcja: rozwiązanie zagadki

Trzy dni temu zapodałem tu zagadkę, która jednak została intensywnie i bardzo uważnie zignorowana przez wszystkich trzech Czytelników blogu. Może z wyjątkiem Buttera, który wprawdzie tylko udał, że się za nią zabiera, w zasadzie „polizał” tylko temat po wierzchu i sobie odpuścił – ale przynajmniej spróbował.

Uprzedzam, że Czytelnicy nieobeznani z podstawami RegEx mogą uznać ten wpis za totalny bełkot. W sumie nie wiem dlaczego o tym teraz wspominam, ponieważ inne wpisy wcale nie są lepsze pod tym względem…

No dobra. Dziś czas na wyjaśnienie co też owa tajemnicza funkcja robi oraz dlaczego.

Najpierw przypomnę kod:

import re

def funkcja_zagadka(n):
    return not re.match(r'^.?$|^(..+?)\1+$', '1' * n)

Na pierwszy, drugi a nawet siódmy rzut oka oczywistym jest, że funkcja ta sprawdza dopasowanie tekstu złożonego z n jedynek do wzorca :

'^.?$|^(..+?)\1+$'

Hmmm. Mamy jakiś wzorzec RegEx, przez który przepuszczamy ciąg n jedynek – cóż w tym takiego interesującego?

Interesujące jest to, że jeżeli n jest liczbą złożoną, wówczas ciąg n jedynek zostanie dopasowany (metoda match() zwróci true. W przeciwnym wypadku zwróci false.

Jeżeli teraz zauważymy, że wynik metody match() jest negowany, to oczywistym jest, że cała funkcja rzeczywiście sprawdza pierwszość liczby n.

Ale jak, do diaska? Jak to jest możliwe, żeby sprawdzać pierwszość liczby za pomocą wyrażeń regularnych?

Pamiętacie ten fragment o zbieraniu jagód, sraczce, wielbłądach i zawiązanych oczach?

Nie pamiętacie?

No bo pamięć ludzka tak właśnie działa: usuwa rzeczy zbyt przerażające 😉

Chodzi o to, że zastosowana tu metoda pasuje jak wół do karety. Niemniej jednak nie da się zaprzeczyć, że kareta ciągnięta przez wołu przejedzie kawałek. Niezbyt długi, ale jednak.

Zobaczmy więc teraz jakim cudem udało się skonstruować wyrażenie regularne sprawdzające pierwszość liczby.

Na pierwszy ogień idzie sam zapis liczby: jest to notacja unarna, czyli jedynkowa.

„Normalni” ludzie posługują się systemem dziesiętnym, a więc takim, w którym jest dziesięć różnych cyfr.

Ludzie chorzy na umyśle Informatycy używają systemu binarnego, czyli takiego, który ma tylko dwie cyfry: 0 i 1.

A ludzie, przy których informatycy wydają się być ostoją normalności, używają zapisu unarnego. Czyli jedynkowego. Do zapisania dowolnej liczby używają wyłącznie jednej cyfry: 1.

Są to ci sami ludzie, którzy używają wyrażeń RegEx do sprawdzania pierwszości liczb, więc proszę się nie śmiać. To przypadek kliniczny i należy go potraktować całkiem na serio.

No więc tak: mamy liczbę n zapisaną unarnie. Co to właściwie znaczy?

To znaczy, że mamy n jedynek po kolei. Liczba dwa będzie zapisana jako 11, siedem jako 1111111, a trzydzieści osiem jako 11111111111111111111111111111111111111.

Jakie są zalety takiej notacji?

Prawie żadne: zapis jest mało czytelny, zużywa MNÓSTWO miejsca oraz jest bardzo niewdzięczny do wykonywania działań arytmetycznych. Ma tylko jedną, całkiem niedużą zaletę: da się dzięki niemu skonstruować wyrażenie regularne, które sprawdza pierwszość liczby!

No dobra. Mamy liczbę n zapisaną jako n jedynek:

'1' * n

Jak więc ma się ów unarny zapis liczby n do naszej zagadki?

Zobaczmy jeszcze raz, z bliska, jak wygląda nasze wyrażenie:

'^.?$|^(..+?)\1+$'

Jak widać składa się ono z dwóch sekcji:

'^.?$'

oraz

'^(..+?)\1+$'

rozdzielonych pionową kreską. Dla niezrzeszonych: operator pipe (czyli właśnie ta taka pionowa kreska) to nic innego jak alternatywa: jeżeli pasuje wyrażenie po lewej stronie, to mamy dopasowanie, a jeżeli nie, sprawdzamy wyrażenie po prawej stronie – i jeżeli ono pasuje, to mamy dopasowanie, w przeciwnym razie brak dopasowania.

Skupmy się teraz na pierwszej sekcji:

'^.?$'

To prościutkie wyrażenie regularne sprawdza, czy cały tekst wejściowy składa się wyłącznie z zera lub jednego znaku. Kropka oznacza dowolny znak, a znak zapytania, że poprzedzające go wyrażenie powinno zostać powtórzone nie więcej niż jeden raz (a więc: zero lub jeden razy). Daszek (^) to początek tekstu, a znak dolara ($) to jego koniec. Czyli cały tekst musi składać się z maksymalnie jednego znaku, żeby to wyrażenie pasowało.

To przypadek trywialny: „na twardo” eliminujemy zero i jedynkę ze zbioru liczb pierwszych, ponieważ liczbami pierwszymi NIE są.

Jeżeli więc n=0 lub n=1 wówczas re.match() natychmiast zwróci true, co po zanegowaniu operatorem not wyrzuci false na wyjściu naszej funkcji.

Co się jednak stanie, jeżeli jedynek będzie więcej niż jedna?

Ponieważ lewa strona wyrażenia nie zostanie dopasowana, „włączy się” jego prawa strona:

'^(..+?)\1+$'

Tu już sytuacja się nieco komplikuje – nie na tyle jednak, żebyśmy nie dali rady tego rozgryźć:

Najpierw zauważamy, że znów mamy daszek na początku oraz znak dolara na końcu: podobnie jak w poprzednim przypadku, CAŁY tekst musi zostać dopasowany, a nie tylko jakiś jego fragment.

Co dalej? Zaraz na początku tekstu (po otwierającym daszku) mamy wyrażenie w nawiasie. Jest to grupa numerowana – cokolwiek zostanie dopasowane do wyrażenia w nawiasie, będzie potem dostępne jako grupa numer jeden, do której możemy się odwołać za pomocą wyrażenia \1.

Co mamy w owym nawiasie?

Otóż mamy tam najpierw dwie kropki symbolizujące dwa znaki (dwa DOWOLNE znaki), przy czym drugi z nich może wystąpić więcej niż raz (mówi o tym znak plus).

Co to znaczy?

To znaczy, że do wyrażenia w nawiasie pasuje zarówno 11, jak też 111111 czy 111111111111111111111. Dowolna ilość jedynek – byleby tylko więcej niż jedna.

A po cholerę jeszcze znak zapytania w tym nawiasie?

Otóż znak zapytania po znaczku plus w składni RegEx powoduje, że znaczek plus będzie niezachłanny. Innymi słowy skończy próby dopasowywania w chwili, kiedy natrafi na pierwsze dopasowanie, a nie dopiero wtedy, kiedy zniknie ostatnie dopasowanie.

W naszym przykładzie jeżeli na wejściu będzie pięć jedynek (11111), wyrażenie ..+? znajdzie dopasowanie w postaci ’11’. Gdyby usunąć zeń znak zapytania, znalazłoby dopasowanie ‚11111’ (a więc w celu znalezienia dopasowania zużyłoby na dzień dobry maksymalnie dużo pasujących znaków).

No dobrze. Mamy więc niezachłanny operator wyszukujący nam ciąg dwóch jedynek. Co dalej?

Dalej mamy zamknięty nawias (koniec grupy!), a zaraz za nim \1+$ czyli wspomniane już odwołanie do grupy numer 1 (fachowo nazywa się to backreference czyli po naszemu chyba referencja wsteczna, czy jakoś tak), powtórzone co najmniej raz – i tak aż do końca tekstu.

Co jest w grupie numer 1? Są w niej (chwilowo) dwie jedynki. Czyli \1+$ oznacza „dopasuj kolejne dwie jedynki raz lub więcej niż raz, i tak już do końca linii”.

Załóżmy, że n=5. Unarnie zapisane wygląda tak: 11111. Grupa numer 1 dopasuje najpierw 11, potem wyrażenie \1+ będzie próbowało dopasować kolejną parę jedynek. Dopasuje 11 na pozycji 3 i 4. Następnie spróbuje dopasować następne dwie jedynki, ale znajdzie tylko jedną, na pozycji 5, a zaraz za nią – koniec jedynek! Dupa blada, nie udało się.

Ale, ale. W grupie (..+?) mowa o co najmniej jednym powtórzeniu, prawda? A więc skoro nie udało się z dwiema jedynkami, teraz spróbujemy z trzema.

Nasza grupa numer jeden oznacza teraz trzy jedynki. RegEx próbuje dopasować kolejne trzy (bo za nawiasem ciągle jest \1+$), ale polegnie, bo zostały już tylko dwie. A więc grupa znów „urośnie” o jedną jedynkę, do czterech, drugiej czwórki nie ma, grupa urośnie do pięciu jedynek, drugiej piątki nie ma, grupa już nie może urosnąć do sześciu jedynek, bo nie ma ich aż tylu – całość zwróci false, które obrócone operatorem not wypluje true na wyjściu całej funkcji.

Tłumacząc w dużym uproszczeniu (które jednak nie eliminuje z powyższego rozumowania żadnych kroków), RegEx będzie próbował „podzielić” n na równe kawałki złożone najpierw z dwóch jedynek, potem z trzech, potem z czterech… i tak dalej, aż do n jedynek. Krótko mówiąc będzie sprawdzał podzielność liczby n przez kolejne liczby od 2 do n tak długo, aż znajdzie dzielnik albo aż mu się skończą jedynki.

Jest to bardzo, ale to bardzo nieefektywna metoda sprawdzania pierwszości liczb: zamiast przepuścić je przez sito Eratostenesa, czyli usuwać wyłącznie wielokrotności liczb pierwszych od dwójki do pierwiastka z n, tutaj sprawdzamy wielokrotności wszystkich kolejnych liczb od dwójki aż do n.

Jeżeli do tego dołożymy fakt, że liczba n jest reprezentowana unarnie, czyli samo jej zapisanie zżera mnóstwo pamięci  – mamy jeden z najgorszych algorytmów na sprawdzenie pierwszości.

Testowałem ów algorytm najpierw na małych liczbach – działał bez pudła – a potem naiwnie kazałem sprawdzić pierwszość liczby dziewięciocyfrowej. Oznaczało to najpierw utworzenie w pamięci komputera ciągu kilkuset milionów jedynek, czyli zaalokowanie kilkuset megabajtów tylko na tę jedną liczbę – a następnie żmudne próby dopasowania kolejnych wielokrotności. Komputer się natychmiast zawiesił i już po kwadransie dojrzałem do tego, żeby go odłączyć od zasilania.

Pomogło 😉

Reasumując: homo sapiens to takie bydlę, które znajdzie najbardziej bezsensowne zastosowanie dowolnego narzędzia, a potem będzie się tym chwalić na lewo i prawo. Wykałaczka? Pogrzebię nią sobie w… tego, w nosie dajmy na to. Laptop? Stół mi się kiwa, podłożę pod krótszą nogę. Wielki Zderzacz Hadronów? Wrzucę tam zapiekankę i zobaczę co się stanie. Grabie? Ułożę je na ścieżce w trawie…

Dodaj komentarz

7 komentarzy do "Tajemnicza funkcja: rozwiązanie zagadki"

Powiadom o
avatar
Sortuj wg:   najnowszy | najstarszy | oceniany
Butter
Gość
Kod: [C#] using System; using System.Text.RegularExpressions; namespace RegExp_B { class Program { static void Main(string[] args) { string txt = „1”; Regex re = new Regex(@”^.?$|^(..+?)\1+$”); bool ok; for (int x = 0; x < 40; x++) { ok = !(re.Match(txt).Success); Console.WriteLine("{0:000} [{1}] ", x,ok); txt += "1"; } } } } Wynik: 000 [False] 001 [True] 002 [True] 003 [False] 004 [True] 005 [False] 006 [True] 007 [False] 008 [False] 009 [False] 010 [True] 011 [False] 012 [True] 013 [False] 014 [False] 015 [False] 016 [True] 017 [False] 018 [True] 019 [False] 020 [False] 021 [False] 022 [True] 023… Więcej »
Butter
Gość

Odszczekuję. Mój błąd [powinno być string txt = „”;].

Yzoja
Gość

Dzięki ;D
przy tym moje próby wymyślenia uniwersalnego wzoru na okrąg wpisany w deltoid mają choć trochę sensu ;p

wpDiscuz