spísal MišoF
Všetky programy sú v Pythone 3. Oproti verzii naozaj napísanej počas hry sú len mierne "sčitateľnené". (Výnimkou je posledný program na konci.)
Implementácia si pamätá množinu živých buniek, z tej počíta množinu živých o generáciu neskôr. (Nové živé môžu byť len medzi starými živými a ich bezprostrednými susedmi. Túto sadu buniek skontrolujeme.) Toto je efektívne: čas aj pamäť potrebná na spracovanie sady buniek sú priamo úmerné ich počtu. Nie že by to bolo treba, keďže na uhádnutie výsledku aj tak stačí prvých pár iterácií :)
def load(): body = set() try: for r in range(1000): row = input().strip() for c in range(len(row)): if row[c] == '0': body.add( (r,c) ) finally: return body def step(zive): okolie = set() for r,c in zive: for dr in [-1,0,1]: for dc in [-1,0,1]: okolie.add( (r+dr,c+dc) ) nove_zive = set() for r,c in okolie: susedov = 0 for dr in [-1,0,1]: for dc in [-1,0,1]: if (dr,dc)!=(0,0) and (r+dr,c+dc) in zive: susedov += 1 if (r,c) in zive and 2 <= susedov <= 4: nove_zive.add( (r,c) ) if (r,c) not in zive and 2 == susedov: nove_zive.add( (r,c) ) return nove_zive bunky = load() for generace in range(100): print( len(bunky) ) bunky = step(bunky)
Len za radom vypĺňame do poľa hodnoty, kým nenájdeme.
F = [0,1] while F[-1] != 0x4c6f53: F.append( (F[-1]+F[-2]) % 256**3 ) print( len(F) )
Danka sa obetovala, prehrabala Tesco letákom a našla akciový tovar. Ja som si zo zadania vykopíroval tabuľku s názvami a prioritami a do tej potom ručne dopísal ceny. Vzniklo toto:
1450 57 Magister 25%, 0,5 l
109 55 Ano Babiččina zeleninová směs, 350 g
319 54 Tesco Štrúdl, jablečný, tvarohový, 500 g
229 51 Ananas střední, 1 ks
399 50 Mikulášské figurky, více druhů, 100–130 g
... a tak ďalej
Program toto dostane na vstupe a potom vyrieši zadanú úlohu dynamickým programovaním. Postupne spracúva veci. Po spracovaní každej veci platí, že best[x] je najlepší súčet priorít, ktorý sa dá dostať, ak spomedzi už spracovaných vecí vyberieme nejakú podmnožinu ktorá stojí presne x/10 korún.
ceny, priority = [], [] try: while True: row = input().split() ceny.append( int(row[0]) ) priority.append( int(row[1]) ) except: pass best = [ 0 for c in range(2104) ] for c,p in zip(ceny,priority): for c2 in range(2103-c,-1,-1): best[c2+c] = max( best[c2+c], best[c2]+p ) print(max(best))
Na túto úlohu máme ťažké srdce, keďže celý boj s úlohou bol boj s hnusne nejednoznačným zadaním. Uteráky a utierky je podľa nás OK prať na 60ke (čo je rýchlejšie): tá 95 je len maximum a často tá 60ka ozaj stačí. Nič v zadaní nezakazuje prať uteráky a utierky spolu, detto košele a spodné prádlo. A detto so sušením, tam síce je aj fráza "sušiť je potřeba podle druhu prádla", načo sú potom ale v zadaní obrázky s inštrukciou k sušeniu? Po niekoľkých zlých pokusoch (bez ktorých by sme boli aspoň o miesto lepší) sme napísali orgom, tí nám aspoň niečo objasnili a už sa to nejak dokleplo.
Samotný program je tá najľahšia časť riešenia. Pre každú činnosť vyskúšame všetky možné poradia, v akom ju robiť. Následne každú aktivitu začneme len čo to ide: napr. žmýkať prvú vec začnem len čo sa ona doperie, a každú ďalšiu keď som dožmýkal tú predchádzajúcu a zároveň sa už doprala tá, ktorú chcem žmýkať teraz.
from itertools import permutations c_pranie = { 'R':80, 'U':80, 'K':40, 'S':40, 'T':75 } c_zmykanie = { 'S':30, 'R':60, 'U':90 } c_susenie = { 'K':110, 'S':30, 'U':30, 'R':50 } c_zehlenie = { 'K':60, 'U':50 } best = 1234567 for pranie in permutations('RUKST'): for zmykanie in permutations('SRU'): for susenie in permutations('KSUR'): for zehlenie in permutations('KU'): dopral = {} p = 0 for x in pranie: p += c_pranie[x] dopral[x] = p odpoved = dopral['T'] dozmykal = {} dozmykal['K'] = dopral['K'] p = 0 for x in zmykanie: if p < dopral[x]: p = dopral[x] p += c_zmykanie[x] dozmykal[x] = p dosusil = {} p = 0 for x in susenie: if p < dozmykal[x]: p = dozmykal[x] p += c_susenie[x] dosusil[x] = p odpoved = max( odpoved, dosusil['R'] ) odpoved = max( odpoved, dosusil['S'] ) p = 0 for x in zehlenie: if p < dosusil[x]: p = dosusil[x] p += c_zehlenie[x] odpoved = max( odpoved, p ) best = min( best, odpoved ) print(best)
WTF, prečo je vo vzorovom riešení prehľadávanie do hĺbky, keď máme podľa zadania nájsť najkratšiu cestu? Môj program prehľadáva do šírky. Lenivo ale pohodlne si pre každé políčko pamätám, aké písmenká vyzbieram optimálnou cestou naň.
from collections import deque from sys import exit pole = [ [ [ [ '' for w in range(10) ] for z in range(10) ] for y in range(10) ] for x in range(10) ] # co je na danom policku ('' pre prazdne) dist = [ [ [ [ 987654321 for w in range(10) ] for z in range(10) ] for y in range(10) ] for x in range(10) ] # ako najrychlejsie sa vieme nan dostat best = [ [ [ [ '' for w in range(10) ] for z in range(10) ] for y in range(10) ] for x in range(10) ] # ake pismenka pri tom vyzbieram for w in range(10): for z in range(10): for y in range(10): row = input() if len(row)<10: row = input() for x in range(10): if row[x]!='1': pole[x][y][z][w] = row[x] dist[0][1][1][1] = 0 Q = deque() Q.append( (0,1,1,1) ) while len(Q) > 0: x,y,z,w = Q.popleft() for dx,dy,dz,dw in [ (-1,0,0,0), (1,0,0,0), (0,-1,0,0), (0,1,0,0), (0,0,-1,0), (0,0,1,0), (0,0,0,-1), (0,0,0,1) ]: nx,ny,nz,nw = x+dx,y+dy,z+dz,w+dw inside = 0<=nx<10 and 0<=ny<10 and 0<=nz<10 and 0<=nw<10 if (x,y,z,w) != (0,1,1,1) and not inside: print(best[x][y][z][w]) exit() if not inside: continue if pole[nx][ny][nz][nw] == '0': continue if dist[nx][ny][nz][nw] <= dist[x][y][z][w]+1: continue dist[nx][ny][nz][nw] = dist[x][y][z][w] + 1 best[nx][ny][nz][nw] = best[x][y][z][w] + pole[nx][ny][nz][nw] Q.append( (nx,ny,nz,nw) )
Inak to riešenie (podľa mňa nesprávne, nemalo byť uznávané, lebo nie je najkratšie!) "nájdem nejakú cestu čo dáva zmysluplné slovo" sa dalo dosť ľahko spraviť ručne. Stačí si za minútku naformátovať zadanie do 2D mriežky mriežok, zmeniť steny na . nech nezavadzajú, a potom sa už dá ľahko riešiť "prstom po mape": hýbem sa buď o políčko, alebo o celý plánik hore/dole/vľavo/vpravo. Aj najkratšiu cestu sa takto dá nájsť ručne, len to vyžaduje trochu viac skúšania možností.
.......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... 11P11P11.. .....1.... .....1.... .....1.... ..H....... ..1..N.... ..1..1.... .......... .......... <-- tu je v 2. plániku vchod .......... .1........ .......... .......... ..O111111. .......... .......... ..1....... .......... .......... .......... .B........ .......... .......... ..1..1..1. .......... .......... ..1....... .......... .......... .......... .......... .......... .....1.... ..1..G..1. .......... .......... ..R....... .......... .......... .......... ..1....... ..1....... ..A....... ..1..1..1. ..1....... ..1....... ..1....... .......... .......... .......... .......... .......... .......... .....1..1. .......... .......... .......... .......... .......... .......... .......... .......... .......... ........H. .......... .......... .......... .......... .......... .......... .......... .......... .......... ........1. .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ..1....... .......... .......... .......... .......... .......... ..1....... .......... .......... .......... .......... .......... .......... ........1. .......... .......... .......... .......... .......... .......... .1........ .......... .......... ..1....... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .....1.... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ........1. .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ..1....... ..1....... ..1....... ..A....... ..1....... ..1....... ..1....... .......... .......... .......... .......... .......... .......... ........D. .......... .......... .......... .......... .......... .......... .X........ .......... .......... ..1....... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ......1... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ........1. .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ..1.....1. .......... .......... ..1....... ..1....... .......... .......... .......... .......... .......... ........K. .......... .......... .......... .......... .......... .......... .1........ .1........ ..1....... ..L.....O. .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ......1... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ........Y. .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ..1....... .......... .......... .......... .......... .......... .......... .......... .......... .......... ........1. .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ..1....... .......... .......... .......... .......... .......... .......... .......... .......... .......... ..1....... .......... .......... .......... .......... .......... .......... .......... .......... .......... ..1111111. .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ........1. .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ..O1...... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ......111. ......1... <-- tu je východ .......... .......... .......... .......... .......... .......... .......... .......... ........1. .......... .......... .......... .......... .......... ........1. ........1. ........1. ........1. ........1. .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ..........
Obyčajná hrubá sila. Z každého políčka ideme vo všetkých smeroch a počítame. Organizátori sú málo zákerní. Ja by som niekde v mriežke mal celý riadok rovnakých písmen, to by niektoré iné programy zblblo, lebo by si mysleli, že je tam nekonečne dlhý palindróm :)
A = [ [ [ None for z in range(100) ] for y in range(100) ] for x in range(100) ] for x in range(100): for y in range(100): row = input().split() if len(row) == 0: row = input().split() for z in range(100): A[x][y][z] = row[z] def palindrom(x,y,z,dx,dy,dz): for i in range(1,50): ax, ay, az = (x+i*dx)%100, (y+i*dy)%100, (z+i*dz)%100 bx, by, bz = (x-i*dx)%100, (y-i*dy)%100, (z-i*dz)%100 if A[ax][ay][az] != A[bx][by][bz]: return 2*i-1 return 99 odpoved = [] for x in range(100): for y in range(100): for z in range(100): a = palindrom(x,y,z,1,0,0) b = palindrom(x,y,z,0,1,0) c = palindrom(x,y,z,0,0,1) if a==1 or b==1 or c==1: continue odpoved.append( (a+b+c,A[x][y][z]) ) odpoved.sort() for x,y in odpoved: print(y,end='') print()
Bonus: to, či sa oplatí programovať, nezávisí od typu úlohy :)
Preženieme zadanie cez pdftotext (alebo len skopírujeme text vo vieweri) a pre pohodlie si ešte zmeníme všetky "medzera dvojšípka medzera" na bodkočiarky.
Ajhľa, vstup, čo riadok to linka:
Řečkovice;Filkukova;Kořískova;Hudcova;Tylova;Semilasso;Husitská;Jungmannova;Kartouzská;Šumavská;Hrnčířská;Pionýrská;Anto...
Stará osada;Kuldova;Vojenská nemocnice;Tkalcovská;Körnerova;Malinovského náměstí;Hlavní nádraží;Nové sady;Hybešova;Václa...
Stará osada;Kuldova;Vojenská nemocnice;Jugoslávská;Dětská nemocnice;Náměstí 28. října;Moravské náměstí;Česká;Grohova;Kon...
...
A potom už len načítame všetko do programu a hrubou silou prehľadávame možnosti. Pamätáme si, ktorými linkami sme už išli a akú trasu sme doteraz prešli.
from sys import stdin linky = [ x.strip().split(';') for x in stdin.readlines() ] max_trasa = [] def chod (pouzite_linky, trasa_doteraz): global max_trasa if 'Janáčkovo divadlo' in trasa_doteraz and len(trasa_doteraz) > len(max_trasa): max_trasa = trasa_doteraz[:] zastavka = trasa_doteraz[-1] for linka, trasa_linky in enumerate(linky): if linka in pouzite_linky: continue if zastavka not in trasa_linky: continue x = trasa_linky.index(zastavka) susedia = [] if x+1 < len(trasa_linky): susedia.append( trasa_linky[x+1] ) if x>0: susedia.append( trasa_linky[x-1] ) for sused in susedia: if sused in trasa_doteraz: continue chod( pouzite_linky+[linka], trasa_doteraz+[sused] ) chod( [], ['Hlavní nádraží'] ) for x in max_trasa: print(x)
Extra spešl bonus na záver: po hre napísaný program, ktorý algoritmom A* prezerá stavy editorov a naozaj (na mojom počítači do minúty) nájde riešenie úlohy P4, teda hľadanú najkratšiu postupnosť stlačení kláves. (Na rozdiel od autorského riešenia, ktoré u mňa vyžerie všetku pamäť a nič nedopočíta.)
Pri A* používam jednoduchú heuristiku: keď mám nejaký stav editora, viem si spočítať, koľko písmen mi ešte v aktuálnom texte oproti cieľu chýba a koľko ich tam mám naopak navyše. Tie prvé treba stihnúť napísať, tie druhé zmazať. Oboje sa dá robiť buď sekvenčne, alebo pomocou makra. (Príklad: ak mám v práve nahrávanom makre 3x backspace, tak tromi stlačeniami enteru viem postupne zmazať nanajvýš 3+6+12 znakov.) Takto viem pre každý stav zdola odhadnúť, aké najlepšie riešenie z neho môžem dostať, a vďaka tomu môžem (oproti prehľadávaniu do šírky) preskočiť / odložiť na neskôr spracúvanie tých stavov, ktoré sú od cieľa priďaleko.
def exponencialny_lowerbound(nahrava, pvm, ciel): # v makre mam pvm akcii, chcem ich spravit ciel, kolko najmenej krokov na to treba? spravil, so, bez = 0, 0, min( ciel, (ciel+max(1,pvm)-1)//max(1,pvm) ) if not nahrava: so, pvm = 1, 0 if pvm==0: so, pvm = so+1, 1 while spravil<ciel: so, spravil, pvm = so+1, spravil+pvm, 2*pvm return min(bez,so) class Editor: def __init__(self,vstupny_text=''): self.__dict__ = { 'text':vstupny_text, 'makro':'', 'kurzor':0, 'shift':False, 'nahrava':False } def nahraj(self,akcia): self.makro += akcia if self.nahrava else '' def __hash__(self): return hash(frozenset(self.__dict__.items())) def __eq__(self,other): return self.__dict__ == other.__dict__ def odhadni_vzdialenost(self,ciel): # zdola odhadneme, kolko este tento editor potrebuje krokov na dosiahnutie ciela # ak existuju nadbytocne pismena, treba ich dost zmazat, ak nejake chybaju, treba ich dost vyrobit chybajuce = sum( max(0, ciel.count(x) - self.text.count(x) ) for x in set(ciel) ) v_makre_pismen = sum( 1 for x in self.makro if x.isalpha() ) dopisanie_chybajucich = exponencialny_lowerbound( self.nahrava, v_makre_pismen, chybajuce ) nadbytocne = sum( max(0, self.text.count(x) - ciel.count(x) ) for x in set(self.text) ) v_makre_mazania = sum( 1 for x in self.makro if x in '39' ) zmazanie_nadbytocnych = exponencialny_lowerbound( self.nahrava, v_makre_mazania, nadbytocne ) return zmazanie_nadbytocnych + dopisanie_chybajucich def urob_akciu(editor,akcia): # zistime, ako sa zmeni dany editor, ak spravime danu akciu new_editor = Editor() new_editor.__dict__ = editor.__dict__.copy() # spracujeme stlacenie pismena if akcia.isalpha(): new_editor.text = editor.text[:editor.kurzor] + akcia + editor.text[editor.kurzor:] new_editor.kurzor += 1 new_editor.nahraj(akcia) # znak sa nahra s proper upper/lowercasom return new_editor # ak sme stlacili cokolvek ine, treba zrusit shift new_editor.shift = False # najskor spracujeme tie, ktore mozu zlyhat: 4 left, 6 right, 9 backspace, 3 delete # note: do makra sa nahraju len ak sa naozaj vykonaju if akcia in '3469': if akcia == '4' and new_editor.kurzor > 0: new_editor.kurzor -= 1 new_editor.nahraj(akcia) if akcia == '6' and new_editor.kurzor < len(new_editor.text): new_editor.kurzor += 1 new_editor.nahraj(akcia) if akcia == '9' and new_editor.kurzor > 0: new_editor.text = new_editor.text[:new_editor.kurzor-1] + new_editor.text[new_editor.kurzor:] new_editor.kurzor -= 1 new_editor.nahraj(akcia) if akcia == '3' and new_editor.kurzor < len(new_editor.text): new_editor.text = new_editor.text[:new_editor.kurzor] + new_editor.text[new_editor.kurzor+1:] new_editor.nahraj(akcia) return new_editor # teraz akcie, ktore sa nenahravaju nikdy: 2 insert, 5 enter, 8 shift if akcia in '258': if akcia == '2': new_editor.nahrava = not new_editor.nahrava if new_editor.nahrava: new_editor.makro = '' if akcia == '5': for x in editor.makro: new_editor = urob_akciu(new_editor,x) if akcia == '8': new_editor.shift = True return new_editor # ostavaju 7 home a 1 end, ktore sa nahraju vzdy if akcia == '7': new_editor.kurzor = 0 if akcia == '1': new_editor.kurzor = len(new_editor.text) new_editor.nahraj(akcia) return new_editor # main: ideme prehladavat algoritmom A* from collections import defaultdict from queue import PriorityQueue as priority_queue from sys import exit from random import random from sys import argv try: start, ciel = argv[1:3] except: start, ciel = 'lol', 'llSooSolSoSoo' akcie = [ x for x in set('123456789'+ciel) ] # piseme len tie pismena, ktore potrebujeme vo vysledku dist, prev, Q = defaultdict(lambda:1234567), {}, priority_queue() vstupny_editor = Editor(start) dist[vstupny_editor], prev[vstupny_editor] = 0, None Q.put( ( vstupny_editor.odhadni_vzdialenost(ciel), random(), vstupny_editor ) ) while True: stav = Q.get()[2] if len(dist)%1000 == 0: print(len(dist),dist[stav],stav.odhadni_vzdialenost(ciel),stav.__dict__) # jednoduchy progress report for akcia in akcie: if (not stav.shift) and akcia.isupper(): continue # nevieme pisat velke pismena ak nedrzime shift novy_stav = urob_akciu(stav,akcia) if dist[novy_stav] <= dist[stav]+1: continue dist[novy_stav], prev[novy_stav] = dist[stav]+1, (akcia,stav) if novy_stav.text == ciel: odpoved, program = dist[novy_stav], '' while prev[novy_stav] is not None: program, novy_stav = prev[novy_stav][0]+program, prev[novy_stav][1] print( 'pocet tahov: {}, program: {}'.format(odpoved,program.upper())) exit() Q.put( ( dist[novy_stav]+novy_stav.odhadni_vzdialenost(ciel), random(), novy_stav ) )