Kolejne łatwe ćwiczenie, dlatego w ramach bonusu demo algorytmu genetycznego zainspirowane streamem Gynvaela Coldwinda.
W tym ćwiczeniu naszym zadaniem jest implementacja algorytmu, który używając podanego klucza wykona operację XOR na podanej wiadomości. Klucz jest krótszy niż wiadomość dlatego po wykonaniu operacji XOR na pierwszych n bajtach wiadomości (n to długość klucza), klucz jest używany ponownie.
def bytes_xor_key(input_bytes, key):
if len(input_bytes) > len(key):
return [x ^ y for x, y in zip(input_bytes, cycle(key))]
else:
return [x ^ y for x, y in zip(cycle(input_bytes), key)]
def string_xor_key(input_string, key):
return bytes_xor_key(bytearray(input_string, 'UTF-8'), bytearray(key, 'UTF-8'))
W podanej wyżej implementacji klucz może być dłuższy niż wiadomość wejściowa, wtedy to wiadomość jest zduplikowana.
Nowość to funkcja cycle (https://docs.python.org/3/library/itertools.html#itertools.cycle), która przez zwróceniem kolejnego elementu robi jego kopię, jeżeli skończą się elementy zaczyna zwracać kopie i tak bez końca.
To co mnie trochę przyblokowało w tym zadaniu to znak nowej linii. Na stronie wygląda to tak:
Po skopiowaniu do kodu powinno wyglądać następująco: „Burning ’em, if you ain’t quick and nimble\nI go crazy when I hear a cymbal”. Pomiędzy liniami znajduje się znak przejścia do nowej linii – ’\n’, ale go nie widać. Z tego powodu początkowo wartość wynikowa, którą uzyskiwałem była inna niż podana na stronie.
Demo algorytmu genetycznego
Jakiś czas temu natknąłem się na stream Gynvaela Coldwinda na którym implementował algorytm genetyczny, który rysował Mona Lisę. Polecam gorąco ten stream (tak jak i cały kanał) https://youtu.be/7zI7M_5_jBE. To jak działa algorytm jest wytłumaczone w wyżej wymienionym filmie, więc nie będę poświęcał temu wiele czasu jedynie któtko opiszę założenia:
- Wyjściowo mamy 40 czarnych obrazków (na streamie jest 100, ale ze względu na fakt, że w moim wypadku użyty jest JavaScript zmniejszyłem ilość).
- Na każdym z obrazków od 10 do 40 w losowym miejscu rysowany jest losowej wielkości prostokąt.
- Każdy obrazków jest oceniany w celu sprawdzenia jak bardzo jest podobny do obrazka, który chcemy uzyskać (w tym wypadku porównywane są kolory pikseli obrazków – im większa różnica w odcieniu tym gorszy wynik uzyskuje dany kandydat).
- Wybierane jest 10 najlepszych obrazków i nadpisujemy nimi wszystkie 40 obrazków – uzyskujemy w ten sposób 4 grupy po 10 najlepszych obrazków.
- Wracamy do punktu 2.
Maksymalna wielkość losowych prostokątów to domyślnie 1/3 szerokości i 1/3 wysokości obrazu wejściowego. Na stronie są podane dwa pola i można eksperymentować z różnymi wielkościami losowych obrazów.
Dlaczego modyfikujemy tylko obrazy od 10 do 40 a nie wszystkie? Na początku modyfikowałem wszystkie obrazy, ale potem doszedłem do wniosku, że przecież w ten sposób może dojść do sytuacji kiedy lepszy obrazek z poprzedniej rundy zostanie nadpisany gorszym obrazkiem z aktualnej rundy. Dzięki zapamiętywaniu najlepszych obrazów z poprzedniej rundy unikamy regresji (to znaczy, że jakość obrazów nie spada w kolejnych rundach).
Demo dostępne jest na stronie: https://koltys.info/genetic_js_demo.html.
Kod dostępny jest tutaj: https://gitlab.com/akoltys/genetic_algorithm_demo/-/tree/master.