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

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

class Cities:                 # 10.3 Kaupungit — varsin suoraviivainen ratkaisu.
    def __init__(self,n):
        self.edges   = [set([a]) for a in range(n+1)]
    def add_road(self,a,b):
        self.edges[a].add(b)
        self.edges[b].add(a)
    def has_route(self,a,b):
        visited = 0
        stack   = [a]
        while len(stack):
          a = stack.pop()
          if visited & (1 << a): continue
          visited |= 1 << a
          stack.extend( self.edges[a] )
        return False

from collections import deque # 10.4 Tietoverkko — kuten tämäkin.
class Network:
    def __init__(self,n):
        self.edges   = [set([a]) for a in range(n+1)]
    def add_link(self,a,b):
        self.edges[a].add(b)
        self.edges[b].add(a)
    def best_route(self,a,b):
        visited = set()
        s = deque(((0, a) for a in [a]))
        while len(s) and s[0][1] != b:
          (lambda cur,a:
            (visited.add(a), s.extend( (cur+1, c) for c in self.edges[a]))
            if not a in visited else None)(*s.popleft())
        return s[0][0] if(len(s) and s[0][1] == b) else -1 # Paluuarvo -1 jos ei löydetty maalia.

def count(r):                 # 10.5 Huoneet
  map = [ sum((c != '#')<<x for (x,c) in enumerate(list(r))) for r in r]
  result = 0
  for y in range(len(map)):
   for x in range(len(r[0])):
    if (map[y] >> x) & 1:
      result += 1
      stack = [(x,y)]
      while len(stack):
        (x,y) = stack.pop()
        if (map[y] >> x) & 1:
          map[y] &= ~(1<<x)
          stack.extend(((x,y-1), (x,y+1), (x-1,y), (x+1,y)))
  return result

from collections import deque # 10.6 Labyrintti
def count(r:
  map = [ sum((c != '#')<<x for (x,c) in enumerate(list(r))) for r in r]
  for s in r:
    if ('A' in s):
      stack = deque( (c, s.index('A'), r.index(s)) for c in [0] )
      while len(stack):
        (score, x,y) = stack.popleft()
        if map[y] & (1 << x):
          if r[y][x] == 'B': return score
          map[y] &= ~(1 << x)
          stack.extend( (score+1,x,y) for (x,y) in ((x-1,y),(x+1,y),(x,y-1),(x,y+1)) )
  return -1

class Coloring:               # 10.7 Väritys
    def __init__(self,n):
        self.edges   = [set() for a in range(n+1)]
    def add_edge(self,a,b):
        self.edges[a].add(b)
        self.edges[b].add(a)
    def check(self):
        colors = [-1] * (len(self.edges))
        for p in range(len(self.edges)):
          if colors[p] >= 0: continue
          stack   = [ (0,p) ]
          while len(stack):
            (modulo,p) = stack.pop()
            if(colors[p] >= 0):
              if (colors[p] != modulo): return False  # Found contradiction
              continue
            colors[p] = modulo
            stack.extend( (1-modulo, c) for c in self.edges[p] )
        return True

from collections import deque # 10.8 Laatikko
def count(r, h=0):            # Sokoban!
  goal,start,box = (0,0), (0,0), (0,0)
  for s in r:
    if ('X' in s): start = (s.index('X'), h)
    if ('Y' in s): goal  = (s.index('Y'), h)
    if ('B' in s): box   = (s.index('B'), h)
    h += 1
  w       = len(r[0])
  visited = [0] * w*h*h
  stack   = deque( ( c, *start, *box ) for c in [0] )
  while len(stack):
    (score, px,py, bx,by) = stack.popleft()
    if (bx,by) == goal: return score
    p = py*w*h + by*w+bx
    if r[py][px] == '#' or visited[p] & (1 << px): continue
    visited[p] |= (1 << px)
    stack.extend( (score+1, px+x,py+y, bx+b*x, by+b*y)
                  for (x,y,b) in ((x,y,bx==px+x and by==py+y)
                                  for (x,y) in ((-1,0), (1,0), (0,-1), (0,1))))
  return -1