pengantar
Anda mengalami kemalangan terjebak di mobil yang sedang melaju di jalur rintangan. Semua fitur mobil tidak responsif, kecuali untuk sistem kemudi, yang rusak. Itu bisa melaju lurus, atau bisa belok kanan. Bisakah mobil dipandu ke tempat yang aman?
Mekanika
Mobil Anda mulai di sudut kiri atas peta 8x8, dan mencoba untuk mendapatkan keselamatan di sudut kanan bawah. Mobil itu memiliki orientasi (awalnya ke kanan), diukur dalam peningkatan 90 derajat. Mobil dapat melakukan salah satu dari dua tindakan:
- Drive satu persegi ke depan, atau
- Putar 90 derajat searah jarum jam, lalu dorong satu kotak ke depan
Perhatikan bahwa mobil tidak dapat berbelok cukup tajam untuk melakukan putaran 180 derajat pada satu kotak.
Beberapa kotak adalah hambatan. Jika mobil memasuki rintangan, itu menabrak. Segala sesuatu di luar jalur 8x8 diasumsikan sebagai hambatan, jadi mengendarai jalur itu sama dengan menabrak.
Kotak kanan bawah adalah kotak yang aman, yang memungkinkan mobil untuk keluar dari rintangan. Alun-alun awal dan kotak aman diasumsikan tidak menjadi hambatan.
Tugas
Anda harus menulis sebuah program atau fungsi yang memasukkan input array 8x8 (matriks, daftar daftar, dll.), Yang mewakili jalur rintangan. Program mengembalikan atau mencetak Boolean, atau sesuatu yang serupa kebenarannya. Jika mungkin bagi mobil untuk sampai ke kotak aman tanpa menabrak (yaitu, jika peta dipecahkan), hasilnya adalah True
, sebaliknya, itu False
.
Mencetak gol
Aturan golf kode standar - pemenangnya adalah kode dengan byte paling sedikit.
Bonus:
Jika, untuk peta yang dapat dipecahkan, kode Anda menghasilkan serangkaian input driver yang valid yang memandu mobil ke kotak yang aman, kurangi 10 poin persentase dari skor Anda. Contoh format output mungkin
SRSSR
(menunjukkan Lurus, Kanan, Lurus, Lurus, Kanan). Output ini akan menggantikanTrue
output standar .Jika, untuk peta yang tidak dapat dipecahkan, output kode Anda membedakan antara situasi di mana crash tidak dapat dihindari, dan situasi di mana dimungkinkan untuk berkendara di sekitar rintangan selamanya, kurangi 10 poin persentase dari skor Anda. Contoh output mungkin
Crash
jika kecelakaan tidak dapat dihindari, atauStuck
jika mobil macet di rintangan selamanya. Output ini akan menggantikanFalse
output standar untuk peta yang tidak dapat diselesaikan.
Contoh
Jika program diberikan array 8x8 seperti ini:
[[0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0],
[1, 1, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 1, 0, 0, 0, 0],
[0, 0, 1, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 1, 0],
[0, 1, 1, 0, 0, 0, 1, 0]]
Ini akan ditafsirkan sebagai peta seperti ini, dengan kotak hitam menunjukkan hambatan:
Dan solusi yang mungkin adalah:
Karena ada solusi, program harus mengembalikan / mencetak True
untuk peta ini. Urutan gerakan yang ditunjukkan di sini adalah SSSSRSRRRSRSSRRRSSRSSS
.
Crash
danStuck
. Mereka ada di sini karena berapa lama mereka. Baris 2 terisi, semuanya kosong ->Crash
. Baris 7 terisi, semuanya kosong ->Stuck
Jawaban:
JavaScript (ES6) - 122
124148byte162172178187190193208Terima kasih banyak kepada Pengoptimal dan DocMax untuk saran yang bermanfaat tentang cara meningkatkan kode ini:
Pengembalian
true
(kebenaran) untuk dipecahkan danfalse
(palsu) untuk tidak terpecahkan.Hanya berfungsi di Firefox pada hari ini karena fitur JavaScript 1.7.
Papan Uji
sumber
D=(x,y,d,t,a)=>!t[i=x+y*8+d*64]&&(t[i]=1,x+=d==0?1:d==2?-1:0,y+=d==1?1:d==3?-1:0,x==7&&y==7||!((x|y)&~7||a[y][x])&&G(x,y,d,t,a));G=(x,y,d,t,a)=>D(x,y,d,t,a)||D(x,y,d+1&3,t,a);F=a=>G(0,0,0,[],a)
.D=d=>!t[i=x+y*8+d/4]&&(t[i]=1,x+=d?d^2?0:-1:1,y+=d^1?d^3?0:-1:1,x==7&&y==7||!((x|y)&~7||b[y][x])&&G(x,y,d));G=(X,Y,d)=>D(d,x=X,y=Y)||D(d+1&3,x=X,y=Y);F=a=>G(0,0,0,b=a,t={})
- Diuji.[[0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0]]
. Itu harus memberi salah.x
dany
keduanya adalah global, Anda tidak dapat menjalankan dua testcas sebelum memuat ulang halaman ...x+=d?d^2?0:-1:1
denganx+=d&1?0:1-d
dany+=d^1?d^3?0:-1:1
dengany+=d&1&&2-d
.Python 2 - 123
125 133 146 148 150 154 160True
pada kesuksesan,False
pada kegagalan.Anda harus memberikan input seperti
f(b=var_containing_board)
.Versi Lambda - 154
Pengembalian
0
(falsy) untuk kegagalan,True
untuk kesuksesan.Terima kasih kepada Will dan Brandon karena membuat fungsinya lebih pendek dari lambda. Juga untuk menambahkan lebih banyak scroll horisontal: D
Terima kasih kepada xnor untuk bashing-bit dan logika superior!
Sunting catatan: Saya cukup yakin bahwa
b[y][x]
tidak akan pernah dieksekusi ketika keluar dari jangkauan. Karena kita berada di luar papan, pemeriksaan sejarahs in c
akan dilakukanFalse
. Maka pemeriksaan batas(x|y)&8
akan8
. Maka python bahkan tidak akan memeriksa nilai terakhir==
karena dua yang pertama sudah berbeda.sumber
x|y>7or
bekerja tetapix|y<0or
tidak ...0o
.C (GNU-C), 163 byte * 0,9 = 146,7
#C (GNU-C), 186 byte * 0.9 = 167.4Versi baru saya menggunakan bilangan bulat yang ditandatangani daripada tidak ditandatangani. Sebelumnya saya takut menandatangani shift kanan, tetapi saya menyadari karena bit tanda adalah kotak tujuan, tidak masalah apa yang terjadi setelah itu.
Fungsi ini mengambil array bit (yang mewakili kotak yang diblokir) dalam bentuk integer 64-bit. Bit-bitnya disusun paling tidak hingga paling signifikan dengan cara yang sama seperti Anda membaca buku. Ia mengembalikan -1 untuk kecelakaan, 0 untuk mengemudi selamanya, atau 1 untuk melarikan diri ke sudut kanan bawah.
Program uji
Keluaran
Konverter array-ke-hex Python:
sumber
memset(&M,~1,8)
(15 karakter) denganM=~(-1ULL/255)
(14 karakter).P(0x00fefefefefefefe);
= (Seharusnya ditembak lurus ke kanan atas, satu belokan, lurus ke sudut. Sama untukP(0x00eeeeeeeeeeeeee);
(jalan buntu pada 4 col). Saya tidak berpikir Anda harus menetapkana
pada awalnya.0x7f7f7f7f7f7f7f00
. Juga perlu untuk menginisialisasia
karena nanti hanya dimodifikasi oleh ORing dalam bit tambahan, jadi saya tidak mampu untuk memiliki bit yang tidak diinginkan pada awalnya.Python, 187
213207 karakter, 10% bonus untuk jalur pencetakan
Pada input tes ia menemukan jalur yang sedikit berbeda:
SSSSRSRSRRSSRSSRRSRSSRSSSSS
Pendekatan umum adalah pertama-tama mengubah input menjadi spasi dan
o
s. Spasi memiliki hex20
, jadi keempat bit yang lebih rendah tidak disetel.o
memiliki hex6F
, jadi empat bit yang rendah sudah siap.Perbatasan
o
s ditempatkan di sekitar papan sehingga kita tidak perlu khawatir tentang indeks buruk.Saat kami berjalan melewati papan, kami menggunakan bit di setiap ubin untuk melihat apakah kami diizinkan melewati ketika datang dari sisi itu. Dengan cara ini, kita menghindari loop tak terbatas. Tidak cukup hanya memiliki satu boolean per ubin, karena arah keluar Anda bergantung pada arah entri Anda, sehingga ubin dapat dikunjungi dua kali.
Kami kemudian melakukan pencarian rekursif untuk jalur yang aman.
sumber
9
di tempatw=len(b[0])+1
, dll?p==79
denganp-79
. Saya mendapatkan kesalahan sintaks melakukan ini dua arah tanpa spasi sebelumelse
. Saya pikir trik itu hanya berhasilif
.-~x
==x+1
tetapi kedua operator unary memiliki prioritas lebih tinggi daripada perkalian, pembagian dan modulus! Jadi(d+1)%4
bisa-~d%4
! Ini juga akan bekerja denganx-1
tetapi gunakan~-x
saja.Javascript -
270 - 20% = 216262 - 20% = 210 byteKarena seharusnya ada setidaknya satu solusi yang menghasilkan kedua bonus (dan tidak mengarah ke kedalaman tumpukan yang konyol;) ...
Diperkecil:
Diperluas:
v
adalah hashtable dengan kunci yang merupakan triples state yang(x,y,d)
sesuai dengan (x, y) koordinat dan arah entrid
. Setiap kunci memiliki nilai terkait yaitu stringS
(lurus) danR
(belok kanan) yang diperlukan untuk mencapai keadaan yang diwakili oleh kunci.Kode juga memelihara setumpuk tiga kali lipat (dalam variabel
n
) yang belum diproses. Tumpukan awalnya hanya berisi triple (0,0,0), sesuai dengan keadaan di mana mobil menghadap tepat di sel (0,0). Di lingkaran luar,,for( S = ... )
rutin memeriksa apakah ada tiga kali lipat yang belum diproses tetap. Jika demikian, ia menjalankan setiap triple yang tidak diproses melalui loop dalamn.map( ...
,.Lingkaran dalam melakukan lima hal:
K
(macet), karena kami telah menemukan setidaknya satu putaran di mana mobil dapat terus berputar selamanya tanpa menabrak.v
) dan ke tumpukan triples yang tidak diproses (m
) untuk lintasan selanjutnya dari loop luarv
, nilainya diatur ke nilai negara asal (urutan gerakan) plusR
atauS
berdasarkan pada langkah saat inix
dany
adalah7
, nilai dari negara asal (urutan langkah yang diambil untuk mencapai negara asal) disalin keS
, karena urutan langkah ini adalah solusi untuk masalahSetelah loop dalam berakhir,
n
(tumpukan) diganti olehm
(tumpukan baru).Setelah loop luar berakhir (tidak ada status baru yang tercapai), fungsi mengembalikan outputnya. Jika sel (7,7) tercapai,
S
akan berisi urutan gerakan yang mengarah ke sel ini, dan ini dikeluarkan. Jika sel tidak tercapai,S
akan menjadi string kosong, dan rutin jatuh ke keluaranO
, yang akan berisiK
(macet) jika dan hanya jika loop ditemukan, atauC
(menabrak) jika mobil pasti akan crash.sumber
Python 339 - 10% = 305 byte
Saya menggunakan pencarian kedalaman-rekursif pertama, yang diakhiri sejak awal melalui kesuksesan
exit
. Juga mencetak jalur kesuksesan dalam bentuk00001010101010101010101110100111001000
,0
untuk lurus,1
untuk kanan. Jawabannya akan lebih lama dari optimal, karena ini adalah kedalaman-pertama. Saya yakin beberapa optimasi pada algoritma dapat menurunkan jumlah byte sedikit.sumber
a
'sfor
lingkaran. Anda juga tidak memerlukan ruang di sekitar operator, mis.(v+1) % 4
->(v+1)%4
. Anda juga dapat menggabungkan beberapa pernyataan ke satu baris dengan menggunakan;
jika tidak adaif
ataufor
, dll pada baris tersebut, misc(l+"0");c(l+"1")
. Beberapa golfs lainnya:x,y,v=0,0,2
,x|y>7 or x|y<0
,x==y==7
. Semoga berhasil :)