Ich bin mir sicher, dass jeder zuvor gesehen hat, dass Tassen in Pyramiden (und andere Formen) gestapelt werden können:
A
A A A
A A A A A
A A A A A A A A
Ja, A
ist definitiv ein adäquater Charakter, um eine Tasse darzustellen.
Neue Becher können entweder auf dem Boden rechts von der Struktur oder auf zwei benachbarten Bechern hinzugefügt werden. Hier ist nochmal die obige Struktur, aber alle verfügbaren Plätze für neue Tassen sind markiert mit _
:
_ A
A A A
A _ _ A A A A
A A A A A A A A _ _ _
Nehmen wir an, wir wollen einen Roboter bauen, der diese Tassenstapel zusammenbauen kann. Der Roboter versteht zwei einfache Anweisungen zum Manipulieren einer solchen Struktur:
a
: Eine neue Tasse in der ersten verfügbaren Stelle in von links nach rechts hinzufügen Lesereihenfolge (das heißt, scannen die Zeilen von oben nach unten, von links nach rechts , bis Sie eine verfügbaren Stelle finden, dann die Schale legt dort). Das obige Beispiel würde lauten:A A A A A A A A A A A A A A A A A A
r
: Entfernen Sie die erste Tasse in der Reihenfolge von links nach rechts. Das obige Beispiel würde lauten:A A A A A A A A A A A A A A A A
Es stellt sich heraus, dass jede Struktur mit nur diesen beiden Operationen von Grund auf neu aufgebaut werden kann. Z.B
A
A A A
A A A A A
Kann mit der Abfolge von Anweisungen gebaut werden
aaaaaaaaaaaarrrrraa
Das größere Beispiel oben kann mit erstellt werden
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrraaaaaaarr
Hier ist eine noch größere:
A
A A A
A A A A A A A
A A A A A A A A A A A A
A A A A A A A A A A A A A A A
was mit gebaut werden kann
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrraaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrraaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrraaaaaaaaaaaaaarrrrrrrrrrraaaaaaaa
Hinweis: Wenn durch Anweisungen zum Entfernen Flecken auf dem Boden freigesetzt werden, werden diese wiederverwendet, bevor die Tassen rechts von allen vorhandenen Tassen platziert werden. Z.B
aaaarrra
wird nachgeben
A A
nicht
A A
Sie können sich den Boden als eine halb unendliche Reihe von Bechern vorstellen.
Die Herausforderung
Bei einer gegebenen Struktur von gestapelten Bechern geben Sie eine Sequenz zurück, die die Anweisungen zum Aufbau dieser Struktur darstellt. Ihre primäre Punktzahl ist die Summe der Anweisungen für die unten angegebenen Testfälle. Im Falle eines Gleichstands (was wahrscheinlich ist, weil ich davon überzeugt bin, dass eine effiziente optimale Lösung möglich ist) gewinnt die kürzeste Lösung.
Hier einige Details zu den Regeln:
- Sie können davon ausgehen, dass in der unteren Reihe der Eingabe keine führenden Leerzeichen vorhanden sind, sodass immer der am weitesten links liegende Bodenpunkt für eine Tasse verwendet wird.
- Sie können von einer angemessenen Anzahl von nachgestellten Leerzeichen ausgehen (keine Leerzeichen, ein Leerzeichen, aufgefüllt mit einem Rechteck, aufgefüllt mit einem einzelnen nachgestellten Leerzeichen).
- Optional können Sie davon ausgehen, dass die Eingabe in einer einzelnen nachgestellten Zeile endet.
- Anstelle von können Sie zwei beliebige druckbare ASCII-Zeichen (0x20 bis 0x7E, einschließlich) auswählen
A
und Leerzeichen (die Regeln für Leerzeichen werden dann auf das von Ihnen ausgewählte Zeichen übertragen). - Ihre Ausgabe sollte nur zwei unterschiedliche Zeichen enthalten, die die Operationen darstellen (Sie können auch andere Zeichen als
a
und auswählen)r
). Sie können optional eine einzelne nachgestellte Zeile drucken. - Ihr Code muss in der Lage sein, einen der folgenden Testfälle in weniger als einer Minute zu lösen auf einem vernünftigen Desktop-PC (wenn es bei mir zwei Minuten dauert, gebe ich Ihnen den Vorteil des Zweifels, aber wenn es zehn Minuten dauert, habe ich gewonnen Ich glaube, ein optimaler Algorithmus ist möglich, der jeden von ihnen in weniger als einer Sekunde löst.
- Sie dürfen Ihren Code nicht für einzelne Testfälle optimieren (z. B. durch Hardcodierung). Wenn ich den Verdacht habe, dass jemand dies tut, behalte ich mir das Recht vor, die Testfälle zu ändern.
Sie können dieses CJam-Skript für den umgekehrten Vorgang verwenden: Es nimmt eine Reihe von Bauanweisungen entgegen und druckt den resultierenden Tassenstapel. (Vielen Dank an Dennis, der das Snippet neu geschrieben und deutlich beschleunigt hat.)
Sp3000 stellte freundlicherweise dieses alternative Python-Skript für denselben Zweck zur Verfügung.
Testfälle
Nach jedem Testfall gibt es eine Zahl, die die optimale Anzahl von Anweisungen gemäß Ell's Antwort angibt.
A
A A
A A A
A A A A
A A A A A
A A A A A A
A A A A A A A
A A A A A A A A
A A A A A A A A A
A A A A A A A A A A
A A A A A A A A A A A
A A A A A A A A A A A A
A A A A A A A A A A A A A
A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
820
A
A A
A A A
A A A A
A A A A A
A A A A A A
A A A A A A A
A A A A A A A A
A A A A A A A A A A
A A A A A A A A A A A A
A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
1946
A
A A
A A A
A A A A
A A A A A
A A A A A A
A A A A A A A
A A A A A A A A
A A A A A A A A A A
A A A A A A A A A A A A
A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
2252
A A
A A A A
A A A A A A
A A A A A A A A
A A A A A A A A A A
A A A A A A A A A A A A
A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
9958
A A
A A A A
A A A A A A
A A A A A A A A
A A A A A A A A A A
A A A A A A A A A A A A
A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
5540
A A A A A A A A A A A A A A A A A A A A
10280
A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
10320
A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
5794
A
A A
A A A
A A A A A
A A A A A A A
A A A A A A A A A A
A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
3297
A A
A A A
A A A A
A A A A A
A A A A A A
A A A A A A A
A A A A A A A A
A A A A A A A A A
A A A A A A A A A A A
A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
4081
A
A A A A
A A A A A A A A A
A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
4475
A
A A A A A A A A
A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
5752
Das heißt, die bestmögliche Punktzahl liegt bei 64.515 Anweisungen.
quelle