Advertisement
Bisqwit

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

Dec 5th, 2021 (edited)
232
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 7.79 KB | None | 0 0
  1. """ Joelin ratkaisut Helsingin yliopiston Tietorakenteet ja algoritmit-kurssin
  2.    viikon 12 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. class Cycles:             # 12.3 Syklit
  18.   def __init__(self,n):   self.edges = [set() for a in range(n)]
  19.   def add_edge(self,a,b): self.edges[a-1].add(b-1)
  20.   def check(self):
  21.     stack = set()         # Paluuarvo on tosi, jos jokin läpikäyntijärjestys tuottaa reitin, jossa
  22.     def gruu1(a): return (stack.add(a), gruu(a), stack.remove(a))[1]    # palataan jo aiemmin läpi
  23.     def gruu(a):  return any(b in stack or gruu1(b) for b in self.edges[a])      # käytyyn soluun.
  24.     return any(gruu1(a) for a in range(len(self.edges)))
  25.  
  26.  
  27. class CoursePlan:         # 12.4 Kurssit
  28.   def __init__(self):            self.names, self.edges = [], [set() for _ in range(50)]
  29.   def add_course(self,course):   self.names.append(course)
  30.   def add_requisite(self,c1,c2): self.edges[ self.names.index(c1) ].add( self.names.index(c2) )
  31.   def find(self):
  32.     colors,l = [0] * len(self.names), []
  33.     def explore(start):      # Ratkaisu käyttää topologista järjestystä (topological sort)
  34.       if colors[start] != 2: # sellaisenaan kirjan mallin pohjalta.
  35.         colors[start] = 1
  36.         if any(colors[e] == 1 or not explore(e) for e in self.edges[start]): return False
  37.         l.insert(0, self.names[start])
  38.         colors[start] = 2
  39.       return True
  40.     return l if all(colors[s] != 0 or explore(s) for s in range(len(colors))) else None
  41.  
  42.  
  43. class LongPath:           # 12.5 Pisin polku
  44.   def __init__(self,n):   self.edges = [set() for m in range(n+1)]
  45.   def add_edge(self,a,b): self.edges[min(a,b)].add(max(a,b))
  46.   def calculate(self):
  47.     length = [0] * len(self.edges)
  48.     for i in range(len(self.edges)-1,-1,-1):
  49.       length[i] = max(0,0, *(length[m]+1 for m in self.edges[i]))
  50.     return max(length)
  51.  
  52. class LongPath_bitmath:   # 12.5 Pisin polku, vaihtoehtoinen
  53.   def __init__(self,n):   self.edges = [0] * (n+1)
  54.   def add_edge(self,a,b): self.edges[min(a,b)] |= (1 << max(a,b))
  55.   def calculate(self):
  56.     length = [0] * len(self.edges)
  57.     for i in range(len(self.edges)-1,-1,-1):
  58.       length[i] = max(0,0, *(length[m]+1 for m in bits(self.edges[i])))
  59.     return max(length)
  60.  
  61.  
  62. import functools,operator # 12.6 Lentokentät
  63. class Airports:
  64.   def __init__(self,n):   self.edges = [(1<<m) for m in range(n)]
  65.   def add_link(self,a,b): self.edges[a-1] |= (1 << (b-1))
  66.   def check(self):
  67.     map = self.edges.copy()
  68.     for b in range(len(self.edges)):
  69.       for a in range(len(self.edges)):
  70.         map[a] |= functools.reduce(operator.__or__, (map[m] for m in bits(self.edges[a])), 0)
  71.     return min(map) == (1 << len(map))-1
  72.  
  73.  
  74. class GraphGame:          # 12.7 Verkkopeli
  75.   def __init__(self,n):   self.edges = [set() for m in range(n)]
  76.   def add_link(self,a,b): self.edges[a-1].add(b-1)
  77.   def winning(self, x):
  78.     e = self.edges
  79.     (win,lose) = [ False ] * len(e), [ len(e[a])==0 for a in range(len(e)) ]
  80.     for n in range(len(e)):
  81.       for a in range(len(e)):
  82.         win[a] |= any(lose[b] for b in e[a])
  83.         lose[a] |= all(win[b] for b in e[a])
  84.     return win[x-1]
  85.  
  86.    
  87. import heapq              # 12.8 Polut
  88. # Koska 12.8 malliratkaisu oli huomattavan lyhyt, mutta ei suinkaan optimaalinen,
  89. # päätin tehdä tästä ratkaisusta sellaisen, joka minimoi kaarien määrän.
  90. #
  91. def create(N, best={}):
  92.   def execute(hist, s=1, e=100, edges=[]):
  93.     for n,code in hist:
  94.       if code:
  95.         z = s+n if code>0 else e
  96.         edges.append( (s,   z))
  97.         edges.extend( (s, s+m) for m in range(1,n) )
  98.         edges.extend( (s+m, z) for m in range(1,n) )
  99.         s = z
  100.       else:
  101.         edges.append((s,e))
  102.         while n > 1:
  103.           edges.append((s, s+1))
  104.           edges.append((s+1, e))
  105.           s += 1
  106.           n -= 1
  107.     return edges
  108.   # Use dijkstra to figure out the best way to plan the route
  109.   # At each point, create one of these alternatives::
  110.   #
  111.   # Triangle of 3 paths:    Diamond of 3 paths:    Straight of 3 paths:
  112.   # ──┬─────z──             ──┬─b─z──              ──┬─────────end
  113.   #   ├──b──┤                 ├─c─┤                  ╰─b───────┤
  114.   #   ╰──c──╯                 ╰─d─╯                    ╰─c─────╯
  115.   #                                                      ╰──
  116.   #  = 2M-1 edges           = 2M edges             = 2M-1 edges
  117.   #
  118.   # Note that a straight(N) followed by a triangle(M) is invalid *at the end* (z=end),
  119.   # because it would generate two parallel arcs to end.
  120.   # This can be easily taken care by never doing triangles or diamonds with M=remaining n.
  121.   # A valid alternative would be to generate straight(N) followed by a diamond(M),
  122.   # but there is no advantage in that approach in terms of arc count.
  123.   # In testing, it was determined for M values that
  124.   # within 1 <= N <= 1200000,
  125.   #   M=2 occurs 99,99% of times
  126.   #   M=3 occurs 92,44% of times
  127.   #   M=5 occurs 9.404% of times
  128.   #   M=7 occurs 0.0952% of times (1142 times)
  129.   # Other values of M (tested up to 19) were not observed, so the search is capped to that.
  130.   #
  131.   # The smallest value of N where the network of 1—100 is too small
  132.   # that I found was 2251799813682908. The number of arcs was still
  133.   # only 170, nowhere close to the task limit of 1000.
  134.   #
  135.   # Element: Number of edges, remaining n, [plan]
  136.   # Plan elements are:
  137.   #    N straight lines to end:       (n,0)
  138.   #    Triangle of M:                 (n,3)
  139.   #    Diamond of M:                  (n,4) -- unused
  140.   #    Triangle of M straight to end: (n,-3) -- unused
  141.   #    Diamond of M straight to end:  (n,-4) -- unused
  142.   s = []
  143.   best={}
  144.   #s.extend( (best[k][0], k, best[k][1]) for k in best.keys() if (k <= N and k >= N-40))
  145.   if len(s)<16: s.append( (0, 0, []) )
  146.   heapq.heapify(s)
  147.   def add(cost, done, newhist):
  148.     if done in best and best[done][0] <= cost: return
  149.     if newhist[-1][1]: best[done] = (cost, newhist)
  150.     heapq.heappush(s, (cost, done, newhist))
  151.   while len(s):
  152.     (cost,done,hist) = heapq.heappop(s)
  153.     if done==N:
  154.       print("For %d best path (cost=%d): " % (N,cost), hist)
  155.       return execute(hist)
  156.     for m in (a for a in range(2,min(8,N-done)) if a!=4 and a!=6): # Try primes < 8 & < n
  157.       r = (N-done) % m
  158.       if r == 0: add(cost +           1+(m-1)*2, N - (N-done  )//m, hist + [       (m,3)])
  159.       else:      add(cost + (r*2-1) + 1+(m-1)*2, N - (N-done-r)//m, hist + [(r,0), (m,3)])
  160.     if (N-done) < 4: add(cost + ((N-done)*2-1), N, hist + [((N-done),0)])
  161.   return None
  162.  
  163.  
  164.  
  165. Tehtävässä 12.6 (ja 12.5 vaihtoehtoinen) käytetyt apufunktiot ovat:
  166.  
  167. def log2(n): return sum(((n&(0xFFFFFFFFFFFFFFFF//((1<<(1<<i))+1)<<(1<<i)))!=0)<<i for i in range(6))
  168. def bits(e): # Returns the list of bit indexes set in e
  169.   result = []
  170.   while e:
  171.     b = e & -e # Clears all but LSB
  172.     e = e & ~b
  173.     result.append( log2(b) )
  174.   return result
  175.  
  176. Huom. log2-funktio toimii vain kahden potensseille.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement