Tag: Python

Opublikowane w

OR-tools

Niedawno xpil wrzucił zagadkę dotyczącą rozmieszczenia liczb na wierzchołkach dwunastościanu foremnego. Nieco rozochocony zeszłorocznym Advent of Code (który w znacznym stopniu odpuściłem, za wiele srok) stwierdziłem, że „to się zaprogramuje”.

Suma liczb na każdym boku była dość spora, ale istniało ograniczenie w postaci wymogu, że muszą być liczbami pierwszymi, więc może nie będzie tak źle? No bo na ile sposobów można wybrać pięć liczb z nieco ponad trzystu tak, by suma dawała określoną wartość? Otóż niestety na wiele i po wstępnej przymiarce wiedziałem, że brnę w ślepą uliczkę.

Przypomniałem sobie o Z3 solver, które bywa wykorzystywane w CTFach do rozwiązywania zadań i wyglądało trochę na szwajcarski scyzoryk. Tyle, że nie znam tego rozwiązania – nigdy nie znalazłem czasu, by się nauczyć. Ale od czego mamy AI? Porozmawiam z chatem, na pewno pomoże.

Rozmowę zacząłem jednak od problemu ogólnego, trochę licząc, że jest jakiś wyjątkowa właściwość lub algorytm dla tego dwunastościanu. Gdy poprosiłem o kod w Pythonie, ku mojemu zdziwieniu zaproponował rozwiązanie z użyciem nie Z3, tylko OR-tools. Zerknąłem i okazuje się, że Microsoft zrobił Z3, a Google zrobiło coś może mniej uniwersalnego, ale podobno szybszego, przeznaczonego do optymalizacji.

Przyznaję, że OR-tools robi dobre wrażenie. Podobnie jak Z3 nie jest proste i intuicyjne, ale po krótkiej chwili walki z chatGPT udało się złożyć program, który znalazł rozwiązanie. W bardzo krótkim czasie, rzędu kilkunastu sekund. Co ciekawe, algorytm jest niedeterministyczny. Rozwiązania nie podaję, bo jest na stronie z rozwiązaniem zagadki – na oko bardzo podobne. Jeśli komuś zależy to znajdę to co chatGPT zaproponował.

To teraz wypadałoby nauczyć się obu narzędzi, ale raczej nie znajdę na to czasu. Za to przynajmniej będę wiedział, że istnieją i co mniej więcej potrafią.

I ciekawostka. Wiecie co to jest „LUB-przykładowe narzędzia”? Jest to odpowiednik „OR-Tools Examples” w tłumaczeniu na oficjalnej stronie Google. To tak dla ustalenia, gdzie jesteśmy z automatycznymi tłumaczeniami. Chciałem napisać, „z AI”, ale chyba nie było tam wykorzystane – Gemini tłumaczy znacznie lepiej i całkiem sensownie.

Opublikowane w

Dict, set, list!

Przy okazji niedawnego code review dostałem pytanie, czemu w skrypcie napisanym w Pythonie nie korzystam z obiektu typu set, tylko z dict. Chodziło o cache na kilka tysięcy elementów, odpytywany kilkaset tysięcy razy. Z przyzerowym hit ratio. Zdziwiłem się, bo kojarzyłem, że czytelna konstrukcja wykorzystująca in dla obiektu typu list 

data = [x for x in range(1000)]
y = 1001
if y in data:
    print("Hit")

jest raczej wolna. Zwłaszcza w porównaniu z nieco mniej czytelnym wariantem z użyciem dict:

data = {x: True for x in range(1000)}
y = 1001
if data.get(y):
    print("Hit")

Odpisałem o co chodziło i usłyszałem, że przecież set jest szybki. Coś mi zaświtało. Bo niby set jest bardziej podobny w użyciu do listy, ale pod spodem ma parę ciekawych właściwości. Zresztą, gdy poprosimy LLM o optymalizację pod kątem szybkości, otrzymamy coś w stylu[1]:

data = {x for x in range(1000)} # Converted 'data' to a set
y = 1001
if y in data:  # Checking membership still works the same way
    print("Hit")

Różnice w czasie wykonania możemy zgrubnie i niezbyt elegancko sprawdzić w następujący sposób:

Jak już jesteśmy przy tego typu ciekawostkach. A co jeśli mamy w cache ciągi znaków i chcemy sprawdzić, czy nasz ciąg znaków nie kończy się jednym z ciągów z cache? LLM poproszony o optymalizację znowu podpowiada, że lepszy jest set. Ale nieoczekiwanie sugeruje też wykorzystanie regexpów. I co? Ku mojemu zaskoczeniu regexp w stylu

pattern = re.compile("("+"|".join(our_set)+")"$")
return bool(pattern.search(tested_value))

okazuje się najszybszym rozwiązaniem! Nie to, że uważam regexpy za szczególnie wolne, co to, to nie. Oczywiście pattern wykonujemy raz, nie dla każdej testowanej wartości.

Dalsza lektura:
O’reily High performance Python Dictionaries and Sets

[1] Tak, różnica niezbyt rzuca się w oczy przy takim zapisie. Mało widać różnicę między dict a set. Kiedyś już o tym wspominałem. Czytelniejszy zapis – którego chyba nikt nie używa – tamże.

Opublikowane w

Połam to jeszcze raz

Niedawno sekurak.pl zorganizował kolejny konkurs z łamaniem hashy. Tym razem dowiedziałem się o nim przypadkiem – ot, wpadło powiadomienie z Discorda, które akurat zauważyłem. Rzuciłem okiem, jest link do wpisu, są hashe, więc warto spróbować, bo do wygrania był kolejny dostęp do Akademii Sekuraka 2024.

Miałem w zasadzie gotowca na podstawie poprzedniego wpisu i writeupu, więc liczyłem, że kilka sztuk wpadnie. I faktycznie, nie zawiodłem się. Opisane wcześniej metody pozwalały złamać 7 do 9 hashy. Skąd rozbieżność? Zależy jak liczyć i jaki się utworzyło dedykowany słownik.

Zajmijmy się trzema hashami, z którymi mógł być problem. Pierwszy to db13ca089eb4860896567399a30558f2c1fc69e7:sekurak.academy.
Przyznaję, że zwyczajnie miałem szczęście. W słowniku zagościł bowiem ciąg sekurakacademy, a OneRuleToRuleThemAll zrobiło resztę. Aż się zdziwiłem, czemu to wpadło, więc sprawdziłem.

Sprawdzenie, która reguła spowodowała dopasowanie robi się zgodnie z opisem z dokumentacji hashcata poprzez dodanie parametrów

--debug-mode=1 --debug-file=matched.rule

Okazuje się, że OneRuleToRuleThemAll ma takie cudo jak

l i7.

Przekładając na bardziej zrozumiały język: zamień wszystkie litery na małe i wstaw kropkę po siódmym znaku. Chwilę po godzinie dziewiętnastej odesłałem 8 złamanych hashy.

Kolejne hasło, które mogło sprawić trudność to złożenie nie dwóch, ale trzech wyrazów. Czułem, że będzie, bo tego typu pojawiały się w poprzednich edycjach. Schemat był zawsze ten sam – dwa wyrazy oddzielone krótkim spójnikiem. Sprawdziłem, ile jest krótkich spójników w moim słowniku. Samych dwuznakowych było aż 428. Uznałem, że to zbyt wiele. W dodatku większość się nie nadawała – zz czy yy po prostu mi nie pasowały.

Postanowiłem spróbować z dwuliterowymi. Ręcznie przejrzałem wszystkie dwuliterowe słowa, wybrałem 25, które wydały mi się najbardziej prawdopodobne, zapisałem do pliku. Dorzuciłem jeszcze 3 jednoliterowe spójniki: i, o, a. Na koniec dodałem 19 wyrazów trzyznakowych. Tak powstał plik laczniki.txt.

Stwierdziłem też, że dla pełnego słownika języka polskiego i tak wyszłoby wiele kombinacji. Hasła z poprzednich edycji były umiarkowanej długości. Postanowiłem wziąć na warsztat tylko wyrazy od 2 do 9 znaków. Nazwałem go 29_slownik_all_nopl.txt. Liczył 845 tys. wierszy.

Krótkim skryptem w Pythonie utworzyłem słownik z wszystkimi kombinacjami wyrazów z 29_slownik_all_nopl.txt oraz 57 łączników. Wynikiem był spory, ale nadal akceptowalny słownik zawierający 48 mln wierszy.

Potem już standardowo – operacja na dwóch słownikach. Pierwszym był 29_slownik_all_nopl_laczniki.txt zaś drugim 29_slownik_all_nopl.txt. Tak udało się złamać 61d54fe02ce6edcde2f5762f2677b3c83d876417:trudnotozgadnac
i kwadrans po dwudziestej pierwszego dnia odesłałem 9 haseł.

Wersja z tworzeniem słownika na dysku nie jest może najefektywniejszym podejściem do haseł zbudowanych z trzech słów, ale jak widać wystarczyła.

Warto w tym miejscu odnotować, że słowo to pojawiało się wcześniej i gdyby człowiek pomyślał, to mógł przyjąć, że będzie i tym razem. Cóż, po fakcie każdy mądry.

Ostatnie hasło jest ciekawą i pouczającą sprawą. Na discordowym kanale pojawiła się informacja, że już dwie osoby mają 9 haseł, w dodatku gdyby połączyć ich odpowiedzi, to będzie komplet, czyli wszystkie hasła z konkursu zostały złamane. Dopuszczałem możliwość, że coś przeoczyłem, bo jak wspominałem do konkursu przystąpiłem w pośpiechu. Na innym kanale Patryk (jego writeup z łamania haseł znajdziecie na tutaj – polecam) też pochwalił się złamaniem 9 hashy.

Po krótkiej rozmowie czego komu brakuje i ustaleniu, że faktycznie chodzi o nas, Patryk rzucił podpowiedzią, że brakujący hash jest podobny do już złamanego, ale po polsku. Cóż, wielkiego wyboru nie było i wkrótce, po dosłownie czterech próbach wykonanych ręcznie, do złamanych dołączył:
283d5cb401e9de6a2e56f97166a639479fb86aee:akademiasekuraka
Komplet haseł odesłałem o 20:23 drugiego dnia konkursu.

Zarówno słowo akademia jak i sekurak oczywiście miałem w słowniku. Zabrakło wersji z deklinacją. Mam zatem pewne wnioski dotyczące słownika na przyszłość…

UPDATE: Artykuł z oficjalnym rozwiązaniem konkursu i statystykami rozwiązań.