Masalah

Katakanlah Anda memiliki N tumpukan bernama S ₁ hingga S _N , di mana setiap S _k (k = 1 hingga N) berisi N salinan dari angka k.

Misalnya, ketika N = 3 tumpukan terlihat seperti ini:

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

^{Di sini ada 3 tumpukan yang diindeks sebagai 1, 2, dan 3, dan masing-masing berisi N contoh indeksnya sendiri.}

Tujuannya adalah untuk mengatur ulang tumpukan N sedemikian rupa sehingga masing-masingnya secara identik berisi angka 1 hingga N secara berurutan dari atas ke bawah.

misalnya untuk N = 3 tujuannya adalah untuk mengatur ulang tumpukan menjadi:

Satu-satunya tindakan yang dapat Anda lakukan dengan tumpukan adalah mengambil nomor atas dari salah satu tumpukan (muncul) kemudian segera menempatkannya di atas tumpukan yang berbeda (mendorong) . Ini tunduk pada ketentuan ini:

Angka hanya dapat didorong ke tumpukan jika kurang dari atau sama dengan nomor teratas di tumpukan itu.
- misalnya 1dapat didorong ke stack dengan 1, 2atau 3di bagian atas, tetapi 2hanya dapat didorong ke stack dengan 2atau 3(atau lebih tinggi) di bagian atas.
- Ini memiliki efek bahwa tumpukan selalu meningkat secara monoton dari atas ke bawah.
Setiap tumpukan kosong dapat muncul dari, dan, dengan asumsi peluru sebelumnya puas, tumpukan apa pun dapat didorong ke.
Jumlah apa pun dapat didorong ke tumpukan kosong.
Tumpukan tidak memiliki batas ketinggian maksimum.
Tumpukan tidak dapat dibuat atau dihancurkan, selalu ada N dari mereka.

Tantangan ini adalah tentang memutuskan muncul dan dorongan yang harus dilakukan untuk menyelesaikan pertukaran tumpukan, tidak harus dalam gerakan paling sedikit, tetapi dengan cara yang pasti.

(Berlatih dengan setumpuk kartu adalah cara yang baik untuk merasakan masalahnya.)

Tantangan

Tulis program atau fungsi yang mengambil dalam bilangan bulat positif N, dijamin 3 atau di atas. Cetak atau kembalikan string yang menunjukkan semua tindakan pop-push yang diperlukan untuk mengatur ulang tumpukan dari kondisi awal:

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

Ke kondisi akhir:

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

Setiap baris dalam output Anda harus berisi dua angka yang dipisahkan oleh spasi. Angka pertama adalah indeks tumpukan untuk muncul dan nomor kedua adalah indeks tumpukan untuk didorong. Melakukan tindakan semua lini agar mengatur tumpukan dengan benar tanpa melanggar aturan.

Sebagai contoh, berikut ini adalah output potensial yang valid untuk kasus 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

Catatan

Output Anda tidak perlu optimal , hanya benar. yaitu Anda tidak perlu meminimalkan jumlah muncul dan dorongan.
- Jadi tidak apa-apa jika, katakanlah, beberapa gerakan dilakukan berulang kali dan segera dibalik.
- Popping dan mendorong ke stack yang sama dalam satu gerakan, misalnya 2 2, diizinkan juga (meskipun tentu saja tidak ada gunanya).
Output Anda memang harus deterministik dan terbatas.
Ingat bahwa tumpukan memiliki pengindeksan berbasis 1. Pengindeksan berbasis 0 tidak diizinkan.
N lebih besar dari 9 tentu saja harus berfungsi sama seperti satu digit N.
Jika diinginkan, Anda dapat menggunakan dua karakter ASCII yang berbeda dan tidak dapat dicetak untuk menggantikan spasi dan baris baru. Baris baru yang tertinggal (atau pengganti baris baru) dalam output baik-baik saja.

Mencetak gol

Kode terpendek dalam byte menang. Tiebreaker adalah jawaban dengan suara lebih tinggi.

Poin brownies berharga jika Anda dapat menunjukkan algoritma Anda optimal.

code-golf number data-structures Hobi Calvin
sumber

Hentikan dengan "poin ekstra untuk hal-hal kecil" omong kosong> _>

user48538

@ zyabin101 Anda baru saja kehilangan peluang di brownies.

Hobi Calvin

Anda selalu datang dengan judul yang luar biasa!

Luis Mendo

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

user48538

Apakah output yang mungkin Anda sertakan untuk kasus N=3optimal?

R. Kap

Pyth 96 94 byte

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

Coba di sini

Bagaimana cara kerjanya?

Penjelasan ini akan menggunakan N = 5.

Bagian 1: Buat lapisan bawah pada setiap tumpukan

Alasan mengapa hal ini memerlukan bagian kode yang terpisah adalah karena setiap tumpukan perlu digunakan: 4 yang pertama membutuhkan 5 untuk diletakkan di bawahnya, dan tumpukan terakhir harus menyediakan 5s. Ini berarti bahwa kita tidak bisa hanya memindahkan semua 4 di suatu tempat, meletakkan 5 di sana, dan memindahkan 4s kembali.

Visualisasi: (tanda kurung berarti apa yang akan dipindahkan)

     _
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

Sebagai gantinya, untuk melakukan pertukaran pertama ini, pertama-tama kita akan memindahkan semua 1s ke ke tumpukan kedua, memindahkan 5 ke tumpukan pertama (yang sekarang kosong), memindahkan 1s ke tumpukan ketiga, memindahkan 2s ke yang pertama stack, pindahkan 1s kembali ke stack pertama, dan akhirnya pindahkan 5 ke stack kedua.

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

Sekarang kita memiliki ruang kosong untuk memindahkan tumpukan (stack 2, yang hanya berisi 5 yang ditempatkan di tempat yang tepat), kita dapat memindahkan semua 3s ke stack 2 dan menempatkan 5 dalam stack 3. Kita kemudian dapat mengulangi hal yang sama untuk stack 4, dan sekarang kita mendapatkan semua 5 di tempat yang tepat! Dan satu hal lagi: kita akan memindahkan semua 1 untuk menumpuk 5 sehingga kita mendapatkan pengaturan yang bagus untuk pertukaran tumpukan berikutnya.

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

Bagian 2: Lakukan segalanya :)

Ini jauh lebih mudah sekarang, karena sekarang kita akan selalu memiliki tumpukan gratis untuk memindahkan nomor-nomor lain yang perlu kita juggle. Jadi, pertama-tama kita mencari tahu di mana angka 4 itu. Sedikit pemeriksaan akan menunjukkan bahwa ia akan selalu naik dari awal, atau 2 di atas tumpukan terakhir. Sekarang, kita teruskan ke tumpukan, menempatkan 4 di tumpukan jika gratis, atau memindahkan nomor lainnya naik 1 tumpukan jika tidak. Sekarang kita memiliki semua 4s di tempatnya.

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

Sekarang, kami menyadari bahwa 3s adalah 2 tumpukan di atas tempat 4s di mana. Ini artinya kita bisa melakukan hal yang sama persis dengan yang kita lakukan dengan 4s! Dan ternyata, kita bisa terus melakukan ini selama kita membungkus indeks tumpukan ke sisi lain.

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

Jadi, kita bisa terus melakukan ini sampai kita menukar semua tumpukan.

Penjelasan kode:

Pertama-tama: Variabel predefined (penting).

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

Ada 2 definisi 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?)

Pertukaran stack: bagian 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

Pertukaran stack: bagian 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

Saya sudah tahu saya tidak mendapatkan poin brownies, karena saya bisa melihat banyak metode yang lebih efisien dan lebih rumit :(

K Zhang
sumber

Susun Bertukar