Pchełki Python: liczbowy most

https://xpil.eu/jk0Kh 📋

Jak niedawno wspominałem, lubię od czasu do czasu ponaprężać mózguły. Rozciąganie aksonów jeszcze nikomu nie zaszkodziło, no i fajnie jest zmierzyć się czasem z jakimś problemem i go samodzielnie rozwiązać.

Tylko teraz tak: załóżmy, że mamy gwóźdź oraz dwie deski, które owym gwoździem mamy za zadanie połączyć. Czy jeżeli użyjemy młotka, zamiast udawać Gustlika (z "Czterech pancernych") i wcisnąć gwóźdź ręką - czy w takiej sytuacji możemy uznać, że gwóźdź wbiliśmy samodzielnie?

Pytam, ponieważ natrafiłem niedawno na problem, z którym nijak nie potrafiłem sobie poradzić i w końcu zaprzągłem doń komputer. Ale nie w taki sposób, że wszedłem na Google w poszukiwaniu odpowiedzi - o, nie. Zamiast tego włączyłem JetBrains PyCharm (Community Edition - bo za darmo) i napisałem malutką Pchełkę, która problem rozwiązała za mnie.

Zadanie jest następujące:

Po jednej stronie rzeki stoi sobie facet.

Przez rzekę przerzucony jest most.

Niestety, most jest zabezpieczony. Na każdym z pięciu przęseł znajduje się wielki wyświetlacz z jakąś liczbą całkowitą.

Jeżeli na wyświetlaczu jest liczba między 21 a 25, to takie przęsło jest bezpieczne. Jeżeli natomiast liczba jest mniejsza od 21 lub większa od 25, to takie przęsło jest pułapką i wejście na nie kończy się śmiercią lub kalectwem.

Liczby można do pewnego stopnia kontrolować: można do nich dodawać osiem lub odejmować trzynaście.

Ale - uwaga - wyłącznie parami.

A więc tak: na początku poszczególne przęsła (będę dalej pisał "pola" bo mi tak łatwiej) mają następujące wartości:

17, 26, 20, 19, 31

Zadanie polega na tym, żeby doprowadzić te liczby - każdą z nich - do wartości z przedziału [21-25], przy czym jedyny sposób na zmianę wartości liczb to wybranie dwóch z nich, a następnie dodanie do nich (do tych dwóch wybranych) osiem lub odjęcie od obydwu trzynaście.

Dodatkowym ograniczeniem jest ilość operacji, których jest maksymalnie dziewięć. A więc po dziewięciu (lub mniej) krokach powinniśmy dostać na każdym polu wartość z przedziału 21-25. Za każdym razem wybieramy dwa pola oraz decydujemy, czy chcemy dodać ósemkę, czy odjąć trzynastkę.

Robiąc to zadanie na piechotę szybko dojdziemy do wniosku, że ilość możliwych kombinacji jest taka, że nijak nie można znaleźć tej właściwej.

Gdyby chcieć zasymulować wszystkie możliwe kombinacje, okaże się, że dziewięć par pól można wybrać na miliard różnych sposobów, a ilość kombinacji rośnie jeszcze o trzy rzędy wielkości po dołożeniu wszystkich kombinacji ósemek i trzynastek. W sumie około biliona kombinacji lekką ręką. Nie stać mnie na taki serwer, więc trzeba temat ugryźć inaczej.

Pamięta ktoś jeszcze moje zabawy z metodą Monte Carlo i losowym spacerem wzdłuż łańcuchów Markowa? Dzisiejsza pchełka jest trochę analogiczna, tylko tym razem zamiast rysowania tras czy też wyszukiwania przybliżenia Pi, zajmiemy się znalezieniem kombinacji, która generuje poprawny wynik.

Ogólny algorytm będzie wyglądał następująco:

1. Ustaw wynik na pusty ciąg, wyzeruj most (czyli ustaw pola na [17, 26, 20, 19, 31]), ustaw krok = 1
2. Wylosuj dwa pola P1, P2, wylosuj D = 8 lub -13
3. Do P1 oraz P2 dodaj D, dopisz pozycje pól P1 i P2 oraz wartość D do wyniku
4. Sprawdź, czy wszystkie pola mieszczą się w przedziale 21-25; jeżeli tak, wyświetl wynik i zakończ program
5. Zwiększ krok o 1
6. Jeżeli krok > 9, przejdź do 1
7. Przejdź do 2

Coś jakby zamiast strzelać celując do tarczy, zamknąć oczy i strzelać w losowych kierunkach tak długo, aż się trafi. Metoda raczej niezalecana na polu bitwy, w przypadku rozwiązywania niektórych zadań logicznych okazuje się działać doskonale!

Poniżej kod:

from random import getrandbits, sample

gotowe, podejscia = 0, 0
while not gotowe:
    podejscia, mostek, rozwiazanie = podejscia + 1, [17, 26, 20, 19, 31], ""
    for i in range(9):
        pola, zmiana = [a for a in sample(range(5), 2)], 8 if getrandbits(1) == 0 else -13
        mostek[pola[0]], mostek[pola[1]] = mostek[pola[0]] + zmiana, mostek[pola[1]] + zmiana
        rozwiazanie += "\n" + str(pola[0]) + "-" + str(pola[1]) + "-" + "({0:+d}) [".format(zmiana) + ",".join(
            str(x) for x in mostek) + "]"
        gotowe = 1 if all([21 <= x <= 25 for x in mostek]) else 0
        if gotowe:
            print("Rozwiązanie:", rozwiazanie, "\nUdało się w {} podejściach".format(podejscia))
            break

W powyższym kodzie sporo się dzieje, postaram się skomentować najciekawsze kawałki:

L1: Funkcja getrandbits umożliwi nam wylosowanie ósemki bądź trzynastki, natomiast funkcja sample wylosuje nam dwa spośród pięciu pól

L7: tu losujemy dwa pola (losujemy dwa elementy z listy pięcioelementowej 0..4 - pamiętajmy więc, że pola są ponumerowane od zera do czterech a nie od jeden do pięciu) oraz ósemkę lub minus trzynastkę

L9-10: Dopisujemy wylosowane pola oraz 8 lub -13 do wyniku. Dodatkowo zapamiętujemy też "obraz" całego mostu. Proszę zwrócić uwagę na wyrażenie {0:+d} - takie sformatownie liczby spowoduje, że przed liczbą pojawi się jej znak (a więc zobaczymy albo -13 albo +8 - bez tego plusika przed d zamiast +8 zobaczylibyśmy samo 8)

L11: Tutaj sprawdzamy, czy wszystkie pola mieszczą się w przedziale 21-25. Proszę zwrócić uwagę na operator all (ładnie skraca zapis - nie musimy jawnie iterować po elementach) oraz sposób, w jaki sprawdzamy przynależność liczby do zakresu: zamiast pisać dwa osobne warunki (x<=25 AND x>=21) piszemy po prostu 21<=x<=25. Ponadto występuje tu opisywany już wcześniej operator trójwartościowy: x if warunek else y (czyli jeżeli warunek jest spełniony, wybierz x, w przeciwnym razie wybierz y - w C++ zapisalibyśmy to jako warunek?x:y)

Jaka jest wydajność powyższego algorytmu?

Hm. Raczej słaba. Na wynik trzeba czekać czasem pięć sekund, czasem pół minuty, czasem pięć minut. Takie są uroki metody Monte Carlo - jest ona stricte losowa i czasem po prostu nie udaje się trafić we właściwe rozwiązanie w krótkim czasie.

Ilość iteracji waha się zazwyczaj między 500 a 5000 prób, jednak zdarzyło mi się raz, że program znalazł rozwiązanie po zaledwie 84 podejściach - zdarzyło mi się też, że podejść było ponad 50 tysięcy.

Wynik działania programu wygląda następująco (pamiętajmy o "przesuniętej" numeracji pól: pierwsze pole ma numer 0 a ostatnie - 4):

Gotowe:

1-4-(+8) [17,34,20,19,39] 3-0-(+8) [25,34,20,27,39] 1-4-(+8) [25,42,20,27,47] 1-4-(-13) [25,29,20,27,34] 4-2-(-13) [25,29,7,27,21] 3-1-(-13) [25,16,7,14,21] 1-2-(+8) [25,24,15,14,21] 3-2-(+8) [25,24,23,22,21] Udało się w 13281 podejściach

Jak widać można łatwo prześledzić i zweryfikować poszczególne kroki.

Nudne, c'nie?

https://xpil.eu/jk0Kh 📋