Építőkockák

Az informatika sok területén használnak egyszerű, absztrakt modelleket mind analitikus, mind empirikus kutatásokban. Egy korai, tervezésről és robotikáról szóló mesterséges intelligencia kutatás (a STRIPS) például egy építőkockákból álló világot használt, amelyben egy robotkar hajtott végre a kockák manipulálásával járó feladatokat.

Ebben a feladatban egy egyszerű, jól meghatározott szabályoknak és megszorításoknak eleget tevő kockavilágot kell modellezned. Annak meghatározása helyett, hogy hogyan lehet elérni egy megadott állapotot, egy robotkart kell „programoznod” úgy, hogy korlátozott számú parancsot végrehajtson.

A feladatod, hogy beolvass egy parancssorozatot, amely egy sík asztalon fekvő kockák mozgatását írja le. Kezdetben n kocka van az asztalon (0-tól n – 1-ig számozva), ahol a b_i kocka szomszédos a b_i + 1 kockával minden 0 ≤ i < n – 1 esetén, ahogy az alábbi ábrán látható:

0 1 2 3 4

…

n – 1

A kezdeti kockavilág

A kockákat manipuláló robotkar által értelmezett parancsok a következők:

• move a onto b
  a és b kockasorszámok. Az a kockát rárakja a b kockára, miután az a és b kockákon található összes kockát visszatette az eredeti helyére.
• move a over b
  a és b kockasorszámok. Az a kockát rárakja a b kockát tartalmazó torony tetejére, miután az a kockán található összes kockát visszatette az eredeti helyére.
• pile a onto b
  a és b kockasorszámok. Az a kockából és a rajta található kockákból álló kockahalmot rárakja a b kockára. A b kockán található összes kockát visszateszi az eredeti helyére a halmozás végrehajtása előtt. Az a kockán található kockák sorrendje a mozgatás során nem változik.
• pile a over b
  a és b kockasorszámok. Az a kockából és a rajta található kockákból álló kockahalmot rárakja a b kockát tartalmazó torony tetejére. Az a kockán található kockák sorrendje a mozgatás során nem változik.
• quit
  Megszakítja a kockavilág manipulációját.

Azok a parancsok, amelyekben a = b, vagy amelyekben a és b ugyanabban a kockatoronyban vannak, érvénytelen parancsok. Az érvénytelen parancsokat figyelmen kívül kell hagyni, semmilyen hatással nem lehetnek a kockák elhelyezkedésére.

A bemenet specifikációja

A bemenet egy olyan sorral kezdődik, amelyben egy n egész szám, a kockavilágban található kockák száma szerepel. Feltételezheted, hogy 0 < n < 25.

A kockák számát soronként egy parancs követi. A programodnak minden parancsot fel kell dolgoznia egészen addig, amíg a quit paranccsal nem találkozik.

Feltételezheted, hogy minden parancs megfelel a fentebb leírt formátumnak. Nem lesznek szintaktikailag helytelen parancsok.

A kimenet specifikációja

A kimenetre a kockavilág végső állapotát kell kiírni. Az összes eredeti kockapozíció i sorszámát meg kell jeleníteni (0 ≤ i < n), amelyet közvetlenül egy kettőspontnak kell követnie. Ha az adott pozíción van legalább egy kocka, a kettőspontot egy szóköznek, majd az adott pozíción felhalmozott kockák sorszámaiból álló listának kell követnie, a kockasorszámokat egymástól egy-egy szóközzel elválasztva. A sorok végén nem állhatnak szóközök!

Minden kockapozícióhoz pontosan egy sort kell a kimenetre írni (azaz a kimenetnek összesen n sorból kell állnia).

Példa bemenet

1. 10
2. move 9 onto 1
3. move 8 over 1
4. move 7 over 1
5. move 6 over 1
6. pile 8 over 6
7. pile 8 over 5
8. move 2 over 1
9. move 4 over 9
10. quit

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. 0: 0
2. 1: 1 9 2 4
3. 2:
4. 3: 3
5. 4:
6. 5: 5 8 7 6
7. 6:
8. 7:
9. 8:
10. 9:

letöltés szöveges állományként