PEDAC to taki amerykański sposób rozwiązywania problemów, stworzony przez Launch School. Jedną z jego zalet jest to, że zamiast naturalnego odruchu aby jak najszybciej dojść do odpowiedzi to wymusza głębsze zastanowienie się nad tym co tak naprawdę robimy. Jest to jedna z odmian metody opisanej przez G Polya:

https://math.berkeley.edu/~gmelvin/polya.pdf

Wizualnie to wygląda mniej więcej tak:

Problem

• zrozumienie problemu i kluczowych idei

• zapisanie wymagań wprost

• znalezienie zasad

• model mentalny problemu

• sparafrazowanie i zapytanie osoby zadającej pytanie czy zrozumieliśmy dobrze problem

Example

Gdy problem został zrozumiany, naturalnym kolejnym krokiem jest wygenerowanie przykładów - najprostszych test-case, sprawdzających przypadki brzegowe, trywialne warianty itd.

Na przykład mając dane równanie do rozwiązania można sprawdzić, co będzie dla N równego 0, dla N równego 1. A co jeśli N jest ujemne? Można tutaj spróbować wymyślić specjalny przypadek.

Tutaj można ewentualnie pokusić się o tak zwanego bruta - czyli wymyślenie algorytmu brute-force ( na ogół nieoptymalnego, o dużej złożoności czasowej i pamięciowej ale też prostszym do udowodnienia )

Zrozumienie problemu -> Napisanie ręcznie kilku przypadków testowych -> Napisanie bruta, który generuje przypadki testowe -> Algorytm właściwy

Data structure

Tutaj pomaga rozwiązywanie dużej ilości zadań, w pewnym momencie od razu można poczuć, czy właściwą strukturą danych jest słownik, tablica, drzewo wyszukiwań binarnych, graf czy może coś innego.

Algo

Wymyślamy poprawny algorytm.

Make it correct, make it clear, make it concise, make it fast. In that order.

Najpierw ma być poprawny, potem re-factor na czytelność, na zwięzłość i na szybkość.

Code

Implementacja. Mając przypadki testowe lub jeszcze lepiej - algorytm brute force, który wiemy, że jest poprawny możemy szybko iterować.

Jak to działa w praktyce?

1. Piszemy klasę z funkcjami testującymi ( o Test Driven Development będzie kolejny newsletter )

2. Generujemy przypadki testowe lub piszemy program, który je generuje.

3. Dla zaawansowanych - https://hypothesis.readthedocs.io/en/latest/

### Write tests there

import unittest

class TestNotebook(unittest.TestCase):

    def test_sroot(self):

        self.assertEqual(sroot(0), 0)

    def test_sroot1(self):

        self.assertEqual(sroot(1), 1)

    def test_sroot2(self):

        self.assertEqual(sroot(2), 1)

    def test_sroot3(self):

        self.assertEqual(sroot(3), 1)

    def test_sroot4(self):

        self.assertEqual(sroot(4), 2)

    def test_sroot5(self):

        self.assertEqual(sroot(5), 2)

    def test_sroot6(self):

        self.assertEqual(sroot(6), 2)

unittest.main(argv=[''], verbosity=1, exit=False)

Powyższy kod wklejony do Jupyter Notebooka oczekuje istnienia funkcji sroot - liczącej część całkowitą pierwiastka z liczby naturalnej. ( zadanie nr 69 z LeetCode )

https://leetcode.com/problems/sqrtx/

I cyk, rozwiązanie gotowe ( tutaj 2 przykładowe rozwiązania, jedno moje, drugie anonimowego znajomego znającego się na algorytmach )

I koniec?

Co ciekawe oba rozwiązania nie są optymalne - oba są złożoności O ( N ^ 0.5 )

Da się rozwiązać to zadanie w czasie logarytmicznym ( poprzez wyszukiwanie binarne)

W ogólności praca IT nigdy się nie kończy, prawie każde złożone rozwiązanie można ulepszyć. Najważniejsze, aby mieć coś działającego i iterować, ulepszać