Tira 2021s tehtäväsarja 9 // Joel Yliluoma

""" Joelin ratkaisut Helsingin yliopiston Tietorakenteet ja algoritmit-kurssin
    viikon 9 harjoitustehtäviin https://cses.fi/tira21s/list/ .
    Nämä ratkaisut eroavat tarkoituksella malliratkaisuista. Niiden pääasiallinen
    tarkoitus on inspiroida ja antaa ideoita sellaisille opiskelijoille, jotka
    haluavat nähdä ohjelmoinnin taiteena — tai kenties vaikka yksinkertaisina
    matemaattisina lausekkeina. Vastaukset ovat tarkoituksella erittäin tiiviitä.
    Missään nimessä niitä ei tule tulkita esimerkkeinä hyvistä ohjelmointitavoista!
    Discordissa saa vapaasti kysyä, jos jokin kohta herättää kysymyksiä.
    Tehtäväsarja 8: https://pastebin.com/5u166swH
    Tehtäväsarja 9: https://pastebin.com/Vs2CNwQA
    Tehtäväsarja 10: https://pastebin.com/jeXQ1JnT
    Tehtäväsarja 11: https://pastebin.com/pTh4ZwFE
    Tehtäväsarja 12: https://pastebin.com/eJ8HMRCF
    Tehtäväsarja 13: https://pastebin.com/ETpqtDBY
"""

import math                 # 9.3 Hyppely
def count(n, a, b, p = lambda A,B,f=math.gamma: f(A+B+1)/(f(A+1)*f(B+1))):
  return round(sum(p(A,B) for(A,B) in ((A, (n-a*A)/b) for A in range(n//a + 1) if not(n-a*A)%b)))

def find(r):                # 9.4 Yhden ero
  best = [1]
  for b in range(1, len(r)):
    best.append( max(1,1,*(best[a]+1 for a in range(b) if abs(r[b]-r[a]) == 1)))
  return max(best)

def count(r, bad=9**9):     # 9.5 Hirviöt
  cache,w,h,f = {},len(r[0]),len(r), lambda x,y,c: bad if c=='#' else \
    (c=='@') + min(memoize(cache, f, (x-1,y, r[x-1][y]))if x else bad if y else 0,
                   memoize(cache, f, (x,y-1, r[x][y-1]))if y else bad if x else 0)
  return (min(bad-1, f(w-1, h-1, r[w-1][h-1])) + 1) % bad - 1

def count(t):               # 9.6 Kolikot
  sums = set()
  for i in t: sums.update([s+i for s in sums], [i])
  return len(sums)

cache = {}                  # 9.7 Bittipoisto
def count(s):
  return sum(memoize(cache, count, [s[:i]+s[i+2:]])
             for i in range(len(s)-1) if s[i]==s[i+1]) if len(s) else 1

import math                 # 9.8 Kurssi
def count(x, c = 7, n_over_k = lambda k,n,l=math.lgamma: l(n+1) - l(k+1) - l(n-k+1)):
   return round(sum( (math.exp(sum(n_over_k(i,8) for i in s))
                      for s in ([5 + ((p>>i*2)&3) for i in range(c)] for p in range(1<<c*2))
                      if sum(s) == x) ))

# Tehtävien 9.5 ja 9.7 käyttämä apufunktio, joka toteuttaa muistin:
def memoize(cache, u, p=()):
  k = hash(p)
  if k in cache: return cache[k]
  result   = u(*p)
  cache[k] = result
  return result
"""
 Huom. Tehtävissä 9.3 ja 9.8 käytetyt funktiot gamma ja lgamma toteuttavat
       laskennan (x-1)! ja ln((x–1)!), eli kertomafunktion (engl. factorial).

       Näin ollen esim. kombinaatio (n yli k), jonka kaava on n! / (k! · (n–k)!),
       voidaan laskea seuraavasti: gamma(n+1) / (gamma(k+1) * gamma(n+k+1))
       tai näin:                   exp(lgamma(n+1) – lgamma(k+1) – lgamma(n+k–1))

       Logaritmisesta gammafunktiosta on se etu, että se välttää kolossaalisen suurten
       numeroiden käsittelyn laskennan välivaiheissa. Lisäksi se yksinkertaistaa jakolaskut
       vähennyslaskuiksi ja kertolaskut yhteenlaskuiksi.
       Liukulukujen epätarkkuudesta johtuen on kuitenkin mahdollista, että esim. arvon 54
       sijaan vastaukseksi tuleekin 53.99999999996 tai 54.00000000002. CSES-järjestelmä
       ei tällaisia tuloksia hyväksy. Virhe on sitä todennäköisempi, mitä useampi
       laskutoimitus suoritetaan. Tästä syystä funktion lopputuloksen laskennan ympärillä
       on yksi round()-lauseke.

       Gammafunktiota käytetään mm. fysiikassa, jossa on käyttöä myös funktion arvoilla
       sellaisilla parametreilla, jotka eivät ole kokonaislukuja.
"""