Textlabyrinth-Löser

14

Wenn Sie ein Labyrinth auf stdin und einen Einstiegspunkt haben, schreiben Sie ein Programm, das einen Pfad zum Ausgang auf stdout ausgibt. Jeder Pfad ist akzeptabel, solange Ihr Programm nicht den trivialen Pfad (der durch jeden Punkt im Labyrinth verläuft) für jedes Labyrinth generiert.

In der Eingabe sind Wände mit einem #und der Einstiegspunkt mit einem gekennzeichnet @. Sie können beliebige Zeichen verwenden, um das Labyrinth und den Pfad in der Ausgabe zu zeichnen, sofern sie alle unterschiedlich sind.

Sie können davon ausgehen, dass:

  • Die Eintritts- und Austrittspunkte befinden sich an den Rändern der Eingabe
  • Jede Zeile der Eingabe hat die gleiche Länge
  • Das Labyrinth ist lösbar und hat keine Zyklen
  • Es gibt nur einen Austrittspunkt

Kürzeste Lösung nach (Unicode) Zeichenzahl gewinnt.

Beispiele

(Beachten Sie, dass die Eingaben mit Leerzeichen aufgefüllt sind)

####   
#  #   
@ #####
#     #
#      
#######

####
#  #
@*#####
#*    #
#******
#######

### ###################
###         #         #
##  #########      #  #
 #             #####  #
 ###############   #@##

###*###################
###*********#*********#
## *#########*     # *#
 # *********** #####**#
 ###############   #@##
Lowjacker
quelle
Kann ich auch ein Zeichen für den Endpunkt hinzufügen? Es würde meinem Programm viel leichter machen, zu wissen, wann es zu beenden ist.
Peter Olson
@ Peter Of The Corn: Sicher. Sie müssen nicht dasselbe Zeichen verwenden, um den gesamten Pfad zu zeichnen, sondern müssen sich nur vom Rest der Ausgabe unterscheiden.
Lowjacker

Antworten:

5

Ruby 1.9, 244 Zeichen

l=*$<
i=l*""
e=[]
d=[1,-1,x=l[0].size,-x]
r=[f=9e9]*s=x*b=l.size;r[i=~/@/]=0
r.map{i.gsub(/ /){r[p=$`.size]=d.map{|u|p>-u&&r[u+p]||f}.min+1;e<<p if p%x%~-~-x*(p/-~x%~-b)<1}}
r[g=e.find{|i|r[i]<f}].times{i[g]=?*;g+=d.find{|l|r[g]>r[g+l]}}
puts i

Ausgabe für die beiden Beispiele:

####   
#  #   
@*#####
#*    #
#******
#######

###*###################
###*        #     *** #
## *######### *****#* #
 # ************#####* #
 ###############   #@##

Bearbeitungen:

  • (247 -> 245) Inline e und umbenannt in g
  • (245 -> 249) Beheben Sie einen Fehler, wenn sich der Ausgang direkt über dem Eingang befindet
  • (249 -> 246) Inlining + Vereinfachungen
  • (246 -> 244) Kürzere Methode zum Durchlaufen aller Felder
Ventero
quelle
8

ANSI C ( 384 373 368 Zeichen)

Hier ist mein C-Versuch. Kompiliert und ausgeführt unter Mac OS X.

m[9999],*r=m,*s=m,c,R=0,*a,L;
P(){while(*s++)putchar(*(s-1));}
C(int*l){if((l-s+2)%R==0||(l-s)%R==0||l-s<R||l>r-R)*l=42,P(),exit(0);}
e(int*l){if(*l==32)C(l),*l=42,e(l-1),*l=32,*l=42,e(l-R),*l=32,*l=42,e(l+1),*l=32,*l=42,e(l+R),*l=32;}
main(){while(~(c=getchar()))*r++=c,R=!R&&c==10?r-s:R,L=c==64?r-s-1:L;L%R==0&&e(s+L+1);(L+2)%R==0&&e(s+L-1);L<R&&e(s+L+R);e(s+L-R);}

Beispielausgabe für einige Tests:

####   
#  #   
@*#####
#*****#
#    *#
#####*#

###*###################
###*        #******** #
##**#########**    #* #
 #*************#####* #
 ###############   #@##

Einschränkungen: Funktioniert nur für Labyrinthe mit bis zu 1000 Zeichen, kann jedoch leicht erhöht werden. Ich habe nur eine beliebige Nummer gewählt, anstatt mich um malloc / remalloc zu kümmern.

Außerdem ist dies der Code mit den meisten Warnungen, den ich jemals geschrieben habe. 19 Warnungen, obwohl es mit der Hervorhebung des XCode-Codes noch mehr aussieht. : D

BEARBEITUNGEN: Bearbeitet und getestet, um int von main zu entfernen und ~ anstelle von! = EOF und putchar anstelle von printf zu verwenden. Danke für die Kommentare!

Jonathan Watmough
quelle
Sie könnten 9999 verwenden - es ist die gleiche Anzahl von Zeichen
Lowjacker
Gut gemacht! Lassen Sie das " int " vor mainund speichern Sie 4 Zeichen. Verwenden Sie putchar(*(s-1))stattdessen auch printf("%c",*(s-1)), um weitere 4 zu speichern.
Casey
Sie können auch 0xAnach 10und !=nach ersetzen ^.
Lowjacker
Noch besser: Sie können den ~Operator verwenden, um nach EOF zu while(~(c=getchar())
suchen
Ich kann auch die! L &&-Wache loslassen, wenn ich L einstelle, die Position im Labyrinth des '@'.
Jonathan Watmough
4

Python, 339 Zeichen

import sys
M=list(sys.stdin.read())
L=len(M)
R=range(L)
N=M.index('\n')+1
D=2*L*[9e9]
D[M.index('@')+N]=0
J=(1,-1,N,-N)
for x in R:
 for i in[N+i for i in R if' '==M[i]]:D[i]=min(1+D[i+j]for j in J)
e=[i+N for i in R[:N]+R[::N]+R[N-2::N]+R[-N:]if 0<D[i+N]<9e9][0]
while D[e]:M[e-N]='*';e=[e+j for j in J if D[e+j]<D[e]][0]
print''.join(M)

Erzeugt einen kürzesten Weg durch das Labyrinth.

Ausgabe zum Beispiel Labyrinthe:

####   
#  #   
@*#####
#*    #
#******
#######

###*###################
###*        #     *** #
## *######### *****#* #
 # ************#####* #
 ###############   #@##
Keith Randall
quelle
Warum alle Additionen und Subtraktionen von N?
Lowjacker
Es verhindert, dass die Indizierung D [i + j] in Zeile 10 negativ wird. Und D [e + j] in Zeile 12.
Keith Randall
1

Python - 510 421 Zeichen

m=[]
i=raw_input
l=i()
x=y=-1
while l:
 if y<0:x+=1;y=l.find('@')
 m.append(list(l));l=i()
s=(x,y)
t={}
q=[s]
v={s:1}
while 1:
 try:(i,j),q=q[0],q[1:];c=m[i][j]
 except:continue
 if c==' 'and(i*j==0)|(i+1==len(m))|(j+1==len(m[0])):break
 for d,D in(-1,0),(0,-1),(1,0),(0,1):
  p=(i+d,j+D)
  if not p in v and'#'!=c:v[p]=0;q.append(p);t[p]=(i,j)
while(i,j)!=s:m[i][j]='*';i,j=t[(i,j)]
print'\n'.join(''.join(l)for l in m)
Juan
quelle
Ich erhalte *unten rechts eine Meldung zum ersten Testfall (Python 2.6.1). Irgendwelche Gedanken?
Lowjacker
@ Lowjacker Danke, es scheint, dass ich während des Golfspiels einen Fehler hinzugefügt habe, der dafür gesorgt hat, dass es funktioniert hat, aber nur für die Testfälle und selbst dann kaum: P
Juan
Gut, es funktioniert jetzt. Aber du hast vergessen, das print b,rund das herauszunehmen print (i,j), von denen ich
annehme
0

Python 3 , 275 Bytes

import sys
def q(g,s=[]):w=len(g[0])+1;k='@'.join(g)+w*'@';*p,x=s or[k.find('#')];return'@'>k[x]and{x}-{*p}and[p,min((q(g,s+[x+a])or k for a in(-1,1,-w,w)),key=len)]['*'>k[x]]
g=''.join(sys.stdin.read());s=q(g.split('\n'))
for i in range(len(g)):print(end=[g[i],'+'][i in s])

Probieren Sie es online!

Port meiner Antwort auf die Suche nach der kürzesten Route auf einer ASCII-Straße .

Verwendet '#'für Anfang, '*'Ende, '@'Wand und ' 'leeren Raum. In diesem Fall qist die Funktion eine Hilfsfunktion, die ein eindimensionales Array mit dem kürzesten Pfad im Labyrinth zurückgibt. Die Funktion fkann um 4 Bytes gekürzt werden, indem die Variable nicht zugewiesen wird s. Dies ist unglaublich ineffizient und führt wahrscheinlich zu einer Zeitüberschreitung, da die Wegfindungsfunktion für jeden Charakter im Labyrinth aufgerufen wird.

Jitse
quelle