Pecahkan puzzle 14-Pasak

8

pengantar

Teka-teki umum melibatkan papan segitiga dengan 15 lubang untuk tee / pasak seperti yang ditunjukkan pada gambar di bawah ini:

Contoh gambar pasak papan

Dimulai dengan semua pasak di papan kecuali untuk lubang di bagian atas, titik teka-teki adalah untuk melompati pasak satu sama lain seperti checker sedemikian rupa untuk meninggalkan tepat satu pasak tersisa. Satu-satunya langkah yang valid adalah dengan melompati satu pasak ke pasak yang berdekatan ke segala arah ke lubang kosong. Pasak yang dilompati kemudian dihapus dari papan. Putar selesai saat tidak ada gerakan yang valid.

Spec

Tugas Anda adalah menulis sebuah program yang dapat menemukan solusi lengkap untuk teka-teki pasak, yaitu, yang hanya menyisakan satu pasak tersisa. Ada beberapa kemungkinan solusi, jadi program Anda hanya perlu mencetak satu.

  • Program Anda tidak akan menerima input. Anda tidak diperbolehkan membaca data dari sumber luar apa pun.
  • Cetak daftar 13 gerakan yang memberikan hasil 1 pasak tersisa menggunakan format ini:

    Peg 1 jumps Peg 3 to Hole 6.

  • Lubang / pasak diberi nomor dari atas ke bawah, kiri ke kanan, sehingga pasak / lubang atas adalah 1, penomoran hingga kanan bawah adalah 15.
  • Program Anda harus menemukan solusinya saat runtime . Mencetak solusi secara langsung dengan cara apa pun selain menyelesaikannya dalam program adalah diskualifikasi otomatis.
  • Bonus : menerima 10 poin bonus jika Anda dapat menghasilkan beberapa solusi unik (hanya dapat mencetak dipisahkan oleh garis kosong).
  • Bonus : menerima 5 poin bonus jika nomor 15tidak muncul di kode sumber Anda.

Mencetak gol

Ini adalah kode-golf, jadi solusi terpendek (dengan jumlah byte) yang mencetak jawaban yang benar akan menjadi pemenang. Poin bonus dikurangi dari jumlah total byte Anda. Harap berikan contoh hasil dari menjalankan program Anda serta tautan ke ideoneatau beberapa situs serupa jika mungkin menunjukkan eksekusi program Anda.

mellamokb
sumber
Bagaimana Anda menggabungkan poin bonus dengan kriteria kemenangan objektif, yang hanya dapat kita anggap sebagai jumlah karakter karena ini memiliki tag kode-golf?
JB
Klarifikasi tambahan "Poin bonus dikurangi dari jumlah total byte Anda.", Apakah itu masuk akal?
mellamokb
bonus kedua terlalu mudah diperoleh,15=0xff=(1<4)-1=~(-1<<4)=...
ratchet freak
3
Beberapa representasi Anda>> = 5 karakter lebih panjang dari 15dirinya sendiri;)
mellamokb

Jawaban:

8

Ruby, skor 240 238 234 = 249 - 10 - 5

s=->t,r,c{c>0?(t+t.reverse).gsub(/[A-O]{2}[a-o]/){|j|s[t.tr(j,j.swapcase),r+"Peg #{j[0].ord-64} jumps Peg #{j[1].ord-64} to Hole #{j[2].ord-96}.\n",c-1]}:$><<r+"\n"}
s["aBD,BDG,DGK,CEH,EHL,FIM,aCF,CFJ,FJO,BEI,EIN,DHM,DEF,GHI,HIJ,KLM,LMN,MNO,","",13]

Implementasi ruby ​​biasa yang mencetak semua solusi yang memungkinkan untuk puzzle ini (membutuhkan waktu kurang dari satu menit di komputer saya). Baris pertama dari output dapat dilihat di sini:

Peg 6 jumps Peg 3 to Hole 1.
Peg 4 jumps Peg 5 to Hole 6.
Peg 1 jumps Peg 2 to Hole 4.
Peg 14 jumps Peg 9 to Hole 5.
Peg 7 jumps Peg 8 to Hole 9.
Peg 12 jumps Peg 13 to Hole 14.
Peg 10 jumps Peg 6 to Hole 3.
Peg 4 jumps Peg 5 to Hole 6.
Peg 3 jumps Peg 6 to Hole 10.
Peg 15 jumps Peg 10 to Hole 6.
Peg 6 jumps Peg 9 to Hole 13.
Peg 14 jumps Peg 13 to Hole 12.
Peg 11 jumps Peg 12 to Hole 13.

Peg 6 jumps Peg 3 to Hole 1.
Peg 4 jumps Peg 5 to Hole 6.
Peg 1 jumps Peg 2 to Hole 4.
Peg 14 jumps Peg 9 to Hole 5.
Peg 7 jumps Peg 8 to Hole 9.
...

Dan contoh online dapat ditemukan di sini .

Howard
sumber
Saya ingin tahu berapa banyak solusi total yang ada?
mellamokb
@ellamokb Dikatakan ada 29760 solusi.
Howard
4
Solusi 29760? Ketika saya pertama kali mengetahui tentang permainan ini, aku butuh selamanya untuk menemukan satu .
PhiNotPi
2
Itu aneh. Ada 2 ^ 14 (16384) status dewan dan mungkin tidak semuanya dapat dijangkau. Saya berani bertaruh ada solusi kurang dari negara.
kaoD
2
@ kaoD: Sebuah solusi sebenarnya adalah urutan 13 gerakan (13 negara berturut-turut dari kondisi papan asli), yang secara teknis ada (2 ^ 15) ^ 13 kemungkinan unik, dan yang sebagian besar sangat tidak benar berdasarkan aturan . Sebenarnya ada juga 2 ^ 15 (32768) kemungkinan status papan karena ada 15 lubang yang dapat diisi atau dikosongkan (yang segelintir tidak relevan sejak papan dimulai dengan sebuah lubang)
mellamokb
3

Python, 324 karakter, skor = 319

f=0xf
x=0x12413624725935836a45647b48d58c59e69d6af78989abcdcdedef
Z=[(x>>12*i&f,x>>12*i+4&f,x>>12*i+8&f)for i in range(18)]
M=[[65532,'']]
for i in' '*13:
 Q=[]
 for p,m in M:
  for a,b,c in[x[::-1]for x in Z]+Z:
   if p>>a&p>>b&~p>>c&1:Q+=[[p^2**a^2**b^2**c,m+"Peg %d jumps Peg %d to Hole %d.\n"%(a,b,c)]]
 M=Q
print M[0][1]

Status pasak disimpan sebagai bitmask. Mberisi daftar negara pasak dan instruksi untuk sampai ke keadaan itu.

Saya bisa membuatnya mencetak semua solusi juga (ada 29.760 di antaranya), tetapi akan membutuhkan biaya lebih dari 10 karakter untuk melakukannya.

Saya tidak dapat mempostingnya di ideone karena membutuhkan waktu sekitar 90 detik untuk berjalan.

Keluaran:

Peg 6 jumps Peg 3 to Hole 1.
Peg 4 jumps Peg 5 to Hole 6.
Peg 1 jumps Peg 2 to Hole 4.
Peg 14 jumps Peg 9 to Hole 5.
Peg 12 jumps Peg 13 to Hole 14.
Peg 7 jumps Peg 8 to Hole 9.
Peg 10 jumps Peg 6 to Hole 3.
Peg 4 jumps Peg 5 to Hole 6.
Peg 3 jumps Peg 6 to Hole 10.
Peg 15 jumps Peg 10 to Hole 6.
Peg 6 jumps Peg 9 to Hole 13.
Peg 14 jumps Peg 13 to Hole 12.
Peg 11 jumps Peg 12 to Hole 13.
Keith Randall
sumber
Anda hanya perlu mencetak minimal 2 solusi untuk menerima bonus 10 poin.
mellamokb
3

C, 386 karakter, skor = 371

int f[37],o[36],t[36],r[14],i[14],m=1,s=~3,j=18;main(){while(j--)o[j]=o[18+j]=(f[j]=t[18+j]="AABBCCDDDEEFFGHKLM"[j]-64)+(t[j]=f[18+j]="DFGIHJKMFLNMOIJMNO"[j]-64)>>1;while(m)if(!f[++j])s=r[--m],j=i[m];else if(s>>f[j]&s>>o[j]&~s>>t[j]&1)if(r[m]=s,s^=1<<f[j]|1<<o[j]|1<<t[i[m]=j],j=-1,++m>13)for(m=printf("\n");m<14;++m)printf("Peg %d jumps Peg %d to Hole %d.\n",f[i[m]],o[i[m]],t[i[m]]);}

Mencetak semua 29760 solusi, dalam waktu kurang dari satu detik.

Versi ini mengasumsikan (antara lain) bahwa kompiler akan mengizinkan deklarasi printf () secara implisit. Sekitar enam karakter lagi dapat disimpan dengan memanfaatkan implisit-int, tetapi fitur itu secara teknis dihapus dari C99.

Juga, empat byte lagi dapat disimpan dengan mengganti huruf kapital dalam dua string dengan karakter kontrol yang sesuai. Saya tidak melakukannya di sini karena kompiler tidak diharuskan untuk mengizinkan string seperti itu, dan itu membuat kode sumber yang sudah padat benar-benar tidak terbaca.

Untuk kejelasan, inilah algoritma yang sama tanpa optimasi ukuran yang lebih membingungkan:

#include <stdio.h>
int f[37], o[36], t[36], r[14], i[14], m, j, s = ~3;
int main(void)
{
    for (j = 0 ; j < 18 ; ++j) {
        f[j] = t[18+j] = "AABBCCDDDEEFFGHKLM"[j] - 64;
        t[j] = f[18+j] = "DFGIHJKMFLNMOIJMNO"[j] - 64;
        o[j] = o[18+j] = (f[j] + t[j]) >> 1;
    }
    j = 0;
    for (m = 1 ; m ; ++j) {
        if (!f[j]) {
            --m;
            s = r[m];
            j = i[m];
        } else if ((s >> f[j]) & (s >> o[j]) & (~s >> t[j]) & 1) {
            r[m] = s;
            i[m] = j;
            s ^= (1 << f[j]) | (1 << o[j]) | (1 << t[j]);
            j = -1;
            ++m;
            if (m > 13) {
                printf("\n");
                for (m = 1 ; m < 14 ; ++m)
                    printf("Peg %d jumps Peg %d to Hole %d.\n",
                           f[i[m]], o[i[m]], t[i[m]]);
            }
        }
    }
    return 0;
}

f, o, dan t adalah daftar lompatan legal yang diinisialisasi pada loop pertama. r dan i membentuk sejarah yang digunakan program untuk mundur dan menjelajahi semua game yang mungkin.

Saya yakin ini bisa diperbaiki!

kotak roti
sumber
Ada penghematan satu-ar di inisialisasi yang diganti >>1oleh /2.
Peter Taylor
Menggunakan / bukannya >> akan membutuhkan parens di sekitar penambahan.
kotak roti
Ah, salah membaca parens karena mereka berbeda dengan yang tidak diserang.
Peter Taylor