Twój przyjaciel dał ci wskazówki do najlepszej restauracji w mieście. To seria skrętów w lewo i w prawo. Niestety zapomnieli wspomnieć o tym, jak długo trzeba iść prosto między tymi turami. Na szczęście masz mapę ulic ze wszystkimi restauracjami. Może możesz dowiedzieć się, o którą restaurację chodziło?

Wkład

Mapa jest podawana jako prostokątna siatka znaków ASCII. .Jest to droga, #jest budynek, Aw celu Zsą różne restauracje. Zaczynasz w lewym górnym rogu, kierując się na wschód. Przykład:

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

Instrukcje twojego przyjaciela będą podane jako (potencjalnie pusty) ciąg znaków lub lista znaków zawierających Ls i Rs.

Wydajność

Możesz przejść dowolną ścieżką, która odpowiada skrętom w lewo i w prawo w ciągu wejściowym, pod warunkiem, że zrobisz co najmniej jeden krok do przodu przed każdym z nich, a także na końcu. W szczególności oznacza to, że jeśli ciąg zaczyna się od R, nie możesz natychmiast udać się na południe w lewej kolumnie. Oznacza to również, że nie możesz obrócić się o 180 ° na miejscu.

Nie możesz przechodzić przez budynki lub restauracje, z wyjątkiem tych, do których dotrzesz na końcu. Możesz założyć, że lewy górny róg to ..

Powinieneś wypisać wszystkie restauracje, do których można dotrzeć z instrukcjami znajomego, w postaci ciągu lub listy.

Możesz założyć, że instrukcje doprowadzą do co najmniej jednej restauracji. Np. Singiel Lbyłby nieprawidłowy dla powyższej mapy.

Kilka przykładów powyższej mapy:

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

Zwróć uwagę, że Rto nie osiąga B.

Możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i wypisując wynik przez STDOUT (lub najbliższą alternatywę), wartość zwracaną funkcji lub parametr funkcji (wyjściowej).

Obowiązują standardowe zasady gry w golfa .

Dodatkowe przypadki testowe

Oto większa mapa, dzięki uprzejmości Conora O'Briena (który nieco zmodyfikowałem):

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

A oto kilka wybranych list kierunków i ich oczekiwanych wyników:

<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

Pytanie bonusowe: czy istnieje wkład, który powoduje tylko I lub tylko U ? Jeśli tak, jaka jest najkrótsza taka ścieżka?

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

Dodano +7 dla -F -Xn0i

Pierwsza próba.

Uruchom z mapą na STDIN i wskazówkami po opcji -i, np

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

Zamknij STDIN za pomocą ^Dlub ^Zcokolwiek, co działa w twoim systemie operacyjnym.

incomplete.pl:

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

Zastąp ^ H literalnym znakiem kontrolnym, aby uzyskać podany wynik

Pytanie bonusowe:

• Nie ma danych wejściowych, które powodują tylko I
• Najkrótsze wejście, które daje tylko wynik, UtoRLLRRLLRLRLRRLRRLRLRLRRLLR
• Najdłuższe wejście potrzebne do uzyskania unikalnego zestawu jest tym, RLLRRRLRLRLLLRRLRLLLLLRRRLLRRRLLLLLLLRRLRRRRco dajeB O R

Python 2, 180 177 168 163 161 158 bajtów

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]

Parametr vto mapa jako ciąg; ojest LRciąg.

Mitch Schwartz zapisał 2 3 10 partii bajtów. Dzięki!

Uratowałem dwa bajty, ustawiając O={0}i powrocie `O`[9::5], co może nie być bardzo przenośny: zakłada, że hash(0) == 0, jak sądzę, bo to powoduje, że kolejność elementów repr(O)będzie

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

i twórcze pocięcie tego sznurka daje mi odpowiedź.

C ++ 465

C ++ jest bardzo gadatliwy ...

#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<<" ";}

Spróbuję to jeszcze bardziej skrócić. Sugestie są mile widziane.