Folgen Sie unvollständigen Anweisungen

21

Ein Freund von Ihnen hat Ihnen eine Wegbeschreibung zum besten Restaurant der Stadt gegeben. Es ist eine Reihe von Links- und Rechtskurven. Leider haben sie vergessen zu erwähnen, wie lange Sie zwischen diesen Kurven geradeaus fahren müssen. Zum Glück haben Sie einen Stadtplan mit allen Restaurants. Vielleicht können Sie herausfinden, welches Restaurant gemeint ist?

Eingang

Die Karte wird als rechteckiges Raster aus ASCII-Zeichen dargestellt. .ist eine Straße, #ein Gebäude, Aum Zdie verschiedenen Restaurants. Sie beginnen in der oberen linken Ecke und gehen nach Osten. Beispiel:

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

Die Anweisungen Ihres Freundes werden als (möglicherweise leere) Zeichenfolge oder Liste von Zeichen ausgegeben, die Ls und Rs enthalten.

Ausgabe

Sie können jeden Pfad gehen, der der Linkskurve und der Rechtskurve in der Eingabezeichenfolge entspricht, vorausgesetzt, Sie gehen vor und am Ende jeweils mindestens einen Schritt vorwärts. Dies bedeutet insbesondere dann, wenn die Zeichenfolge mit beginnt, dass RSie in der äußersten linken Spalte nicht sofort nach Süden gehen können. Es bedeutet auch, dass Sie sich vor Ort nicht um 180 ° drehen können.

Sie können nur durch die Gebäude oder Restaurants gehen, die Sie am Ende erreichen. Sie können annehmen, dass die obere linke Ecke a ist ..

Sie sollten alle Restaurants, die mit den Anweisungen Ihres Freundes erreichbar sind, als Zeichenfolge oder Liste ausgeben.

Sie können davon ausgehen, dass die Anweisungen zu mindestens einem Restaurant führen. Beispielsweise wäre eine einzelne Lfür die obige Karte ungültig.

Einige Beispiele für die obige Karte:

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

Beachten Sie insbesondere, dass Rnicht erreicht B.

Sie können ein Programm oder eine Funktion schreiben, indem Sie eine Eingabe über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen und das Ergebnis über STDOUT (oder die nächstgelegene Alternative), einen Funktionsrückgabewert oder einen Funktionsparameter (out) ausgeben.

Es gelten die Standardregeln für .

Zusätzliche Testfälle

Hier ist eine größere Karte mit freundlicher Genehmigung von Conor O'Brien (die ich ein wenig modifiziert habe):

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

Und hier sind einige ausgewählte Listen mit Wegbeschreibungen und den erwarteten Ergebnissen:

<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

Bonusfrage: Gibt es eine Eingabe, die nur zu I oder nur zu ergibt U? Wenn ja, welcher Weg ist der kürzeste?

Martin Ender
quelle

Antworten:

17

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

+7 für -F -Xn0i hinzugefügt

Ein erster Versuch.

Führen Sie mit der Karte STDIN und den Anweisungen nach der Option -i aus, z

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

Schließen Sie STDIN mit ^Doder ^Zoder was auch immer auf Ihrem Betriebssystem funktioniert.

incomplete.pl:

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

Ersetzen Sie das ^ H durch das Literal-Steuerzeichen, um die angegebene Punktzahl zu erhalten

Bonus-Frage:

  • Es gibt keine Eingabe, die nur zu führt I
  • Die kürzeste Eingabe, die nur zu führt, UistRLLRRLLRLRLRRLRRLRLRLRRLLR
  • Die längste Eingabe, die benötigt wird, um eine eindeutige Menge zu erhalten, ist RLLRRRLRLRLLLRRLRLLLLLRRRLLRRRLLLLLLLRRLRRRRwelcheB O R
Tonne Hospel
quelle
4
Das Tonnenhospel? :)
Lynn
14
Es gibt nur einen Außerirdischen mit diesem Namen
Ton Hospel
2
@TonHospel Es ist eine Ehre, Sie hier zu haben.
msh210
8

Python 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]

Parameter vist die Map als String; oist die LRZeichenfolge.

Mitch Schwartz sparte 2 3 10 viele Bytes. Vielen Dank!

Ich sparte zwei Bytes durch Setzen O={0}und Rückkehr `O`[9::5], die nicht sehr portabel sein könnte: es , dass davon ausgegangen hash(0) == 0, denke ich, denn das ist die Reihenfolge der Elemente in verursacht repr(O)werden

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

und kreatives Schneiden dieser Zeichenfolge gibt mir die Antwort.

Lynn
quelle
Ich denke, dies leidet unter einer exponentiellen Explosion, wenn Sie es auf einem großen, fast leeren Gitter mit langen Turn-Strings laufen lassen
Ton Hospel
Oh ja, es ist eine absolute Leistungskatastrophe. Es funktioniert jedoch für die Beispielgitter!
Lynn
1

C ++ 465

C ++ ist so ausführlich ...

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

Ich werde versuchen, es weiter zu verkürzen. Vorschläge sind willkommen.

Jerry Jeremiah
quelle