Problem

Angenommen, Sie haben N Stapel mit den Namen S ₁ bis S _N , wobei jedes S _k (k = 1 bis N) N Kopien der Zahl k enthält.

Wenn beispielsweise N = 3 ist, sieht der Stapel folgendermaßen aus:

1  2  3  <- top of stack
1  2  3
1  2  3  <- bottom of stack
=======
1  2  3  <- stack index

^{Hier gibt es 3 Stapel, die als 1, 2 und 3 indiziert sind, und jeder enthält N Instanzen seines eigenen Index.}

Das Ziel besteht darin, die N Stapel so neu anzuordnen, dass jeder von ihnen die Nummern 1 bis N in der Reihenfolge von oben nach unten enthält.

zB für N = 3 ist das Ziel, die Stapel neu anzuordnen in:

1  1  1
2  2  2
3  3  3
=======
1  2  3

Die einzige Aktion, die Sie mit den Stapeln ausführen können, besteht darin , die oberste Zahl von einem der Stapel zu nehmen (Poppen) und sie dann sofort auf einen anderen Stapel zu legen (Schieben) . Dies unterliegt diesen Bestimmungen:

• Eine Zahl kann nur dann auf einen Stapel gelegt werden, wenn sie kleiner oder gleich der obersten Zahl auf diesem Stapel ist.

  • zB 1kann a mit a 1, 2oder 3oben 2auf einen Stapel geschoben werden , aber a kann nur mit a 2oder 3(oder höher) oben auf einen Stapel geschoben werden .

  • Dies hat zur Folge, dass Stapel von oben nach unten immer monoton ansteigen .

• Jeder nicht leere Stapel kann aus dem Stapel entfernt werden, und unter der Annahme, dass der vorherige Aufzählungspunkt erfüllt ist, kann ein beliebiger Stapel in den Stapel verschoben werden.

• Jede Zahl kann auf einen leeren Stapel gelegt werden.

• Stapel haben keine maximale Höhenbeschränkung.

• Stapel können nicht erstellt oder zerstört werden, es gibt immer N davon.

Bei dieser Herausforderung geht es darum, zu entscheiden, welche Aktionen ausgeführt werden müssen, um den Stapelaustausch abzuschließen, und zwar nicht unbedingt mit den wenigsten Zügen, sondern auf todsichere Weise.

(Das Üben mit einem Kartenspiel ist ein guter Weg, um ein Gefühl für das Problem zu bekommen.)

Herausforderung

Schreiben Sie ein Programm oder eine Funktion, die eine positive ganze Zahl N (3 oder höher) enthält. Einen String drucken oder zurückgeben, der alle Pop-Push-Aktionen angibt, die erforderlich sind, um die Stapel aus dem Ausgangszustand neu anzuordnen:

1  2  3  4  5
1  2  3  4  5
1  2  3  4  5
1  2  3  4  5
1  2  3  4  5
=============
1  2  3  4  5

^{(N = 5 Fall)}

Zum endgültigen Zustand:

1  1  1  1  1
2  2  2  2  2
3  3  3  3  3
4  4  4  4  4
5  5  5  5  5
=============
1  2  3  4  5

Jede Zeile in Ihrer Ausgabe muss zwei durch ein Leerzeichen getrennte Zahlen enthalten. Die erste Zahl gibt den Index des Stapels an, von dem aus die Daten abgerufen werden sollen, und die zweite Zahl gibt den Index des Stapels an, zu dem die Daten verschoben werden sollen. Durch Ausführen der Aktionen aller Zeilen in der angegebenen Reihenfolge sollten die Stapel korrekt angeordnet werden, ohne dass Regeln verletzt werden.

Hier ist zum Beispiel eine mögliche gültige Ausgabe für den Fall N = 3:

1 2  [move the top number on stack 1 to the top of stack 2]
1 2  [repeat]
1 2  [repeat]
3 1  [move the top number on stack 3 to the top of stack 1]
2 3  [etc.]
2 3
2 3
2 1
2 1
2 1
3 1
3 1
3 1
3 2
1 2
1 2
1 2
1 3
2 3
2 3
2 3
1 2
3 2
3 1

Anmerkungen

• Ihre Ausgabe muss nicht optimal sein , sondern nur korrekt. Das heißt, Sie müssen die Anzahl der Pops und Pushs nicht minimieren.

  • Es wäre also in Ordnung, wenn zum Beispiel einige Schritte wiederholt und sofort rückgängig gemacht würden.
  • Poppen und Schieben in einem Zug zum selben Stapel 2 2ist ebenfalls erlaubt (obwohl natürlich sinnlos).

• Ihre Ausgabe muss deterministisch und endlich sein.

• Denken Sie daran, dass Stapel eine 1-basierte Indizierung haben. 0-basierte Indizierung ist nicht zulässig.

• N größer als 9 sollte natürlich genauso gut funktionieren wie einstelliges N.

• Falls gewünscht, können Sie anstelle von Leerzeichen und Zeilenumbrüchen zwei verschiedene, nicht einstellige druckbare ASCII- Zeichen verwenden. Eine abschließende Newline (oder Newline-Ersatz) in der Ausgabe ist in Ordnung.

Wertung

Der kürzeste Code in Bytes gewinnt. Tiebreaker ist höher gestimmte Antwort.

Wertlose Brownie-Punkte, wenn Sie zeigen können, dass Ihr Algorithmus optimal ist.

Pyth 96 94 Bytes

Mt*Q+++bGdHM|%+y_GHQQg1 2++Qd1g2 3g2 1g3 1++Qd2Vr3QgNtN++QdN;g1QVStQVStQI<NHgnNHnNtH)++nN0dnNH

Probieren Sie es hier aus

Wie funktioniert es?

Diese Erklärung verwendet N = 5.

Teil 1: Erstellen Sie die unterste Ebene auf jedem Stapel

Der Grund, warum dies einen separaten Code erfordert, ist, dass jeder Stapel verwendet werden muss: Die ersten 4 müssen mit einer 5 unterlegt werden, und der letzte Stapel muss die 5 liefern. Dies bedeutet, dass wir nicht einfach alle 4er irgendwohin verschieben, eine 5er dorthin setzen und die 4er zurück verschieben können.

Visualisierung: (Klammern bedeuten, was verschoben wird)

     _
11111 |
22222 |_ Can't move 4s here, not monotonically increasing
33333_|
(44444)------------??? Where to put the 4s?
55555 <- Must supply the 5 that will be moved

Stattdessen verschieben wir für diesen ersten Austausch zuerst alle Einsen auf den zweiten Stapel, verschieben eine 5 auf den ersten Stapel (der jetzt leer ist), verschieben die Einsen auf den dritten Stapel, verschieben die Zweisen auf den ersten stapeln, die Einsen zurück auf den ersten Stapel legen und schließlich eine 5 auf den zweiten Stapel legen.

(11111)-----.
2222211111<-'
===============================
5<---------.
2222211111 : (from stack 5)
===============================
5
22222(11111)-.
3333311111<--'
===============================
522222<-.
(22222)-'
3333311111
===============================
52222211111<-.
             |
33333(11111)-'
===============================
52222211111
5<-----.
33333  |
44444  |
555(5)-'

Jetzt, da wir einen freien Platz haben, in den wir Stapel verschieben können (Stapel 2, der nur eine 5 enthält, die an der richtigen Stelle platziert ist), können wir alle 3s in Stapel 2 verschieben und eine 5 in Stapel 3 platzieren. Dann können wir wiederholen Das gleiche gilt für Stapel 4, und jetzt haben wir alle 5 an der richtigen Stelle! Und noch eins: Wir werden alle Einsen auf Stapel 5 verschieben, damit wir ein gutes Setup für den nächsten Stapelaustausch bekommen.

522222(11111)-.
533333        |
544444        |
5             |
511111<-------'

Teil 2: Mach alles andere :)

Dies ist jetzt viel einfacher, da wir jetzt immer einen freien Stapel haben, um andere Zahlen zu verschieben, in die wir hinein jonglieren müssen. Also, zuerst finden wir heraus, wo die 4 ist. Eine kleine Untersuchung wird zeigen, dass es immer 1 höher als der Startpunkt oder 2 höher als der letzte Stapel ist. Jetzt gehen wir einfach die Stapel runter, setzen eine 4 in den Stapel, wenn sie frei ist, oder verschieben die anderen Zahlen um einen Stapel nach oben, wenn dies nicht der Fall ist. Jetzt haben wir alle 4 an Ort und Stelle.

522222<------.
533333<----. |
544444-.-.-'-'
5<-----' |
511111<--'
===============================
5433333
54
54
5411111
5422222

Jetzt stellen wir fest, dass die 3 2 Stapel über den 4 Stapeln sind. Dies bedeutet, dass wir genau das gleiche tun können, was wir mit den 4ern getan haben! Und wie sich herausstellt, können wir dies so lange tun, wie wir den Stapelindex auf die andere Seite legen.

5433333-'wrap around 543
54                   543
54                   54311111
5411111 .----------->54322222
5422222 |2 stacks up 543

Und so können wir weitermachen, bis wir alle Stapel ausgetauscht haben.

Code Erklärung:

Zuallererst: Die (wichtigen) vordefinierten Variablen.

Q: Evaluated input.
b: The newline character, '\n'
d: A space, ' '

Es gibt 2 Lambda-Definitionen.

M           | g(G)(H), used for moving Q numbers at a time.
            | We will call these Q numbers a "(number) block"
 t          | Tail, used to remove beginning newline
  *Q        | Repeat the following Q times
    +++bGdH | '\n' + G + ' ' + H. Just a whole bunch of concatenating.
            |
M           | n(G)(H), used for figuring out which stacks to move from
 |       Q  | If the following code is 0 (false), then use Q instead
  %     Q   | Mod Q
   +   H    | Add H
    y       | Multiply by 2
     _G     | Negate (remember in the explanation part 2? Always 2 stacks above?)

Der Stapelaustausch: Teil 1

g1 2                       | Move the 1 block to stack 2
    ++Qd1                  | Move a Q to stack 1
         g2 3              | Move the 1 block to stack 3
             g2 1          | Move the 2 block to stack 1
                 g3 1      | Move the 1 block back to stack 1
                     ++Qd2 | Move a Q to stack 2
 v---Code-continuation---' |I don't have enough room!!!
Vr3Q                       | For N in range(3, Q)
    gNtN                   | Move the number block in stack N up 1
        ++QdN              | Move a Q to stack N
             ;g1Q          | End for loop; move the 1 block to the last stack

Der Stapelaustausch: Teil 2

VStQ                           | For N in [1, 2, ..., Q - 1]
    VStQ                       | For H in [1, 2, ..., Q - 1]
        I<NH                   | If N < H
            g                  | Number block move
             nNH               |  (find number block)
                nNtH           |  (find the previous stack)
                    )          | End "For H"
                     ++nN0dnNH | Find start, move number to next location down

Ich weiß bereits, dass ich keine Brownie-Punkte bekomme, weil ich viel effizientere und kompliziertere Methoden sehen kann :(