Otchłań | Myśl jak programista, odc.6

Cała lekcja dostępna tutaj: https://ed.ted.com/lessons/the-chasm-think-like-a-coder-ep-6

To szósty odcinek naszej animowanej serii „Myśl jak programista".
Ta 10-odcinkowa historia pokazuje losy dziewczyny o imieniu Etyka
i towarzyszącego jej robota, Hedga. Razem próbują uratować świat. Wyruszają na wyprawę, by zebrać trzy artefakty. Po drodze muszą jednak rozwiązać serię programistycznych zagadek.

Lekcja: Alexa Rosenthala, reżyseria: Kozmonot Animation Studio.

Etyka, Hedge i Octavia
stoją na skraju jaru bez dna.

To jedyne, co dzieli ich od wieży,

która mieści drugi z trzech
potężnych artefaktów.

Mają tylko chwilę, by do niej dotrzeć
przed powrotem straży.

Z prawie pustym zbiornikiem paliwa Hedge
nie może zabrać Etyki na drugą stronę,

jedyną opcją jest budowa mostu.

Na szczęście unoszące się nieopodal
stosy kamieni to elementy mostu.

Wynalazła je Octavia
i nazwała wiszącymi kamieniami.

Stos aktywuje się za pomocą energii,

a elementy same ułożą się nad jarem
z każdym krokiem Etyki.

Jest oczywiście pewien haczyk.

Wiszące kamienie są stabilne jedynie,
gdy są całkowicie symetryczne.

Co oznacza, że muszą stworzyć sekwencję,

która jest taka sama z przodu i z tyłu.

Pierwszy blok ze sterty jest losowy,

ale kolejne nakładają się na siebie,
zachowując układ palindromu

jeśli się da.

Jeśli dotrą tam, gdzie palindrom
nie jest możliwy,

most się zawali,

a ten, kto na nim stoi, spadnie do jaru.

Spójrzmy na przykład.

Ten stos stałby się stabilny.

Najpierw pozycję zajmują bloki A.

Potem B.

Na końcu blok C
usadowiłby się pomiędzy dwoma B.

Załóżmy jednak,
że jest jeszcze jeden blok A.

Najpierw rozkładają się
dwa bloki A, potem B,

ale w ten sposób bloki A i C
nie mają gdzie się podziać,

więc całość się rozpada.

Dzięki Węzłowi Mocy Hedge
może aktywować pojedynczy stos bloków.

Jaką instrukcję powinna dać Etyka,
by Hedge sprawnie odnalazł

i uruchomił stabilny stos palindromiczny?

Zatrzymaj, by znaleźć rozwiązanie.

Przykłady palindromów to ANNA,
RACECAR czy MADAM IM ADAM.

Liczenie, jak często dana litera
pojawia się w palindromie,

ujawni przydatny wzorzec.

Zatrzymaj, by znaleźć rozwiązanie.

Spróbujmy najpierw rozwiązania naiwnego.

Rozwiązanie naiwne to podejście proste,
"na siłę", które nie jest zoptymalizowane,

ale wykona zadanie.

Rozwiązania naiwne przydają się
do analizowania problemu

i jako podwaliny dla lepszych rozwiązań.

W tym przypadku naiwnym rozwiązaniem
jest budowa stosu bloków

i próba wszystkich możliwych kombinacji,

by znaleźć palindrom
czytając każdą wprzód i w tył.

Niestety to podejście

zajęłoby ogromnie dużo czasu.

Gdyby Hedge próbował
jednej kombinacji na sekundę,

stos zaledwie 10 różnych bloków
zająłby mu 42 dni.

To dlatego, że całkowity czas to silnia

liczby dostępnych bloków.

10 bloków to ponad 3 miliony kombinacji.

Rozwiązanie naiwne pokazuje,
że potrzeba znacznie szybszego sposobu,

by sprawdzić czy dany stos może
utworzyć palindrom.

Po pierwsze, intuicja podpowiada,
że stos 10 różnych bloków

nigdy nie utworzy palindromu.

Dlaczego?

Pierwszy i ostatni blok
nie będą identyczne,

jeśli nie ma dwóch takich samych bloków.

Kiedy więc dana sekwencja
utworzy palindrom?

Jednym ze sposobów, by to ustalić
jest analiza istniejących palindromów.

W ANNA są 2 A, 2 N.

W słowie RACECAR mamy 2 R, 2 A, 2C i 1 E.

Zwrot MADAM IM ADAM
ma 4 M, 4 A, 2 D i 1 I.

Schemat ten pokazuje,
że większość liter pojawia się

parzystą liczbę razy

i najwyżej 1 pojawia się tylko raz.

Czy to wystarczy?

Co by było gdyby słowo RACECAR
miało 3 E zamiast 1?

Można by dodać E na każdym z końców
i nadal utworzyć palindrom,

więc 3 jest ok.

Ale jeśli będziemy mieć 3 E i 3 C,
ostatnie C nie będzie miało miejsca.

Tak więc, uogólniając,

najwyżej jedna litera może pojawić się
nieparzystą ilość razy,

reszta musi być parzysta.

Hedge może policzyć litery w każdym stosie
i uporządkować je w słownik,

co jest schludną metodą
przechowywania informacji.

Za pomocą pętli można policzyć
ile razy pojawia się nieparzysta liczba.

Jeśli są mniej niż 2 nieparzyste liczby,
stos może stworzyć palindrom.

To podejście jest znacznie szybsze,
niż rozwiązanie naiwne.

Zamiast złożoności typu silnia,
mamy złożoność liniową.

Czasu przybywa

proporcjonalnie do liczby bloków,
którymi dysponujemy.

Wystarczy napisać pętlę, dzięki której
Hedge podejdzie do każdego stosu osobno

i zatrzyma się, gdy znajdzie właściwy.

Oto, co się dzieje:

Hedge jest szybki, ale taka liczba
stosów zabiera dużo czasu.

Za dużo.

Etyka i Hedge są bezpieczni.

Ale Octavia nie ma tyle szczęścia.