проблема

Скажем, у вас есть N стеков с именами от S ₁ до S _N , где каждый S _k (от k = 1 до N) содержит N копий числа k.

Например, когда N = 3, стеки выглядят так:

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

^{Здесь есть 3 стека, проиндексированных как 1, 2 и 3, и каждый содержит N экземпляров своего собственного индекса.}

Цель состоит в том, чтобы переставить N стеков так, чтобы каждое из них идентично содержало числа от 1 до N в порядке сверху вниз.

например, для N = 3 цель состоит в том, чтобы переставить стеки в:

Единственное действие, которое вы можете выполнить со стеками, - это взять верхний номер из одного из стеков (выталкивание), а затем немедленно поместить его поверх другого стека (толкание) . Это зависит от следующих условий:

Число может быть помещено в стек только в том случае, если оно меньше или равно верхнему числу в этом стеке.
- например, 1может быть выдвинут на стек с 1, 2или 3в верхней части, но 2может быть выдвинут только на стек с 2или 3(или выше) в верхней части.
- Это приводит к тому, что стеки всегда монотонно увеличиваются сверху вниз.
Любой непустой стек может быть извлечен, и, если предыдущий маркер удовлетворен, любой стек может быть передан.
Любое число может быть помещено в пустой стек.
Стеки не имеют ограничения по максимальной высоте.
Стеки не могут быть созданы или уничтожены, их всегда N.

Эта задача состоит в том, чтобы решить, какие щелчки и толчки нужно сделать, чтобы завершить обмен стека, причем не обязательно за наименьшее количество ходов, но безошибочно.

(Практика с колодой карт - хороший способ почувствовать проблему.)

Вызов

Напишите программу или функцию, которая принимает положительное целое число N, гарантированно равное 3 или выше. Выведите или верните строку, которая обозначает все всплывающие действия, необходимые для перестановки стеков из исходного состояния:

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

До конечного состояния:

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

Каждая строка в вашем выводе должна содержать два числа, разделенных пробелом. Первое число - это индекс стека для извлечения, а второе число - это индекс стека, к которому нужно выдвинуть. Выполнение действий всех линий по порядку должно правильно расставлять стеки, не нарушая никаких правил.

Например, вот потенциальный допустимый выход для случая 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

Заметки

Ваш вывод не должен быть оптимальным , только правильным. т.е. вам не нужно минимизировать количество всплывающих окон и толчков.
- Так что было бы хорошо, если бы, скажем, какой-то шаг был неоднократно сделан и немедленно изменен.
- Попадание в один и тот же стек за один ход, например 2 2, также разрешено (хотя, конечно, бессмысленно).
Ваш вывод делает потребность быть детерминированным и конечным.
Помните, что стеки имеют индексирование на основе 1. Индексирование на основе 0 не допускается.
N больше 9, конечно, должно работать так же хорошо, как однозначное число N.
При желании вы можете использовать любые два различных нецифровых печатаемых символа ASCII вместо пробелов и символов новой строки. Конечный символ новой строки (или заменитель новой строки) в выводе - это нормально.

счет

Самый короткий код в байтах побеждает. Ответ Tiebreaker выше.

Бесполезные очки брауни, если вы можете показать, что ваш алгоритм оптимален.

code-golf number data-structures Кальвин Хобби
источник

Остановимся на ерунде "дополнительные баллы за мелочи"> _>

user48538

@ zyabin101 Вы только что потеряли шанс на пирожные.

Увлечения Кэлвина

Вы всегда придумываете такие замечательные названия!

Луис Мендо

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

user48538

Является ли возможный вывод, который вы включаете для случая N=3оптимального?

Р. Кап

Pyth 96 94 байта

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

Попробуй здесь

Как это работает?

Это объяснение будет использовать N = 5.

Часть 1. Создание нижнего слоя в каждом стеке

Причина, по которой для этого нужен отдельный фрагмент кода, заключается в том, что необходимо использовать каждый стек: первым 4 нужно поместить 5 под ними, а последний стек должен предоставить 5. Это означает, что мы не можем просто переместить все четверки куда-либо, поставить туда 5 и сдвинуть четверки назад.

Визуализация: (круглые скобки означают, что будет перемещено)

     _
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

Вместо этого, чтобы сделать этот первый обмен, мы сначала переместим все 1 во второй стек, переместим 5 в первый стек (который теперь пуст), переместим 1 в третий стек, переместим 2 в первый стек, переместите 1 обратно в первый стек и, наконец, 5 во второй стек.

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

Теперь, когда у нас есть свободное пространство для перемещения стеков (стек 2, который содержит только 5, который помещен в правильное место), мы можем переместить все 3 с в стек 2 и поместить 5 в стек 3. Затем мы можем повторить то же самое для стека 4, и теперь мы получаем все 5 в нужном месте! И еще одна вещь: мы переместим все 1 в стек 5, чтобы получить хорошую настройку для следующего обмена стека.

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

Часть 2: Делай все остальное :)

Теперь это намного проще, потому что теперь у нас всегда будет свободный стек для перемещения других чисел, в которые нам нужно перетасовываться. Итак, сначала мы выясним, где находится 4. Немного изучения покажет, что он всегда будет на 1 выше, чем с начала, или на 2 выше последнего стека. Теперь мы просто продолжаем идти вниз по стопкам, помещая 4 в стек, если он свободен, или перемещая другие числа на 1 стопку, если это не так. Теперь у нас есть все четверки на месте.

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

Теперь мы понимаем, что 3s на 2 стека выше, где 4s, где. Это означает, что мы можем сделать то же самое, что и с 4-мя! И, как оказалось, мы можем продолжать делать это до тех пор, пока не перевернем индекс стека на другую сторону.

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

И так, мы можем продолжать делать это, пока мы не обменяем все стеки.

Объяснение кода:

Прежде всего: (важные) предопределенные переменные.

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

Есть 2 лямбда-определения.

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

Обмен стеком: часть 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

Обмен стеком: часть 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

Я уже знаю, что я не получаю очки брауни, потому что я вижу много более эффективных и более сложных методов :(

К Чжан
источник

Обмен стека