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.

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:

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:

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.

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:

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

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.

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”