Problem

Powiedzmy, że masz N stosów o nazwach od S ₁ do S _N , gdzie każda S _k (k = 1 do N) zawiera N kopii liczby k.

Na przykład, gdy N = 3 stosy wyglądają tak:

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

^{Tutaj są 3 stosy indeksowane jako 1, 2 i 3, a każdy z nich zawiera N instancji własnego indeksu.}

Celem jest takie przestawienie stosów N, aby każdy z nich identycznie zawierał liczby od 1 do N w kolejności od góry do dołu.

np. dla N = 3 celem jest zmiana kolejności stosów na:

Jedyną czynnością, którą możesz wykonać za pomocą stosów, jest pobranie najwyższego numeru z jednego ze stosów (wyskakiwanie), a następnie natychmiastowe umieszczenie go na innym stosie (pchanie) . Jest to uzależnione od następujących postanowień:

Liczba może zostać wypchnięta na stos tylko wtedy, gdy jest mniejsza lub równa najwyższej liczbie na tym stosie.
- na przykład 1może być popychany na stos z 1, 2lub 3od góry, ale 2może być popychany na stos tylko z 2albo 3(lub więcej) na wierzchu.
- Powoduje to, że stosy zawsze monotonicznie wzrastają od góry do dołu.
Każdy niepusty stos może zostać wyskakujący, a przy założeniu, że poprzedni punkt jest spełniony, każdy stos może zostać przesunięty.
Dowolną liczbę można przesunąć na pusty stos.
Stosy nie mają limitu maksymalnej wysokości.
Stosów nie można tworzyć ani niszczyć, zawsze jest ich N.

Wyzwanie polega na podjęciu decyzji, które trzaski i pchnięcia zrobić, aby zakończyć wymianę stosu, niekoniecznie w najmniejszej liczbie ruchów, ale w pewny sposób.

(Ćwiczenie z talią kart jest dobrym sposobem na zrozumienie problemu).

Wyzwanie

Napisz program lub funkcję, która przyjmuje dodatnią liczbę całkowitą N, z gwarancją 3 lub więcej. Wydrukuj lub zwróć ciąg znaków, który oznacza wszystkie akcje pop-push wymagane do zmiany kolejności stosów od stanu początkowego:

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 przypadków)}

Do stanu końcowego:

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

Każdy wiersz wyniku musi zawierać dwie liczby oddzielone spacją. Pierwsza liczba to indeks stosu, z którego można wyskoczyć, a druga liczba to indeks stosu, do którego należy nacisnąć. Wykonanie akcji wszystkich linii w kolejności powinno poprawnie ułożyć stosy bez łamania zasad.

Na przykład tutaj jest potencjalnie poprawny wynik dla przypadku 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

Notatki

Twój wynik nie musi być optymalny , tylko poprawny. tzn. nie musisz minimalizować liczby popów i pchnięć.
- Byłoby więc dobrze, gdyby, powiedzmy, jakiś ruch był wielokrotnie wykonywany i natychmiast odwracany.
- 2 2Dozwolone jest również popping i pchanie do tego samego stosu jednym ruchem, choć oczywiście bezcelowe.
Twoja moc ma potrzebę bycia deterministyczne i skończony.
Pamiętaj, że stosy mają indeksowanie 1. Indeksowanie na podstawie 0 jest niedozwolone.
N większe niż 9 powinno oczywiście działać tak samo dobrze jak pojedyncza cyfra N.
W razie potrzeby zamiast spacji i znaków nowej linii możesz użyć dowolnych dwóch różnych, niecyfrowalnych znaków ASCII do wydrukowania . Końcowy znak nowej linii (lub zamiennik nowej linii) w wyjściu jest w porządku.

Punktacja

Najkrótszy kod w bajtach wygrywa. Tiebreaker jest wyżej głosowaną odpowiedzią.

Bezwartościowe punkty brownie, jeśli możesz pokazać, że twój algorytm jest optymalny.

code-golf number data-structures Hobby Calvina
źródło

Zatrzymaj się na

nonsensie

@ zyabin101 Właśnie straciłeś szansę na ciasteczka.

Calvin's Hobbies

Zawsze wymyślasz takie wspaniałe tytuły!

Luis Mendo

@HelkaHomba-._(._.)_.-

user48538

Czy możliwe wyjście podasz w przypadku N=3optymalnego?

R. Kap

Pyth 96 94 bajty

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

Wypróbuj tutaj

Jak to działa?

To wyjaśnienie będzie używać N = 5.

Część 1: Utwórz dolną warstwę na każdym stosie

Powodem, dla którego jest to konieczne, jest oddzielny fragment kodu, ponieważ każdy stos musi zostać użyty: pierwsze 4 wymagają umieszczenia 5 pod nimi, a ostatni stos musi zawierać 5. Oznacza to, że nie możemy po prostu przenieść gdzieś wszystkich 4s, umieścić tam 5 i cofnąć 4s.

Wizualizacja: (nawiasy oznaczają, co zostanie przeniesione)

     _
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

Zamiast tego, aby wykonać tę pierwszą wymianę, najpierw przestawimy wszystkie 1 na drugi stos, przestawimy 5 na pierwszy stos (który jest teraz pusty), przestawimy 1 na trzeci stos, przestawimy 2 na pierwszy stosu, przenieś je z powrotem do pierwszego stosu, a na koniec przenieś 5 do drugiego stosu.

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

Teraz, gdy mamy wolne miejsce, na które można przenosić stosy (stos 2, który zawiera tylko 5, które umieszcza się w odpowiednim miejscu), możemy przenieść wszystkie 3s na stos 2 i umieścić 5 na stosie 3. Następnie możemy powtórzyć to samo dotyczy stosu 4, a teraz otrzymujemy wszystkie 5 w odpowiednim miejscu! I jeszcze jedna rzecz: przeniesiemy wszystkie 1 na stos 5, aby uzyskać dobrą konfigurację do następnej wymiany stosów.

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

Część 2: Zrób wszystko inne :)

Jest to teraz o wiele łatwiejsze, ponieważ teraz zawsze będziemy mieć wolny stos, aby przenieść inne liczby, do których musimy żonglować. Najpierw ustalimy, gdzie jest 4. Trochę analizy pokaże, że zawsze będzie to 1 w górę od miejsca rozpoczęcia lub 2 powyżej ostatniego stosu. Teraz po prostu zmniejszamy stosy, kładąc 4 na stosie, jeśli jest wolny, lub przesuwamy pozostałe liczby na 1 stos, jeśli nie jest. Teraz mamy wszystkie 4s na swoim miejscu.

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

Teraz zdajemy sobie sprawę, że 3s to 2 stosy powyżej, gdzie 4s gdzie. Oznacza to, że możemy zrobić dokładnie to samo, co zrobiliśmy z 4s! I jak się okazuje, możemy to robić, dopóki owiniemy indeks stosu na drugą stronę.

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

I tak możemy to robić, dopóki nie wymienimy wszystkich stosów.

Objaśnienie kodu:

Po pierwsze: (ważne) predefiniowane zmienne.

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

Istnieją 2 definicje 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?)

Wymiana stosu: część 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

Wymiana stosów: część 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

Wiem już, że nie dostaję punktów brownie, ponieważ widzę wiele bardziej wydajnych i bardziej skomplikowanych metod :(

K Zhang
źródło

Wymiana stosów