Sestavljanka

V tej nalogi bomo sestavljali sestavljanke. Takšne.

                                     /;    ;\
                                   __  \\____//
                                  /{_\_/   `'\____
                                  \___   (o)  (o  }
       _____________________________/          :--'
   ,-,'`@@@@@@@@       @@@@@@         \_    `__\
  ;:(  @@@@@@@@@        @@@             \___(o'o)
  :: )  @@@@          @@@@@@        ,'@@(  `===='
  :: : @@@@@:          @@@@         `@@@:
  :: \  @@@@@:       @@@@@@@)    (  '@@@'
  ;; /\      /`,    @@@@@@@@@\   :@@@@@)
  ::/  )    {_----------------:  :~`,~~;
 ;;'`; :   )                  :  / `; ;
;;;; : :   ;                  :  ;  ; :
`'`' / :  :                   :  :  : :
    )_ \__;      ";"          :_ ;  \_\       `,','
    :__\  \    * `,'*         \  \  :  \   *  8`;'*  *
        `^'     \ :/           `^'  `-^-'   \v/ :  \/

(Inspiracija prihaja iz Advent of Code, naloga Jurassic Jigsaw, vendar je narejena na novo.)

Kako so videti posamezni koščki, si lahko pogledate v priloženih datotekah. V programu jih bomo zapisovali s terkami nizov. Košček

Qm55
7 _H
2o\R
H3cc

torej zapišemo kot ("Qm55", "7 _H", "2o\R", "H3cc").

Iz teh koščkov se da sestaviti sestavljanko, s tem da je potrebno koščke vrteti in celo zrcaliti. Ko jo sestavimo, bo potrebno še odbiti robove, ki niso del slike - od gornjega koščka bo ostal samo srednji kvadrat 2x2:

 _
o\

A do tam pridemo šele pri oceni 10; šli pa bomo lepo počasi.

  1. Pretvarjanje v terko: če imamo seznam s in potrebujemo terko s, uporabimo tuple(s). Toliko, da me ne boste spraševali vsak posebej. :)

  2. Vzvratne poševnice: V spodnjih izpisih so vzvratne poševnice zaradi preglednosti napisane z enim samim znakom. V testih sta po dve, ker, vemo, napišeš dve in dobiš eno.

  3. Oblika sestavljank: vsi koščki so kvadratni. Same sestavljanke pa so pravokotne, ne pa nujno kvadratne. Gornja krava je bolj dolga kot visoka.

  4. Naloga ni tako težka, zato ker jo bomo reševali po korakih in vse lepo sproti testirali. Držite se navodil in ko programirate določeno funkcijo, razmišljajte o tem, zakaj sem vam dal sprogramirati tiste prej. Ne uporabljajte pa jih vedno in na silo.

Za oceno 6

  • Napiši funkcijo zrcaljen_vod(kos), ki prejme košček in vrne vodoravno prezrcaljen košček. Za gornji košček vrne

    ("55mQ",
     "H_ 7",
     "R\o2",
     "cc3H")
    
  • Napiši funkcijo zrcaljen_navp(kos), ki vrne navpično prezrcaljen košček. Za košček iz uvoda v nalogo vrne

    ("H3cc",
     "2o\R",
     "7 _H",
     "Qm55")
    
  • Napiši funkcijo obrnjen(kos), ki vrne košček, obrnjen za 90 stopinj v smeri urinega kazalca. Za košček iz uvoda v nalogo vrne

    ('H27Q', '3o m', 'c\_5', 'cRH5')

    V gornji vrstici se pojavi, kar je bil prej levi rob. Gornja vrstica je postala desni rob...

  • Napiši funkcijo obrnjen_n(kos, n), ki vrne košček, ki je n-krat obrnjen za 90 stopinj v smeri urinega kazalca. Košček in število obratov sta lahko tudi precej velika.

  • Napiši funkcijo stranice(kos), ki vrne seznam s stranicami kosa v naslednjem vrstnem redu: gornja, desna, spodnja (od leve proti desni!), leva (od zgoraj navzdol) in nato še zrcaljena gornja, desna, spodnja in leva. Pozorno poglej tale primer: za košček iz primera,

    Qm55
    7 _H
    2o\R
    H3cc
    

    mora vrniti ['Qm55', '5HRc', 'H3cc', 'Q72H', '55mQ', 'cRH5', 'cc3H', 'H27Q'].

  • Napiši funkcijo obrati(kos), ki vrne množico vseh koščkov, ki jih je mogoče dobiti z obračanjem in zrcaljenjem podanega koščka. Za gornji košček vrne

    {('55mQ', 'H_ 7', 'R\o2', 'cc3H'),
     ('5HRc', '5_\c', 'm o3', 'Q72H'),
     ('H27Q', '3o m', 'c\_5', 'cRH5'),
     ('H3cc', '2o\R', '7 _H', 'Qm55'),
     ('Q72H', 'm o3', '5_\c', '5HRc'),
     ('Qm55', '7 _H', '2o\R', 'H3cc'),
     ('cRH5', 'c\_5', '3o m', 'H27Q'),
     ('cc3H', 'R\o2', 'H_ 7', '55mQ')}
    

Za oceno 7

  • Napiši funkcijo preberi_datoteko(ime_datoteke), ki prebere koščke iz podane datoteke. Vrniti mora seznam koščkov, torej seznam terk nizov, na primer

    [('bmq8', 'b__8', 'O__s', 'fyuX'),
     ('Qm55', '7 _H', '2o\R', 'H3cc'),
     ('cj97', 'c  7', 'x \m', 'KZ9K'),
     ... in tako naprej
    
  • Napiši funkcijo zbirka_stranic(kosi), ki prejme seznam koščkov (tak, kot ga vrača gornja funkcija). Vrniti mora slovar, katerega ključi so vse možne stranice (vključno s prezrcaljenimi), pripadajoče vrednosti pa so množice koščkov, ki vsebujejo takšno stranico.

    {'bmq8': {('bmq8', 'b__8', 'O__s', 'fyuX'),
              ('8J99', 'q_ k', 'm_ 2', 'bUee')},
     '88sX': {('XH00', 's)_P', '8  H', '8v2H'),
              ('bmq8', 'b__8', 'O__s', 'fyuX')},
     'fyuX': {('bmq8', 'b__8', 'O__s', 'fyuX')},
     'bbOf': {('o855', 'A__Y', 'X__j', 'fObb'),
              ('bmq8', 'b__8', 'O__s', 'fyuX')},
     ... in tako naprej
    

    Stranica "bmq8" je zgornja stranica koščka v prvi vrstici in zrcaljena leva stranica koščka v drugi vrstici (od leve proti desni preberemo prve črke nizov v drugi terki).

    V množicah naj se koščki pojavljajo v svojih originalnih legah - takšnih, ko so v podanem seznamu - in ne obrnjeni ali zrcaljeni.

    Vsak košček se pojavi v osmih različnih množicah - toliko, kolikor različnih stranih ima (skupaj z zrcaljenimi).

    (Tale opis je dolg, sama funkcija pa ima pet vrstic, brez kakšnih fint z izpeljanim čemerkoli.)

    Opazil(a) boš nekaj prijetnega: vsaka množica vsebuje le en ali dva koščka. Kaj to pomeni, razmisli sam(a). Še preden greš naprej.

Za oceno 8

Po razmisleku o gornjem napiši naslednje funkcije.

  • Funkcija kotni(kosi) prejme vse kose sestavljanke (kot jih vrne preberi_datoteko) in vrne množico kosov, ki so v vogalih. Kosi naj ne bodo obrnjeni ali zavrteni, temveč takšni, kot so v seznamu kosi.

    Če nimaš pojma, kako to napisati, ponovno preveri zadnji odstavek zadnje funkcija naloge za oceno 7.

  • Funkcija robni(kosi) vrne množico kosov, ki so na robovih sestavljanke (vendar ne v kotih). Če nimaš pojma, kako to napisati, potem ne vem, kako ti je uspelo napisati prejšnjo funkcijo. :)

  • Funkcija prvi_kot(kosi) vrne tisti, kot, pri katerem je prva vrstica prva po abecedi. Uporabljaj Pythonovo urejenost (števke pred črkami, velike črke pred malimi; z drugimi besedami, samo uporabljaj Pythonove funkcije in vse bo dobro).

(Funkcij, ki jih pišeš tu, morda ne potrebuješ, so pa uporabne, če želiš kaj izvedeti o sestavljanki. In za dodatno nalogo onstran one za oceno 10.)

Za oceno 9

  • Funkcija preobrni(kos, levo, gor, po_stranicah) prejme kos sestavljanke, podatek o tem, kaj mora biti levo in zgoraj, ter slovar po_stranicah, ki je takšen, kot ga vrača funkcija zbirka_stranic. Vrniti mora kos, ki ga dobi z vrtenjem in/ali zrcaljenjem podanega kosa tako, da le-ta ustreza pogojema levo in gor.

    Argumenta levo in gor povesta, kakšna morata biti leva in zgornja stranica vrnjenega kosa. Če je argument enak 1, to pomeni, da mora biti leva oz gor-nja stranica robna stranica. Če je argument niz, pa pove, kakšna mora biti stranica.

    Klic

    preobrni(("Qm55",
              "7 _H",
              "2o\R",
              "H3cc"), "cc3H", 1, po_stranicah)
    

    vrne

    ('cRH5', 'c\_5', '3o m', 'H27Q')

    To je namreč tista oblika tega koščka, pri katerem je leva stranica enaka "cc3H" (argument leva), zgornja, "cRH5" pa se v po_stranicah pojavi le enkrat (argument gor).

    Funkcija sme predpostaviti, da je košček možno obrniti v zahtevano lego na natančno en način. Če razmisliš, to pomeni tudi, da je vsaj eden od argumentov vedno niz.

  • Funkcija vzemi_kos(levo, gor, po_stranicah, uporabljeni) prejme pogoja levo in gor, ki imata enak pomen kot pri prejšnji funkciji (in je vsaj eden od njiju niz); slovar po_stranicah, ki je prav tako enak onemu iz prejšnje funkcije; ter množico uporabljeni, ki vsebuje koščke, ki so že uporabljeni.

    Tako kot slovar po_stranicah, naj/bo tudi uporabljeni vsebuje koščke v njihovih originalnih legah.

    Funkcija vzemi_kos mora:

    • vrniti košček, ki ustreza pogojema in še ni bil uporabljen; košček mora biti obrnjen/zrcaljen tako, da sta levo in zgoraj stranici, ki ju predpisujeta argumenta.
    • poleg tega mora ta košček dodati v množico uporabljeni. (Footnote: to je grdo, ker funkcija vrača rezultat in hkrati nekaj spreminja. Vendar: če v Pythonu napišete import this, se med drugim izpiše tudi "practicality beats purity")

    Ker je vaš profesor kljub temu, da vam daje takšne domače naloge, nekje globoko v srcu vseeno za silo prijazen človek, so stvari so organizirane tako, da bo v vsakem trenutku obstajal natančno en košček, ki bo ustrezal pogojem. (Tako je bilo tudi v nalogi v Advent of Code.)

Za oceno 10

  • Napiši funkcijo sestavi_koscke(kosi, kos), ki dobi kose, kot jih vrne preberi_datoteko in za pomoč še kos, ki ga je potrebno postaviti v gornji levi kot. Ta košček je tudi pravilno obrnjen (glede na želeni končni izgled sestavljanke.)

    Ta funkcija mora v bistvu sestaviti sestavljanko.

    Vrniti mora seznam seznamov koščkov (vsak košček pa je terka nizov, torej funkcija vrača seznam seznamov terk nizov). Vsak seznam znotraj tega seznama predstavlja vrstico sestavljanke. Slika muca je sestavljena iz dveh vrstic in osmih stolpcev, torej mora funkcija vrniti seznam, ki vsebuje dva seznama s po osmimi seznami terk, takole:

    [
        [('wJMY', 'w  Y', '2  T', 'Fnyq'), ('YTPO', 'Y  O', 'T  v', 'q625'),
         ('OVfe', 'O  e', 'v__U', '5Yjb'), ('e2k9', 'e  9', 'U__J', 'bmq8'),
         ('9J6c', '9 /c', 'J/ 3', '8v2H'), ('cRH5', 'c\_5', '3o m', 'H27Q'),
         ('5kC7', '5/\7', 'mo m', 'QRbK'), ('79jc', '7  c', 'm\ x', 'K9ZK')],
        [('Fnyq', 'F  q', '8 (z', '4MJn'), ('q625', 'q/~5', 'z__8', 'nc1o'),
         ('5Yjb', '5__b', '8__O', 'oAXf'), ('bmq8', 'b__8', 'O__s', 'fyuX'),
         ('8v2H', '8  H', 's)_P', 'XH00'), ('H27Q', 'H=øQ', 'P_mh', '0Ew4'),
         ('QRbK', 'Q= K', 'h_mO', '41K4'), ('K9ZK', 'K/ K', 'O) a', '40YO')]
    ]
    

    Prvi košček v prvem seznamu je podani kotni košček (v podani legi). Ostali se z njim ujemajo (torej so po potrebi obrnjeni drugače kot v podatkih).

    Če pozorno pogledamo, vidimo, da je desna stranica prvega koščka YYTq, in prav taka je leva stranica drugega. Prvi košček prve vrstice se konča z FNyq in z istim robom se začne prvi košček druge vrstice. In tako povsod drugje.

    Funkcijo je najlažje napisati tako, da postavimo podani prvi košček in nato dokončamo prvo vrstico, tako da izbiramo ustrezne koščke za nadaljevanje. (Kako dolga je vrstica, vidimo sproti.) Pod prvo vrstico sestavimo drugo vrstico. Pod drugo dodamo tretjo. In tako naprej.

    Če kaj pomaga (ni pa nujno potrebno): ko zaključimo prvo vrstico, vemo tudi, koliko vrstic bo.

  • Napiši funkcijo slika(kosi), ki prejme kose, kot jih vrne prejšnja funkcija, in vrne niz s sliko: od vsakega koščka mora odstraniti rob, kar ostane, pa lepo zložiti. Med vrsticami niza so \n.

    print(slika(kosi)), kjer so kosi gornji seznam, bi izpisal

           /\_/\
      ____/ o o \
    /~____  =ø= /
    (______)__m_m)
    
  • Napiši funkcijo sestavljanka(kosi, kot), ki prejme enake argumente kot sestavi_koscke in vrne enak rezultat kot slika.

Za dodatno zabavo

  • Spremeni funkcijo sestavi_koscke tako, da bo lahko argument kos, ki pove gornji levi kot, tudi None. To ustreza situaciji, ko preberemo datoteko in pravzaprav ne vemo, kateri košček bo levo zgoraj. Funkcija naj v tem primeru vzame enega od kotnih kosov (lahko kar prvi_kot) in ga ustrezno zasuka.

    Dobljena sestavljanka bo sicer morda obrnjena in prezrcaljena. Vseeno pa je pomembno, da prvi kot pravilno zasukaš: če predpostavimo, da gre za gornji levi kot, mora biti košček obrnjen tako, da sta zgornja in leva stranica robni.

    Tega v resnici sploh ni težko sprogramirati, samo testov se mi ne piše in naloga je že dovolj dolga. :)

  • Napiši program, ki prejme datoteko z ASCII artom in sestavi sestavljanko. Se pravi to, kar sem moral jaz početi s temi kravami in mačkami. :)

Testi

Vse datoteke morajo biti v istem direktoriju kot vaš program.