Problème

Supposons que vous ayez N piles nommées S ₁ à S _N , où chaque S _k (k = 1 à N) contient N copies du nombre k.

Par exemple, lorsque N = 3, les piles ressemblent à ceci:

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

^{Ici, il y a 3 piles indexées comme 1, 2 et 3, et chacune contient N instances de son propre index.}

Le but est de réorganiser les N piles de telle sorte que chacune d'entre elles contienne à l'identique les nombres 1 à N dans l'ordre de haut en bas.

Par exemple, pour N = 3, l'objectif est de réorganiser les piles en:

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

La seule action que vous pouvez effectuer avec les piles est de prendre le numéro supérieur de l'une des piles (popping) puis de le placer immédiatement au-dessus d'une pile différente (pousser) . Ceci est soumis à ces stipulations:

• Un nombre ne peut être poussé sur une pile que s'il est inférieur ou égal au numéro supérieur de cette pile.

  • Par exemple, un 1peut être poussé sur une pile avec un 1, 2ou 3en haut, mais un 2ne peut être poussé que sur une pile avec un 2ou 3(ou plus) en haut.

  • Cela a pour effet que les piles augmentent toujours de façon monotone de haut en bas.

• Toute pile non vide peut être extraite de, et, en supposant que la puce précédente est satisfaite, toute pile peut être poussée vers.

• Tout nombre peut être poussé sur une pile vide.

• Les piles n'ont pas de limite de hauteur maximale.

• Les piles ne peuvent pas être créées ou détruites, il y en a toujours N.

Ce défi consiste à décider des actions à effectuer et à effectuer afin de terminer l'échange de pile, pas nécessairement en un minimum de mouvements, mais de manière infaillible.

(S'entraîner avec un jeu de cartes est un bon moyen de se faire une idée du problème.)

Défi

Écrivez un programme ou une fonction qui accepte un entier positif N, garanti égal ou supérieur à 3. Affiche ou retourne une chaîne qui dénote toutes les actions pop-push nécessaires pour réorganiser les piles à partir de l'état initial:

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 cas)}

À l'état final:

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

Chaque ligne de votre sortie doit contenir deux nombres séparés par un espace. Le premier nombre est l'index de la pile à extraire et le deuxième nombre est l'index de la pile vers laquelle pousser. L'exécution des actions de toutes les lignes dans l'ordre doit organiser les piles correctement sans enfreindre aucune règle.

Par exemple, voici une sortie potentiellement valide pour le cas 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

Remarques

• Votre sortie n'a pas besoin d'être optimale , seulement correcte. c'est-à-dire que vous n'avez pas besoin de minimiser le nombre de pops et de pushs.

  • Donc, ce serait bien si, par exemple, des mesures étaient répétées et inversées immédiatement.
  • Popping et pousser vers la même pile en un seul mouvement, par exemple 2 2, est également autorisé (bien sûr inutile).

• Votre sortie ne besoin d'être déterministe et fini.

• N'oubliez pas que les piles ont une indexation basée sur 1. L'indexation basée sur 0 n'est pas autorisée.

• N supérieur à 9 devrait bien sûr fonctionner aussi bien que le seul chiffre N.

• Si vous le souhaitez, vous pouvez utiliser deux caractères ASCII imprimables non numériques distincts à la place des espaces et des retours à la ligne. Un retour à la ligne de fin (ou un substitut de nouvelle ligne) dans la sortie est très bien.

Notation

Le code le plus court en octets gagne. Tiebreaker est la réponse la plus votée.

Points sans valeur brownie si vous pouvez montrer que votre algorithme est optimal.

Pyth 96 94 octets

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

Essayez-le ici

Comment ça marche?

Cette explication utilisera N = 5.

Partie 1: Créez la couche inférieure sur chaque pile

La raison pour laquelle cela a besoin d'un morceau de code séparé est parce que chaque pile doit être utilisée: les 4 premiers ont besoin d'un 5 pour être placés en dessous, et la dernière pile doit fournir les 5. Cela signifie que nous ne pouvons pas simplement déplacer tous les 4 quelque part, y mettre un 5 et reculer les 4.

Visualisation: (les parenthèses signifient ce qui sera déplacé)

     _
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

Au lieu de cela, pour faire ce premier échange, nous allons d'abord déplacer tous les 1 vers la deuxième pile, déplacer un 5 vers la première pile (qui est maintenant vide), déplacer les 1 vers la troisième pile, déplacer les 2 vers la première pile, déplacez les 1 vers la première pile, et enfin déplacez un 5 vers la deuxième pile.

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

Maintenant que nous avons un espace libre pour déplacer des piles (pile 2, qui ne contient qu'un 5 qui est placé au bon endroit), nous pouvons déplacer tous les 3 vers la pile 2 et placer un 5 dans la pile 3. Nous pouvons ensuite répéter la même chose pour la pile 4, et maintenant nous obtenons tous les 5 au bon endroit! Et encore une chose: nous déplacerons tous les 1 vers la pile 5 afin d'avoir une bonne configuration pour le prochain échange de pile.

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

Partie 2: Faites tout le reste :)

C'est beaucoup plus facile maintenant, car maintenant nous aurons toujours une pile gratuite pour déplacer d'autres numéros dans lesquels nous devons jongler. Donc, d'abord, nous trouvons où est le 4. Un petit examen montrera qu'il sera toujours à 1 point de départ, ou 2 au-dessus de la dernière pile. Maintenant, nous continuons à descendre les piles, en plaçant un 4 dans la pile s'il est libre, ou en déplaçant les autres numéros d'une pile dans le cas contraire. Maintenant, nous avons tous les 4 en place.

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

Maintenant, nous nous rendons compte que les 3 sont 2 piles au-dessus de l'endroit où les 4 où. Cela signifie que nous pouvons faire exactement la même chose que nous avons fait avec les 4! Et en fin de compte, nous pouvons continuer à le faire tant que nous enroulons l'index de la pile de l'autre côté.

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

Et donc, nous pouvons continuer à le faire jusqu'à ce que nous ayons échangé toutes les piles.

Explication du code:

Tout d'abord: les variables (importantes) prédéfinies.

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

Il existe 2 définitions lambda.

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?)

L'échange de pile: partie 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

L'échange de pile: partie 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

Je sais déjà que je n'obtiens pas de points brownie, car je peux voir de nombreuses méthodes plus efficaces et plus compliquées :(