Puzzled

Najpewniej w obawie bym z żoną nie poszedł w ślady siostry, mama podarowała mi na Mikołaja pucle.

Jak wiadomo układanie zaczyna się od ramki, bo obwód jest bytem o jeden wymiar chudszym niż wnętrze. Podczas, gdy małżonka zajęła się najbardziej interesującą ją częścią obrazka, a więc przyziemną, ja postanowiłem pobujać w obłokach. Niestety, górna połówka ramki, a więc około 75 klocków było bezchmurne. Mając więc przed sobą kupkę 75 identycznie w pełni niebieskich klocków z jednym płaskim brzegiem oraz dwa takież narożniki postanowiłem podejść do sprawy systematycznie.

Nie wiem czy znacie to uczucie: wiecie, że jedyny słuszny sposób zrobienia czegoś to postępować zgodnie z algorytmem X, ale czujecie się jakoś tak nieswojo na myśl, że będąc istotą ludzką mielibyście coś zrobić zgodnie ze schematem. Przykładowo: czy widząc leżące na podłodze wyprane skarpetki próbowaliście użyć algorytmu maxflow by połączyć je w pary? Albo czy zdarzyło Wam się karty na ręce posortować radixem?

No więc jeśli przyjąć, że pewne klocki do siebie pasują a pewne nie, to mamy do czynienia z grafem relacji "pasowania", zaś ułożenie ramki to nic innego jak szukanie w nim cyklu Hamiltona. Zajęcie to jak wiadomo jest dość trudne, a jednak ludzie puzzle układają. Jest tak zapewne dlatego, że często do danego puzzla pasuje dokładnie jeden inny, więc tak naprawdę nasz graf jest już cyklem i układanie ramki idzie jak po sznurku. Nawet jeśli mamy do czynienia z puzzlem nieco bardziej wykwintnym, to należy się spodziewać, że to czy klocki do siebie pasują zależy głównie od kształtu brzegu, co prowadzi do innego modelu: zamiast traktować klocki jak wierzchołki, a pasowanie do siebie jak krawędzie, można traktować kształty brzegów jak wierzchołki, a posiadanie dwóch brzegów reprezentować przez krawędzie. Co nam to daje? Ano wtedy problem zaczyna przypominać szukanie cyklu Eulera w grafie skierowanym, co jak wiadomo jest znacznie prostsze.

Nie wiem czy kiedyś próbowaliście szukać cyklu Eulera, ale generalnie algorytm jest dość prosty -- na tyle prosty, że daje się uruchomić na mózgu w wersji Homo Sapiens. W oryginale (czyli na komputerze) wystarczy DFS. W praktyce należy układać ramkę "na hurra", czyli dopóki klocki pasują to dokładać je na koniec takiego długiego węża. Gdy w końcu wydaje nam się, że węża już się nie da przedłużyć, to znak, że należy ostatnio dołożony klocek przełożyć na sam początek (albo na inny stół jeśli tak nam wygodniej) -- co zabawne, będzie tam pasował:)

Oczywiście takie podejście wymagałoby czasu n^2, co przy 75 klockach jest trochę niehalo. Powodami dla których ja osobiście czuje opór przed wykonywaniem algorytmów w sposób dokładnie taki jak robi to komputer NIE jest to, że :

• nie umiem wykonywać miliarda operacji na sekundę
• nie umiem pamiętać miliarda liczb na raz

o nie, problem jest gdzie indziej:

• nie potrafię się skupić
• mylę się
• nienawidzę robić czegoś bezmyślnie, dla zasady, bo tak mówi procedura, jeśli widzę "od razu", że coś da się zrobić szybciej

Zwłaszcza ten ostatni punkt, powoduje, że większość algorytmów, które mają fajną złożoność wg notacji O, w praktyce zanudziłyby mnie na śmierć.

No więc po pierwsze, znalezienie cyklu Eulera wymaga znalezienia pasującego klocka. Jeśli interesuje nas równość, np. równość brzegów, to naturalnie narzucającą się strukturą danych jest tablica hashująca. Zabrałem się więc do kategoryzowania klocków. Na początek podzieliłem je na te co mają pimpelek i te co mają dziurkę. Potem postanowiłem podzielić je na te co mają brzeg skośny w prawo, skośny w lewo i pozostałe. I tutaj poległem. Okazało się, że weryfikacja w którą stronę skończy jest klocek wymaga ode mnie kręcenia głową, klockiem i długiego wpatrywania -- to było dla mnie zaskakujące. Nie wiem czy próbowaliście kiedyś po omacku włożyć kabel od monitora do karty graficznej -- ten taki trapezoidalny -- ja zawsze mam problem bez patrzenia aby ustalić, w którą stronę ten trapez jest skośny. Dziwne, ale prawdziwe.

Postanowiłem więc porzucić koncepcję dalszego hashowania moich klocków. Gdy zawodzi tablica hashująca, należy spróbować posortowanej tablicy i binary searcha. Plan był prosty. Posortować wszystkie klocki wg długości górnej części lewego boku (tj od narożnika do pimpelka bądź dziurki). Po takim preprocessingu możnaby znajdować dobry klocek w czasie lg 33, czyli około 5 porównań.

No ale jak posortować? Oczywiście w grę wchodziły tylko algorytmy o złożoności O(n lg n) -- niestety radix sort nie wchodzi w grę. Do głowy przyszły mi tylko dwa: quick sort i merge sort. Ważnym kryterium wyboru było to czy będę umiał się połapać. Niestety quicksort wymaga trzech rąk (zmiennych) jednej do trzymania pivotu, jednej do trzymania lewego i jednej do trzymania prawego klocka. Nie wiem czemu nie pomyślałem o heap sorcie, który byłby idealny bo nie trzeba nic pamiętać, wystarczy tylko dobrze wszystko ułożyć na stole. Koniec końców może nieco losowo, ale wybrałem merge sorta. Wybór był jak się szybko okazało słuszny.

Otóż, porównanie który z dwóch klocków ma dłuższy boczek nie jest rzeczą łatwą ani chyba nawet wykonalną gołym okiem. Przykładanie ich do siebie dawało różne wyniki w zależności od lekkich przechyleń na boki. Powodowało to, że podczas operacji scalania posortowanych ciągów, tworzyły mi się klastry nierozróżnialnych elementów. Analogicznie w quicksorcie oznaczałoby to, że oprócz kupki małych i kupki dużych elementów, powstawałaby nam też kupka nieodróżnialnych od pivota.

Muszę powiedzieć, że nie wierzyłem, że dotrwam, ale jestem pewnie jedną z niewielu żyjących osób, która ręcznie wykonała mergesorta na 75 elementach. Po drodzę jednak odkryłem coś, co pogrążyło moje nadzieje na wielomianowy algorytm układania puzzli. Relacja podobieństwa klocków nie jest przechodnia. Tzn. może być tak (i było), że masz trzy klocki a,b,c takie że a i b wydają się identyczne, b i c też, ale między a i c już dostrzegasz różnicę. Implikacja jest taka, że graf przestajemy mieć do czynienia z cyklem Eulera. Musimy wrócić do interpretacji grafowej, w której to klocki są wierzchołkami i do szukania cyklu Hamiltona. Pocieszające jest może jednak to, że graf jest pewną formą grafu interwałowego. Niestety trochę zawaliłem obecność na wykładzie z Algorytmów Grafowych i nie znam, żadnego łatwego algorytmu na szukanie cyklu Hamiltona w grafie przedziałowym, zwłaszcza takim skierowanym.

To co mnie jednak zaczęło zastanawiać, to jak w zasadzie wygląda optymalny algorytm sortowania floatów, czy innych obiektów takich jak puzzle, które można porównywać tylko w granicach pewnego błędu dokładności. Czyli w takim modelu, gdzie porównanie mówi nam ab+eps, albo a jest blisko b. Czytelnik zechce zauważyć, że mimo iż w sortowanym zbiorze mogą być elementy nierozróżnialne, to i tak może się zdarzyć tak że istnieje dokładnie jeden porządek. Przykładowo jeśli epsilon=0.1, a my do posortowania mamy ciąg 0, 0.14 , 0.2, 0.26, to mimo, że 0.14 jest nie do odróżnienia od 0.2, to i tak, wiemy, że musi być przed nim (dlaczego?).

Tak więc posortowawszy tak starannie, przystąpiłem do układania bylejak (tzn. zachłannie), bo straciłem wiarę w to, że to ma jakiś sens. Gdy po tygodniu w skończyłem, moja ukochana wręczyła mi kubek paruset idealnie niebieskich klocków wewnętrznych.