Bisqwit

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

Dec 4th, 2021 (edited)
265
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 6.95 KB | None | 0 0
  1. """ Joelin ratkaisut Helsingin yliopiston Tietorakenteet ja algoritmit-kurssin
  2.    viikon 11 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. import heapq              # 11.3 Paras reitti
  18. class BestRoute:
  19.   def __init__(self,n):
  20.     self.edges   = [{a: 0} for a in range(n+1)]
  21.   def add_road(self,a,b, length):
  22.     self.edges[a][b] = min(length, self.edges[a][b] if(b)in self.edges[a] else 9999)
  23.     self.edges[b][a] = min(length, self.edges[b][a] if(a)in self.edges[b] else 9999)
  24.   def find_route(self,a,b, push=heapq.heappush, pop=heapq.heappop):
  25.     visited = set()
  26.     s = [(0, a)]
  27.     while len(s) and s[0][1] != b:
  28.       (lambda cur,a:
  29.         (visited.add(a), *(push(s, (cur+cost, c)) for (c,cost) in self.edges[a].items()))
  30.         if not a in visited else None)(*pop(s))
  31.     return s[0][0] if(len(s) and s[0][1] == b) else -1 # Paluuarvo -1 jos ei löydetty maalia.
  32.  
  33. import heapq              # 11.4 Välimatkat
  34. class AllRoutes:          #      Nope, en käyttänyt tässä Bellman-Fordia.
  35.   def __init__(self,n):
  36.     self.edges   = [{a: 0} for a in range(n)]
  37.   def add_road(self,a,b, length):
  38.     self.e[a-1][b-1] = min(length, self.e[a-1][b-1] if(b-1)in self.e[a-1] else 9999)
  39.     self.e[b-1][a-1] = min(length, self.e[b-1][a-1] if(a-1)in self.e[b-1] else 9999)
  40.   def get_table(self):
  41.     def find_all_routes(e, s, seen, pop=heapq.heappop, push=heapq.heappush):
  42.       while len(s):        # Tämä käyttää Dijkstraa.
  43.         (c,a) = pop(s)     # Sivutuotteena siitä syntyy kustannuskaavio kaikille solmuille.
  44.         seen[a] = (c,*(push(s, (c+C,d)) for (d,C) in e[a].items()))[0] if seen[a]<0 else seen[a]
  45.       return seen
  46.     return [ find_all_routes(self.e, [(0,a)], [-1]*len(self.e)) for a in range(len(self.e)) ]
  47.  
  48. import heapq              # 11.5 Listahyppy
  49. def calculate(t):
  50.   visited = set()
  51.   s       = [ (0,0) ]
  52.   while len(s) and s[0][1] != len(t)-1:
  53.     cur,a) = heapq.heappop(s)
  54.     (visited.add(a), heapq.heappush(s, (cur+t[a], a+t[a])),
  55.                      heapq.heappush(s, (cur+t[a], a-t[a]))
  56.     )if a>=0 and a<len(t) and not a in visited else None
  57.   return s[0][0] if(len(s) and s[0][1]==len(t)-1) else -1
  58.  
  59. import heapq              # 11.6 Seinän poisto
  60. def count(r):             # Tässä tehtävässä olennaista oli oivaltaa, ettei
  61.   visited = set()         # tietoa siitä, onko seinä jo poistettu vaiko ei,
  62.   for s in r:             # tarvitse säilyttää, koska samaan solmuun ei ole
  63.     if ('A' in s):        # mitään hyötyä palata missään tilanteessa.
  64.       s = [ (0, s.index('A'), r.index(s)) ] # Nyt s[0] = (pisteet, x,y) aloituskoordinaatille
  65.       while len(s) and r[s[0][2]][s[0][1]] != 'B':
  66.         (score,px,py) = heapq.heappop(s)
  67.         ([heapq.heappush(s, (score + (r[py+dy][px+dx] == '*'), px+dx,py+dy))
  68.          for (dx,dy) in ((-1,0), (1,0), (0,-1), (0,1)) if r[py+dy][px+dx] != '#']
  69.         if (0 if hash((px,py))in visited else visited.add(hash((px,py)))is None)else 0)
  70.       return s[0][0] if(len(s) and r[s[0][2]][s[0][1]] == 'B') else -1
  71.  
  72. class Shortening:         # 11.7 Lyhennys.  Tehtävä oli vaikea ja malliratkaisu
  73.   def __init__(self,n):   #                 oli vaikealukuinen, joten koodista
  74.     self.edges  =[{} for a in range(n+1)] # on poikkeuksellisesti tehty (lähes)
  75.     self.sources=[{} for b in range(n+1)] # esimerkillinen ja selkeä.
  76.                                           # Algoritmi poikkeaa osin myös malliratkaisusta.
  77.   def add_edge(self,a,b, length):
  78.     if not (b in self.edges[a]) or (self.edges[a][b] > length):
  79.       self.edges[a][b]   = length
  80.       self.sources[b][a] = length
  81.  
  82.   def check(self,source,goal, big=10**9, sentinel=10**9+1):
  83.     # First, build a list of nodes that can participate in route from source to goal.
  84.     recursion  = lambda r,*p: r(*p, r)    # No ehkä tätä osaa lukuunottamatta ;-)
  85.     candidates = (lambda a,b: a.intersection(b))(*(recursion((lambda e,s,seen,rec: \
  86.      (lambda a: rec(e,s,(0 if a in seen else s.extend(e[a].keys()),seen.add(a),seen)[2],rec)
  87.      )(s.pop()) if len(s) else seen), edges, stack, set())
  88.                  for(edges,stack) in ((self.edges, [source]), (self.sources, [goal]))))
  89.     # Use Bellman-Ford algorithm, but only on those nodes that can participate.
  90.     dist  = [big] * (max(candidates)+1 if candidates else 0) + [sentinel]
  91.     if candidates: dist[source] = 0
  92.     for i in dist:
  93.       done = True
  94.       for a in candidates:
  95.         for (b, length) in self.edges[a].items():
  96.           if b in candidates:
  97.             newdist = dist[a] + length
  98.             if newdist < dist[b]:
  99.               dist[b] = newdist
  100.               done    = False
  101.       # Return true if there is a negative loop in the remaining net,
  102.       # which consists of only those nodes that participate in route
  103.       # from source to goal.
  104.       # The negative loop is identified by the node distances getting
  105.       # shorter and shorter without limit (i.e. loop is never ”done”).
  106.       # If there are negative edges, but not a negative loop,
  107.       # the loop will only run for num(nodes)-1 times at max.
  108.       if done or i == sentinel: return not done
  109.       # The loop will also never terminate if candidates is empty
  110.       # (i.e. source cannot reach goal). This is desired, because
  111.       # False is the correct answer in that case.
  112.  
  113. import heapq              # 11.8 Veden mittaus
  114. def count(capA,capB, goal):
  115.   s       = [ (0,0,0) ] # Siirretty määrä; A:n sisältö, B:n sisältö
  116.   visited = set()
  117.   while len(s) and s[0][1] != goal:
  118.     (lambda cur,a,b: [heapq.heappush(s, (cur+move, a + da*move, b + db*move))
  119.         for (move,da,db) in ( # Siirrettävä määrä (vain jos > 0), siirtosuunnat A ja B:n suhteen
  120.            (a,           -1,0),  (b,            0,-1), # Tyhjentämiset
  121.            (capA-a,       1,0),  (capB-b,       0, 1), # Täyttämiset
  122.            (min(capA-a,b),1,-1), (min(capB-b,a),-1,1)) # Siirtämiset
  123.         if move > 0] \
  124.       if (0 if hash((a,b))in visited else visited.add(hash((a,b)))is None)else 0
  125.     )(*heapq.heappop(s)) # Käydään läpi seuraava kappale pinosta, mikäli (a,b) ei ole käyty jo.
  126.   return s[0][0] if(len(s) and s[0][1] == goal) else -1 # Paluuarvo -1 jos ei löydetty maalia.
Add Comment
Please, Sign In to add comment