2D Maze Minus 1D

27

Bei dieser Herausforderung geht es darum, 2D-Labyrinthe in 1D-Labyrinthe zu konvertieren.

Überblick

+-+-+-+-+-+-+   +-+-+-+-+-+-+                    graph {
| |   |     |   |A|   |    B|   A         B        A -- D
+ + + + +-+-+   + + + + +-+-+    \        |        C -- D
|   | |     |   |   | |     |     \       |        D -- E
+-+-+ +-+-+ +   +-+-+ +-+-+ +      \      |        E -- F
|           |   |C   D E   F|   C---D-E---F        E -- G
+-+-+-+ +-+ +   +-+-+-+ +-+ +         |   |        B -- F
|         | |   |      G  | |     .---G   |        F -- J
+ +-+-+-+ + +   + +-+-+-+ + +   .'   /    |        G -- H
| |       | |   |H|I      |J|   H I-'     J        G -- I
+-+-+-+-+-+-+   +-+-+-+-+-+-+     (ascii)        } // (graphviz dot)       
   Figure 1       Figure 2                 Figure 3

Für die Zwecke dieser Herausforderung ist ein traditionelles 2D-Labyrinth ein rechteckiges Labyrinth, das aus Gitterpunkten gebildet wird, an denen alle folgenden Punkte zutreffen:

  • Es ist geschlossen (der äußere Rand ist durch Wände verbunden).
  • Alle Gitterpunkte sind mit Wänden verbunden
  • Es ist verbunden (für jeweils zwei Räume X und Y gibt es einen Pfad zwischen ihnen)
  • Es ist azyklisch (es gibt keine Pfade von einem Raum X zurück zu X ohne Rückverfolgung)

Abbildung 1 zeigt ein traditionelles 2D-Labyrinth. Diese Labyrinthe haben drei Bereiche von Interesse:

  • Sackgassen - Orte, von denen nur ein Pfad verfügbar ist
  • Korridore - Orte, von denen aus zwei Wege zur Verfügung stehen
  • Entscheidungspunkte - Orte, von denen aus drei oder vier Pfade verfügbar sind

Für jedes dieser Labyrinthe kann ein Diagramm erstellt werden, in dem die Sackgassen und Entscheidungspunkte Knoten sind und zwischen jeweils zwei Knoten, die durch einen Pfad entlang eines Korridors verbunden sind, eine Kante vorhanden ist. Abbildung 2 zeigt dasselbe Labyrinth mit diesen Knoten und Abbildung 3 das Diagramm des Labyrinths (in ASCII- und Graphviz-Punktnotation).

1D Labyrinthe

1D-Labyrinthe enthalten paarweise Warp-Punkte, die (in beiden Fällen) durch einen Buchstaben gekennzeichnet sind. Abbildung 4 zeigt ein Beispiel für ein 1D-Labyrinth. Dies ist ansonsten identisch mit einem 2D-Labyrinth mit einer Höhe von 1, wie in Abbildung 5 dargestellt. Beachten Sie insbesondere in Abbildung 5 die mit gekennzeichneten Gitterpunktpositionen +, die sich von links nach rechts abwechseln. Im 1D-Labyrinth ist jedes andere Zeichen, das mit der äußersten linken Wand beginnt, ebenfalls ein Gitterpunkt.

                                 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  D|  D E|G E F|  F  |  G  |    |  D|  D E|G E F|  F  |  G  |
                                 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            Figure 4                         Figure 5

Die Regeln zum Navigieren in diesem Labyrinth lauten wie folgt. Jede Bewegung kann entweder vorwärts ( >) oder rückwärts ( <) dargestellt werden. Vorwärts und Rückwärts haben hier standardmäßig die gleiche Bedeutung wie unser intuitives räumliches Bewusstsein; Vorwärts geht zur Position sofort nach rechts und rückwärts sofort nach links.

Warp-Punkte repräsentieren Orte, die die Verbundenheit mit Nachbarn asymmetrisch vertauschen. Wenn Sie von einem Nachbarn zu einem Warp-Punkt kommen, wird die Position der beiden Warp-Punkte vertauscht. Wenn Sie von einem Warp-Punkt zu einem Nachbarn kommen, werden diese nicht getauscht. Beispiel: Wenn Sie in Abbildung 6 von 1 nach hinten gehen, gelangen Sie zu 2 (da 1 der Nachbar von G ist und wir uns vom Nachbarn entfernen, werden die Punkte 2 und @ vertauscht). Wenn Sie von 2 (Warp-Punkt G) nach vorne gehen, gelangen Sie zu 3 (hier beginnen wir mit einem Warp-Punkt, es gibt also keinen Tausch). Wenn Sie von 3 nach hinten gehen, gelangen Sie ebenfalls zu @.

        54 2367    89^   @1
|  D|  D E|G E F|  F  |  G  |
                     Y     X
          Figure 6

Abbildung 6 zeigt auch ein Beispiel für die Navigation von X nach Y unter Verwendung der Bewegungssequenz <<>><>>>>>. Diese Züge bringen Sie 123456789^in dieser Reihenfolge zu den jeweils markierten Punkten . Probieren Sie es einfach mit dem Code-Snippet im nächsten Abschnitt aus.

Umwandlung von 2D in 1D

In einem 1D-Labyrinth kann ein Diagramm erstellt werden, in dem jeder Knoten entweder eine Sackgasse oder ein Verzerrungspunktpaar ist und Kanten zwischen zwei beliebigen Knoten vorhanden sind, die entlang eines Korridors verbunden sind. Mit dieser Grafik können wir 1D- und 2D-Labyrinthe vergleichen.

Zum Beispiel ist das 1D-Labyrinth in Abbildung 4 das gleiche Labyrinth wie in Abbildung 1. In Abbildung 7 werden den Sackgassen Beschriftungen hinzugefügt, um zu sehen, warum. Unter Verwendung dieser Beschriftungen zum Erstellen eines Diagramms ist das Diagramm von Abbildung 7 einfach wieder Abbildung 3. Abbildung 8 zeigt einen Aufriss der Erstellung dieses Diagramms.

|  D|  D E|G E F|  F  |  G  |
 A   C           B   J H   I 
          Figure 7

|  D|  D E|G E F|  F  |  G  |
+ + + + + + + + + + + + + + + <- lattice points
|A  |C    |     |B   J|H   I| <- dead ends
|A D|C D E|G E F|B F J|H G I| <- all nodes (dead ends+warp points); i.e.:
                                 "where each end is either a dead end
                                  or a warp point pair"; note that each
                                  pair of warp points is the same node.
|A-D|C-D-E|G-E-F|B-F-J|H-G-I| <- corridors; note each is a connection, since
  1   2 3   4 5   6 7   8 9      "edges exist between any two nodes
                                  connected along a corridor"
   graph {                 graph {                 
     A -- D  // 1 <---->     A -- D                
     C -- D  // 2 <---->     C -- D                
     D -- E  // 3 <---->     D -- E                
     G -- E  // 4 <---->     E -- G                
     E -- F  // 5 <---->     E -- F                
     B -- F  // 6 <---->     B -- F                
     F -- J  // 7 <---->     F -- J                
     H -- G  // 8 <---->     G -- H                
     G -- I  // 9 <---->     G -- I                
   }                ^      }
    Built from      |      From Figure 3
     1D maze         `-> isomorphic mappings
                Figure 8

(Beachten Sie, dass die Beschriftungen und das Layout jedes Diagramms zur Veranschaulichung künstlich ausgewählt wurden. Im Allgemeinen handelt es sich hierbei um ein Diagrammisomorphieproblem .)

Das folgende Snippet dient zur Veranschaulichung der Mechanik des 1D-Labyrinths und der Verbindung zwischen dem 1D-Labyrinth, dem Äquivalenzdiagramm und dem 2D-Labyrinth.

Code-Snippet anzeigen

Während Sie in diesem Snippet durch das 1D-Labyrinth navigieren, werden die beiden zuletzt berührten Knoten hervorgehoben. Dieselben Knoten werden im Äquivalenzdiagramm und im 2D-Labyrinth auf dieselbe Weise hervorgehoben.

Im Allgemeinen kann für jedes herkömmliche 2D-Labyrinth ein entsprechendes 1D-Labyrinth dieses Typs erstellt werden. Ein etwas komplexeres Beispiel ist Abbildung 9:

+-+-+-+-+-+-+   +-+-+-+-+-+-+                   graph {
| |   |   | |   |A|   |   |B|   A         B       A -- D
+ + + + + + +   + + + + + + +    \       /        C -- D
|   | | |   |   |   | | |   |     \     /         D -- E
+-+-+ + +-+-+   +-+-+ + +-+-+      \   /          B -- E
|           |   |C   D E    |   C---D-E           E -- F
+-+-+-+ +-+ +   +-+-+-+ +-+ +         |\          E -- I
|         | |   |      F  | |     .---F \         F -- G
+ +-+-+-+ + +   + +-+-+-+ + +   .'   /   \        G -- H
| |       | |   |G|H      |I|   G H-'     I       H -- I
+-+-+-+-+-+-+   +-+-+-+-+-+-+     (ascii)       } // (graphviz dot)
   Figure 9       Figure 10             Figure 11

|  D|  D E  |F E  |  F  |       |  D|  D E  |F E  |  F  |
                                 A   C     I     B G   H
      Figure 12                       Figure 13

Dieses Labyrinth hat einen Knoten mit vier Pfaden (E in Abbildung 10). Abbildung 11 zeigt die Grafik. Fig. 12 ist ein äquivalentes 1D-Labyrinth; und 13 zeigt dasselbe Labyrinth mit Bezeichnungen für Sackgassen zum Vergleich mit 11.

Herausforderung

Schreiben Sie mit einem 2D-Labyrinth als Eingabe eine Funktion oder ein Programm, das das 2D-Labyrinth in ein 1D-Labyrinth mit Verzerrungspunkten umwandelt. Warp Points können jeweils einen der 52 Buchstaben verwenden.

Eingabegarantien (wenn eine dieser Garantien in der Eingabe nicht erfüllt ist, müssen Sie sich nicht damit befassen):

  • Das Eingabelabyrinth ist verbunden (dh Sie können jederzeit von einem beliebigen Ort zu einem anderen wechseln).
  • Das Eingabelabyrinth ist geschlossen.
  • Das Eingabelabyrinth ist rechteckig.
  • Alle Gitterpunkte verwenden +.
  • Alle Wände zwischen Gitterpunkten in derselben Reihe werden verwendet |
  • Alle Wände zwischen Gitterpunkten in der gleichen Spalte verwenden -.
  • Alle Räume sind Teil eines Pfades (und alle innerhalb des Labyrinths).
  • Pfade sind alle Leerzeichen (dies wird immer traditionell sein, ohne Verwerfungen)
  • Pfade sind genau ein Leerzeichen breit.
  • Das Labyrinth besteht aus Verbindungspunkten auf einem Gitter.
  • Es gibt nicht mehr als 52 Gesamtknoten (dh Sackgassen plus Entscheidungspunkte) im Diagramm des Labyrinths.

Ausgabeformat:

  1. Ihre Ausgabe sollte eine einzelne Linie sein, die ein 1D-Labyrinth zeigt.
  2. Ihre Ausgabe sollte kein führendes / nachfolgendes Leerzeichen enthalten. mit der Ausnahme, dass eine nachgestellte Zeile in Ordnung ist.
  3. Das erste und jedes weitere Zeichen sind Gitterpunkte.
  4. Alle Wände sollten auf Gitterpunkten stehen; und alle Warppunkte zwischen ihnen.
  5. Das Diagramm Ihres 1D-Labyrinths sollte dem Diagramm des 2D-Labyrinths entsprechen.
  6. Ihre 1D-Labyrinthe müssen kompakt sein. Alle Nichtgitterpunkte müssen Sackgassen (dh angrenzend an Wände) oder Verzerrungspunkte sein.
  7. Die einzigen Buchstaben in Ihrer Ausgabe sollten Verzerrungspunkte sein. Jeder Verzerrungspunkt tritt genau zweimal auf der Linie auf.

Beispiel:

|  D|  D E|G E F|  F  |  G  | <- (1,2) The single line output
+ + + + + + + + + + + + + + + <- lattice point spacing... (3) 
                                 (4,6) lattice points are all walls or spaces
                                 (5) See Figure 8
                                 (7) D, E, F, G appear twice; no other labels

Das ist Code-Golf. Der Gewinner ist die korrekte, lückenlose Einsendung mit den wenigsten Bytes.

Testen

Es gibt keine Testfälle für diese Herausforderung, da es für jedes nichttriviale Labyrinth eine große Anzahl korrekter Ausgaben gibt.

Ich habe jedoch einen Checker in C ++ erstellt (dieser Checker zeichnet beide Lösungen durch eine Graph-Kanonisierung auf ).

Darüber hinaus finden Sie hier einige Beispiele zur Veranschaulichung der richtigen Formatierung:

Beispiel 1

+-+-+-+-+-+-+
| |   |     |
+ + + + +-+-+
|   | |     |
+-+-+ +-+-+ +
|           |
+-+-+-+ +-+ +
|         | |
+ +-+-+-+ + +
| |       | |
+-+-+-+-+-+-+
->
|  D|  D E|G E F|  F  |  G  |

Beispiel 2

+-+-+-+-+-+-+
| |   |   | |
+ + + + + + +
|   | | |   |
+-+-+ + +-+-+
|           |
+-+-+-+ +-+ +
|         | |
+ +-+-+-+ + +
| |       | |
+-+-+-+-+-+-+
->
|  D|  D E  |F E  |  F  |

Weitere Beispiele finden Sie hier .

code-golf graph-theory maze H Walters
quelle
1
Ich denke, die Erklärung von 1D-Labyrinthen ist überhaupt nicht sehr klar ... Vielleicht würde es helfen, ein kleineres / einfacheres Beispiel hinzuzufügen.
mbomb007
Das ist ziemlich cool. Ja das hilft.
mbomb007
Obwohl Ihr interaktives Skript geholfen hat, ist es immer noch ein schwieriges Problem. Also überspringe ich es einfach. Mein Verständnis dafür ist bestenfalls noch schwach.
mbomb007
Die Beschreibung von 1D Labyrinth ist lückenhaft. Ich musste bis zu Abbildung 7 lesen, um zu verstehen, dass die vertikalen Strichzeichen in einem 1D-Labyrinth Wände sind, über die man nicht fahren kann.
EDC65
1
Beispiel 1 mit dem 1d-Labyrinth in einem 2d-Labyrinth, in dem jedes Buchstabenpaar eine Leiter ist: gist.github.com/sparr/36d6355cc4c785a27b12157666169082
Sparr

Antworten:

3

Python 2 mit Igraph , 492 369 Bytes

import igraph,string
def f(s):
 C=s.find('\n')/2;N=' ';g=igraph.Graph(0,[(i,i+j)for i in range(len(s)/(4*C+4)*C)for j in(1,C)if s[(i/C*2+1)*(2*C+2)+i%C*2+2*j+j/C*3]==N]);V=g.vs;g.d=g.degree;O='';V(_d=1)[N]=N;V(_d_gt=2)[N]=list(string.ascii_letters)
 while g.es:
    v=V(_d=1)[0];O+='|'+v[N]
    while g.d(v):w=v.neighbors()[0];g-=(v,w);v=w;O+=N+v[N]if v[N]else''
 print O+'|'

(Die fünfte und sechste Zeile beginnen jeweils mit einem Tabulator und nicht mit vier Leerzeichen, wie StackExchange zeigt.)

  • Es wurden sechs Bytes gespeichert, um einige Arithmetik neu zu ordnen
  • Sieben Bytes mit einem Slice anstelle von zip gespeichert
  • Gespeichert drei Bytes mit g+=tuple(v.neighbors())anstelle vong.add_edge(*v.neighbors())
  • Sieben Bytes mit g-=g.es[g.incident(v)]anstelle von gespeichertg.delete_edges(g.incident(v))
  • Elf Bytes Aliasing gespeichert g.d=g.degree
  • Es wurden 52 Bytes (!) Gespart, wodurch eine Schleife eliminiert wurde, die alle Korridore zusammenzog, indem Knoten vom Grad 2 durch Kanten zwischen ihren Nachbarn ersetzt wurden. Stattdessen ignoriert die Ausgabeschleife diese Scheitelpunkte.
  • Es wurden 13 Bytes gespart, wobei beachtet wurde, dass es igraph beim Zuweisen von Namen egal ist, ob die bereitgestellte iterable zu lang ist
  • Es wurden vier Bytes gespart, indem keine Variable Rfür die Anzahl der Zeilen vorhanden war, und die Berechnung wurde an den einzigen Verwendungspunkt verschoben
  • Gespeicherte zwei Bytes, die den Einzug der zweiten Ebene in Tabulatoren anstelle von Leerzeichen ändern
  • Gespeichert sechs Bytes neu anordnen 2*(i%C)zu i%C*2, 2*(i/C)zu i/C*2, und (C-1)*jzuj*C-j
  • Benennung von vier Bytes gespeichert N='n'
  • Es wurde ein Byte gespeichert, um zu bestimmen, ob ein Zeichen ein Leerzeichen ist, <'-'und nicht ==' ', unter der Annahme, dass nur gültige Zeichen angezeigt werden.
  • Dann wurde mir klar, dass ich das Vertex-Attribut ' 'anstelle der beiden Literal-Leerzeichen in der Quelle benennen 'n'und wieder verwenden Nund ==Nstattdessen <'-'fünf weitere Bytes sparen kann

Es folgt eine etwas ungelöste Version. Die Grundidee besteht darin, zunächst ein Diagramm über alle Labyrinthscheitelpunkte zu erstellen (die Punkte mit ungerader Zeile und Spalte, wenn sie mit einem Nullindex versehen sind). Wenn das folgende Zeichen ein Leerzeichen ist, gibt es eine Kante von einem Scheitelpunkt zum nächsten in derselben Zeile und nicht |. Wenn das entsprechende Zeichen in der folgenden Zeile ein Leerzeichen ist und nicht, gibt es eine Kante vom Scheitelpunkt bis zum darunter liegenden Scheitelpunkt -.

Nachdem wir dieses Diagramm erstellt haben, wählen wir ein beliebiges Blatt aus und folgen nacheinander benachbarten Scheitelpunkten, schreiben deren Namen auf, wenn sie kein Korridor sind, und löschen die verwendeten Kanten, bis wir stecken bleiben. Dann nehmen wir ein weiteres Blatt und fahren fort, bis alle Kanten verschwunden sind.

import string
import igraph
def f(s):
  C = s.find('\n')/2 # number of maze vertices in each row
  R = len(s)/(4*C+4) # number of rows
  def strpos(r, c):
    """Index of the vertex at row r, col c in the newline-delimited string s"""
    return (2*r+1)*(2*C+2) + 2*c + 1
  def vertpos(i):
    """Index of the i-th vertex in s"""
    return strpos(i/C, i%C)
  g = igraph.Graph(edges=[(i, i+(C if j else 1))
                          for i in range(R*C)
                          for j in (0, 1)
                          if s[vertpos(i)+(2*C+2 if j else 1)] == ' '])
  V = g.vs # the graph's vertex sequence
  O = ''
  V(_degree=1)['n'] = ' ' # All leaves are named space
  W = V(_degree_gt=2) # All warp points...
  W['n'] = list(string.ascii_letters[:len(W)]) # ...are named successive letters
  while g.es: # while any edges remain...
    v = V(_degree=1)[0] # find a leaf
    O += '|'+v['n'] # start a new 'block'
    while v.degree():
      w = v.neighbors()[0] # pick a neighbor
      g -= (v, w) # delete that edge
      v = w
      if v['n']: # If it's a dead end or warp point...
        O += ' '+v['n'] # ...write out the new neighbor
  print O+'|'

Sie können Ergebnisse für die fünf Beispiel-Labyrinthe sehen . (Leider igraphnicht verfügbar bei Try It Online; diese Ergebnisse wurden aus SageMathCloud exportiert .)

Nick Matteo
quelle
4

Haskell - 481 405 387 Bytes

import Data.List
s&t=elemIndices s t
l=last
c!(x:y:z)=l$(y:c)!(x:z):do{[x:p,q]<-mapM([id,reverse]<*>)[[x],[y]];x&[l q];[[]!((q++p):c++z)]}
c![x]=x:[]!c
c!z=z
main=interact(\m->let{g=' '&m;
u=(\\[k|k<-g,length(v>>=(k&))==2])<$>[]!v;
v=[[x,y]|x<-g,y<-g,elem(y-x-1)[0,head$'\n'&m]];
}in '|':(u>>=(++"|").init.(>>=(:" ").toEnum.((+)<*>(+65).(*32).(`div`26)).l.(-1:).(&(nub$u>>=init.tail)))))

Dadurch wird eine Liste der Leerzeichen im Labyrinth erstellt, die durch den Index in der Zeichenfolge nummeriert sind, und zum Suchen aller Paare benachbarter Leerzeichen verwendet. Anschließend werden die Paare zu längeren Punktfolgen zusammengefügt, die auf übereinstimmenden ersten / letzten Elementen basieren, und die Korridore werden entfernt, sodass jede Sequenz einen Raum im 1D-Labyrinth darstellt. Die Sequenzen werden dann in eine Zeichenfolge übersetzt, indem Punkte im Inneren mindestens eines Raums (die Warp-Punkte) in entsprechende Buchstaben und der Rest in Leerzeichen ersetzt werden.

Das 2D-Labyrinth wird aus STDIN gelesen und das 1D-Labyrinth wird auf STDOUT gedruckt.

Edit: Reduziert um 62 Bytes ein paar Sachen neu anordnen , und der Algorithmus ein wenig ändern, und eine andere 14 durch den Ersatz chrmit toEnumwie von Laikoni.

Edit 2: 13 weitere Bytes durch Vereinfachung der Logik in gespeichert (!), 3 durch Verwendung des >>=Listenmuster- Übereinstimmungszuckers und 2 durch Verwendung von Concat in u.

faubi
quelle
Ich denke, Sie brauchen keine Zeilenumbrüche und Leerzeichen, bevor die Pattern Guards o(x:p)q|x==last q=[q++p]|1>0=[]funktionieren , zB sollten sie auch funktionieren.
Laikoni,
Sollte auch toEnumstattdessen funktionieren chr, dann import Data.Charkönnte abgeworfen werden.
Laikoni
Und als letztes, wenn die Herausforderung nach einem Programm oder einer Funktion fragt, können Sie es durch main=interact(\m->...)just ersetzen f m=.... Dies sollte ausreichen, um die Python-Antwort zu unterbieten, wenn Ihnen das etwas bedeutet.
Laikoni