Masalah Pertukaran Kereta yang Diperpanjang

Bagian 1: Masalah Pertukaran Kereta Normal

Dalam CCC 1996 (Kompetisi Komputasi Kanada), masalah Tahap 2 pertama adalah Masalah Penukaran Kereta. Anda dapat mengunjungi tautan di sini . Pada dasarnya, Anda memiliki banyak kereta bernomor, dan Anda ingin mencari tahu berapa banyak kereta yang perlu Anda peroleh secara berurutan, dan setiap operasi pertukaran kereta memungkinkan Anda untuk menukar dua kereta yang berdekatan. Karena gerbong kereta bisa berjalan dengan baik, tidak ada yang peduli dengan kenyataan bahwa gerbong kereta menghadapi sebaliknya ketika ditukar. Ini cukup mudah; yang perlu Anda lakukan adalah:

Temukan jumlah langkah untuk mengurutkannya; itu adalah algoritma penyortiran yang paling efisien ketika Anda hanya dapat melakukan swap elemen yang berdekatan

Jadi, saya membuat yang lebih sulit.

Bagian 2: Cara kerja tantangan ini

Pada dasarnya, Anda sekarang dapat bertukar lebih dari sekadar kereta yang berdekatan. Dengan platform yang lebih panjang, Anda dapat menukar posisi beberapa kereta. Misalnya, dengan platform yang berputar panjang 4, Anda dapat menukar kedua pasangan dalam dan luar pada saat yang sama, sehingga 1 2 3 4menjadi 4 3 2 1. Berikut adalah beberapa contoh untuk berbagai ukuran platform berputar:

Length 2:
1 2 3 4 5
  ---
1 3 2 4 5

Length 3:
1 2 3 4 5
  -----
1 4 3 2 5

Length 4:
1 2 3 4 5
-------
4 3 2 1 5

Pada dasarnya, Anda hanya membalikkan sublist seluruh kereta. Untuk memperjelas, dalam setiap gerakan, Anda hanya bisa menukar kereta dengan tepat N .

Bagian 3: Spesifikasi

Memasukkan

Masukan Anda harus mencakup dua hal: panjang platform yang berputar, dan urutan gerbong kereta. Anda juga mungkin memerlukan jumlah gerbong kereta jika diinginkan. Urutan gerbong kereta diberikan oleh daftar nomor yang diurutkan (setiap nomor mewakili gerbong kereta), sehingga Anda dapat membaca input sebagai bilangan bulat yang dipisahkan ruang, bilangan bulat yang dipisahkan oleh baris baru, bilangan, dll.

Keluaran

Anda harus menampilkan jumlah swap optimal (minimum) yang diperlukan untuk memasukkan semua carriage ke dalam pesanan 1 2 3 ... N. Jika tidak ada solusi, keluaran -1, No solutionatau beberapa pesan yang konsisten lainnya. Anda mungkin tidak menghasilkan ke stderr.

Mencetak gol

Ini adalah tantangan kode-golf , jadi penilaian dilakukan dalam byte. Solusi dengan jumlah byte terendah pada 1 September 2016 akan menjadi solusi yang diterima.

Contohnya

Masalah 1 Input

4
2
1 3 2 4

Keluaran

1

Penjelasan
Ini sangat sepele; dengan platform berputar dengan panjang 2, itu sama dengan masalah pertukaran kereta normal. Tukar 2dan 3.

Masalah 2 Input

4
3
1 3 2 4

Keluaran

No solution (or an equivalent consistent message).

Masalah 3 Input

9
3
1 4 5 6 3 8 7 2 9

Keluaran

4

Penjelasan

1 4 5 6 3 8 7 2 9
          -----
1 4 5 6 3 2 7 8 9
      -----
1 4 5 2 3 6 7 8 9
    -----
1 4 3 2 5 6 7 8 9
  -----
1 2 3 4 5 6 7 8 9

Celah standar berlaku

Semoga berhasil!

EDIT 1 : Membuat format input lebih fleksibel. Terima kasih kepada @Mego!
EDIT 2 : Klarifikasi bahwa platform putar dengan panjang 4 menukar pasangan dalam dan luar. Terima kasih kepada @TimmyD!
EDIT 3 : Mengklarifikasi bahwa Anda harus membuat permutasi dengan panjang Npersis, paling banyak. Terima kasih kepada @Zgarb!

Perl, 120 byte

Termasuk +6 untuk -Xapi( -dan spasi juga dihitung karena kedua -idan $'dalam kode membuatnya tidak mungkin untuk menggabungkan opsi dengan -e)

Jalankan dengan input pada STDIN dan panjang platform setelah -iopsi, mis

perl -Xapi3 trains.pl <<< "1 4 5 6 3 8 7 2 9"

Mencetak -2jika tidak ada solusi

trains.pl:

1until$_=$n++*$z{pack"W*",@F}||-!grep!$z{$_}++&&/.{$^I}(??{!\$z{$`.reverse($&).$'}})$/s,keys%z,pack"W*",1..@F;$_--

jika N <= 9kemudian Anda bisa mendapatkan 5 byte lebih banyak:

1until$_=$n++*$z{join"",@F}||-!grep!$z{$_}++&&/.{$^I}(??{!\$z{$`.reverse($&).$'}})$/,keys%z,join"",1..@F;$_--