Szathmáry László honlapja @ DEIK

AoC2017, Day 5, Part 1 (Maze Runner)

A CPU egy olyan programot futtat, amiben csak ugróutasítások vannak (jump instructions). A kérdés az, hogy hány ugrást kell végrehajtania a CPU-nak, mire sikerül befejeznie a programot.

A futtatandó program csak eltolási (offset) értékeket tartalmaz. Ezek relatív értékek, s az ugrások számára utalnak. Pl. a -1 jelentése: lépjünk vissza az előző utasításra; a 2 jelentése: ugorjunk előre 2 utasítást (vagyis a köv. utasítást ugorjuk át). A program offset értékek listája. A végrehajtást az első offset értéknél kezdjük. A program akkor ér véget, ha kiugrunk az utasítások listájából, vagyis ha egy olyan pozícióra ugrunk, ami a listán kívül esik.

Az ugrások egy kicsit speciálisak. Minden ugrás után az aktuális offset értéke 1-gyel megnő. Például ha az offset értéke 3, akkor hármat előre lépünk, és az offset értékét 3-ról 4-re állítjuk.

Tekintsük pl. az alábbi offset értékek listáját:

A pozitív értékek hatására lefelé mozgunk ("előre"), a negatív értékek hatására pedig felfelé ("vissza"). Az egyszerűség kedvéért a listát vízszintesen fogjuk ábrázolni, s az aktuális offset pozíciót zárójelbe tesszük. A program futása a következőképpen néz ki, mielőtt egy kiugrás hatására leállna:

"(0) 3 0 1 -3" - Kezdeti állapot, a legelső utasításon állunk.
"(1) 3 0 1 -3" - 0 pozíciót kell ugrani, vagyis maradunk egy helyben. Ugrás után viszont az offset értéke 1-gyel nő.
"2 (3) 0 1 -3" - Az offset új értéke 1, ezért egyet előre lépünk. Az első utasítást újból megnöveljük 1-gyel, így lesz 2.
"2 4 0 1 (-3)" - Hármat előre ugrunk, az offset 3-ról 4-re változik.
"2 (4) 0 1 -2" - Lépjünk vissza hármat. -3 + 1 = -2
"2 5 0 1 -2" - Négyet előre ugrunk, ami már a program utasításain kívül esik => vége a programnak.

Ebben a példában 5 lépés kellett ahhoz, hogy befejeződjön a program.

Kérdés: az input állományban található program hány lépés után fejeződik be?

A feladat bemenete innen tölthető le. A feladat eredeti kiírása itt olvasható el.

20180307c