# Memoizacija funkcij, koristno za dinamično programiranje, kadar se nam ne da
# implementirati dinamičnega programiranja na roke. V bistvu tole deluje tako dobro,
# da niti nima smisla implementirati dinamičnega programiranja na roko.

def memo(f):
    """memo(f) memoizira funkcijo f. Prvi argument f mora biti funkcija, ki jo f klice, kadar se zeli poklicati rekurzivno."""
    # Sem spravimo rezultate, ki smo jih že izračunali
    cache = {}

    # Pomožna funkcija, ki deluje tako kot f, le da pogleda v cache, preden
    # izračuna rezultat. V Pythonu *args pomeni "vsi argumenti, kolikor jih pač je".
    # Na ta način lahko memoiziramo funkcije, ki sprejmejo poljubno število argumentov.
    def g(*args):
        if args in cache:
            return cache[args]
        else:
            # Ko pokličemo f mu damo kot argument g. Tako bodo tudi rekurzivni klici prestreženi z g.
            y = f(g, *args)
            cache[args] = y
            return y

    # Rezultat memo(f) je funkcija g
    return g

# Z uporabo dekoracij (https://docs.python.org/3/glossary.html#term-decorator) se lahko
# izognemo razpiranju rekurzije in napišemo prvotno rekurzivno funkcijo.

def caching(f):
    """Dekorator, ki shranjuje rezultate funkcije f. To deluje tudi na rekurzivnih funkcijah."""
    cache = {}
    def g(*args):
        if args in cache: return cache[args]
        else:
            y = f(*args)
            cache[args] = f(*args)
            return y
    
    return g

# Navedimo nekaj primerov.

# 1. Fibonaccijeva števila.

# Najprej definiramo pomozno funkcijo, ki namesto rekurzivnih klicev klice svoj prvi argument:
def fib_pomozna(jaz, n):
    if n == 0 or n == 1: return 1
    else: return jaz(n-1) + jaz(n-2)

# Takole lahko naredimo običajno (počasno) rekurzicno funkcijo za računanje Fibonaccijevih števil.
def fib_rekurzivna(n):
    return fib_pomozna(fib_rekurzivna, n)

# Takole naredimo hitro verzijo. Njena slabost je, da si zapomni vse rezultate, ki jih je kadarkoli
# izračunala.
fib = memo(fib_pomozna)

# V resnici se nam ni treba mučiti z memo in pomožnimi funkcijami, ker dekorator
# caching že opravi vse delo. Edina slabost tega pristopa je, da bo v pomnilniku
# spravljen slovar, ki hrani vse rezultate vseh klicev.

@caching
def fib_cache(n):
    if n == 0 or n == 1: return 1
    else: return fib_cache(n-1) + fib_cache(n-2)

# Preizkus: primerjaj, koliko traja, da se izracuna fib_rekurzivna(30) in fib(300).

# 2. Binomski koeficienti.

# Tokrat bomo takoj definirali hitro verzijo, ki poleg vsega ne trati nepotrebnega pomnilnika,
# saj ob vsakem klicu naredi novo verzijo memoizirane funkcije. To je priporočena uporaba funkcije memo.

def binomski(n,k):
    """Binomski koeficient n nad k"""

    def binomski_pomozna(jaz,n,k):
        if k < 0 or k > n: return 0
        if k == 0 or k == n: return 1
        else: return jaz(n-1,k-1) + jaz(n-1,k)

    # Naredimo hitro verzijo in jo uporabimo na (n,k). Torej se pri vsakem klicu
    # naredi nov cache, ki se po potrebi napolni, ko je rezultat izračunan, pa se ga zavrže.
    return memo(bin_pomozna)(n,k)

# 3. Dinamično programiranje

# Klasična naloga dinamičnega programiranja je naslednja: dana je kvadratna tabela a
# velikosti n x m, v kateri so zapisana cela števila. Poiskati moramo _ceno_ najcenejše
# poti od zgornjega levega polja a[0][0] do spodnjega desnega a[n-1][m-1], pri čemer se
# smemo premikati samo navzdol in desno. Cena poti je vsota števil na poti.
#
# Naj bo c(i,j) cena najcenejše poti od a[0][0] do a[i][j]. Tedaj imamo rekurzivno
# definicijo:
# c(0,0) = a[0][0]
# c(0,j) = c(0,j-1) + a[0][j] za 0 < j < m
# c(i,0) = c(i-1,0) + a[i][0] za 0 < i < n
# c(i,j) = min (c(i-1,j), c(i,j-1)) + a[i][j] za 0 < i < n, 0 < j < m
#
# Če bi funkcijo c implementirali neposredno z rekurzivnimi klici, bi bila zelo
# neučinkovita. Tu pa je učinkovita implementacija s pomočjo dekoratorja @caching

def cena(a):
    """Izračunaj ceno najcenejše poti od zgornjega levega do spodnjega desnega kota."""

    # Pomožna funkcija cena (če odstranimo @caching, bo delala zelo počasi),
    # ki smo jo tudi poimenovali cena, da bo vzgojno
    @caching
    def cena(i, j):
        if i == 0 and j == 0: return a[0][0]
        elif i == 0: return cena(0,j-1) + a[0][j]
        elif j == 0: return cena(i-1,0) + a[i][0]
        else: return min(cena(i-1,j), cena(i,j-1)) + a[i][j]

    n = len(a)
    m = len(a[0])
    return cena(n-1, m-1) # kličemo funkcijo iz vrstice pod @caching

# Preizkus:
t = [[9,1,0,4,3,5],
     [7,3,2,3,4,8],
     [4,1,6,0,3,2],
     [5,3,8,7,1,3],
     [1,3,2,1,4,0],
     [1,3,2,1,4,0]]
print ("I. Najcenejsa pot na t stane", cena(t))

# Preizkus na večji tabeli:
s = [[(i**7 + j**5 + i**4 * j**3 + j) % 17 for i in range(100)] for j in range(100)]
print ("II. Najcenejsa pot na s stane", cena(s))

# Seveda bi želeli vedeti tudi, _katera_ je najcenejša pot. Pot lahko rekonstruiramo
# tako, da se premikamo od končnega polja proti začetnemu po najcenejših poljih.

def pot(a):
    """V tabeli a poišči najcenejšo pot od zgornjega levega do spodnjega desnega polja."""

    # Pomožna funkcija c, ki namesto rekurzivnih klicev kliče svoj prvi argument
    @caching
    def cena(i, j):
        if i == 0 and j == 0: return a[0][0]
        elif i == 0: return cena(0,j-1) + a[0][j]
        elif j == 0: return cena(i-1,0) + a[i][0]
        else: return min(cena(i-1,j), cena(i,j-1)) + a[i][j]

    n = len(a)
    m = len(a[0])
    # Naredimo pot prave dolžine
    pot = [None for i in range(n+m-1)]
    # Pot napolnimo od konca proti začetku
    (i,j) = (n-1,m-1)
    for k in range(n+m-1):
        pot[k] = (i,j)
        # Premaknemo se levo ali gor, odvisno od tega, kaj je ceneje in ali smo na robu
        if i == 0: j = j - 1
        elif j == 0: i = i - 1
        elif cena(i-1,j) < cena(i,j-1):
            i = i - 1
        else:
            j = j - 1
    return pot

# Preizkus:
print ("III. Najcenejsa pot za t je", pot(t))
print ("IV. Najcenejsa pot za s je", pot(s))