Bearbeiten: Ich werde am Ende der Frage eine Prämie von 100 Reputationen für den ersten Löser des Bonus-Puzzles vergeben !
Ich werde das Kopfgeld nur dann zur Frage hinzufügen, wenn die Antwort erscheint, da dieses Kopfgeld keine Frist hat.
Bei einer nicht abnehmenden Liste einstelliger positiver Ganzzahlen sollten Sie bestimmen, wie tief der Dungeon die Ziffern graben wird.
███ ███ A dungeon with 5 blocks removed and a depth of 3.
███ ███
███ ████
████████
Vor Beginn des Grabens ist der Boden eben.
Jede Ziffer kann genau einen Erdblock von unten entfernen, muss diese Position jedoch von außerhalb des Dungeons erreichen, und nachdem sie entfernt wurde, muss der Block den Dungeon verlassen. Dabei kann eine Ziffer in keinem horizontalen Schritt mehr als ihren numerischen Wert ab- oder aufsteigen .
Die Ziffern verwenden die folgende Strategie zum Graben:
- Die Ziffer mit dem kleinsten Wert gräbt zuerst und danach ist der nächste Bagger immer der nächstkleinere Wert aus den restlichen Ziffern.
- Die erste Ziffer kann an jeder Position graben. (Alle Böden sind gleich.)
- Die folgenden Ziffern graben sich immer in der bereits gestarteten Spalte ganz links ein, wo sie herauskommen können. Wenn keine solche Spalte vorhanden ist, beginnen sie, eine neue Spalte auf der rechten Seite der am weitesten rechts stehenden Spalte zu graben.
Zum Beispiel würden die Ziffern 1 1 1 2 3 3
den folgenden Dungeon graben (schrittweise Visualisierung mit Zahlen, die markieren, welche Art von Ziffer diese Position ausgräbt):
███1████ ███11███ ███11███ ███11███ ███11███ ███11███
████████ ████████ ███1████ ███1████ ███1████ ███13███
████████ ████████ ████████ ███2████ ███2████ ███2████
████████ ████████ ████████ ████████ ███3████ ███3████
████████ ████████ ████████ ████████ ████████ ████████
Erläuterung zum Beispiel:
- Der zweite
1
konnte nicht aus der einzigen verfügbaren Säule herausklettern, wenn er sie vertiefen würde, um2
tief zu gehen, damit er direkt darauf gräbt. - Der dritte
1
kann in die Spalte ganz links graben und eine2
tiefe Spalte erstellen, während er sich in die1
tiefe Spalte und dann in die Bodenhöhe bewegen kann . - Der nächste
2
und3
beide können in der linken Spalte graben. - Der letzte
3
kann nicht in der Spalte ganz links graben, sondern in der nächsten.
Eingang
- Eine nicht abnehmende Liste positiver einstelliger Ganzzahlen mit mindestens einem Element.
Ausgabe
- Eine einzelne positive ganze Zahl, die Tiefe des konstruierten Dungeons.
Beispiele
Eingabe => Ausgabe (mit den Tiefen der Spalten des Dungeons von links nach rechts als Erklärung, die nicht Teil der Ausgabe ist)
[3] => 1
(column depths are [1])
[1, 1, 1, 2, 3, 3] => 4
(column depths are [4, 2])
[1, 1, 1, 1, 1, 1, 1, 1] => 3
(column depths are [3, 2, 2, 1])
[1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 3, 5, 5, 5, 5, 5, 5, 5, 5] => 11
(column depths are [11, 6, 2])
[1, 1, 1, 1, 1, 2, 2, 9, 9, 9] => 7
(column depths are [7, 2, 1])
[2, 2, 2, 2, 2, 5, 5, 5, 7, 7, 9] => 9
(column depths are [9, 2])
[1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5] => 10
(column depths are [10, 5])
[1, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 9] => 13
(column depths are [13, 5])
[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9] => 13
(column depths are [13, 5])
[1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9] => 21
(column depths are [21, 12, 3])
Dies ist Code-Golf, also gewinnt der kürzeste Eintrag.
Bonus-Puzzle
Können Sie beweisen (oder widerlegen), dass die im Abschnitt "Die Ziffern verwenden die folgende Strategie zum Graben" beschriebene Strategie immer den tiefstmöglichen Dungeon für die angegebenen Ziffern bietet?
quelle