Opublikowane w

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

Była część pierwsza i część druga, pora na kolejną, niezupełnie planowaną. Jak pamiętamy w części drugiej udało się ograniczyć sprawdzane liczby do 49 sztuk. To, co chodziło mi od czasu do czasu po głowie to pytanie, czy da się rozwiązać tę zagadkę „na piechotę”, bez użycia komputera?

Rozejrzałem się za możliwymi uproszczeniami i zauważyłem kolejne potencjalne pole do zmniejszenia liczby obliczeń. Jak wiadomo, 711 jest liczbą nieparzystą. Aby suma dwóch liczb była nieparzysta, jedna z nich musi być parzysta, druga nieparzysta. Z kolei aby suma dwóch liczb była parzysta, albo obie muszą być parzyste, albo nieparzyste. Tu mamy do czynienia z sumą czterech liczb, więc są dwa przypadki: albo 1 liczba jest nieparzysta, a 3 parzyste, albo odwrotnie.

Z naszych 49 liczb, 37 jest parzystych, a 12 nieparzystych. Jak to wpływa na przestrzeń rozwiązań? Z 49^4, czyli ok. 5,8 mln przechodzimy na 12*37^3 + 37*12^3 czyli ok. 672 tys. Nadal trochę dużo jak na ręczne liczenie, ale jak to wpłynie na czas obliczeń? Nasz skrypt będzie miał postać:

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

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

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

Niezależnie od kolejności bloków (najpierw 1 liczba parzysta i 3 nieparzyste, co jest teoretycznie korzystniejszym wariantem, czy odwrotnie), potrzebować będziemy poniżej 95 tys. iteracji. Czas to 0,08 sekundy dla zwykłego interpretera Pythona lub 0,12 sekundy dla Pypy.

Możliwa jest też wersja „w dół”:

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

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

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

Ilość potrzebnych iteracji waha się od 18 do 28 tys. w zależności od kolejności bloków, a czas wykonania to 0,06 sekundy dla zwykłego interpretera Pythona i 0,1 sekundy dla Pypy.

Nadal nie jest to wersja do policzenia ręcznie, ale… coraz bliżej.

Opublikowane w

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.

Opublikowane w

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.

Opublikowane w

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.

Opublikowane w

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…