V prvem delu igramo vojno s kartami, pri čemer ima vsaka karta drugačno številko.
V drugem delu igra postane rekurzivna: zmagovalne karte ne določimo glede na njuni števili temveč glede na to, kdo zmaga rekurzivno igro. Če ima en igralec številko 7 in drugi 5, bo prvi vzel naslednjih 7 kart in drugi naslednjih 5. Z njima bosta odigrala igro vojne in karti 7 in 5 dobi tisti igralec, ki zmaga v tej igri. Pri tem igrata s "kopijama kupčkov" - po igri za 5 in 7 ostane tistih naslednjih 7 in 5 kart normalno v igri. Če kateri od igralec nima dovolj kart za rekurzivno igro (v gornjem primeru, če prvi nima vsaj 7 in drugi vsaj 5 preostalih kart), se karti 7 in 5 primerjata kot v običajni igri (zmaga tisti, ki ima karto z višjo številko).
Da se igra ne bi zaciklala, je potrebno paziti, ali se je točno enaka situacija že kdaj pojavila. V tem primeru takoj zmaga igralec 1. Enakost situacij primerjamo le znotraj posamične igre oz. podigre itd. Igralec 1 zmaga le "rekurzivno" igro in ne vsega skupaj.
Naloga ima kup zoprnih detajlov; če se zataknemo obnje, se splača pogledati primere v izvirnem opisu naloge.
Podatki so v datoteki takšne oblike.
Player 1:
9
2
6
3
1
Player 2:
5
8
4
7
10
Razdelimo glede na "\n\n"
in poberemo oba dela v
p1
in p2
. Vsakega razkosamo po `splitline
= open("input.txt").read().split("\n\n")
p1, p2 = ([int(x) for x in p.splitlines()[1:]] for p in (p1, p2)) c1, c2
Tole smo imeli enkrat celo za domačo nalogo pri Programiranju 1, tako
preprosto je. Dokler imata oba igralca kaj kart, poberemo prvi karti iz
obeh kupčkov (pop(0)
) in ju dodamo na konec zmagovalčevega
kupčka v vrstnem redu, ki ga predpisuje naloga.
while c1 and c2:
= c1.pop(0), c2.pop(0)
a1, a2 if a2 > a1:
+= [a2, a1]
c2 else:
+= [a1, a2] c1
Tu se na vso moč spodobi povedati: pop(0)
je počasen,
ker mora vse elemente seznama prestaviti za eno mesto nazaj. Podatkovni
strukturi, pri kateri je učinkovito tako dodajanje kot pobiranje, tako
na koncu kot na začetku, pravimo double ended queue ali
deque (izgovori: "dek"). Z njim bi vojno izvedli tako.
from collections import deque
= (deque(int(x) for x in p.splitlines()[1:]) for p in (p1, p2))
c1, c2
while c1 and c2:
= c1.popleft(), c2.popleft()
a1, a2 if a2 > a1:
c2.extend([a2, a1])else:
c1.extend([a1, a2])
Glede na našo velikost problema to niti ni pomembno, predvsem pa z deque ne moremo udobno delati v drugem delu naloge.
Naloga zahteva, da pomnožimo številko na zadnji zmagovalčevi karti z 1, številko na predzadnji z 2 in tako naprej ter izračunamo vsoto.
Tu nima smisla gledati, kdo je zmagovalec: enostavno zložimo vse
karte skupaj, c1 + c2
. Eden od teh dveh kupčkov je prazen,
drugi zmagovalčev. To obrnemo (reversed(c1 + c2)
), in
oštevilčimo od 1 naprej
enumerate(reversed(c1 + c2), start=1)
. Čez to spustimo
zanko, množimo in seštevamo.
print(sum(i * x for i, x in enumerate(reversed(c1 + c2), start=1)))
34255
Na en zanimiv način je privlačna tudi spodnja različica (ki sicer
uvozi par funkcij in tako naprej, ampak ... je zanimiva). Vzamemo
obrnjen kupček in vsa števila od 1 naprej. Čez te pare z
map
spustimo množenje (mul
) in rezultat
seštejemo.
from operator import mul
from itertools import count
print(sum(map(mul, reversed(c1 + c2), count(1))))
34255
To nima nobenih prednosti pred gornjim, nemara je celo počasnejše. Je pa zanimivo.
Naloga ni težka, le veliko priložnoti za napake nudi.
Rekurzivno funkcijo bomo napisali tako, da vrne dve stvari: pove, ali je zmagal igralec številka 2, poleg tega pa vrne zmagovalčev kupček kart. Kdo je zmagal, potrebujemo za rekurzivne vojne, kupček kart pa za prvi klic. Da bo funkcija le ena, pa bomo pač vračali oboje, uporabili pa, kar potrebujemo.
V množici seen
bomo hranili vse že videne situacije.
V zanki najprej sestavimo situacijo kot terko terk c1
in
c2
. Pri tem se c1
in c2
skopirata; to je potrebno zato, ker ju spodaj spreminjamo.
Če je situacija že videna, javimo, da ni zmagal drugi igralec.
Sicer pa dodamo situacijo med videne. Poberemo karti. Če imata oba igralca dovolj preostalih kart, zmagovalca določi rekurzivna igra na začetkih kupčkov, sicer pa številki na kartah.
Na koncu povemo, ali je zmagal drugi igralec (to je, ali ima neprazen kupček kart) in vrnemo kupček zmagovalčevih kart, ki ga dobimo tako, da seštejemo (prazni) poražencev in zmagovalčev kupček.
def game(c1, c2):
= set()
seen
while c1 and c2:
= (tuple(c1), tuple(c2))
situation if situation in seen:
return False, c1
seen.add(situation)= c1.pop(0), c2.pop(0)
a1, a2 if len(c1) >= a1 and len(c2) >= a2:
= game(c1[:a1], c2[:a2])
winner, _ else:
= a2 > a1
winner if winner:
+= [a2, a1]
c2 else:
+= [a1, a2]
c1
return bool(c2), c1 + c2
= ([int(x) for x in p.splitlines()[1:]] for p in (p1, p2))
c1, c2 = game(c1, c2)
_, cards print(sum(i * x for i, x in enumerate(reversed(cards), start=1)))
33369