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

""" Joelin ratkaisut Helsingin yliopiston Tietorakenteet ja algoritmit-kurssin
    viikon 12 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 Cycles:             # 12.3 Syklit
  def __init__(self,n):   self.edges = [set() for a in range(n)]
  def add_edge(self,a,b): self.edges[a-1].add(b-1)
  def check(self):
    stack = set()         # Paluuarvo on tosi, jos jokin läpikäyntijärjestys tuottaa reitin, jossa
    def gruu1(a): return (stack.add(a), gruu(a), stack.remove(a))[1]    # palataan jo aiemmin läpi
    def gruu(a):  return any(b in stack or gruu1(b) for b in self.edges[a])      # käytyyn soluun.
    return any(gruu1(a) for a in range(len(self.edges)))


class CoursePlan:         # 12.4 Kurssit
  def __init__(self):            self.names, self.edges = [], [set() for _ in range(50)]
  def add_course(self,course):   self.names.append(course)
  def add_requisite(self,c1,c2): self.edges[ self.names.index(c1) ].add( self.names.index(c2) )
  def find(self):
    colors,l = [0] * len(self.names), []
    def explore(start):      # Ratkaisu käyttää topologista järjestystä (topological sort)
      if colors[start] != 2: # sellaisenaan kirjan mallin pohjalta.
        colors[start] = 1
        if any(colors[e] == 1 or not explore(e) for e in self.edges[start]): return False
        l.insert(0, self.names[start])
        colors[start] = 2
      return True
    return l if all(colors[s] != 0 or explore(s) for s in range(len(colors))) else None


class LongPath:           # 12.5 Pisin polku
  def __init__(self,n):   self.edges = [set() for m in range(n+1)]
  def add_edge(self,a,b): self.edges[min(a,b)].add(max(a,b))
  def calculate(self):
    length = [0] * len(self.edges)
    for i in range(len(self.edges)-1,-1,-1):
      length[i] = max(0,0, *(length[m]+1 for m in self.edges[i]))
    return max(length)

class LongPath_bitmath:   # 12.5 Pisin polku, vaihtoehtoinen
  def __init__(self,n):   self.edges = [0] * (n+1)
  def add_edge(self,a,b): self.edges[min(a,b)] |= (1 << max(a,b))
  def calculate(self):
    length = [0] * len(self.edges)
    for i in range(len(self.edges)-1,-1,-1):
      length[i] = max(0,0, *(length[m]+1 for m in bits(self.edges[i])))
    return max(length)


import functools,operator # 12.6 Lentokentät
class Airports:
  def __init__(self,n):   self.edges = [(1<<m) for m in range(n)]
  def add_link(self,a,b): self.edges[a-1] |= (1 << (b-1))
  def check(self):
    map = self.edges.copy()
    for b in range(len(self.edges)):
      for a in range(len(self.edges)):
        map[a] |= functools.reduce(operator.__or__, (map[m] for m in bits(self.edges[a])), 0)
    return min(map) == (1 << len(map))-1


class GraphGame:          # 12.7 Verkkopeli
  def __init__(self,n):   self.edges = [set() for m in range(n)]
  def add_link(self,a,b): self.edges[a-1].add(b-1)
  def winning(self, x):
    e = self.edges
    (win,lose) = [ False ] * len(e), [ len(e[a])==0 for a in range(len(e)) ]
    for n in range(len(e)):
      for a in range(len(e)):
        win[a] |= any(lose[b] for b in e[a])
        lose[a] |= all(win[b] for b in e[a])
    return win[x-1]


import heapq              # 12.8 Polut
# Koska 12.8 malliratkaisu oli huomattavan lyhyt, mutta ei suinkaan optimaalinen,
# päätin tehdä tästä ratkaisusta sellaisen, joka minimoi kaarien määrän.
#
def create(N, best={}):
  def execute(hist, s=1, e=100, edges=[]):
    for n,code in hist:
      if code:
        z = s+n if code>0 else e
        edges.append( (s,   z))
        edges.extend( (s, s+m) for m in range(1,n) )
        edges.extend( (s+m, z) for m in range(1,n) )
        s = z
      else:
        edges.append((s,e))
        while n > 1:
          edges.append((s, s+1))
          edges.append((s+1, e))
          s += 1
          n -= 1
    return edges
  # Use dijkstra to figure out the best way to plan the route
  # At each point, create one of these alternatives::
  #
  # Triangle of 3 paths:    Diamond of 3 paths:    Straight of 3 paths:
  # ──┬─────z──             ──┬─b─z──              ──┬─────────end
  #   ├──b──┤                 ├─c─┤                  ╰─b───────┤
  #   ╰──c──╯                 ╰─d─╯                    ╰─c─────╯
  #                                                      ╰──
  #  = 2M-1 edges           = 2M edges             = 2M-1 edges
  #
  # Note that a straight(N) followed by a triangle(M) is invalid *at the end* (z=end),
  # because it would generate two parallel arcs to end.
  # This can be easily taken care by never doing triangles or diamonds with M=remaining n.
  # A valid alternative would be to generate straight(N) followed by a diamond(M),
  # but there is no advantage in that approach in terms of arc count.
  # In testing, it was determined for M values that
  # within 1 <= N <= 1200000,
  #   M=2 occurs 99,99% of times
  #   M=3 occurs 92,44% of times
  #   M=5 occurs 9.404% of times
  #   M=7 occurs 0.0952% of times (1142 times)
  # Other values of M (tested up to 19) were not observed, so the search is capped to that.
  #
  # The smallest value of N where the network of 1—100 is too small
  # that I found was 2251799813682908. The number of arcs was still
  # only 170, nowhere close to the task limit of 1000.
  #
  # Element: Number of edges, remaining n, [plan]
  # Plan elements are:
  #    N straight lines to end:       (n,0)
  #    Triangle of M:                 (n,3)
  #    Diamond of M:                  (n,4) -- unused
  #    Triangle of M straight to end: (n,-3) -- unused
  #    Diamond of M straight to end:  (n,-4) -- unused
  s = []
  best={}
  #s.extend( (best[k][0], k, best[k][1]) for k in best.keys() if (k <= N and k >= N-40))
  if len(s)<16: s.append( (0, 0, []) )
  heapq.heapify(s)
  def add(cost, done, newhist):
    if done in best and best[done][0] <= cost: return
    if newhist[-1][1]: best[done] = (cost, newhist)
    heapq.heappush(s, (cost, done, newhist))
  while len(s):
    (cost,done,hist) = heapq.heappop(s)
    if done==N:
      print("For %d best path (cost=%d): " % (N,cost), hist)
      return execute(hist)
    for m in (a for a in range(2,min(8,N-done)) if a!=4 and a!=6): # Try primes < 8 & < n
      r = (N-done) % m
      if r == 0: add(cost +           1+(m-1)*2, N - (N-done  )//m, hist + [       (m,3)])
      else:      add(cost + (r*2-1) + 1+(m-1)*2, N - (N-done-r)//m, hist + [(r,0), (m,3)])
    if (N-done) < 4: add(cost + ((N-done)*2-1), N, hist + [((N-done),0)])
  return None



Tehtävässä 12.6 (ja 12.5 vaihtoehtoinen) käytetyt apufunktiot ovat:

def log2(n): return sum(((n&(0xFFFFFFFFFFFFFFFF//((1<<(1<<i))+1)<<(1<<i)))!=0)<<i for i in range(6))
def bits(e): # Returns the list of bit indexes set in e
  result = []
  while e:
    b = e & -e # Clears all but LSB
    e = e & ~b
    result.append( log2(b) )
  return result

Huom. log2-funktio toimii vain kahden potensseille.