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.
| def ex8(window_size): | |
| large_number = open("source.txt", 'r').read() | |
| max_product = 1 | |
| for i in range(0, len(large_number)): | |
| product = 1 | |
| if i + window_size <= len(large_number): | |
| for j in range(i, i + window_size): | |
| product *= int(large_number[j]) | |
| max_product = max(max_product, product) | |
| return max_product | |
| assert ex8(4) == 5832 | |
| print(ex8(13)) |
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:
- Wyliczamy początkową sumę w okienku (window_sum) – jest ona w tym momencie również maksymalną sumą (max_sum)
- Przesuwamy okienko – wyliczamy kolejną sumę korzystając z poprzednich wyliczeń:
- od window_sum odejmujemy cyfrę, która opuściła okienko
- do window_sum dodajemy cyfrę, która trafiła do okieka
- Jeśli nowa suma jest większa niż max_sum, to za max_sum przypisujemy window_sum
- 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:
| large_number = '6717483933' | |
| large_number_array = list(map(int, large_number)) | |
| def count_max_sum(window_size): | |
| if len(large_number) < window_size: | |
| return –1 | |
| max_sum = 0 | |
| for i in range(0, window_size): | |
| max_sum += large_number_array[i] | |
| window_sum = max_sum | |
| for i in range(window_size, len(large_number_array)): | |
| window_sum += large_number_array[i] – large_number_array[i – window_size] | |
| max_sum = max(max_sum, window_sum) | |
| return max_sum | |
| print(count_max_sum(4)) |
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:
| large_number = open("source.txt", 'r').read() | |
| large_number_array = list(map(int, str(large_number))) | |
| def find_max_product(k): | |
| max_product = 1 | |
| for i in range(0, k): | |
| max_product *= large_number_array[i] | |
| window_product = max_product | |
| for i in range(k, len(large_number_array)): | |
| window_product = window_product // large_number_array[i – k] * large_number_array[i] | |
| max_product = max(window_product, max_product) | |
| return max_product | |
| assert find_max_product(4) == 5832 | |
| print(find_max_product(13)) |
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.
| (…) | |
| if next_item is not 0: | |
| window_product = window_product // previous_item * next_item | |
| i += 1 | |
| else: | |
| i += 1 | |
| window_product = 1 | |
| if i + k <= len(large_number_array): | |
| for j in range(i, i + k): | |
| window_product *= large_number_array[j] | |
| else: | |
| break | |
| i += k | |
| (…) |
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:
| (…) | |
| while 0 in large_number_array[i:i + k]: | |
| zero_index = large_number_array[i:i + k].index(0) | |
| i += zero_index + 1 | |
| (…) |
Można by się jeszcze pokusić o sprawdzanie, czy w pierwszym okienku jest 0 i trochę refaktoringu. Finalnie program wygląda tak:
| large_number = open("source.txt", 'r').read() | |
| large_number_array = list(map(int, large_number)) | |
| def find_max_product(window_size): | |
| if len(large_number_array) < window_size: | |
| return –1 | |
| i = skip_zeros(0, window_size) | |
| max_product = count_initial_product(i, window_size) | |
| i += window_size | |
| window_product = max_product | |
| while i + window_size <= len(large_number_array): | |
| next_item = large_number_array[i] | |
| previous_item = large_number_array[i – window_size] | |
| if next_item is not 0: | |
| window_product = window_product // previous_item * next_item | |
| i += 1 | |
| else: | |
| i = skip_zeros(i, window_size) | |
| if i + window_size <= len(large_number_array): | |
| window_product = count_initial_product(i, window_size) | |
| else: | |
| break | |
| i += window_size | |
| max_product = max(window_product, max_product) | |
| return max_product | |
| def skip_zeros(i, window_size): | |
| while 0 in large_number_array[i:i + window_size]: | |
| zero_index = large_number_array[i:i + window_size].index(0) | |
| i += zero_index + 1 | |
| return i | |
| def count_initial_product(i, window_size): | |
| window_product = 1 | |
| for j in range(i, i + window_size): | |
| window_product *= large_number_array[j] | |
| return window_product | |
| assert find_max_product(4) == 5832 | |
| print(find_max_product(13)) |
Więcej zadań, które można rozwiązać przy pomocy tej techniki można znaleźć tu: https://www.geeksforgeeks.org/tag/sliding-window/