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

""" Joelin ratkaisut Helsingin yliopiston Tietorakenteet ja algoritmit-kurssin
    viikon 13 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
"""

from collections import deque # 13.3 Komponentit — Lähes suora kopio
class Components:             # tehtävistä 10.4 Tietoverkko ja 11.3 Paras reitti
  def __init__(self,n):   self.E   = [set([a]) for a in range(n)]
  def add_road(self,a,b): self.E[a-1].add(b-1), self.E[b-1].add(a-1)
  def count(self):
    result,d = 0,set()
    for s in (n for n in range(len(self.E)) if not n in d):
      result,s = result+1, deque(((0, s) for s in [s]))
      while len(s): (lambda cur,a: None if a in d else (d.add(a), s.extend( (cur+1, c) for c in self.E[a])))(*s.popleft())
    return result

class NewRoads:               # 13.4 Uudet tiet — using adjacency matrix
  def __init__(self,n):          self.E = [[-1]*n for _ in range(n)]
  def set_road(self,a,b,length): self.E[a-1][b-1] = min(length, self.E[a-1][b-1]) if self.E[a-1][b-1]>0 else length
  def add_road(self,a,b,length): self.set_road(a,b,length), self.set_road(b,a,length)
  def min_cost(self):         # Minimum spanning tree using Prim's algorithm without heap
    visited,cost,V = 1,0, len(self.E)
    while visited != (1<<V)-1:
      min,a,b = 10**9,0,0
      for m in range(V):
        if visited & (1<<m):
          for n in range(V):
            if (not visited & (1<<n)) and self.E[m][n] > 0 and self.E[m][n] < min:
              min = self.E[m][n]
              a,b = m,n
      if a==b: return -1
      visited |= (1<<b)
      cost    += self.E[a][b]
    return cost

class MaxSet:                 # 13.5 Suurin joukko — ei yllätyksiä, ~identtinen malliratkaisun kanssa
  def __init__(self,n):
    self.size    = [1] * n        # Task: Merge sets, and return the
    self.parent  = list(range(n)) # size of largest set. Using Union-Find.
    self.maxsize = 1
  def merge(self,a,b):
    def rep(x): return x if x==self.parent[x] else rep(self.parent[x])
    a,b = rep(a-1), rep(b-1)
    if a == b: return
    if self.size[a] < self.size[b]: a,b=b,a
    self.parent[b] = a
    self.size[a]  += self.size[b]
    self.maxsize = max(self.maxsize, self.size[a])
  def get_max(self):
    return self.maxsize

pass                          # 13.6 Samat painot — Tätä tehtävää en tehnyt.

class WallGrid:               # 13.7 Seinät ja lattiat — Pieni muunnelma tehtävästä 13.5
  def __init__(self,n): r,parent,open,rep,self.count,self.remove = [0],list(range(n*n)),[False]*n*n, \
    lambda x: x if x==parent[x] else rep(parent[x]),             lambda:r[0], \
    lambda x,y: (lambda a: setp(open,a,True) is setp(r,0,r[0]+
        1 - sum( (lambda a,b: setp(parent,b,a)is None if a!=b else 0)(rep(a),rep(b))
                 for b in (a-1, a+1, a-n, a+n) if open[b])) if not open[a] else 0) (x-1 + n*(y-1))
    # Room count is incremented by 1 by each new room, reduced by sum of successfully performed merges.

# Tehtävä: Yhdistellään joukkoja, ja palautetaan jäljelle jäävien joukkojen määrä. Menetelmä: Union-Find.
# Koska palautuslomake ei ole pikkutarkka algoritmin tehokkuudesta, algoritmista poistettiin kokojen käsittely.


class AllTrees:               # 13.8 Kaikki puut
  def __init__(self,n):   self.E,self.N = [[0]*n for _ in range(n)], n
  def add_edge(self,a,b): self.E[a-1][b-1], self.E[b-1][a-1] = 1,1
  def count(self):            # Using the Matrix Tree algorithm. See https://youtu.be/NcOYysnlx-0
    return round(determinant([[(0 if x-y else sum(self.E[y])) - self.E[y][x] for x in range(1,self.N)]
                                                                             for y in range(1,self.N)]))

# Tehtävässä 13.8 käytetty yleispätevä matriisin determinantin laskeva funktio:
# Sovellettu: https://integratedmlai.com/find-the-determinant-of-a-matrix-with-pure-python-without-numpy-or-scipy/
# Ensiksi muuntaa matriisin yläkolmiomuotoon ja sitten laskee determinantin päädiagonaalin arvojen tulosta.
def determinant(A, p=lambda f,x,*a:x*(f(f,*a)if len(a)else 1)): # Note: Modifies the matrix passed as parameter.
  for fd in range(len(A)):
    A[fd+1:] = [(lambda scaler: [A[i][j] - scaler*A[fd][j]      for j in range(      len(A))]
                )(A[i][fd] / A[fd][fd] if A[fd][fd] else 10**9) for i in range(fd+1, len(A))]
  return p(p,*(A[i][i] for i in range(len(A)))) # p is just like reduce(mul, ..) but w/out import functools,operator.

# Tehtävässä 13.7 käytetty funktio, joka vain muuttaa muuttujaan asetuksen lausekkeeksi:
def setp(w,b,a): w[b] = a