Periksa apakah 15 puzzle dapat dipecahkan

9

The lima belas teka-teki adalah aneh dalam bahwa hanya setengah negara-negara yang mungkin pengaturan yang dipecahkan. Jika Anda membalik 14 dan 15 ubin, tidak mungkin Anda bisa menggeser balok sehingga dibalik.

Tugas Anda adalah membuat program yang menerima daftar bilangan bulat dalam format pilihan Anda (berisi persis satu contoh dari setiap angka dari 0 hingga 15, dengan 0 sebagai ruang kosong) yang mewakili keadaan susunan ubin di kisi 4x4, dan menampilkan nilai boolean tunggal yang menentukan apakah kisi tersebut dapat dipecahkan atau tidak.

Kode terpendek untuk melakukan ini dalam bahasa apa pun menang.

Joe Z.
sumber
Pertanyaan bagus :)
Cruncher
Saya akan mengajukan pertanyaan ini, tetapi dengan panjang lebar sewenang-wenang; tapi itu menambah sedikit tantangan.
Jonathan Allan

Jawaban:

0

Jelly , 9 byte

Œc>/€;TSḂ

Tautan monadik yang menerima daftar bilangan bulat yang membaca dalam urutan baris-utama bergantian antara kiri-kanan dan kanan-kiri yang menghasilkan 0jika dipecahkan dan 1jika tidak (untuk membalikkan ini tambahkan ¬ke kanan kode).

Cobalah online! (contoh ini adalah papan di mana 12 hanya perlu meluncur ke tempatnya)

Bagaimana?

Mirip dengan jawaban John Dvorak, kami menghitung paritas dan menggunakan urutan input seperti ular untuk menyederhanakan paritas checker-board, meskipun alih-alih memeriksa persamaan paritas, kami menjumlahkan jumlah out-of-order dengan indeks non-nol dan menguji apakah itu aneh:

Œc>/€;TSḂ - Link: list of integers
Œc        - unordered pairs
    €     - for each:
   /      -   reduce with:
  >       -     greater than?
      T   - truthy indices (i.e. [1..16] without 1-indexed index of 0)
     ;    - concatenate
       S  - sum
        Ḃ - is odd?
Jonathan Allan
sumber
4

J, 28 karakter

((C.!.2=_1^i.&0)&.".&.stdin''

Urutan input adalah baris-utama dengan baris yang dibaca bergantian dari kiri ke kanan dan kanan ke kiri dalam satu jalur di seberang tabel. Diasumsikan nol milik sudut kiri atas.

Penggunaan di Windows:

<nul set /p="0 1 2 3 7 6 5 4 8 9 10 11 15 14 13 12" | jconsole c:\...\15.jhs

Penjelasan:

  • <nul set /p=digunakan untuk mencegah baris baru dalam input, yang echomenghasilkan yang ".tidak suka. Tentu saja, Unix mendukung echo /n.
  • v&.".&.stdin''membaca "v under parse di bawah stdin" berarti "input, lalu parsing input, lalu lakukan v, lalu unduh parse (= format), lalu undo input (= output)". 1!:1]3lebih pendek satu karakter, tetapi tidak memiliki invers yang ditentukan.
  • C.!.2berarti "paritas permutasi". Ia mengembalikan 1(bahkan paritas) atau _1(paritas ganjil). Itu adalah,_1^inversions
  • _1^i.&0 berarti "-1 pangkat indeks 0".
  • dengan demikian, C.!.2=_1^i.&0berarti "apakah paritas permutasi sama dengan paritas posisi lubang?"

Ini berfungsi untuk papan 4x4, tetapi jika posisi ujung yang diinginkan adalah baris-utama kiri-ke-kanan, maka permutasi untuk posisi yang diselesaikan memiliki jumlah ganjil inversi, dan dengan demikian paritas ganjil. Juga, paritas dibalik (untuk urutan input apa pun) ketika posisi lubang yang diinginkan bergerak dari kiri atas ke kanan bawah. Dalam kedua kasus, perbaikannya adalah satu karakter: tambahkan -setelah =untuk membalikkan paritas yang diharapkan.

Bukti kebenaran:

Setelah setiap gerakan, nol bertukar posisi dengan beberapa angka, membalikkan paritas permutasi. Angka nol juga bergantian antara posisi kotak-kotak putih dan hitam, ditunjukkan oleh posisi ganjil dan genap dalam pemesanan input. Dengan demikian, kondisi ini perlu. Ini juga cukup dengan argumen penghitungan: sudah menjadi rahasia umum bahwa separuh dari posisi itu bisa dipecahkan. Kondisi ini menyaring tepat setengah dari posisi yang mungkin.

John Dvorak
sumber
Ketika Anda mengatakan "nol juga berganti-ganti antara posisi ganjil dan genap": bukankah itu berubah +1, -1, +4, atau -4? Saya pikir bahwa pola yang diperiksa memberikan pewarnaan yang Anda butuhkan, tetapi bisa dijelaskan lebih akurat.
Peter Taylor
@PeterTaylor Anda benar; Maaf. Apakah hasil edit saya dihitung sebagai perbaikan yang valid?
John Dvorak
Saya pikir edit Anda membahas masalah yang sepenuhnya terpisah. Bit yang saya kutip ada di paragraf terakhir.
Peter Taylor
"Antara posisi ganjil dan genap" lebih seperti "antara kotak hitam dan putih di papan catur".
Joe Z.