2D Maze Minus 1D
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
.
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 ofg.add_edge(*v.neighbors())
- Saved seven bytes using
g-=g.es[g.incident(v)]
instead ofg.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)
toi%C*2
,2*(i/C)
toi/C*2
, and(C-1)*j
toj*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 reuseN
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.)