Advertisement
Bisqwit

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

Nov 14th, 2021 (edited)
303
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.11 KB | None | 0 0
  1. """ Joelin ratkaisut Helsingin yliopiston Tietorakenteet ja algoritmit-kurssin
  2.    viikon 8 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. def create(n):              # 8.3 ABC-lista
  18.   return ["".join("ABC"[(i // 3**j)%3] for j in range(n))[::-1] for i in range(3**n)]
  19.  
  20. def create(n):              # 8.4 ABC-erot
  21.   return [s[::-1] for s in ["".join("ABC"[(i // 3**j)%3] for j in range(n)) for i in range(3**n)]
  22.                   if 0==sum(s[k]==s[k+1] for k in range(len(s)-1))]
  23.  
  24. def create(s, a=""):        # 8.5 Anagrammit
  25.   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))
  26.             for i in j] if len(a) < len(s) else [a]
  27.  
  28. def check(t, i=0, total=0): # 8.6 Tasajako
  29.   return (check(t,i+1,total+t[i]) or check(t,i+1,total-t[i])) if i<len(t) else total==0
  30.  
  31. def count(goal, min=1):     # 8.7 Numerot - OEIS A000041
  32.   return 1 + sum(count(goal-sum, sum) for sum in range(min,goal)) if min<=goal else 0
  33.  
  34. #                             8.8 Peitteet
  35. def count(w,h, max, lb = lambda g: (~g & - ~g).bit_length()-1):
  36.   def search(grid, remain, at=0):                   # lb palauttaa 1-bittien määrän oikeassa reunassa.
  37.     return sum(search((grid|mask) >> lb(grid|mask), remain-1, at+lb(grid|mask))
  38.                for mask in ( ((1<<i)-1) * ((1<<j*w) - 1) // ((1<<w) - 1)
  39.                  for j in range(1, h - at//w + 1)   # Kaikille ko'oille
  40.                  for i in range(1, w - at%w  + 1))
  41.                if not (grid & mask)) if remain>0 and at<w*h else at>=w*h
  42.   return search(0, max)
  43.  
  44. """ Tehtävän 8 ratkaisu on hieman muokattu malliratkaisusta.
  45. Lisäsin siihen kuitenkin oman ratkaisuni piirteen, jossa koko taulukkoa
  46. esitetään yhdellä ainoalla kokonaisluvulla, jossa kukin bitti kuvastaa yhtä solua.
  47. Tämä oli mahdollista tehdä, koska tehtävänannossa määriteltiin, että taulukon koko
  48. on max. 4×4 ⇒ 16 solua; se mahtuu siis hyvin kokonaislukumuuttujaan.
  49. Ratkaisu on varsin tehokas, ja menee ongelmitta läpi jopa CPython3-moodissa.
  50.  
  51. Mystisen näköinen lauseke    ((1<<i)-1) * ((1<<j*w) - 1) // ((1<<w) - 1)
  52. toteuttaa saman laskun kuin  sum( ((1<<i)-1) << k*w for k in range(j) ).
  53. Siinä muodostetaan rivin mittainen bitmask ((1<<i)-1),
  54. joka toistetaan jokaiselle riville k.
  55. Käytin Wolfram Alphaa silmukan poistamiseen."""
  56.  
  57.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement