2D Maze Minus 1D

Question

This challenge is about converting 2D mazes into 1D mazes.

Overview

+-+-+-+-+-+-+   +-+-+-+-+-+-+                    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

For the purposes of this challenge, a traditional 2D maze is a rectangular maze formed from lattice points where all of the following holds:

• It is closed (the outer rim is connected by walls).
• All lattice points are connected to walls
• It is connected (for every two spaces X and Y there is a path between them)
• It is acyclic (there are no paths from any space X back to X without backtracking)

Figure 1 shows a traditional 2D maze. These mazes have three areas of interest:

• Dead ends - places from which there is only one available path
• Corridors - places from which there are two available paths
• Decision points - places from which there are three or four available paths

For every such maze, one can create a graph where the dead ends and decision points are nodes, and there is an edge between every two nodes connected by a path along a corridor. Figure 2 shows the same maze with such nodes labeled, and Figure 3 the maze's graph (in ASCII and Graphviz dot notation).

1D mazes

1D mazes incorporate warp points, which come in pairs, and are identified using a letter (in either case). Figure 4 shows an example 1D maze. This is otherwise identical to a 2D maze with a height of 1, as shown in Figure 5. Note in particular in Figure 5 the lattice point positions marked by +, which alternate left to right; in the 1D maze, every other character starting with the leftmost wall is also a lattice point.

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

The rules for navigating this maze are as follows. Every move can be represented as either forward (>) or backward (<). Forward and backward here by default have the same meaning as our intuitive spatial awareness; forward goes to the position immediately to the right, and backwards immediately to the left.

Warp points represent locations that asymmetrically swap connectedness with neighbors. If you're coming from a neighbor to a warp point, the position of the two warp points is swapped; if you're coming from a warp point to a neighbor, they are not swapped. For example, in Figure 6, moving backwards from 1 brings you to 2 (since 1 is the neighbor of G, and we're moving from the neighbor, points 2 and @ are swapped). Moving forward from 2 (warp point G) brings you to 3 (here, we're starting from a warp point, so there's no swap). Likewise, moving backwards from 3 brings you to @.

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

Figure 6 also shows an example navigation from X to Y, using the sequence of moves <<>><>>>>>. These moves bring you to the points labeled 123456789^ respectively, in that order. Feel free to explore it yourself using the code snippet in the next section.

Converting 2D to 1D

Given a 1D maze, one can create a graph where each node is either a dead end or a warp point pair, and edges exist between any two nodes connected along a corridor. This graph allows us to compare 1D and 2D mazes.

For example, the 1D maze in Figure 4 is the same maze in Figure 1. To see why, Figure 7 adds labels to dead ends. Using those labels to build a graph, Figure 7's graph is simply Figure 3 again. Figure 8 shows a breakout of building this graph.

|  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

(Note that the labels and layout of each graph were artificially chosen to align for illustration purposes; generally speaking this is a graph isomorphism problem).

The following snippet is provided to help visualize the mechanics of the 1D maze and the connection between the 1D maze, the equivalence graph, and the 2D maze.

var mazeloc = 27; var cheese=21; var pnode=9; var cnode=9;
var spacing = "                            ";
function newCheese() {
   while(cheese==mazeloc){
      var rnum=Math.ceil(Math.random()*23);
      if(rnum>3) ++rnum; if(rnum>9) ++rnum; if(rnum>15)++rnum; if(rnum>21)++rnum;
      cheese=rnum;
   }
   document.getElementById("cheese").innerHTML = spacing.substr(1,cheese)+"#";
}
function getNodeClass(node) {
  switch (node) { case 1: return "ANode"; case 2: return "BNode"; case 3: return "CNode";
      case 4: return "DNode"; case 5: return "ENode"; case 6: return "FNode";
      case 7: return "GNode"; case 8: return "HNode"; case 9: return "INode"; case 10: return "JNode"; } }
function getNodeDefCol(node) {
  switch (node) { case 1: case 2: case 3: case 8: case 9: return "#666"; default: return "#000"; } }
function markMove() {
  var newNode = nodeByLocation(mazeloc);
  if (newNode==0) return;
  var pn = document.getElementsByClassName(getNodeClass(pnode));
  for (var i=0; i<pn.length; ++i) { pn[i].style.color = getNodeDefCol(i); pn[i].style.backgroundColor = "#FFF"; pn[i].style.fontWeight = "400";}
  var cn = document.getElementsByClassName(getNodeClass(cnode));
  for (var i=0; i<cn.length; ++i) { cn[i].style.color = "#800"; cn[i].style.backgroundColor = "#ED9"; cn[i].style.fontWeight="700"; }
  var nn = document.getElementsByClassName(getNodeClass(newNode));
  for (var i=0; i<nn.length; ++i) { nn[i].style.color = "#F00"; nn[i].style.backgroundColor = "#FE8"; nn[i].style.fontWeight="700"; }
  pnode=cnode; cnode=newNode;
}
function nodeByLocation(loc) { switch(loc) { default: return 0;
  case 1: return 1; case 17: return 2; case 5: return 3; case 3: case 7: return 4;
  case 9: case 13: return 5; case 15: case 19: return 6; case 11: case 25: return 7;
  case 23: return 8; case 27: return 9; case 21: return 10; } }
function onClickLeft() {
   switch (mazeloc) {
   case 1: case 5: case 11: case 17: case 23: break;
   case 8: mazeloc=3; break; case 12: mazeloc=25; break;
   case 14: mazeloc=9; break; case 20: mazeloc=15; break;
   case 26: mazeloc=11; break; default: mazeloc=mazeloc-1; break;
   }
   if(mazeloc==cheese) newCheese();
   markMove();
   document.getElementById("inmaze").innerHTML = spacing.substr(1,mazeloc)+"@";
}
function onClickRight() {
   switch (mazeloc) {
   case 3: case 9: case 15: case 21: case 27: break;
   case 2: mazeloc=7; break; case 6: mazeloc=3; break;
   case 8: mazeloc=13; break; case 12: mazeloc=9; break;
   case 14: mazeloc=19; break; case 18: mazeloc=15; break;
   case 24: mazeloc=11; break; default: mazeloc=mazeloc+1;
   }
   if(mazeloc==cheese) newCheese();
   markMove();
   document.getElementById("inmaze").innerHTML = spacing.substr(1,mazeloc)+"@";
}

<div><div style="float:left">
<pre><div id="cheese" style="color:#FA0; font-weight:bold">                     #</div>|<font class='ANode' color='#666'>A</font> <font class='DNode'>D</font>|<font class='CNode' color='#666'>C</font> <font class='DNode'>D</font> <font class='ENode'>E</font>|<font class='GNode'>G</font> <font class='ENode'>E</font> <font class='FNode'>F</font>|<font class='BNode' color='#666'>B</font> <font class='FNode'>F</font> <font class='JNode' color='#666'>J</font>|<font class='HNode' color='#666'>H</font> <font class='GNode'>G</font> <font class='INode' color='#666'>I</font>|
<div id="inmaze" style="color:#00F;  background-color:#FFD">                           @</div><div id="dbg"></div></pre>
<div style="float:left"><button type="button" onclick="onClickLeft()">&lt;</button></div>
<div style="float:right"><button type="button" onclick="onClickRight()">&gt;</button></div></div>
<div style="float:left">
<pre>  <font class='ANode' color='#666'>A</font>         <font class='BNode' color='#666'>B</font>
   \        |
    \       |
     \      |
  <font class='CNode' color='#666'>C</font>---<font class='DNode'>D</font>-<font class='ENode'>E</font>---<font class='FNode'>F</font>
        |   |
    .---<font class='GNode'>G</font>   |
  .'   /    |
  <font class='HNode' color='#666'>H</font> <font class='INode' color='#666'>I</font>-'     <font class='JNode' color='#666'>J</font></pre>
</div>
<div style="float:left">
<pre>  +-+-+-+-+-+-+
  |<font class='ANode' color='#666'>A</font>|   |    <font class='BNode' color='#666'>B</font>|
  + + + + +-+-+
  |   | |     |
  +-+-+ +-+-+ +
  |<font class='CNode' color='#666'>C</font>   <font class='DNode'>D</font> <font class='ENode'>E</font>   <font class='FNode'>F</font>|
  +-+-+-+ +-+ +
  |      <font class='GNode'>G</font>  | |
  + +-+-+-+ + +
  |<font class='HNode' color='#666'>H</font>|<font class='INode' color='#666'>I</font>      |<font class='JNode' color='#666'>J</font>|
  +-+-+-+-+-+-+</pre>
</div></div>

As you navigate the 1D maze in this snippet, the last two nodes you touch are highlighted. The same nodes are highlighted the same way on the equivalence graph and the 2D maze.

---

In general, for any traditional 2D maze an equivalent 1D maze of this type can be created. A slightly more complex example is Figure 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

This maze has a node with four paths (E in Figure 10). Figure 11 shows its graph. Figure 12 is an equivalent 1D maze; and Figure 13 shows the same maze with labels for dead ends to compare with Figure 11.

Challenge

Given a 2D Maze as input, write a function or program that transforms the 2D maze into a 1D maze with warp points. Warp points may use any of the 52 letters in each case.

Input guarantees (if any of these aren't met in the input you don't have to deal with it):

• The input maze is connected (that is, you can always go from any spot to any other).
• The input maze is closed.
• The input maze is rectangular.
• All lattice points use +.
• All walls between lattice points on the same row use |
• All walls between lattice points in the same column use -.
• All spaces are part of a path (and all inside the maze).
• Paths are all spaces (this will always be traditional, non-warping)
• Paths are exactly one space wide.
• The maze is built by connecting points on a lattice.
• There are no more than 52 total nodes (i.e., dead ends plus decision points) in the maze's graph.

Output format:

1. Your output should be a single line showing a 1D maze.
2. Your output should have no leading/trailing whitespace; except that a trailing newline is fine.
3. The first character and every other character afterwards are lattice points.
4. All walls should be on lattice points; and all warp points between them.
5. The graph of your 1D maze should be equivalent to the graph of the 2D maze.
6. Your 1D mazes must be compact; all non-lattice points must be dead ends (i.e., adjacent to walls) or warp points.
7. The only letters in your output should be warp points. Each warp point occurs on the line exactly twice.

Example:

|  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

This is code-golf. The winner is the correct non-loophole submission with the least bytes.

Testing

There are no test cases for this challenge, since there are a large number of correct outputs for any nontrivial maze.

I have, however, built a checker in C++ (this checker graphs both solutions through a graph canonicalization).

In addition, here are a few examples to help illustrate proper formatting:

Example 1

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

Example 2

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

More examples can be found in here.

Answer 1

Python 2 with 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+'|'

(The fifth and sixth lines each begin with a tab, not four spaces as StackExchange shows.)

• Saved six bytes rearranging some arithmetic
• Saved seven bytes using a slice instead of zip
• Saved three bytes using g+=tuple(v.neighbors()) instead of g.add_edge(*v.neighbors())
• Saved seven bytes using g-=g.es[g.incident(v)] instead of g.delete_edges(g.incident(v))
• Saved eleven bytes aliasing g.d=g.degree
• Saved 52 bytes (!) eliminating a loop which contracted all the corridors by replacing degree-2 vertices with an edge between their neighbors. Instead, the output loop just ignores these vertices.
• Saved 13 bytes noticing that when assigning names, igraph doesn't care if the provided iterable is too long
• Saved four bytes by not having a variable R for the number of rows, moving its calculation to the only use point
• Saved two bytes changing the second-level indentation to tabs instead of spaces
• Saved six bytes rearranging 2*(i%C) to i%C*2, 2*(i/C) to i/C*2, and (C-1)*j to j*C-j
• Saved four bytes naming N='n'
• Saved one byte determining if a character is space using <'-' rather than ==' ', under the assumption that only valid characters appear.
• Then realized I can name the vertex attribute ' ' instead of 'n', and reuse N for the two literal spaces in the source, and ==N instead of <'-', saving five more bytes

A somewhat ungolfed version follows. The basic idea is to first make a graph on all the maze vertices (the spots with odd row and column when zero-indexed.) There is an edge from one vertex to the next one on the same row if the following character is a space, and not |. There is an edge from the vertex to the one right below it if the corresponding character in the following row is a space, and not -.

After building this graph, we pick any leaf, and follow along successively adjacent vertices, writing out their names if they are not a corridor, and deleting used edges, till we get stuck. Then we take another leaf and continue till all the edges are gone.

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+'|'

You can see results for the five example mazes. (Unfortunately, igraph is not available on Try It Online; these results were exported from SageMathCloud.)

Answer 2

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)))))

This creates a list of spaces that are in the maze, numbered by index in the string, and uses it to find all the pairs of adjacent spaces. It then stitches the pairs together into longer sequences of points based on matching first/last elements and removes the corridors, so that each sequence is one room in the 1D maze. The sequences are then translated into a string by replacing points on the interior of at least one room (the warp points) into corresponding letters and the rest into spaces.

The 2D maze is read from STDIN and the 1D maze is printed to STDOUT.

Edit: Reduced by 62 bytes rearranging a bunch of stuff and modifying the algorithm a bit, and another 14 by replacing chr with toEnum as suggested by Laikoni.

Edit 2: Saved 13 more bytes by simplifying the logic in (!), 3 by using the list pattern match sugar, and 2 by using >>= to concat in u.