711 wyrazów o optymalizacji – część 2

Tym, co nie czytali polecam lekturę części pierwszej, a tymczasem pojawił się wpis z rozwiązaniem i pojawiło się tam znacznie lepsze podejście do tematu. Korzysta ono z właściwości, że wszystkie składowe muszą być dzielnikami 7,11 i wielokrotnością 0,01. W wersji całkowitej – muszą być liczbami całkowitymi będącymi dzielnikami . Następnie generuje kombinacje tych liczb i sprawdza właściwe warunki. Lekko dostosowany kod to:

import itertools
number = 711
iterations = 0
divs = list()
for i in range(1, number + 1):
    if 711000000 % i == 0:
        divs.append(i)

for i in itertools.combinations_with_replacement(divs, 4):
    iterations += 1
    if sum(i) == 711 and i[0] * i[1] * i[2] * i[3] == 711000000:
        print(i, iterations)

print(len(divs))

Dodałem wyświetlanie ilości dzielników – jest ich raptem 62, więc przeszukiwana przestrzeń to 62^4 czyli… niecałe 15 mln. Rozwiązanie jest znajdowane po nieco ponad 600 tys. iteracji w czasie… pomijalnym, bowiem ok. 0,2 sekundy, niezależnie od interpretera. Przy pomiarze tak niskich czasów wykonania wypadałoby się pobawić już w uśrednianie, ale chodzi o wartości orientacyjne.

W zasadzie nie ma sensu optymalizować dalej, ale pobawić się można. Przede wszystkim, można wyeliminować samo 711 – jeśli którakolwiek wartość byłaby taka, to pozostałe musiałyby być zerami, co jest sprzeczne z warunkami zadania. Kolejny całkowity dzielnik to połowa 711. Po uwzględnieniu tego, skrypt przyjmie postać:

import itertools
number = 711
iterations = 0
divs = list()
for i in range(1, round(number/2) + 1):
    iterations += 1
    if 711000000 % i == 0:
        divs.append(i)

for i in itertools.combinations_with_replacement(divs, 4):
    iterations += 1
    if sum(i) == 711 and i[0] * i[1] * i[2] * i[3] == 711000000:
        print(i, iterations)

print(len(divs))

Ogranicza nam to liczbę sprawdzanych dzielników do 49, przestrzeń do niecałych 6 mln, a liczbę iteracji potrzebnych do znalezienia rozwiązania do 266 tys. Dla przypomnienia, w pierwszym rozwiązaniu, które było czystym brute force zaczynaliśmy od przestrzeni 225 miliardów, czyli 44 tys. razy większej.

A gdyby tak nadal korzystać z dzielników, ale zapomnieć o itertools i wrócić do starych, dobrych pętli, tym razem nie na wartościach, tylko na indeksach w liście divs? Wersja naiwna to:

number = 711
iterations = 0
divs = list()
for i in range(1, round(number/2) + 1):
    iterations += 1
    if 711000000 % i == 0:
        divs.append(i)

for a in range(0, len(divs)-1):
    for b in range(0, len(divs)-1):
        for c in range (0, len(divs)-1):
            for d in range (0, len(divs)-1):
                iterations += 1
                if divs[a] + divs[b] + divs[c] + divs[d] == 711:
                    if divs[a] * divs[b] * divs[c] * divs[d] == 711000000:
                        print("Solved: ", divs[a], divs[b], divs[c], divs[d], iterations)
            exit()

Wyraźny krok wstecz – 3,6 mln iteracji i prawie sekunda (PyPy nadal ~0,2s). Ale otwiera nam to drogę do znanych już optymalizacji:

number = 711
iterations = 0
divs = list()
for i in range(1, round(number/2) + 1):
    iterations += 1
    if 711000000 % i == 0:
        divs.append(i)

for a in range(0, len(divs)-1):
    for b in range(a, len(divs)-1):
        for c in range (b, len(divs)-1):
            for d in range (c, len(divs)-1):
                iterations += 1
                if divs[a] + divs[b] + divs[c] + divs[d] == 711:
                    if divs[a] * divs[b] * divs[c] * divs[d] == 711000000:
                        print("Solved: ", divs[a], divs[b], divs[c], divs[d], iterations)
            exit()

Jest tak dobrze, jak przy itertoolsach: ~0,2s oraz 246 tys. iteracji. Pamiętamy jednak, że najlepsze wyniki były dla sprawdzania od największych do najmniejszych, zatem:

number = 711
iterations = 0
divs = list()
for i in range(1, round(number/2) + 1):
    iterations += 1
    if 711000000 % i == 0:
        divs.append(i)

for a in range(len(divs)-1, 0, -1):
    for b in range(a, 0, -1):
        for c in range (b, 0, -1):
            for d in range (c, 0, -1):
                iterations += 1
                if divs[a] + divs[b] + divs[c] + divs[d] == 711:
                    if divs[a] * divs[b] * divs[c] * divs[d] == 711000000:
                        print("Solved: ", divs[a], divs[b], divs[c], divs[d], iterations)
            exit()

Wynik znajdowany jest już po 30 tys. iteracji, w czasie poniżej 0,1s na zwykłym interpreterze Pythona. Co ciekawe, w tym wariancie PyPy jest nieco wolniejsze, z czasem nieco ponad 0,1s, zapewne większy narzut na uruchomienie interpretera.

711 wyrazów o optymalizacji

Tytuł jest przekorny – raczej nie będzie to 711 wyrazów, ale liczba na początku tytułu dobrze wpływa na klikalność, a 711 jak najbardziej jest na miejscu, za to będzie o optymalizacji.

Mianowicie pojawił się pod koniec zeszłego roku Sekurak Book Simple CTF, gdzie było pewne zadanie. Jeśli chcesz pobawić się w zrobienie tego CTF samodzielnie, choć jest już zakończony[1], to dobry moment na przerwanie lektury wpisu. Zadanie jest na tyle proste i znane, że publikacja rozwiązania nie spowoduje krzywdy, a przy tym podczas dyskusji z kolegą z pracy pojawiły się ciekawe zagadnienia natury optymalizacyjnej, więc postanowiłem opisać.

Zmodyfikowana treść zadania, z zachowaniem pierwotnego sensu, pojawiła się – z moją niewielką pomocą – jako wpis zagadka o siódmej jedenaście na zaprzyjaźnionym blogu. Jeśli ktoś nie chce się bawić w całą CTFową otoczkę, a ma ochotę wytężyć mózg, zapraszam tamże. Tym bardziej, że jest więcej zagadek.

Całość daje się sprowadzić do układu dwóch równań z czterema niewiadomymi:
a + b + c + d = 7,11
a * b * c * d = 7,11
WolframAlpha – być może niewprawnie użyty – protestował Standard computation time exceeded, ale przecież to się da policzyć… W końcu chodzi o wartości nieciągłe, bo ceny muszą być wielokrotnością jednego grosza. Wiemy zatem, że każda z wartości jest większa od zera, mniejsza od 711 i jest wielokrotnością 0,01. Tu pauza – komputery znacznie lepiej radzą sobie z wartościami całkowitymi[2], więc przemnóżmy wartości przez 100 i przejdźmy w tym momencie na resztę czasu równoważną formę:
a + b + c + d = 711
a * b * c * d = 711000000

Przy naiwnym brute force, korzystając jedynie z faktu, że wszystkie zmienne muszą być liczbami całkowitymi, bez żadnych optymalizacji, mamy do sprawdzenia maksymalnie 711^4 kombinacji, czyli 225 miliardów. Można to zapisać w Pythonie w postaci:

limit = 712
iterations = 0
for a in range(1, limit):
    print(a)
    for b in range(1, limit):
        for c in range(1, limit):
            for d in range(1, limit):
                iterations += 1
                if a + b + c + d == 711:
                    if a * b * c * d == 711000000:
                        print("Solved: ", a, b, c, d, iterations)
                        exit()

Jak widać zliczam też ilość iteracji, i dzięki temu wiem, że komputer musi – w różnych pętlach – policzyć w sumie prawie do 43 miliardów, zanim znajdzie rozwiązanie. Czas znalezienia rozwiązania litościwe pominę – spokojnie można wybrać się na spacer czy zakupy.

Mamy jednak dwie dodatkowe własności: iloczyn czterech liczb oraz ich sumę. Jeśli ktoś bawił się w sprawdzanie, czy dana liczba jest pierwsza, to pamięta zapewne, jeśli liczba jest złożona, to mniejszy dzielnik będzie co najwyżej równy pierwiastkowi danej liczby. W naszym przypadku iloczyn dwóch niewiadomych będzie co najwyżej równy pierwiastkowi z 711000000, czyli 26665. Z kolei któraś z niewiadomych będzie mniejsza od pierwiastka z 26665, czyli nieco ponad 163. Można więc ograniczyć jedną ze zmiennych – oczywiście tę najczęściej używaną – do 163.
Dodatkowo, niewiele myśląc, można skorzystać z własności sumowania i ograniczyć pozostałe zmienne do 711-163=548, czyli zmniejszyć przeszukiwaną przestrzeń do niecałych 27 miliardów. Oblekając to w skrypt:

limit = 549
iterations = 0
for a in range(1, limit):
    print(a)
    for b in range(1, limit):
        for c in range(1, limit):
            for d in range(1, 164):
                iterations += 1
                if a + b + c + d == 711:
                    if a * b * c * d == 711000000:
                        print("Solved: ", a, b, c, d, iterations)
                        exit()

Czas potrzebny na rozwiązanie nadal pomijam, ale jest to raczej tyle, ile potrzeba na zrobienie kawy czy herbaty, niż zakupów. Ilość iteracji potrzebnych do znalezienia rozwiązania to niecałe 6 mld.

Jeśli nie pamiętamy o ciekawej własności związanej z dzielnikami danej liczby, to nadal możemy zoptymalizować pętle tak, żeby automatycznie uwzględniać w nich warunek związany z sumą – daną zmienną zwiększamy do wartości zależnej od wartości pozostałych zmiennych, dzięki czemu można zaobserwować, że w miarę wzrostu wartości zmiennej a sprawdzenia pozostałych są coraz szybsze.

limit = 712
iterations = 0
for a in range(1, limit):
    print(a)
    for b in range(1, limit - a):
        for c in range(1, limit - a - b):
            for d in range(1, limit - a - b - c):
                iterations += 1
                if a + b + c + d == 711:
                    if a * b * c * d == 711000000:
                        print("Solved: ", a, b, c, d, iterations)
                        exit()

Rozwiązanie jest znajdowane nawet nieco szybciej, niż w poprzednim przypadku – ok. 5,5 mld iteracji.

Tu pojawił się pomysł – a co gdyby zapisać to w taki sposób, by program działał na początku bardzo szybko i zwalniał? Czyli nie zaczynamy od niskich wartości zmiennych i zwiększamy, tylko zaczynamy od wysokich i zmniejszamy? Można to zapisać następująco:

limit = 711
iterations = 0
for a in range(limit, 0, -1):
    print(a)
    for b in range(limit - a, 0, -1):
        for c in range(limit - a - b, 0, -1):
            for d in range(limit - a - b - c, 0, -1):
                iterations += 1
                if a + b + c + d == 711:
                    if a * b * c * d == 711000000:
                        print("Solved: ", a, b, c, d, iterations)
                        exit()

Przyznaję, że efekty tego podejścia mnie zaskoczyły. Tylko 1 mld operacji potrzebnych do znalezienia rozwiązania. Na moim sprzęcie skrypt wykonał się poniżej 3 minut na Pythonie 3.8.3. Co ciekawe dla Pythona 2.7.18 był to czas poniżej 2 minut, więc znacznie szybciej. Oba z paczek z repo Debiana unstable. Ale to raczej tylko ciekawostka, Python 2 jest martwy.

Dochodzimy jednak do sedna. Widać, że interpreter Pythona ma znaczenie. Jeśli zależy nam na szybkości, to warto zainteresować się alternatywną implementacją Pythona, czyli projektem PyPy. PyPy w wersji 7.3.1 (kompatybilna z Pythonem 3.6.9) wykonuje powyższy program w… nieco ponad 3 sekundy. Czyli jakieś pięćdziesiąt razy szybciej. Jeśli wrócimy do rozwiązania drugiego, to okaże się, że z użyciem PyPy można je znaleźć w 17 sekund. Natomiast wersja naiwna to… raptem 2 minuty.

Jak widać, szybkie narzędzia mogą prowadzić do lenistwa umysłowego – skoro działa szybko, to po co optymalizować? Optymalizacja algorytmu w powyższych przykładach nie jest skończona, da się lepiej. Znacznie lepiej. Na razie zostawię pole do popisu czytelnikom w komentarzach, za jakiś tydzień zaktualizuję wpis.

[1] Jest to naprawdę prosty CTF, jeśli ktoś nie miał okazji się bawić – polecam przymierzyć.
[2] Jak mawiają: real programmers use integers.

Poznańskie Targi Piwne

W tym roku pierwszy raz w życiu wylądowałem na Poznańskich Targach Piwnych. Jakoś nigdy nie miałem parcia i zawsze wolałem iść do pubu, gdzie wybór piw pewnie mniejszy, ale nadal duży, niż na imprezę typu targi, która kojarzy mi się z halą i kolejkami.

Niesłusznie. Kolejki owszem, były, atmosfera hali również, ale… nie przeszkadza to aż tak bardzo. Wybór browarów i piw faktycznie imponujący, a zawsze miło napić się dobrego piwa w dobrym towarzystwie.

Wstęp na jeden dzień to 20 zł i w ramach wstępu otrzymujemy… wstęp. Nawet bez talonu na jakieś piwo, czyli tak trochę smutno. Do wersji dwudniowej (35 zł) dodawana jest szklanka, niestety 0,5 l. Niestety w ramach wstępu nie było żadnej „mapy” z opisem browarów, więc startowaliśmy po omacku, rozdarci między nowymi browarami, których nazwy nic nam nie mówiły, a tymi, które znamy. Nie był to może duży problem, ale na początku odczuwaliśmy zgodnie głód czegoś do poczytania. Zdecydowanie jest pole do poprawy, można dać i „mapę” stoisk wraz z opisem browarów, i małe (0,25-0,3 l) szklanki do wszystkich pakietów, żeby nie generować tony plastikowych śmieci.

Kolejny minus – ceny piw. W większości stoisk były co prawda porcje 100 ml, ale po 5 zł. Typowa cena za 0,5 l to 13 zł, czyli nadal porównywalnie z pubem, więc wybór był prosty. Szczęśliwie byliśmy grupą i szybko opracowaliśmy system, że kupujemy duże piwa, a każdy ma mały kubeczek do degustacji. Może źle rozumiem ideę targów, ale zakładam, że chodzi o promocję wyrobów, czyli dominować powinny małe porcje w niskich cenach (3 zł za 100 ml brzmi dobrze). Niektóre browary sprzedawały co prawda zestawy bodajże sześciu próbek na tekturowej tacce z otworami. Pomysł niezły, choć nie unikamy plastiku. Niestety ponownie cena nie zachęcała.

Poza piwem było także jedzenie z foodtrucków w przyległej hali, więc jeśli ktoś zgłodniał, to mógł coś przegryźć, a nawet miał spory wybór. Warunki zdecydowanie sprzyjające dłuższej biesiadzie.

Były też dwie dodatkowe atrakcje. Reklamowane ze sceny „badanie jajek”, czyli profilaktyka raka jąder. W jednym ze stoisk można było wykonać badanie. Ostatecznie niestety się nie wybraliśmy, ale pomysł dobry.

Kolejna atrakcja to bieg Piwna mila. O biegu dowiedziałem się zbyt późno (czytaj: po fakcie), a szkoda. Komponuje się z bieganiem, którego ostatnio u mnie więcej (notka wkrótce), więc pobiegłbym. For fun, nie na czas, rzecz jasna. W końcu mila nie dystans…

Browarowych odkryć nie było – dwa browary ugruntowały sobie u mnie dobrą opinię, kolejne dwa zdobyły status godne uwagi. Czas spędzony miło i ogólnie, mimo wymienionych wyżej drobnych minusów, imprezę oceniam wysoko i zdecydowanie postaram się nie przegapić jej za rok.

Google CTF beginners quest 2019

W tym roku zostałem zaskoczony informacją o odbywającym się Google CTF na urlopie. Link o tym, że się odbywa wpadł z Hacker News. Zdziwiłem się, że minął już rok od ostatniej edycji. Planowałem poklikać podobne rzeczy, więc choć miałem nieco inne plany to stwierdziłem, że mogą poczekać, bo w zeszłym roku zabawa przednia była.

Google CTF 2019 screenshot

W tym roku formuła CTF dla początkujących była nieco inna. Wiele ścieżek, różne przejścia między węzłami (czyli więcej, niż jedna flaga w zadaniu), różne zakończenia w zależności od poziomu trudności. Nieco mieszane uczucia mam w stosunku do tego podejścia, zwł. szkoda, że nie widać wszystkich przejść między zadaniami.

Ponieważ urlop, to było sporo innych, ciekawszych zajęć, więc dość szybko się zniechęciłem. W zasadzie od razu po dotarciu do najłatwiejszego końca. Zadania wydawały mi się trudniejsze, niż w zeszłym roku. Albo inaczej – wymagające użycia dedykowanych narzędzi. W zeszłym roku chyba było bardziej ogólnie, przynajmniej jeśli chodzi o narzędzia, w tym bez gdb i pwntools wydaje mi się, że nie było szansy, nawet na najprostszym poziomie.

Nadal można próbować sił, do czego zachęcam. I w sumie sam pewnie siądę do reszty zadań w chwili wolnej, o ile jeszcze CTF będzie aktywny…

Security score compare

Nazwa projektu jest nieciekawa, ale przyznaję, nie miałem weny. Za to mówi wszystko. Zaczęło się od porównywania punktacji na platformach do zabaw z security wśród znajomych z pracy. Szybko zeszło na to, że suche porównywanie wyników nie jest zbyt fajne, lepiej byłoby rysować wyniki w czasie.

I tak powstał skrypt w Pythonie, który pobiera wyniki z Root Me oraz RingZer0 Team Online CTF[1], parsuje HTML przy pomocy regexpa[2] i zapisuje do bazy SQLite. W innym trybie pobiera dane dla podanej platformy i generuje obrazek z wykresem punktacji. Taki jak poniżej:

Przykładowy ocenzurowany wykres generowany przez security score compare

Po drodze jest parę uproszczeń (typu dopełnianie braków zerami „od lewej”) i jest to bardzo wstępna wersja, ale działa i coś tam już widać. Strzelać z tego nikt nie będzie. 😉

Security score compare znaleźć można na GitHubie. Może komuś się przyda, albo nawet ktoś pomoże w rozwoju?

Jakby ktoś się zastanawiał, czemu ostatnio jest mniej wpisów na blogu, to tak, mam nowe zajęcie w czasie wolnym. 😉

[1] Nie są to wszystkie platformy na których się bawimy, ale te dwie są najpopularniejsze i… nie wymagają logowania, by sprawdzić punktację.
[2] Tak, wiem, ble i fuj. Ale działa.