Ikuti petunjuk yang tidak lengkap

21

Seorang teman Anda telah memberi Anda petunjuk ke restoran terbaik di kota. Ini serangkaian belokan kiri dan kanan. Sayangnya, mereka lupa menyebutkan berapa lama Anda harus berjalan lurus di antara belokan itu. Untungnya Anda memiliki peta jalan dengan semua restoran di atasnya. Mungkin Anda bisa mencari tahu restoran mana yang dimaksud?

Memasukkan

Peta diberikan sebagai kotak persegi panjang karakter ASCII. .adalah jalan, #adalah bangunan, Auntuk Zmenjadi berbagai restoran. Anda mulai di sudut kiri atas, ke timur. Contoh:

.....A
.#.###
B....C
##.#.#
D....E
##F###

Instruksi teman Anda akan diberikan sebagai string (kemungkinan kosong) atau daftar karakter yang mengandung Ls dan Rs.

Keluaran

Anda dapat berjalan di setiap jalur yang sesuai dengan belokan kiri dan kanan pada string input, asalkan Anda mengambil setidaknya satu langkah ke depan sebelum masing-masing, serta di akhir. Khususnya ini berarti jika string dimulai dengan RAnda tidak dapat langsung ke selatan di kolom paling kiri. Ini juga berarti Anda tidak dapat berbalik 180 ° di tempat.

Anda tidak dapat berjalan melalui bangunan atau restoran kecuali yang Anda jangkau di akhir. Anda dapat menganggap bahwa sudut kiri atas adalah a ..

Anda harus menampilkan semua restoran yang dapat dijangkau dengan instruksi teman Anda, sebagai string atau daftar.

Anda dapat berasumsi bahwa instruksi akan mengarah ke setidaknya satu restoran. Misalnya satu Lakan tidak valid untuk peta di atas.

Beberapa contoh untuk peta di atas:

<empty> A
R       F
RR      B,D
RL      C,E
RLRL    E
RLLR    C
RLLL    B
RLRR    D
RLRRRR  A,C
RLLLRLL B

Perhatikan khususnya yang Rtidak mencapai B.

Anda dapat menulis sebuah program atau fungsi, mengambil input melalui STDIN (atau alternatif terdekat), argumen baris perintah atau argumen fungsi dan mengeluarkan hasilnya melalui STDOUT (atau alternatif terdekat), nilai pengembalian fungsi atau parameter function (out).

Aturan standar berlaku.

Kasus Uji Tambahan

Ini adalah peta yang lebih besar, milik Conor O'Brien (yang saya modifikasi sedikit):

.......Y..........................######
.####.....#.##....##..######....#.###.##
B.........#.##.#..##....##...##.#.#P...#
.#.#####..#.##..#.##....##.#....#.####.#
.#.#...C..#.##...G##..#.##.#....#.#....#
.#.#.#.#..#.####.###.#..##.#....#.#.NO.#
.#.#A#.#..#.##...F###...##.#.##.#......#
.#.###....#.##....##....##.#....###....#
.#.....##...##....##...D##........###R.#
.#.##..##...##E...##..######....####...#
.....X....#.#.....................##S.T#
###########.###########M############...#
#................................###.#.#
#.#########.########.######.#.######.#.#
#......V#.....######.IJ...........##.#.#
#########.###......ZH############L##.#.#
#########.##########.###############.#.#
####K##...##########.#....#..........#.#
####....########U......##...#######Q.#.#
#####################################W.#

Dan berikut adalah beberapa daftar arah yang dipilih dan hasil yang diharapkan:

<empty>                                 Y
RR                                      B
RLL                                     Y
RLRR                                    B,C,X
RLLLRRR                                 G
RLRLRLRL                                I,Z
RLLRRRLRRLRR                            C,D,F,G,Y
RLRRLLRLLLRL                            B,C,Y
RLLRRLRRRLLLL                           F,M,N,O,Y
RLRRLLLRRRRLLLL                         F,M,Y
RLRRLRRRRRRRRRR                         E,F,Y
RLRRRLLLRLLRRLL                         M,N,O
RLLRRLRRLRLRLRRLLR                      E,U
RLRLLRLRRLRRRRRLRL                      F,G,I,Z
RLLRRLLRLLRRRLRRLLRR                    W
RLLLRRRLRRLLLLLRLLLLLL                  D,G,X
RLRLLRLRRLRLRRRLRLLLRR                  B,C,E,J,X
RLRLRLLLLRLRRRRRRLRLRRLR                Y
RLRLRRRLRLLLLRLRRLLLLRLLRRL             E,M,X
RLRLLLRRRLLLRLLRLLRLRRLRLRR             B,E,F,K
RLRRRLLLLLLLLLLLLLLLRRRRLLL             A,B

Pertanyaan bonus: apakah ada input yang hanya menghasilkan I atau hanya U ? Jika demikian, apa jalan tersingkat seperti itu?

Martin Ender
sumber

Jawaban:

17

Perl, 150 149 146 145 141 140 138 136 135 133 130 126 125 124

Menambahkan +7 untuk -F -Xn0i

Upaya awal.

Jalankan dengan peta pada STDIN dan arah setelah opsi -i, mis

perl -F -Xn0iRL incomplete.pl
.....A
.#.###
B....C
##.#.#
D....E
##F###

Tutup STDIN dengan ^Datau ^Zatau apa pun yang berfungsi pada sistem operasi Anda.

incomplete.pl:

%P=0;$^I=~s``{%;=!/
/;%P=map{$_|=$F[$^H=$_+=(1,@+,-1,"-@+")[$d&3]]=~/(\w)|#|^$/*~!\$;{$1}}(%P)x@F}$d-=B&$'^u`eg;print%

Ganti ^ H dengan karakter kontrol literal untuk mendapatkan skor yang diberikan

Pertanyaan bonus:

  • Tidak ada input yang menghasilkan hanya I
  • Input terpendek yang menghasilkan hanya UadalahRLLRRLLRLRLRRLRRLRLRLRRLLR
  • Input terpanjang yang dibutuhkan untuk menghasilkan set unik adalah RLLRRRLRLRLLLRRLRLLLLLRRRLLRRRLLLLLLLRRLRRRRyang memberiB O R
Ton Hospel
sumber
4
The Ton Hospel? :)
Lynn
14
Hanya ada satu alien dengan nama itu
Ton Hospel
2
@TonHospel Merupakan suatu kehormatan memiliki Anda di sini.
msh210
8

Python 2, 180 177 168 163 161 158 byte

def a(v,o,c=0,A=0,d='.',O={0}):
 while'.'==d:w=v.find('\n');c+=[1,~w,-1,w+1][A%4];d=v[c];o>v<a(v+' '*w,o[1:],c,ord(o[0])-~A,d);d>v>o<O.add(d)
 return`O`[9::5]

Parameter vadalah peta sebagai string; oadalah LRstring.

Mitch Schwartz menyimpan 2 3 10 banyak byte. Terima kasih!

Saya menyimpan dua byte dengan mengatur O={0}dan mengembalikan `O`[9::5], yang mungkin tidak terlalu portabel: ia menganggap itu hash(0) == 0, saya pikir, karena itu menyebabkan urutan elemen repr(O)menjadi

set([0, 'A', 'B', 'C'])

dan mengiris string itu dengan kreatif membuat saya mendapatkan jawabannya.

Lynn
sumber
Saya pikir ini menderita dari ledakan eksponensial jika Anda menjalankannya pada kotak besar yang hampir kosong dengan string putaran gondrong
Ton Hospel
Oh, ya, ini adalah bencana kinerja absolut. Ini bekerja untuk contoh grid!
Lynn
1

C ++ 465

C ++ begitu verbose ...

#include <vector>
#include <iostream>
using namespace std;
#define M m[y][x]
#define A if(M!=46)break
vector<string>m;char n[99];int r(int x,int y,int z,const char *d){for(;;){if(z%2)y=y-2+z;else x=x+1-z;if(y<0||y>=m.size()||x<0||x>=m[y].size())break;if(*d){A;r(x,y,(*d==82?z+3:*d==76?z+1:z)%4,d+1);}else{if(M>64&&M<91)n[M]++;A;}}}int main(int c,char**v){string l;while(getline(cin,l))m.push_back(l);r(0,0,0,c>1?v[1]:"");for(char j=0;j<99;j++)if(n[j])cout<<j<<" ";}

Saya akan mencoba untuk mempersingkat lebih lanjut. Saran diterima.

Jerry Jeremiah
sumber