Sigue instrucciones incompletas

21

Un amigo tuyo te ha dado indicaciones para llegar al mejor restaurante de la ciudad. Es una serie de giros a la izquierda y a la derecha. Desafortunadamente, se olvidaron de mencionar por cuánto tiempo necesitas avanzar entre esos turnos. Afortunadamente, tienes un mapa de calles con todos los restaurantes. ¿Quizás puedas averiguar a qué restaurante se referían?

Entrada

El mapa se proporciona como una cuadrícula rectangular de caracteres ASCII. .es un camino, #es un edificio, Aque Zson los diversos restaurantes. Comienzas en la esquina superior izquierda, hacia el este. Ejemplo:

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

Las instrucciones de su amigo se darán como una cadena (potencialmente vacía) o una lista de caracteres que contienen Lsy Rs.

Salida

Puede caminar por cualquier camino que corresponda a los giros a la izquierda y a la derecha en la cadena de entrada, siempre que avance al menos un paso antes de cada uno de ellos, así como al final. En particular, esto significa que si la cadena comienza con Rusted, no puede ir al sur inmediatamente en la columna más a la izquierda. También significa que no puede girar 180 ° en el acto.

No puede caminar a través de edificios o restaurantes, excepto el que llega al final. Puede suponer que la esquina superior izquierda es a ..

Debe mostrar todos los restaurantes a los que se puede llegar con las instrucciones de su amigo, como una cadena o una lista.

Puede suponer que las instrucciones conducirán a al menos un restaurante. Por ejemplo, un solo Lsería inválido para el mapa anterior.

Algunos ejemplos para el mapa de arriba:

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

Tenga en cuenta en particular que Rno llega B.

Puede escribir un programa o función, tomando la entrada a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función y generando el resultado a través de STDOUT (o la alternativa más cercana), el valor de retorno de la función o el parámetro de función (out).

Aplican reglas estándar de .

Casos de prueba adicionales

Aquí hay un mapa más grande, cortesía de Conor O'Brien (que modifiqué un poco):

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

Y aquí hay algunas listas seleccionadas de direcciones y sus resultados esperados:

<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

Pregunta adicional: ¿hay una entrada que da como resultado solo I o solo U ? Si es así, ¿cuál es el camino más corto?

Martin Ender
fuente

Respuestas:

17

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

Se agregó +7 para -F -Xn0i

Un intento inicial.

Ejecute con el mapa en STDIN y las instrucciones después de la opción -i, p. Ej.

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

Cierre STDIN con ^Do ^Zlo que sea que funcione en su sistema operativo.

incomplete.pl:

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

Reemplace ^ H por el carácter de control literal para obtener la puntuación dada

Pregunta extra:

  • No hay entrada que solo dé como resultado I
  • La entrada más corta que da como resultado solo UesRLLRRLLRLRLRRLRRLRLRLRRLLR
  • La entrada más larga necesaria para dar como resultado un conjunto único es RLLRRRLRLRLLLRRLRLLLLLRRRLLRRRLLLLLLLRRLRRRR que daB O R
Ton Hospel
fuente
44
El Ton Hospel? :)
Lynn
14
Solo hay un alienígena con ese nombre
Ton Hospel
2
@TonHospel Es un honor tenerte aquí.
msh210
8

Pitón 2, 180 177 168 163 161 158 bytes

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]

Parámetro v es el mapa como una cadena; oes la LRcuerda

Mitch Schwartz salvó 2 3 10 lotes de bytes. ¡Gracias!

Ahorré dos bytes configurando O={0}y devolviendo `O`[9::5], lo que podría no ser muy portátil: hash(0) == 0supongo que, creo, porque eso hace que el orden de los elementos repr(O)sea

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

y cortar creativamente esa cuerda me da la respuesta.

Lynn
fuente
Creo que esto sufre una explosión exponencial si lo ejecutas en una gran cuadrícula casi vacía con cadenas de giro largas
Ton Hospel
Oh, sí, es un desastre de rendimiento absoluto. Sin embargo, funciona para las cuadrículas de ejemplo.
Lynn
1

C ++ 465

C ++ es tan detallado ...

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

Trataré de acortarlo aún más. Las sugerencias son bienvenidas.

Jerry Jeremiah
fuente