Bisqwit

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

Dec 15th, 2021 (edited)
286
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 5.33 KB | None | 0 0
  1. """ Joelin ratkaisut Helsingin yliopiston Tietorakenteet ja algoritmit-kurssin
  2.    viikon 13 harjoitustehtäviin https://cses.fi/tira21s/list/ .
  3.    Nämä ratkaisut eroavat tarkoituksella malliratkaisuista. Niiden pääasiallinen
  4.    tarkoitus on inspiroida ja antaa ideoita sellaisille opiskelijoille, jotka
  5.    haluavat nähdä ohjelmoinnin taiteena — tai kenties vaikka yksinkertaisina
  6.    matemaattisina lausekkeina. Vastaukset ovat tarkoituksella erittäin tiiviitä.
  7.    Missään nimessä niitä ei tule tulkita esimerkkeinä hyvistä ohjelmointitavoista!
  8.    Discordissa saa vapaasti kysyä, jos jokin kohta herättää kysymyksiä.
  9.    Tehtäväsarja 8: https://pastebin.com/5u166swH
  10.    Tehtäväsarja 9: https://pastebin.com/Vs2CNwQA
  11.    Tehtäväsarja 10: https://pastebin.com/jeXQ1JnT
  12.    Tehtäväsarja 11: https://pastebin.com/pTh4ZwFE
  13.    Tehtäväsarja 12: https://pastebin.com/eJ8HMRCF
  14.    Tehtäväsarja 13: https://pastebin.com/ETpqtDBY
  15. """
  16.  
  17. from collections import deque # 13.3 Komponentit — Lähes suora kopio
  18. class Components:             # tehtävistä 10.4 Tietoverkko ja 11.3 Paras reitti
  19.   def __init__(self,n):   self.E   = [set([a]) for a in range(n)]
  20.   def add_road(self,a,b): self.E[a-1].add(b-1), self.E[b-1].add(a-1)
  21.   def count(self):
  22.     result,d = 0,set()
  23.     for s in (n for n in range(len(self.E)) if not n in d):
  24.       result,s = result+1, deque(((0, s) for s in [s]))
  25.       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())
  26.     return result
  27.  
  28. class NewRoads:               # 13.4 Uudet tiet — using adjacency matrix
  29.   def __init__(self,n):          self.E = [[-1]*n for _ in range(n)]
  30.   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
  31.   def add_road(self,a,b,length): self.set_road(a,b,length), self.set_road(b,a,length)
  32.   def min_cost(self):         # Minimum spanning tree using Prim's algorithm without heap
  33.     visited,cost,V = 1,0, len(self.E)
  34.     while visited != (1<<V)-1:
  35.       min,a,b = 10**9,0,0
  36.       for m in range(V):
  37.         if visited & (1<<m):
  38.           for n in range(V):
  39.             if (not visited & (1<<n)) and self.E[m][n] > 0 and self.E[m][n] < min:
  40.               min = self.E[m][n]
  41.               a,b = m,n
  42.       if a==b: return -1
  43.       visited |= (1<<b)
  44.       cost    += self.E[a][b]
  45.     return cost
  46.  
  47. class MaxSet:                 # 13.5 Suurin joukko — ei yllätyksiä, ~identtinen malliratkaisun kanssa
  48.   def __init__(self,n):
  49.     self.size    = [1] * n        # Task: Merge sets, and return the
  50.     self.parent  = list(range(n)) # size of largest set. Using Union-Find.
  51.     self.maxsize = 1
  52.   def merge(self,a,b):
  53.     def rep(x): return x if x==self.parent[x] else rep(self.parent[x])
  54.     a,b = rep(a-1), rep(b-1)
  55.     if a == b: return
  56.     if self.size[a] < self.size[b]: a,b=b,a
  57.     self.parent[b] = a
  58.     self.size[a]  += self.size[b]
  59.     self.maxsize = max(self.maxsize, self.size[a])
  60.   def get_max(self):
  61.     return self.maxsize
  62.  
  63. pass                          # 13.6 Samat painot — Tätä tehtävää en tehnyt.
  64.  
  65. class WallGrid:               # 13.7 Seinät ja lattiat — Pieni muunnelma tehtävästä 13.5
  66.   def __init__(self,n): r,parent,open,rep,self.count,self.remove = [0],list(range(n*n)),[False]*n*n, \
  67.     lambda x: x if x==parent[x] else rep(parent[x]),             lambda:r[0], \
  68.     lambda x,y: (lambda a: setp(open,a,True) is setp(r,0,r[0]+
  69.         1 - sum( (lambda a,b: setp(parent,b,a)is None if a!=b else 0)(rep(a),rep(b))
  70.                  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))
  71.     # Room count is incremented by 1 by each new room, reduced by sum of successfully performed merges.
  72.  
  73. # Tehtävä: Yhdistellään joukkoja, ja palautetaan jäljelle jäävien joukkojen määrä. Menetelmä: Union-Find.
  74. # Koska palautuslomake ei ole pikkutarkka algoritmin tehokkuudesta, algoritmista poistettiin kokojen käsittely.
  75.  
  76.  
  77. class AllTrees:               # 13.8 Kaikki puut
  78.   def __init__(self,n):   self.E,self.N = [[0]*n for _ in range(n)], n
  79.   def add_edge(self,a,b): self.E[a-1][b-1], self.E[b-1][a-1] = 1,1
  80.   def count(self):            # Using the Matrix Tree algorithm. See https://youtu.be/NcOYysnlx-0
  81.     return round(determinant([[(0 if x-y else sum(self.E[y])) - self.E[y][x] for x in range(1,self.N)]
  82.                                                                              for y in range(1,self.N)]))
  83.  
  84. # Tehtävässä 13.8 käytetty yleispätevä matriisin determinantin laskeva funktio:
  85. # Sovellettu: https://integratedmlai.com/find-the-determinant-of-a-matrix-with-pure-python-without-numpy-or-scipy/
  86. # Ensiksi muuntaa matriisin yläkolmiomuotoon ja sitten laskee determinantin päädiagonaalin arvojen tulosta.
  87. def determinant(A, p=lambda f,x,*a:x*(f(f,*a)if len(a)else 1)): # Note: Modifies the matrix passed as parameter.
  88.   for fd in range(len(A)):
  89.     A[fd+1:] = [(lambda scaler: [A[i][j] - scaler*A[fd][j]      for j in range(      len(A))]
  90.                 )(A[i][fd] / A[fd][fd] if A[fd][fd] else 10**9) for i in range(fd+1, len(A))]
  91.   return p(p,*(A[i][i] for i in range(len(A)))) # p is just like reduce(mul, ..) but w/out import functools,operator.
  92.  
  93. # Tehtävässä 13.7 käytetty funktio, joka vain muuttaa muuttujaan asetuksen lausekkeeksi:
  94. def setp(w,b,a): w[b] = a
Add Comment
Please, Sign In to add comment