Problem
Powiedzmy, że masz N stosów o nazwach od S 1 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:
1 1 1
2 2 2
3 3 3
=======
1 2 3
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 z1,2lub3od góry, ale2może być popychany na stos tylko z2albo3(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.
-._(._.)_.-
N=3optymalnego?