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

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

def create(n):              # 8.3 ABC-lista
  return ["".join("ABC"[(i // 3**j)%3] for j in range(n))[::-1] for i in range(3**n)]

def create(n):              # 8.4 ABC-erot
  return [s[::-1] for s in ["".join("ABC"[(i // 3**j)%3] for j in range(n)) for i in range(3**n)]
                  if 0==sum(s[k]==s[k+1] for k in range(len(s)-1))]

def create(s, a=""):        # 8.5 Anagrammit
  return [i for j in (create(s, a+c) for c in set(k for k in s) if a.count(c) < s.count(c))
            for i in j] if len(a) < len(s) else [a]

def check(t, i=0, total=0): # 8.6 Tasajako
  return (check(t,i+1,total+t[i]) or check(t,i+1,total-t[i])) if i<len(t) else total==0

def count(goal, min=1):     # 8.7 Numerot - OEIS A000041
  return 1 + sum(count(goal-sum, sum) for sum in range(min,goal)) if min<=goal else 0

#                             8.8 Peitteet
def count(w,h, max, lb = lambda g: (~g & - ~g).bit_length()-1):
  def search(grid, remain, at=0):                   # lb palauttaa 1-bittien määrän oikeassa reunassa.
    return sum(search((grid|mask) >> lb(grid|mask), remain-1, at+lb(grid|mask))
               for mask in ( ((1<<i)-1) * ((1<<j*w) - 1) // ((1<<w) - 1)
                 for j in range(1, h - at//w + 1)   # Kaikille ko'oille
                 for i in range(1, w - at%w  + 1))
               if not (grid & mask)) if remain>0 and at<w*h else at>=w*h
  return search(0, max)

""" Tehtävän 8 ratkaisu on hieman muokattu malliratkaisusta.
 Lisäsin siihen kuitenkin oman ratkaisuni piirteen, jossa koko taulukkoa
 esitetään yhdellä ainoalla kokonaisluvulla, jossa kukin bitti kuvastaa yhtä solua.
 Tämä oli mahdollista tehdä, koska tehtävänannossa määriteltiin, että taulukon koko
 on max. 4×4 ⇒ 16 solua; se mahtuu siis hyvin kokonaislukumuuttujaan.
 Ratkaisu on varsin tehokas, ja menee ongelmitta läpi jopa CPython3-moodissa.

 Mystisen näköinen lauseke    ((1<<i)-1) * ((1<<j*w) - 1) // ((1<<w) - 1)
 toteuttaa saman laskun kuin  sum( ((1<<i)-1) << k*w for k in range(j) ).
 Siinä muodostetaan rivin mittainen bitmask ((1<<i)-1),
 joka toistetaan jokaiselle riville k.
 Käytin Wolfram Alphaa silmukan poistamiseen."""