Mobil Anda hanya belok kanan!

49

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:

  1. Drive satu persegi ke depan, atau
  2. 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 menggantikan Trueoutput 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 Crashjika kecelakaan tidak dapat dihindari, atau Stuckjika mobil macet di rintangan selamanya. Output ini akan menggantikan Falseoutput 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:

masukkan deskripsi gambar di sini

Dan solusi yang mungkin adalah:

masukkan deskripsi gambar di sini

Karena ada solusi, program harus mengembalikan / mencetak Trueuntuk peta ini. Urutan gerakan yang ditunjukkan di sini adalah SSSSRSRRRSRSSRRRSSRSSS.

fosgen
sumber
2
Saya menulis beberapa test case yang sangat sederhana untuk Crashdan Stuck. Mereka ada di sini karena berapa lama mereka. Baris 2 terisi, semuanya kosong -> Crash. Baris 7 terisi, semuanya kosong ->Stuck
undergroundmonorail
3
Saya bingung tentang poin persentase (dibandingkan dengan persentase). Mendapatkan bonus akan mengalikan skor Anda dengan 0,9. Apakah mendapatkan keduanya kalikan dengan 0,8 atau 0,9 ^ 2?
undergroundmonorail
3
Tentu, S dan C baik-baik saja. Keluaran saya hanya saran.
phosgene
13
"Dua kesalahan tidak membuat benar, tetapi tiga kiri melakukannya." - Ayah.
hoosierEE
2
"Mobilmu hanya bisa menghasilkan nol atau tiga kiri!"
feersum

Jawaban:

17

JavaScript (ES6) - 122 124 148 162 172 178 187 190 193 208 byte

Terima kasih banyak kepada Pengoptimal dan DocMax untuk saran yang bermanfaat tentang cara meningkatkan kode ini:

F=a=>(D=(x,y,d)=>!D[i=[x,y,d]]&&(D[i]=1,x-=~d%2,y-=~-~d%2,x*y==49||!((x|y)&8||a[y][x])&&(D(x,y,d)||D(x,y,~-d%4))),D(-1,0))

Pengembalian true(kebenaran) untuk dipecahkan dan false(palsu) untuk tidak terpecahkan.

Hanya berfungsi di Firefox pada hari ini karena fitur JavaScript 1.7.

Papan Uji

saya dan kucing saya
sumber
1
Ini adalah 193 byte: 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).
Pengoptimal
1
172: 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.
Pengoptimal
1
@ Pengoptimal Saya masih mendapatkan kenyataan untuk kasus uji kedua [[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.
saya dan kucing saya
2
Itu karena karena xdan ykeduanya adalah global, Anda tidak dapat menjalankan dua testcas sebelum memuat ulang halaman ...
Pengoptimal
1
Anda dapat menyimpan total 9 lebih banyak dengan mengganti x+=d?d^2?0:-1:1dengan x+=d&1?0:1-ddan y+=d^1?d^3?0:-1:1dengan y+=d&1&&2-d.
DocMax
10

Python 2 - 123 125 133 146 148 150 154 160

Truepada kesuksesan, Falsepada kegagalan.

def f(h=1,v=0,b=0,x=0,y=0,c=[]):s=x,y,h,v;a=b,x+h,y+v,c+[s];return(s in c)==(x|y)&8==b[y][x]<(x&y>6or f(h,v,*a)|f(-v,h,*a))

Anda harus memberikan input seperti f(b=var_containing_board).

Versi Lambda - 154

Pengembalian 0(falsy) untuk kegagalan, Trueuntuk kesuksesan.

F=lambda b,x=0,y=0,h=1,v=0,c=[]:0if[x,y,h,v]in c or x|y>7or x|y<0 or b[y][x]else x&y==7or F(b,x+h,y+v,h,v,c+[[x,y,h,v]])or F(b,x+h,y+v,-v,h,c+[[x,y,h,v]])

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 sejarah s in cakan dilakukan False. Maka pemeriksaan batas (x|y)&8akan 8. Maka python bahkan tidak akan memeriksa nilai terakhir ==karena dua yang pertama sudah berbeda.

FryAmTheEggman
sumber
1
Versi fungsional dapat menggabungkan dua jika yang keduanya kembali; sebagai pengembalian sendiri kembali Tidak ada yang palsu, Anda juga tidak perlu mengembalikan 0.. Cukup membalas budi;)
Akan
Jika Anda membalik cek, Anda dapat menggabungkan kedua jika juga
Will
Bisakah Anda menggabungkan kedua pernyataan pengembalian?
Brandon
1
@ Akan Terima kasih, saya tahu ada cara yang lebih baik untuk melakukan itu: D Um, saya tidak dapat menemukan ruang untuk dihapus yang tidak menyebabkan saya kesalahan sintaks. Saya tidak benar-benar mengerti mengapa x|y>7orbekerja tetapi x|y<0ortidak ...
FryAmTheEggman
1
Anda dapat membuat awal oktal secara literal 0o.
feersum
9

C (GNU-C), 163 byte * 0,9 = 146,7

#C (GNU-C), 186 byte * 0.9 = 167.4

Versi 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.

g(long long o) {
    typeof(o) a=0,i=255,r=1,u=0,l=0,d=0,M=~0LLU/i,D;
    for( ;i--;d = D<<8&~o)
        a |= D = d|r,
        r = (r|u)*2&~M&~o,
        u = (u|l)>>8&~o,
        l = ((l|d)&~M)/2&~o;
    return a<0?:-!(d|r|u|l);
}

Program uji

f(long long o){typeof(o)a=0,i=255,r=1,u=0,l=0,d=0,M=~0LLU/i,D;for(;i--;d=D<<8&~o)a|=D=d|r,r=(r|u)*2&~M&~o,u=(u|l)>>8&~o,l=((l|d)&~M)/2&~o;return a<0?:-!(d|r|u|l);}
{
    char* s[] = {"Crash", "Stuck", "Escape"};
    #define P(x) puts(s[f(x)+1])
    L ex = 0x4640500C0A034020;
    P(ex);
    L blocked = 0x4040404040404040;
    P(blocked);

    L dead = 0x10002;
    P(dead);

    return 0;
}

Keluaran

Escape
Stuck
Crash

Konverter array-ke-hex Python:

a2b=lambda(A):"0x%X"%sum(A[i/8][i%8]<<i for i in range(64))
feersum
sumber
1
Ganti memset(&M,~1,8)(15 karakter) dengan M=~(-1ULL/255)(14 karakter).
R ..
@R .. Bagus sekali! -4 byte dari itu.
feersum
2
Saya suka format input - sangat keren!
phosgene
Saya mendapatkan 'crash' untuk P(0x00fefefefefefefe);= (Seharusnya ditembak lurus ke kanan atas, satu belokan, lurus ke sudut. Sama untuk P(0x00eeeeeeeeeeeeee);(jalan buntu pada 4 col). Saya tidak berpikir Anda harus menetapkan apada awalnya.
@tolos Anda telah mengubah urutan baris / kolom-utama. Agar baris atas dan kolom kanan terbuka, seharusnya 0x7f7f7f7f7f7f7f00. Juga perlu untuk menginisialisasi akarena nanti hanya dimodifikasi oleh ORing dalam bit tambahan, jadi saya tidak mampu untuk memiliki bit yang tidak diinginkan pada awalnya.
feersum
6

Python, 187 213

207 karakter, 10% bonus untuk jalur pencetakan

b=map(ord," "*9+" ".join("".join("o "[i]for i in j)for j in input())+" "*9)
def r(p,d,s):
 p+=(1,9,-1,-9)[d]
 if b[p]&1<<d:b[p]^=1<<d;return(s+"S")*(p==79)or r(p,d,s+"S")or r(p,(d+1)%4,s+"R")
print r(8,0,"")

Pada input tes ia menemukan jalur yang sedikit berbeda: SSSSRSRSRRSSRSSRRSRSSRSSSSS

Pendekatan umum adalah pertama-tama mengubah input menjadi spasi dan os. Spasi memiliki hex 20, jadi keempat bit yang lebih rendah tidak disetel. omemiliki hex 6F, jadi empat bit yang rendah sudah siap.

Perbatasan os 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.

Akan
sumber
3
"Mobil Anda mulai di sudut kiri atas peta 8x8" - tidak bisakah Anda membuat hardcode 9di tempat w=len(b[0])+1, dll?
FryAmTheEggman
@FryAmTheEggman terima kasih, bagaimana saya bisa mengabaikannya? : D
Will
Anda dapat membalikkan pernyataan terner Anda dan menggantinya p==79dengan p-79. Saya mendapatkan kesalahan sintaks melakukan ini dua arah tanpa spasi sebelum else. Saya pikir trik itu hanya berhasil if.
FryAmTheEggman
@FryAmTheEggman Saya pikir tes kedalaman harus sebelum perulangan? Saya telah bermain dengan multiplikasi oleh boolean sebagai gantinya.
Will
7
Saya baru saja menemukan trik yang sangat rapi. Anda mungkin tahu bahwa -~x== x+1tetapi kedua operator unary memiliki prioritas lebih tinggi daripada perkalian, pembagian dan modulus! Jadi (d+1)%4bisa -~d%4! Ini juga akan bekerja dengan x-1tetapi gunakan ~-xsaja.
FryAmTheEggman
6

Javascript - 270 - 20% = 216 262 - 20% = 210 byte

Karena seharusnya ada setidaknya satu solusi yang menghasilkan kedua bonus (dan tidak mengarah ke kedalaman tumpukan yang konyol;) ...

Diperkecil:

V=I=>{n=[N=[0,0,0]];v={};v[N]='';O='C';for(S='';n[0];){m=[];n.map(h=>{[x,y,d]=h;D=i=>[1,0,-1,0][d+i&3];p=v[h];for(j=2;j--;){O=v[c=[X=x+D(j),Y=y+D(3-3*j)),d+j&3]]?'K':O;J=X|Y;J<0||J>7||I[Y][X]||v[c]?O:(m.push(c),v[c]=p+'SR'[j])}S=(x&y)>6?p:S});n=m;}return S||O;};

Diperluas:

V = I => {
    n = [N=[0,0,0]];
    v = {};
    v[N] = '';
    O = 'C';

    for( S = ''; n[0]; ) {
        m = [];
        n.map( h => {
            [x,y,d] = h;
            D = i => [1,0,-1,0][d+i&3];
            p = v[h];
            for( j = 2; j--; ) {
                O = v[c = [X = x+D(j),Y = y+D(3-3*j),d+j&3]] ? 'K' : O;
                J = X|Y;
                J<0 || J>7 || I[Y][X] || v[c] ? O : (
                    m.push( c ),
                    v[c] = p + 'SR'[j]
                );
            }

            S = (x&y) > 6 ? p : S;
        } );
        n = m;
    }
    return S || O;
};

vadalah hashtable dengan kunci yang merupakan triples state yang (x,y,d)sesuai dengan (x, y) koordinat dan arah entri d. Setiap kunci memiliki nilai terkait yaitu string S(lurus) dan R(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 dalam n.map( ...,.

Lingkaran dalam melakukan lima hal:

  1. menghitung dua kemungkinan gerakan (mengemudi lurus, berbelok ke kanan) dari kondisi saat ini
  2. jika salah satu dari langkah-langkah ini mengarah ke negara yang sudah terdaftar di hashtable, itu diabaikan untuk diproses lebih lanjut. Namun, kami menandai output FALSE K(macet), karena kami telah menemukan setidaknya satu putaran di mana mobil dapat terus berputar selamanya tanpa menabrak.
  3. jika suatu negara legal dan novel, ia ditambahkan ke hashtable ( v) dan ke tumpukan triples yang tidak diproses ( m) untuk lintasan selanjutnya dari loop luar
  4. ketika negara baru terdaftar v, nilainya diatur ke nilai negara asal (urutan gerakan) plus Ratau Sberdasarkan pada langkah saat ini
  5. jika xdan yadalah 7, nilai dari negara asal (urutan langkah yang diambil untuk mencapai negara asal) disalin ke S, karena urutan langkah ini adalah solusi untuk masalah

Setelah loop dalam berakhir, n(tumpukan) diganti oleh m(tumpukan baru).

Setelah loop luar berakhir (tidak ada status baru yang tercapai), fungsi mengembalikan outputnya. Jika sel (7,7) tercapai, Sakan berisi urutan gerakan yang mengarah ke sel ini, dan ini dikeluarkan. Jika sel tidak tercapai, Sakan menjadi string kosong, dan rutin jatuh ke keluaran O, yang akan berisi K(macet) jika dan hanya jika loop ditemukan, atau C(menabrak) jika mobil pasti akan crash.

COTO
sumber
1
Mendapat konfirmasi dari OP, Anda dapat mengganti nama 'Crash' dan 'Stuck' menjadi 'C' dan 'S'.
FryAmTheEggman
Ah. Itu menghemat sedikit, kalau begitu. Terima kasih. ;)
COTO
Bisakah Anda menjelaskan apa yang kode Anda lakukan? Saya tidak bisa membuat kepala atau ekornya.
phosgene
@ phosgene: Saya sudah memasukkan penjelasan terperinci inline.
COTO
Itu prosedur yang cerdas. Tidak ada yang terbuang.
phosgene
4

Python 339 - 10% = 305 byte

Saya menggunakan pencarian kedalaman-rekursif pertama, yang diakhiri sejak awal melalui kesuksesan exit. Juga mencetak jalur kesuksesan dalam bentuk 00001010101010101010101110100111001000, 0untuk lurus, 1untuk kanan. Jawabannya akan lebih lama dari optimal, karena ini adalah kedalaman-pertama. Saya yakin beberapa optimasi pada algoritma dapat menurunkan jumlah byte sedikit.

b=input()
D=[(-1,0),(0,-1),(1,0),(0,1)]
def a(l):
 x,y=0,0
 v=2
 for d in l:
  if d=='1':v=(v+1) % 4
  x+=D[v][0]
  y+=D[v][1]
  if x<0 or x>7 or y<0 or y>7:return 0,x,y
  if b[y][x]:return -1,x,y
 return 1,x,y
def c(l):
 if len(l) < 39:
  t,x,y=a(l)
  if t==1:
   if (x,y)==(7,7):
    print l;exit(0)
   c(l+"0")
   c(l+"1")
c("")
print 0
stokastik
sumber
3
Karena ini adalah Python 2, Anda dapat mencampur tab dan spasi untuk indentasi, seperti di a's forlingkaran. 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 ada ifatau for, dll pada baris tersebut, mis c(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 :)
FryAmTheEggman