Weihnachtsgeschenke stapeln

– Vielen Dank an CipSoft für das bereitstellen dieser Aufgabe.

Szenario

Die Weihnachtselfe muss Geschenke in einen Schlitten absteigend nach Geschenkgröße übereinander stapeln, so dass das größte Geschenk ganz unten liegt, das kleinste ganz oben. Nach mühsamer Arbeit stellt sie jedoch fest, dass der schöne Geschenkestapel in einen anderen Schlitten gehört hätte. Sie muss nun den Stapel in den richtigen Schlitten bringen, kann jedoch nur ein Päckchen gleichzeitig bewegen und kann keine größeren auf kleinere Päckchen legen, da sonst deren Inhalte beschädigt werden würden. Neben dem vollen und dem leeren Schlitten gibt es noch eine ganz kleine Ablagefläche zum Verpacken der Geschenke. Sowohl die Ablagefläche als auch die beiden Schlitten erlauben aus Platzgründen nur einen einzigen Geschenkestapel, es können also keine Geschenke nebeneinander abgelegt werden, sondern stets nur übereinander. Es gibt keine gleichgroßen Päckchen im Geschenkestapel.

Aufgabenbeschreibung

Schreibe ein Programm, das die kleinstmögliche Menge notwendiger Aktionen angibt, die zum Verschieben der Päckchen durchgeführt werden müssen. Das Programm liest als Eingabe die Standard-Eingabe Stdin. Jede Eingabezeile enthält ein Geschenk und die Größe des Geschenks im Format Name, Größe in cm. Die letzte Zeile ist dann das unterste Päckchen im Schlitten.

Das Programm soll die errechneten Aktionen in die Standard-Ausgabe Stdout schreiben. Jede Aktion soll wie folgt formatiert sein: Ursprungs-Ablageplatz -> Ziel-Ablageplatz. Pro Aktion wird eine neue Zeile ausgegeben. Als Ablageplätze stehen zur Verfügung:

• A für Anfangs-Schlitten,
• V für Verpackungsablageplatz, und
• Z für Ziel-Schlitten.

Beispiel-Eingabe

Ball, 30
Pluesch-Einhorn, 50

Beispiel-Ausgabe

A -> V
A -> Z
V -> Z