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.

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.

Aktualizacja Debiana do Buster

Parę dni temu Debian ogłosił wydanie nowego stabilnego wydania o nazwie kodowej Buster. Aktualizację zacząłem natychmiast, ale dopiero teraz mogę nieco o niej napisać.

Przede wszystkim, pospieszyłem się. Szóstego lipca tylko zerknąłem na newsy i… pomyliłem poprzedniego newsa, dotyczącego wydania wersji 9.9 z wydaniem Bustera. Co prawda rzecz działa się już w trakcie wydawania (co widać było na Twitterze), ale zrobiłem lekki falstart.

Lekko zdziwił mnie brak release notes (zasługa falstartu), ale większość rzeczy mam odseparowanych w kontenerach LXC, więc aktualizacje powinny proste, poza tym, który to już raz? Wziąłem na warsztat przy kawie jedną maszynkę fizyczną i kontenery LXC na niej. Kontenery poszły od kopa w stylu apt-get update && apt-get upgrade && apt-get update && apt-get dist-upgrade. Nie jest to zalecany sposób – w release notes jest napisane, by korzystać z apt, ale nie wiedziałem o tym i… nie miało to znaczenia.

Aktualizacja hypervisora również gładka, kontrolny reboot i… kontenery się nie podnoszą. Co prawda apt-listchanges (polecam!) pisał, że LXC 3 got some significant changes from LXC 2, ale pozwoliłem zmienić konfigurację do nowej wersji, stosowane brakujące linie też były dodane. Wyszukiwarka nie pomagała, ludzie na kanale też nie. Z szybkiego upgrade od kawy zrobiła się godzinna walka z debugiem. Okazało się, że czyste, nowe kontenery z Busterem z minimalnym konfigiem także nie startują (error w loglevel INFO, hmm…):

# create
lxc-create -n test3 -t download -- -d debian -r buster -a amd64

# run
lxc-start -n test3 -l debug -o /tmp/debuuug.txt

# logs
tail -n 8 /tmp/debuuug.txt
lxc-start test3 20190706132233.984 NOTICE   start - start.c:start:2037 - Exec'ing "/sbin/init"
lxc-start test3 20190706132233.985 NOTICE   start - start.c:post_start:2048 - Started "/sbin/init" with pid "8584"
lxc-start test3 20190706132233.985 NOTICE   start - start.c:signal_handler:430 - Received 17 from pid 8582 instead of container init 8584
lxc-start test3 20190706132233.985 DEBUG    lxccontainer - lxccontainer.c:wait_on_daemonized_start:830 - First child 8580 exited
lxc-start test3 20190706132233.999 DEBUG    start - start.c:signal_handler:447 - Container init process 8584 exited
lxc-start test3 20190706132233.999 INFO     error - error.c:lxc_error_set_and_log:49 - Child <8584> ended on error (255)
lxc-start test3 20190706132233.999 DEBUG    network - network.c:lxc_delete_network:3180 - Deleted network devices
lxc-start test3 20190706132234.152 INFO     conf - conf.c:run_script_argv:356 - Executing script "/usr/share/lxcfs/lxc.reboot.hook" for container "test3", config section "lxc"

O dziwo kontenery w wersji ze Squeeze startowały. Doraźnie wróciłem w kontenerach do Squeeze (z backupu, nie downgrade) i na pewien czas zostawiłem sprawę., chociaż okazało się, że startują dość kulawo – nie podnosiła się sieć ani nie uruchamiały usługi, trzeba to było robić ręcznie po każdym restarcie kontenera. Niefajne, ale do czasu znalezienia rozwiązania docelowego można wytrzymać, tym bardziej, że restarty są rzadkością.

Ostatecznie właśnie problemy ze startem i porównanie działania LXC na innym, świeżym hypervisorze z Buster, gdzie wszystko działało bez problemu naprowadziły mnie na rozwiązanie. Przy diagnostyce przy pomocy systemctl status otrzymywałem komunikat:

System has not been booted with systemd as init system (PID 1). Can't operate

Rozwiązaniem okazało się przejście na systemd i odinstalowanie pakietów związanych ze starym systemem init (niestety nie zapisałem nazw). IIRC na hypervisorze i w kontenerach. Po tym zabiegu wszystko działa poprawnie i startuje automatycznie, zarówno ze Squeeze w kontenerach, jak i po aktualizacji do Bustera.

Nie zaktualizowałem jeszcze wszystkich maszyn[1], ale z godnych odnotowania zmian – kontener generujący Planetę Joggera został w końcu zaktualizowany do nowej wersji Debiana, tj. do Bustera, bezpośrenio z Jessie zresztą[2]. Z działaniem na Squeeze był problem, na wersji testowej czy unstable także wtedy nie działało. Na szczęście jest już poprawione, co oznacza, że planeta ma szansę istnieć kolejne parę lat.

Ogólnie póki co aktualizacja całkiem przyjemna i prosta, o ile się ma systemd.

UPDATE: Na ostatnim serwerze napotkałem kolejny problem – skrypty w Pythonie korzystające z virtualenv przestały działać. Rozwiązanie łatwe do znalezienia po wpisaniu komunikatu – trzeba usunąć i utworzyć virtualenv na nowo. Dotyczyło zarówno Pythona 2 jak i Pythona 3.

[1] Został jeden serwer i jakieś desktopy na których akurat nie mam unstable i RPi robiące za router, którego trochę boję się zdalnie aktualizować, bo to zdalny system i nie mam żadnej alternatywnej łączności.

[2] Aktualizacja z przeskokiem wersji nie jest zalecanym sposobem, ale skoro to tylko okrojony kontener, który mogę w każdej chwili przywrócić z backupu, to czemu by nie spróbować?

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.