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

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

import heapq              # 11.3 Paras reitti
class BestRoute:
  def __init__(self,n):
    self.edges   = [{a: 0} for a in range(n+1)]
  def add_road(self,a,b, length):
    self.edges[a][b] = min(length, self.edges[a][b] if(b)in self.edges[a] else 9999)
    self.edges[b][a] = min(length, self.edges[b][a] if(a)in self.edges[b] else 9999)
  def find_route(self,a,b, push=heapq.heappush, pop=heapq.heappop):
    visited = set()
    s = [(0, a)]
    while len(s) and s[0][1] != b:
      (lambda cur,a:
        (visited.add(a), *(push(s, (cur+cost, c)) for (c,cost) in self.edges[a].items()))
        if not a in visited else None)(*pop(s))
    return s[0][0] if(len(s) and s[0][1] == b) else -1 # Paluuarvo -1 jos ei löydetty maalia.

import heapq              # 11.4 Välimatkat
class AllRoutes:          #      Nope, en käyttänyt tässä Bellman-Fordia.
  def __init__(self,n):
    self.edges   = [{a: 0} for a in range(n)]
  def add_road(self,a,b, length):
    self.e[a-1][b-1] = min(length, self.e[a-1][b-1] if(b-1)in self.e[a-1] else 9999)
    self.e[b-1][a-1] = min(length, self.e[b-1][a-1] if(a-1)in self.e[b-1] else 9999)
  def get_table(self):
    def find_all_routes(e, s, seen, pop=heapq.heappop, push=heapq.heappush):
      while len(s):        # Tämä käyttää Dijkstraa.
        (c,a) = pop(s)     # Sivutuotteena siitä syntyy kustannuskaavio kaikille solmuille.
        seen[a] = (c,*(push(s, (c+C,d)) for (d,C) in e[a].items()))[0] if seen[a]<0 else seen[a]
      return seen
    return [ find_all_routes(self.e, [(0,a)], [-1]*len(self.e)) for a in range(len(self.e)) ]

import heapq              # 11.5 Listahyppy
def calculate(t):
  visited = set()
  s       = [ (0,0) ]
  while len(s) and s[0][1] != len(t)-1:
    cur,a) = heapq.heappop(s)
    (visited.add(a), heapq.heappush(s, (cur+t[a], a+t[a])),
                     heapq.heappush(s, (cur+t[a], a-t[a]))
    )if a>=0 and a<len(t) and not a in visited else None
  return s[0][0] if(len(s) and s[0][1]==len(t)-1) else -1

import heapq              # 11.6 Seinän poisto
def count(r):             # Tässä tehtävässä olennaista oli oivaltaa, ettei
  visited = set()         # tietoa siitä, onko seinä jo poistettu vaiko ei,
  for s in r:             # tarvitse säilyttää, koska samaan solmuun ei ole
    if ('A' in s):        # mitään hyötyä palata missään tilanteessa.
      s = [ (0, s.index('A'), r.index(s)) ] # Nyt s[0] = (pisteet, x,y) aloituskoordinaatille
      while len(s) and r[s[0][2]][s[0][1]] != 'B':
        (score,px,py) = heapq.heappop(s)
        ([heapq.heappush(s, (score + (r[py+dy][px+dx] == '*'), px+dx,py+dy))
         for (dx,dy) in ((-1,0), (1,0), (0,-1), (0,1)) if r[py+dy][px+dx] != '#']
        if (0 if hash((px,py))in visited else visited.add(hash((px,py)))is None)else 0)
      return s[0][0] if(len(s) and r[s[0][2]][s[0][1]] == 'B') else -1

class Shortening:         # 11.7 Lyhennys.  Tehtävä oli vaikea ja malliratkaisu
  def __init__(self,n):   #                 oli vaikealukuinen, joten koodista
    self.edges  =[{} for a in range(n+1)] # on poikkeuksellisesti tehty (lähes)
    self.sources=[{} for b in range(n+1)] # esimerkillinen ja selkeä.
                                          # Algoritmi poikkeaa osin myös malliratkaisusta.
  def add_edge(self,a,b, length):
    if not (b in self.edges[a]) or (self.edges[a][b] > length):
      self.edges[a][b]   = length
      self.sources[b][a] = length

  def check(self,source,goal, big=10**9, sentinel=10**9+1):
    # First, build a list of nodes that can participate in route from source to goal.
    recursion  = lambda r,*p: r(*p, r)    # No ehkä tätä osaa lukuunottamatta ;-)
    candidates = (lambda a,b: a.intersection(b))(*(recursion((lambda e,s,seen,rec: \
     (lambda a: rec(e,s,(0 if a in seen else s.extend(e[a].keys()),seen.add(a),seen)[2],rec)
     )(s.pop()) if len(s) else seen), edges, stack, set())
                 for(edges,stack) in ((self.edges, [source]), (self.sources, [goal]))))
    # Use Bellman-Ford algorithm, but only on those nodes that can participate.
    dist  = [big] * (max(candidates)+1 if candidates else 0) + [sentinel]
    if candidates: dist[source] = 0
    for i in dist:
      done = True
      for a in candidates:
        for (b, length) in self.edges[a].items():
          if b in candidates:
            newdist = dist[a] + length
            if newdist < dist[b]:
              dist[b] = newdist
              done    = False
      # Return true if there is a negative loop in the remaining net,
      # which consists of only those nodes that participate in route
      # from source to goal.
      # The negative loop is identified by the node distances getting
      # shorter and shorter without limit (i.e. loop is never ”done”).
      # If there are negative edges, but not a negative loop,
      # the loop will only run for num(nodes)-1 times at max.
      if done or i == sentinel: return not done
      # The loop will also never terminate if candidates is empty
      # (i.e. source cannot reach goal). This is desired, because
      # False is the correct answer in that case.

import heapq              # 11.8 Veden mittaus
def count(capA,capB, goal):
  s       = [ (0,0,0) ] # Siirretty määrä; A:n sisältö, B:n sisältö
  visited = set()
  while len(s) and s[0][1] != goal:
    (lambda cur,a,b: [heapq.heappush(s, (cur+move, a + da*move, b + db*move))
        for (move,da,db) in ( # Siirrettävä määrä (vain jos > 0), siirtosuunnat A ja B:n suhteen
           (a,           -1,0),  (b,            0,-1), # Tyhjentämiset
           (capA-a,       1,0),  (capB-b,       0, 1), # Täyttämiset
           (min(capA-a,b),1,-1), (min(capB-b,a),-1,1)) # Siirtämiset
        if move > 0] \
      if (0 if hash((a,b))in visited else visited.add(hash((a,b)))is None)else 0
    )(*heapq.heappop(s)) # Käydään läpi seuraava kappale pinosta, mikäli (a,b) ei ole käyty jo.
  return s[0][0] if(len(s) and s[0][1] == goal) else -1 # Paluuarvo -1 jos ei löydetty maalia.