• View
• Edit
• History
• Print

20180307d

AoC2017, Day 6, Part 1 (Memory Reallocation)

Adott 16 memóriaegység, s minden egyes memóriaegység tetszőleges számú blokkot tartalmazhat. Egy olyan rutint szeretnénk futtatni, ami a blokkokat átcsoportosítja a memóriaegységek között. A probléma az, hogy ez a rutin egy idő után végtelen ciklusba kerül.

Az átcsoportosító rutin a következőképpen működik. Először megkeresi azt a memóriaegységet, ami a legtöbb blokkot tartalmazza (ha két memóriaegységben megegyezik a blokkszám, akkor a bal oldalit veszi), majd ezeket a blokkokat szétosztja a memóriaegységek között. Ez úgy néz ki, hogy a kiválasztott memóriaegységből kiveszi az összes blokkot (azaz lenullázza), majd eggyel jobbra lép (veszi a következő memóriaegységet), s oda betesz 1 blokkot. Ezt addig folytatja, míg el nem fogynak a blokkok. A jobbra való lépegetés cirkuláris, vagyis az utolsó (jobb szélső) memóriaegység után kezdi elölről a legelső (bal szélső) memóriaegységgel.

A kérdés az, hogy hányszor kell lefuttatni az átcsoportosító rutint ahhoz, hogy végtelen ciklusba kerüljünk. A végtelen ciklust onnan ismerjük fel, hogy egy olyan memóriaegység-konfiguráció áll elő, amivel már találkoztunk korábban.

Vegyünk egy példát 4 db memóriaegységgel:

• A memóriaegységek tartalmazzanak 0, 2, 7 és 0 blokkot. Ez a kezdőállapot. A harmadik memóriaegységben van a legtöbb blokk, így ezt fogjuk szétosztani.
• A harmadik memóriaegységet kinullázzuk, majd a 7 blokkot elkezdjük szétosztani. A 4. memóriaegység kap egy blokkot, aztán az 1. is kap egyet, majd a 2. is, stb. A végén a negyedik, első és második memóriaegység mindegyike 2 blokkot kap, míg a harmadik memóriaegység 1-et. A memóriaegység-konfiguráció jelenlegi állapota: 2 4 1 2.
• Ezután a második memóriaegységet választjuk ki, mivel ebben van a legtöbb blokk (4 db). Nullázzuk a memóriaegységet, majd a szétosztás után minden memóriaegység kap 1 blokkot. Az eredmény: 3 1 2 3.
• Az első és a negyedik memóriaegység döntetlenre áll, mindkettő 3 blokkot tartalmaz. Az elsőt választjuk ki, majd ezt a három blokkot szétosztjuk a többiek között. Az aktuális eredmény: 0 2 3 4.
• A negyedik memóriaegységet választjuk ki, majd a 4 blokkot szétosztjuk. Mindenki kap 1 blokkot: 1 3 4 1.
• A harmadik memóriaegységet választjuk ki, majd a szétosztás után az eredmény: 2 4 1 2.

Ekkor elértünk egy olyan konfigurációhoz, amit már láttunk korábban: 2 4 1 2. Az átcsoportosító rutin ötödik futtatása után észrevettük, hogy végtelen ciklusba kerültünk, így ezen példa esetén a válasz: 5.

A bemenet a 16 memóriaegység kezdeti állapotát tartalmazza, vagyis hogy az egyes memóriaegységekben hány blokk található. Hányszor kell lefuttatni az átcsoportosító rutint ahhoz, hogy egy olyan konfigurációt kapjunk, ami már szerepelt korábban?

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