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/