Zadanie z trójkami pitagorejskimi #PytaniaRekrutacyjne – Special Pythagorean triplet

1. Iterujemy po wszystkich możliwościach od 1 do n(1000) dla każdej zmiennej a,b oraz c.
2. Sprawdzamy warunek czy suma potęg a oraz b jest potęgą zmiennej c.
3. Dodatkowo sprawdzamy czy suma wszystkim 3 zmiennych a,b,c da nam liczbę n (1000).
4. Jeśli tak dodajemy naszą trojką do hashsetu (po prostu jakiegoś kontenera).
5. Następnie szukamy dalej. przechodząc przez 1000^3 iteracji. Nasz algorytm ma złożoność O(n^3) – ogólnie rzecz biorąc kiepsko 🙁

Optymalizacja

Zmniejszenie Ilości iteracji

Zachęcam Cię do zaimplementowania własnej wersji algorytmu w języku, który znasz. Teraz skupmy się na tym co można by usprawnić. Skorzystajmy z własności:  a < b < c oraz, że a + b + c = 1000

Musimy przemyśleć jaka może być maksymalna wartość liczby a, jeśli a wynosiłoby 500 to b = 501, a c = 502, wtedy nie zostanie spełnione równanie a + b + c = 1000

Chwila główkowania, prowadzi nas do liczby a = 332, czyli tak na prawdę 1000/3 – 1. Co w takim razie ze zmienną b? Może ją też można by zoptymalizować?, no jasne! Szukamy maksymalnego  b, więc dając np. b = 700, c musiałoby wynosić minimum 701, 700 + 701 = 1401, niestety przekracza to już liczbę 1000 nie wspominając o zmiennej a!

W takim razie b musi być maksymalnie równe 499, czyli 1000/2 -1.

Dodatkowo warto zauważyć, że jeśli a < b to możemy jako początek iteracji dla pętli b zainicjalizować jako b = a + 1, znowu będziemy do przodu o kilka iteracji.

Zredukowanie wewnętrznej pętli

Możemy dokonać jeszcze jednej optymalizacji, otóż zamiast sprawdzać za każdym razem czy suma wszystkich 3 zmiennych jest równa poszukiwanej liczbie (u nas 1000), można wyliczyć zmienną c z następującego wzoru:

a + b + c = n (1000), po przekształceniach uzyskamy:

c = n – a – b – jedno proste przekształcenie pozwala nam na zredukowanie całej pętli!

Jak teraz będzie wyglądał nasz kod?

    for a in 1..n/3
    {
        for b in (a+1)..n/2
        {
            let c = n - a - b;
            if  a.pow(2) + b.pow(2) == c.pow(2)
            {
                return_set.insert([a, b, c]);                  
            }
        }
    }

Jest już dużo lepiej, ale czy można by coś jeszcze zrobić?

Rozwiązanie bardziej „analityczne”

Na stronie https://www.xarg.org/puzzle/project-euler/problem-9/ znalazłem ciekawe podejście do tego problemu, uzależniając się tylko od jednej pętli! Chciałbym tu rozpisać krok po kroku jakich przekształceń należy użyć aby tego dokonać. Przyznam szczerze, że sam miałem sporo problemów, w dojściu do niektórych wzorów – cóż trzeba trochę bardziej polubić matematykę 😉

Zaczynamy, naszym celem będzie takie przekształcenie wzoru, aby obliczyć zmienne a oraz b tylko iterując po zmiennej c. Wiem, może to brzmieć skomplikowanie, ale spokojnie pamiętam te lekcje matematyki, które bardziej przypominały zajęcia ze szkoły magii i czarodziejstwa…Postaram Ci się wytłumaczyć krok po kroku co się dzieje.

Na początku przekształćmy wzór:

na postać

w naszym arsenale mamy jeszcze wzór: – dodajemy do niego po obu stronach wartość Zapytasz po co? Będziemy mogli skorzystać ze wzoru skróconego mnożenia!

Wzór po dodaniu będzie wyglądał następująco:

, „zwijamy” (ze wzoru skróconego mnożenia) lewą stronę równania do postaci:

po niewielkim przekształceniu

skąd wzięło się n – c ? Zobacz kilka wzorów wyżej a + b = n – c, więc bez przeszkód możemy podstawić te wartości.

Dobra czas na odjęcie tych 2 wzorów od siebie (zabawne jest to, że odejmujemy, żeby stworzyć całkowicie nowy wzór, który przyda nam się w obliczeniach ;))
oraz

Po odjęciu wzór będzie wyglądał następująco:

Do czego doszliśmy, przekształcając nasz wzór? Udało nam się poznać liczbę a oraz b uzależniając je tylko od zmiennej n (już znamy) oraz c po której iterujemy!

Jak znaleźć liczbę b bazując jedynie na zmiennych n oraz c?

Wiedząc jak obliczyć zajmijmy się obliczeniem zmiennej b, wyjdźmy od wzoru:
Odejmijmy od obu stron b (pamiętaj, możesz dodać lub odjąć po obu stronach równania co tylko chcesz, to zawsze sprowadzi się do 0 ;))
Wychodzi , teraz przenieśmy składnik a-b na prawą stronę. Wychodzi

Co teraz? Gdzie zastosować naszą znaną informację odnośnie: Możemy zauważyć, że to po przekształceniu , tak ujęliśmy to w nawias.

W jaki sposób z zrobić ? Wystarczy to wyrażenie spierwiastkować w efekcie dostaniemy 2 możliwości gdy oraz Przypominając sobie własność wiemy, że będą nast interesować jedynie ujemne liczby (bo a musi być mniejsze od b), więc ten minus możemy wyciągnąć przed nawias. W efekcie wzór na obliczenie b będzie następujący:

Czas na składnik a

Jak teraz wyliczyć a? To już całkiem proste wystarczy delikatnie przekształcić wzór: do postaci: i to wszystko 🙂

Sprawdzenie czy liczba jest całkowita

Żeby sprawdzić czy będziemy w stanie wyliczyć a oraz b wystarczy sprawdzić czy pierwiastek z jest liczbą całkowitą, w tym przypadku mnożymy razy dwa to wyrażenie i sprawdzamy czy da liczbę podniesioną do potęgi ((a-b)^2) jeśli tak to znaczy, że liczba jest całkowita i możemy znaleźć a oraz b.

Po co nam ta cała matematyka?

I w sumie możesz myśleć, że jak zwykle przekształciliśmy parę wzorów, coś tam skróciliśmy i jak to w szkole nic z tego nie wynika, jednak zobacz jak zmieni się nasz kod:

    let mut return_set = HashSet::new();
    for c in 1..n
    {
        let sqa_b = c * c - n * n + 2 * n * c;
        let a_b = (sqa_b as f64).sqrt().floor() as i32;
    
        if a_b * a_b == sqa_b {
          let b = (n - c + a_b) / 2;
          let a = n - b - c;
          return_set.insert([a, b, c]);   
        }
    }
    return return_set;