Advertisement
Bisqwit

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

Nov 21st, 2021 (edited)
254
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 4.56 KB | None | 0 0
  1. """ Joelin ratkaisut Helsingin yliopiston Tietorakenteet ja algoritmit-kurssin
  2.    viikon 10 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 Cities:                 # 10.3 Kaupungit — varsin suoraviivainen ratkaisu.
  18.     def __init__(self,n):
  19.         self.edges   = [set([a]) for a in range(n+1)]
  20.     def add_road(self,a,b):
  21.         self.edges[a].add(b)
  22.         self.edges[b].add(a)
  23.     def has_route(self,a,b):
  24.         visited = 0
  25.         stack   = [a]
  26.         while len(stack):
  27.           a = stack.pop()
  28.           if visited & (1 << a): continue
  29.           visited |= 1 << a
  30.           stack.extend( self.edges[a] )
  31.         return False
  32.  
  33. from collections import deque # 10.4 Tietoverkko — kuten tämäkin.
  34. class Network:
  35.     def __init__(self,n):
  36.         self.edges   = [set([a]) for a in range(n+1)]
  37.     def add_link(self,a,b):
  38.         self.edges[a].add(b)
  39.         self.edges[b].add(a)
  40.     def best_route(self,a,b):
  41.         visited = set()
  42.         s = deque(((0, a) for a in [a]))
  43.         while len(s) and s[0][1] != b:
  44.           (lambda cur,a:
  45.             (visited.add(a), s.extend( (cur+1, c) for c in self.edges[a]))
  46.             if not a in visited else None)(*s.popleft())
  47.         return s[0][0] if(len(s) and s[0][1] == b) else -1 # Paluuarvo -1 jos ei löydetty maalia.
  48.  
  49. def count(r):                 # 10.5 Huoneet
  50.   map = [ sum((c != '#')<<x for (x,c) in enumerate(list(r))) for r in r]
  51.   result = 0
  52.   for y in range(len(map)):
  53.    for x in range(len(r[0])):
  54.     if (map[y] >> x) & 1:
  55.       result += 1
  56.       stack = [(x,y)]
  57.       while len(stack):
  58.         (x,y) = stack.pop()
  59.         if (map[y] >> x) & 1:
  60.           map[y] &= ~(1<<x)
  61.           stack.extend(((x,y-1), (x,y+1), (x-1,y), (x+1,y)))
  62.   return result
  63.  
  64. from collections import deque # 10.6 Labyrintti
  65. def count(r:
  66.   map = [ sum((c != '#')<<x for (x,c) in enumerate(list(r))) for r in r]
  67.   for s in r:
  68.     if ('A' in s):
  69.       stack = deque( (c, s.index('A'), r.index(s)) for c in [0] )
  70.       while len(stack):
  71.         (score, x,y) = stack.popleft()
  72.         if map[y] & (1 << x):
  73.           if r[y][x] == 'B': return score
  74.           map[y] &= ~(1 << x)
  75.           stack.extend( (score+1,x,y) for (x,y) in ((x-1,y),(x+1,y),(x,y-1),(x,y+1)) )
  76.   return -1
  77.  
  78. class Coloring:               # 10.7 Väritys
  79.     def __init__(self,n):
  80.         self.edges   = [set() for a in range(n+1)]
  81.     def add_edge(self,a,b):
  82.         self.edges[a].add(b)
  83.         self.edges[b].add(a)
  84.     def check(self):
  85.         colors = [-1] * (len(self.edges))
  86.         for p in range(len(self.edges)):
  87.           if colors[p] >= 0: continue
  88.           stack   = [ (0,p) ]
  89.           while len(stack):
  90.             (modulo,p) = stack.pop()
  91.             if(colors[p] >= 0):
  92.               if (colors[p] != modulo): return False  # Found contradiction
  93.               continue
  94.             colors[p] = modulo
  95.             stack.extend( (1-modulo, c) for c in self.edges[p] )
  96.         return True
  97.  
  98. from collections import deque # 10.8 Laatikko
  99. def count(r, h=0):            # Sokoban!
  100.   goal,start,box = (0,0), (0,0), (0,0)
  101.   for s in r:
  102.     if ('X' in s): start = (s.index('X'), h)
  103.     if ('Y' in s): goal  = (s.index('Y'), h)
  104.     if ('B' in s): box   = (s.index('B'), h)
  105.     h += 1
  106.   w       = len(r[0])
  107.   visited = [0] * w*h*h
  108.   stack   = deque( ( c, *start, *box ) for c in [0] )
  109.   while len(stack):
  110.     (score, px,py, bx,by) = stack.popleft()
  111.     if (bx,by) == goal: return score
  112.     p = py*w*h + by*w+bx
  113.     if r[py][px] == '#' or visited[p] & (1 << px): continue
  114.     visited[p] |= (1 << px)
  115.     stack.extend( (score+1, px+x,py+y, bx+b*x, by+b*y)
  116.                   for (x,y,b) in ((x,y,bx==px+x and by==py+y)
  117.                                   for (x,y) in ((-1,0), (1,0), (0,-1), (0,1))))
  118.   return -1
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement