Projekt Euler – zadanie 8 – Window sliding technique

Rozwiązuję sobie ostatnio zadania z Projektu Euler i natrafiłam na zadanie 8, które zainspirowało mnie do tej notki.

Największy iloczyn 13 kolejnych cyfr z 1000 cyfrowej liczby 🙂 Można to zrobić najprościej – pętla po wszystkich cyfrach, a potem branie 13 kolejnych cyfr. Wynik dla 4 kolejnych cyfr, który jest podany w treści zadania wykorzystam jako test sprawdzający.

https://gist.github.com/jezinka/666182658ca933dc31928a41d432cc17

Niestety, nie optymalne, złożoność czasowa aż O(n*k). Dla 4 liczb mamy 4 * 1000 obrotów w pętli, ale dla 13 to już 13000. A gdyby liczba była 10, 100 razy większa? Musi być inny sposób… I jest.

Window sliding technique – technika przesuwanego okienka. Można to sobie wyobrazić jako kalendarz z przesuwanym na taśmie okienkiem:

Dla uproszczenia skupię się na mniejszym przykładzie i poszukam największej sumy z wymyślonej mniejszej liczby. W tym wypadku okienko będzie mieściło w sobie 4 cyfry.

Algorytm wygląda tak:

  1. Wyliczamy początkową sumę w okienku (window_sum) – jest ona w tym momencie również maksymalną sumą (max_sum)
  2. Przesuwamy okienko – wyliczamy kolejną sumę korzystając z poprzednich  wyliczeń:
    1. od window_sum odejmujemy cyfrę, która opuściła okienko
    2. do window_sum dodajemy cyfrę, która trafiła do okieka
  3. Jeśli nowa suma jest większa niż max_sum, to za max_sum przypisujemy window_sum
  4. Jeśli mamy jeszcze jakieś cyfry w „dużej liczbie” to wracamy do punktu 2

W formie graficznej wygląda to mniej więcej tak:

 

 

 

 

 

A kod tak:

https://gist.github.com/jezinka/eaaed2eb8e8c3ea8041a49306deb4a84

Tutaj kroków w pętli jest tyle ile wynosi długość „dużej liczby”, czyli złożoność czasowa O(n). Zupełnie nie zależy to od wielkości okienka.

Ok, ale to było dodawanie, a w zadaniu każą znaleźć największy iloczyn.

Niestety nie można po prostu przenieść wersji z dodawaniem na mnożenie:

https://gist.github.com/jezinka/ea40d83447e14713c9e4fd1e9e444b78

Bardzo szybko wypadnie error, że nie wolno dzielić przez 0.

Pierwsze zabezpieczenie: sprawdźmy, czy następny element jest równy 0. Jeśli jest to przeskakujemy go i wyliczamy od nowa sumę w okienku.

https://gist.github.com/jezinka/89be6db2e2e153abe89601566f9fdb88

Prawie dobrze, ale co w wypadku jeśli w nowym okienku znajdzie się 0, a może nawet dwa, więc omińmy je wszystkie:

https://gist.github.com/jezinka/17ade8dae2a318bba550710d3d009d5c

Można by się jeszcze pokusić o sprawdzanie, czy w pierwszym okienku jest 0 i trochę refaktoringu. Finalnie program wygląda tak:

https://gist.github.com/jezinka/450b279358d823e559a775590806d95e

Więcej zadań, które można rozwiązać przy pomocy tej techniki można znaleźć tu: https://www.geeksforgeeks.org/tag/sliding-window/

Python challenge – #01

Pierwsze zadanie

adreshttp://www.pythonchallenge.com/pc/def/map.html

tytuł stronyWhat about making trans?
zadanie:g fmnc wms bgblr rpylqjyrc gr zw fylb. rfyrq ufyr amknsrcpq ypc dmp. bmgle gr gl zw fylb gq glcddgagclr ylb rfyr’q ufw rfgq rcvr gq qm jmle. sqgle qrpgle.kyicrpylq() gq pcamkkclbcb. lmu ynnjw ml rfc spj.
podpowiedźeverybody thinks twice before solving this.
rozwiązanie: K -> M, O -> Q, E -> G. Brzmi jak szyfr, gdzie zamieniamy jedną literę na drugą. Odległość K od M to 2 (K->L->M), taka sama odległość jest między O i Q, i E i G. Jaką funkcję pythona można wykorzystać do tego żeby przerobić jeden słownik na drugi? Skorzystajmy z podpowiedzi z tytułu strony i użyjmy metody string.maketrans.

https://gist.github.com/jezinka/106b92b0834045ebccbf874de34855ac

Zaznaczenie_039.png

w url jest słowo: map

Zaznaczenie_040.png

adres kolejnej zagadki: http://www.pythonchallenge.com/pc/def/ocr.html

Python Challenge – #00

Odpoczywam ostatnio od mojej aplikacji „CoNaObiad”. Nie porzucam jej, po prostu poświęciłam jej dużo czasu i trochę mnie zmęczyła. W ramach wolnego czasu rozwiązuję sobie zadania z Python Challenge. Jeśli nie słyszeliście o tych puzzlach, to czas to nadrobić 😉 Continue reading „Python Challenge – #00”

stary kod – Mrówka Langtona – #0E

Przeglądając RSS rzucił mi się w oczy nostalgiczny wpis opisujący pierwszą stronę www. Kolejny dzień przyniósł wpis o próbach implementacji algorytmu mrówkowego. Te dwa wpisy poruszyły jakąś klapkę w mojej pamięci i przypomniał mi się czas kiedy miałam potrzebę sprawić, żeby programowanie znowu sprawiło mi trochę radości. Poszperałam trochę w starych kodach i znalazłam to czego szukałam.

Imentacja Mrówki Langtona zrobiona w lipcu 2014. Continue reading „stary kod – Mrówka Langtona – #0E”