Uvozimo numpy
in preberemo podatke.
import numpy as np
= np.array([list(v.strip()) for v in open("example.txt")]) state
Vsako vrstico smo odstripali znaka za novo vrsto in jo spremenili v seznam. Stanje je zdaj
state
array([['v', '.', '.', '.', '>', '>', '.', 'v', 'v', '>'],
['.', 'v', 'v', '>', '>', '.', 'v', 'v', '.', '.'],
['>', '>', '.', '>', 'v', '>', '.', '.', '.', 'v'],
['>', '>', 'v', '>', '>', '.', '>', '.', 'v', '.'],
['v', '>', 'v', '.', 'v', 'v', '.', 'v', '.', '.'],
['>', '.', '>', '>', '.', '.', 'v', '.', '.', '.'],
['.', 'v', 'v', '.', '.', '>', '.', '>', 'v', '.'],
['v', '.', 'v', '.', '.', '>', '>', 'v', '.', 'v'],
['.', '.', '.', '.', 'v', '.', '.', 'v', '.', '>']], dtype='<U1')
Višino in širino si bomo za preglednejši rabo shranili v spremenljivki.
= state.shape h, w
Oglejmo si tiste, ki hočejo dol. Kje so?
= np.nonzero(state == "v") y, x
x
array([0, 7, 8, 1, 2, 6, 7, 4, 9, 2, 8, 0, 2, 4, 5, 7, 6, 1, 2, 8, 0, 2,
7, 9, 4, 7])
y
array([0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 4, 5, 6, 6, 6, 7, 7,
7, 7, 8, 8])
Kakšne so koordinate polj pod njimi od njih?
= x, (y + 1) % h newx, newy
newy
v resnici potrebujemo, newx
, ki je kar
enak x
, pa nam bo prišel prav kasneje.
Katera izmed teh polj, na katera bi šli tile, so prosta?
= state[newy, newx] == "." can_move
can_move
array([ True, False, True, False, True, True, True, False, True,
False, True, False, False, True, True, True, True, True,
False, True, True, True, False, False, False, False])
Še enkrat izpišimo stanje (da ga bomo lažje primerjali), potem premaknimo tiste, ki jih lahko in potem ponovno izpišimo stanje.
state
array([['v', '.', '.', '.', '>', '>', '.', 'v', 'v', '>'],
['.', 'v', 'v', '>', '>', '.', 'v', 'v', '.', '.'],
['>', '>', '.', '>', 'v', '>', '.', '.', '.', 'v'],
['>', '>', 'v', '>', '>', '.', '>', '.', 'v', '.'],
['v', '>', 'v', '.', 'v', 'v', '.', 'v', '.', '.'],
['>', '.', '>', '>', '.', '.', 'v', '.', '.', '.'],
['.', 'v', 'v', '.', '.', '>', '.', '>', 'v', '.'],
['v', '.', 'v', '.', '.', '>', '>', 'v', '.', 'v'],
['.', '.', '.', '.', 'v', '.', '.', 'v', '.', '>']], dtype='<U1')
= "."
state[y[can_move], x[can_move]] = "v" state[newy[can_move], newx[can_move]]
state
array([['.', '.', '.', '.', '>', '>', '.', 'v', '.', '>'],
['v', 'v', '.', '>', '>', '.', '.', '.', 'v', '.'],
['>', '>', 'v', '>', 'v', '>', 'v', 'v', '.', '.'],
['>', '>', 'v', '>', '>', '.', '>', '.', '.', 'v'],
['v', '>', 'v', '.', '.', '.', '.', '.', 'v', '.'],
['>', '.', '>', '>', 'v', 'v', '.', 'v', '.', '.'],
['.', '.', 'v', '.', '.', '>', 'v', '>', '.', '.'],
['.', 'v', '.', '.', '.', '>', '>', 'v', 'v', 'v'],
['v', '.', 'v', '.', 'v', '.', '.', 'v', '.', '>']], dtype='<U1')
Deluje, ne? Zložimo vse skupaj v program, premike v desno in dol pa zložimo v zanko, saj je večina dela enaka ne glede na smer.
= np.array([list(v.strip()) for v in open("input.txt")])
state
= True
changes = 0
step = state.shape
h, w while changes:
= False
changes for dir in ">v":
= np.nonzero(state == dir)
y, x if dir == ">":
= (x + 1) % w, y
xnew, ynew else:
= x, (y + 1) % h
xnew, ynew = state[ynew, xnew] == "."
can_move = "."
state[y[can_move], x[can_move]] = dir
state[ynew[can_move], xnew[can_move]] = changes or np.any(can_move)
changes += 1
step
print(step)
534
Rešitev je lepa, ker vse teče lepo, vzporedno, z minimalnim številom zank, pa tudi kar razumljivo je.
S tem se naš tečaj končuje. Upam, da ste prišli čez, se veliko naučili in se ob tem tudi zabavali.
Srečno novo leto!