Kategoria: project euler

Projekt Euler – zadanie 8 – Window sliding technique

Posted on by paulinakaczmarek

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))

view raw

brute_force.py

hosted with ❤ by GitHub

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:


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))

view raw

window_sliding_technique.py

hosted with ❤ by GitHub

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))

view raw

window_sliding_product.py

hosted with ❤ by GitHub

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
(…)

view raw

window_sliding_product.py

hosted with ❤ by GitHub

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
(…)

view raw

window_sliding_product.py

hosted with ❤ by GitHub

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))

view raw

8.py

hosted with ❤ by GitHub

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