Skrite slike
Tokratno nalogo je -- gotovo ne zadnjič -- navdihnil Advent of Code. Gre za malo spremenjeno nalogo 8 Space Image Format.
Testi
Testi: testi-skrite-slike.zip
Ne odpiraj datotek "macka.txt" in "mleko.txt" v PyCharmu, ker jih bo pokvaril (pobrisal bo presledke na koncu vrstic). Odpreš jih lahko v kakšnem drugem programu, recimo Visual Studio Code, Sublime, Notepad... Če jih pokvariš, jih ponovno odzipaj.
Naloga
Imamo nek ASCII art, recimo tegale mačka.
|\_/|
/ @ @ \
( > o < )
`>>x<<'
/ O \
Sliko bi radi nekomu poslali, vendar jo bomo malo prikrili. Takole. Najprej jo stlačimo v eno vrstico.
|\_/| / @ @ \ ( > º < ) `>>x<<' / O \
Sliko, stlačeno v eno vrstico pošljemo večkrat, pri čemer včasih kakega dela ne povemo -- v tem primeru dotični znak nadomestimo z ?. Ko enkrat povemo določen znak, pa lahko v naslednjih pošiljanjih na isto mesto postavimo kak drug znak, vendar te, naknadne spremembe, zanemarimo.
Gornjo sliko bi torej lahko zapakirali v datoteko, ki bi bila videti tako:
11
????_?????? ????@???????????????? ?>?????? ? ???? ?? ???
?|?_??? ? O????' ??????????<????O?/??????' `???? ?<???
O?(?|?|?@ </? ??\_??????????'????º`O??????>º_????ºº?> ??
O?x?'?'?''|\/`@?`|??????>???\????\\|>?????/ @???? |?'/
O ?|/|?|`()`>> ()\???? º ??( )??`@_>??<??)'º????)`?\``<
)`@?|)|?><º>('Oº<)> ???\`<??_>< ?@)x)??<? OOx? O('?(/@`
xxº?)`O?| @``)º@xº>º (º'>??x|º\?@| )??/?> >`/O| O?|O/<
\)`\\_( )_\º<<|Ox<|>|ºº/_)º @(x' ºº`(x<)')(<_><><\>\`(>(
Prva vrstica pove širino slike, v našem primeru 11 znakov. To potrebujemo zato, da bomo znali sliko na koncu pravilno razdeliti v vrstice.
Sledi več ponovitev zakodirane slike. V našem primeru je ponovitev 8, lahko pa bi jih bilo tudi več ali manj.
V prvi ponovitvi slike povemo nam, da je peti znak _, dvanajsti je presledek, sedemnajsti je @... Ne pove pa, recimo, vsebine prvih štirih, saj so tam vprašaji.
Ali, če gledamo po znakih: da izvemo prvi znak, moramo opazovati prvi stolpec. V prvi vrstici je ?. V drugi je presledek in tako vemo, da bo prvi znak slike presledek. Sledijo neki O-ji in oklepaji, ki pa jih zanemarimo, saj zdaj že vemo, da bo tu presledek.
Drugi stolpec razodene drugi znak slike. V prvih štirih vrsticah o njem ne izvemo ničesar, v peti vrstici pa je presledek, torej vemo, da je tudi drugi znak presledek.
Tretji stolpec pove tretji znak: ta bo |. Najdemo ga v drugi vrstici, te pod njim pa ignoriramo.
Obvezna naloga
Branje datoteke
Napiši funkcijo preberi(ime_datoteke), ki prejme ime datoteke s sliko in vrne dve stvar: širino slike in zakodirano sliko, predstavljeno kot seznam seznamov. Seznamov je toliko, kolikor je vrstic in vsak vsebuje vse znake iz te vrstice.
Za gornjo datoteko mora funkcija vrniti 11 in seznam:
[['?', '?', '?', '?', '_', '?', '?', '?', '?', '?', '?', ' ', '?', '?', '?', '?', '@', '?', '?', '?', '?', '?', '?', '?', '?', '?', '?', '?', '?', '?', '?', '?', '?', ' ', '?', '>', '?', '?', '?', '?', '?', '?', ' ', '?', ' ', '?', '?', '?', '?', ' ', '?', '?', ' ', '?', '?', '?'], [' ', '?', '|', '?', '_', '?', '?', '?', ' ', '?', ' ', 'O', '?', '?', '?', '?', ''', ' ', '?', '?', '?', '?', '?', '?', '?', '?', '?', '?', '<', '?', '?', '?', '?', 'O', '?', '/', '?', '?', '?', '?', '?', '?', ''', ' ', '`', '?', '?', '?', '?', ' ', ' ', '?', '<', '?', '?', '?'], ['O', '?', '(', '?', '|', '?', '|', '?', '@', ' ', '<', '/', '?', ' ', '?', '?', '\\', '_', '?', '?', '?', '?', '?', '?', '?', '?', '?', '?', ''', '?', '?', '?', '?', 'º', '`', 'O', '?', '?', '?', '?', '?', '?', '>', 'º', '_', '?', '?', '?', '?', 'º', 'º', '?', '>', ' ', '?', '?'], ['O', '?', 'x', '?', ''', '?', ''', '?', ''', ''', '|', '\\', '/', '`', '@', '?', '`', '|', '?', '?', '?', '?', '?', '?', '>', '?', '?', '?', '\\', '?', '?', '?', '?', '\\', '\\', '|', '>', '?', '?', '?', '?', '?', '/', ' ', '@', '?', '?', '?', '?', ' ', '|', '?', ''', '/', ' ', ' '], ['O', ' ', ' ', '?', '|', '/', '|', '?', '|', '`', '(', ')', '`', '>', '>', ' ', '(', ')', '\\', '?', '?', '?', '?', ' ', 'º', ' ', '?', '?', '(', ' ', ')', '?', '?', '`', '@', '_', '>', '?', '?', '<', '?', '?', ')', ''', 'º', '?', '?', '?', '?', ')', '`', '?', '\\', '`', '`', '<'], [')', '`', '@', '?', '|', ')', '|', '?', '>', '<', 'º', '>', '(', ''', 'O', 'º', '<', ')', '>', ' ', '?', '?', '?', '\\', '`', '<', '?', '?', '_', '>', '<', ' ', '?', '@', ')', 'x', ')', '?', '?', '<', '?', ' ', 'O', 'O', 'x', '?', ' ', ' ', 'O', '(', ''', '?', '(', '/', '@', '`'], ['x', 'x', 'º', '?', ')', '`', 'O', '?', '|', ' ', '@', '`', '`', ')', 'º', '@', 'x', 'º', '>', 'º', ' ', ' ', '(', 'º', ''', '>', '?', '?', 'x', '|', 'º', '\\', '?', '@', '|', ' ', ')', '?', '?', '/', '?', '>', ' ', '>', '`', '/', 'O', '|', ' ', ' ', 'O', '?', '|', 'O', '/', '<'], ['\\', ')', '`', '\\', '\\', '_', '(', ' ', ')', '_', '\\', 'º', '<', '<', '|', 'O', 'x', '<', '|', '>', '|', 'º', 'º', '/', '_', ')', 'º', ' ', '@', '(', 'x', ''', ' ', 'º', 'º', '`', '(', 'x', '<', ')', ''', ')', '(', '<', '_', '>', '<', '>', '<', '\\', '>', '\\', '`', '(', '>', '(']]
Poleg funkcij, ki sem jih pokazal na predavanjih -- read() in readlines() -- imajo datoteke tudi funkcijo readline(), ki prebere in vrne eno samo vrstico datoteke. Morda ti bo prišla prav, ali pa ne -- kakor se boš lotil(a) reševanja.
Rešitev
Odpremo datoteko. Z datoteka.readline() preberemo prvo vrstico in jo spremenimo v int. Nato z zanko for preberemo ostale vrstice. Tem odstranimo s strip("\n") odstranimo znak za novo vrstico in jih z list spremenimo v seznam. Na koncu vrnemo širino in vrstice.
def preberi(filename):
datoteka = open(filename)
sirina = int(datoteka.readline())
vrstice = [list(x.strip("\n")) for x in datoteka]
return sirina, vrstice
Združevanje vrstic
Napiši funkcijo zdruzi(skupno, nova_vrstica), ki prejme seznam skupno, ki predstavlja sliko, skonstruirano iz prvih nekaj vrstic, in vanjo doda informacije iz nova_vrstica. Funkcija ne vrača ničesar, temveč spremeni seznam skupno.
>>> a = ['?', '?', 'x', 'o', '?']
>>> b = ['*', '?', '?', '#', '?']
>>> zdruzi(a, b)
>>> print(a)
['*', '?', 'x', 'o', '?']
Funkcija je zamenjala ? z *. Na drugem mestu ostane ?. Na tretjem pusti x, ker je ta že znan, poleg tega pa ? pomeni neznano vrednost. Na četrtem ohrani o (# pa ignorira), ker kasnejše vrstice ne morejo spreminjati že znanih podatkov.
Funkcija ne vrača ničesar in ne spreminja seznama nova_vrstica.
Rešitev
# Tole ne deluje!!!
def zdruzi(skupno, nova_vrstica):
zdruzeno = []
for doslej, novo in zip(skupno, nova_vrstica):
if doslej == "?":
zdruzeno.append(novo)
else:
zdruzeno.append(doslej)
skupno = zdruzeno
To ne deluje zaradi zadnje vrstice. Ta pove, naj se ime skupno poslej nanaša na novo ustvarjeni seznam, medtem ko seznam, ki je bil podan kot argument (in na katerega se je do te vrstice nanašalo ime skupno) ni spremenjen.
Ena možnost je, da naredimo tako:
# Tole ne deluje!!!
def zdruzi(skupno, nova_vrstica):
zdruzeno = []
for doslej, novo in zip(skupno, nova_vrstica):
if doslej == "?":
zdruzeno.append(novo)
else:
zdruzeno.append(doslej)
skupno[:] = zdruzeno
To je drugače zato, ker zadnja vrstica zamenja vse elemente seznama skupno z elementi seznama zdruzeno.
Poučnejša, krajša, lepša rešitev (za moj okus) je ta.
def zdruzi(skupno, nova_vrstica):
for i in range(len(skupno)):
if skupno[i] == "?":
skupno[i] = nova_vrstica[i]
Res pa običajno sovražim range(len(...)) zato bi raje pisal
def zdruzi(skupno, nova_vrstica):
for i, (doslej, novo) in enumerate(zip(skupno, nova_vrstica)):
if doslej == "?":
skupno[i] = novo
Pazite na zanimivo zanko. Zgoraj smo imeli for doslej, novo in zip(skupno, nova_vrstica): ker zip naredi pare, pridemo do njih z for doslej, novo in .... Če želimo še indekse, napišemo enumerate(zip(skupno, nova_vrstica)), vendar tako dobimo oštevilčene pare, zato for i, (doslej, novo) in ....
Morda lepše pa je tako:
from itertools import count
def zdruzi(skupno, nova_vrstica):
for i, doslej, novo in zip(count(), skupno, nova_vrstica):
if doslej == "?":
skupno[i] = novo
count je generator, ki šteje od 0 do ... neskončno, če je treba. Zdaj zipamo tri reči: števec count, skupno in nova_vrstica, zato jih razpakiramo v tri stvari, for i, doslej, novo in ....
Če bi se komu mudilo, pa bi napisal
def zdruzi(skupno, nova_vrstica):
skupno[:] = [novo if doslej == "?" else doslej for doslej, novo in zip(skupno, nova_vrstica)]
Sestavljanje slike
Napiši funkcijo sestavi(vrstice), ki prejme vrstice, kot jih vrača funkcija preberi in jih združi tako, da pri tem kliče funkcijo zdruzi. Funkcija seveda ne sme spreminjati podanega seznam.
Program
sirina, vrstice = preberi("maček.txt")
sestavljen = sestavi(vrstice)
mora izpisati
[' ', ' ', '|', '\\', '_', '/', '|', ' ', ' ', ' ', ' ', ' ', '/', ' ', '@', ' ', '@', ' ', '\\', ' ', ' ', ' ', '(', ' ', '>', ' ', 'º', ' ', '<', ' ', ')', ' ', ' ', ' ', '`', '>', '>', 'x', '<', '<', ''', ' ', ' ', ' ', ' ', '/', ' ', ' ', 'O', ' ', ' ', '\\', ' ', ' ', ' ', ' ']
To je že praktično isto kot mačka, stisnjena v eno vrstico,
|\_/| / @ @ \ ( > º < )>>x<<' / O \ `, le da imamo namesto niza seznam znakov.
Rešitev
Tule moramo le razumeti, kako klicati funkcijo zdruzi. Ker ne vrača rezultatov, jo kličemo z vrstico, ki jo želimo spreminjati. Najpreprosteje bo, če za začetek sestavimo vrstico, ki vsebuje same vprašaje.
def sestavi(vrstice):
skupno = ["?"] * len(vrstice[0])
for nivo in vrstice:
zdruzi(skupno, nivo)
return skupno
Shranjevanje slike
Napiši funkcijo shrani_sliko(slika, sirina, ime_datoteke), ki v datoteko s podanim imenom shrani podano sliko. Slika je v takšni obliki, kot jo vrača prejšnja funkcija.
Klic
shrani_sliko(" |\_/| / @ @ \ ( > º < ) `>>x<<' / O \ ",
11, "macka.txt")
v datoteko macka.txt zapiše
|\_/|
/ @ @ \
( > º < )
`>>x<<'
/ O \
Rešitev
Prva vrstica se začne pri indeksu 0, druga pri sirina, tretja pri 2 * sirina, in tako naprej dokler ne pridemo do len(slika). Torej bomo začetne indekse dobili z zanko for i in range(0, len(slika), sirina).
Posamično vrstico potem dobimo z slika[i:i+sirina]. To slepimo skupaj z "".join(slika[i:i+sirina]. K temu dodamo \n in zapisujemo v datoteko.
def shrani_sliko(slika, sirina, filename):
f = open(filename, "wt")
for i in range(0, len(slika), sirina):
f.write("".join(slika[i:i+sirina]) + "\n")
Dekodiranje
Napiši funkcijo dekodiraj(kodirana_slika, dekodirana_slika), ki prejme ime datoteke s kodirano sliko (na primer "macka.txt") in v datoteko z imenom dekodirana_slika shrani dekodirano sliko.
Funkcija bo imela kvečjemu tri vrstice, saj bo le poklicala tri izmed gornjih funkcij.
Nato odpri datoteko zival.txt. :) Lahko v PyCharmu.
Rešitev
Tule pa le pokličemo tri funkcije, ki smo jih že napisali.
def dekodiraj(kodirana_slika, dekodirana_slika):
sirina, kodirana = preberi(kodirana_slika)
slika = sestavi(kodirana)
shrani_sliko(slika, sirina, dekodirana_slika)
Dodatna naloga
V teh datotekah je veliko vprašajev, zato jih bomo stisnili s posebnim algoritmom: vedno, kadar vidimo zaporedje vprašajev, ga zamenjamo z vprašajem in številom vprašajev.
Napiši funkcijo stisni(niz). Funkcija kot argument dobi nek niz in kot rezultat vrne stisnjen niz.
>>> stisni("Trije vprašaji, ???, in še trinajst, ?????????????, skupaj jih je 16, mar ne?")
'Trije vprašaji, ?3, in še trinajst, ?13, skupaj jih je 16, mar ne?1'
Prvo zaporedje treh vprašajev je funkcija stisni zamenjala z ?3, drugo zaporedje vsebuje 13 vprašajev, zato ga zamenja z ?13, tretjič pa se pojavi le en vprašaj, zato za zamenja z `?1.
Napiši tudi funkcijo razsiri(niz), ki prejme tako stisnjen niz in vrne razširjenega.
>>> razsiri("Trije vprašaji, ?3, in še trinajst, ?13, skupaj jih je 16, mar ne?1")
Trije vprašaji, ???, in še trinajst, ?????????????, skupaj jih je 16, mar ne?
Rešitev
Ko naletimo na vprašaj, štejemo, koliko vprašajev še sledi. Ko je konec vprašajev, napišemo vprašaj in dodamo številko. Ostale znake pa le prepisujemo.
Če se niz konča z vprašajem, teh ne smemo pozabiti dodati. Za to poskrbi if na koncu.
def stisni(niz):
stisnjen = ""
zaporednih = 0
for c in niz:
if c == "?":
zaporednih += 1
else:
if zaporednih:
stisnjen += "?" + str(zaporednih)
zaporednih = 0
stisnjen += c
if zaporednih:
stisnjen += "?" + str(zaporednih)
return stisnjen
Razširjanje je podobno: ko naletimo na vprašaj, začnemo zlagati števke v niz. Ko je konec števk, dodamo toliko vprašajev, kot je potrebno.
def razsiri(stisnjeno):
razsirjen = ""
vprasajev = None
for c in stisnjeno:
if c == "?":
vprasajev = ""
elif vprasajev is not None:
if c in "0123456789":
vprasajev += c
else:
razsirjen += "?" * int(vprasajev) + c
vprasajev = None
else:
razsirjen += c
if vprasajev is not None:
razsirjen += "?" * int(vprasajev)
return razsirjen