sed maze solver

instructions.md

Usage

sed -E -f solver.sed input where input is a file containing the maze.

For best results, resize your terminal to match the height of the maze. To disable animations, delete the lines containing p.

Maze format

The solver assumes the following:

• The maze only contains the characters # \nSE
• Every line has the same number of characters
• There is only one start (S) and end (E)
• There exists an unbroken path from the start to the end

There is no need to wrap a border around the maze but it does make the output clearer.

sample-maze

###############################
#     #     #     #     #     #
#  S        #     #           #
#     #     #     #     #     #
### ##### ##### ##### ##### ###
#     #     #     #     #     #
#     #                       #
#     #     #     #     #     #
### ##### ################# ###
#     #     #     #     #     #
#     #     #        E        #
#     #     #     #     #     #
###############################

solver.sed

:input
$!{N;binput}
G

# insert horizontal wall to disable wrapping
s/^[^\n]*\n/&&/
:sub
s/^(#*)[^#\n]([^\n]*\n)/\1#\2/
tsub

:bfs
# insert EOF marker
s/.*/&@/

:rotate1

# interleave first line with markers
s/^([^\n]*\n)([^\n]*\n)/\2\1\2/
:sub1
s/^([^\n@]*)@/\1/
s/^(=*)[^=\n]([^\n]*\n)/\1=\2/
tsub1
s/^(=*)\n/\1=/;s/^/=/
:interleave1
s/=((=[^=])+)/\1=/
tinterleave1
s/=//

s/^([Eudlr].*=) ([^=]*)$/\1U\2/
s/^ (.*=[Eudlr][^=]*)$/D\1/
s/^([Eudlr].*=)S([^=]*)$/\1^\2/
s/^S(.*=[Eudlr][^=]*)$/v\1/

s/=//g
# rotate queue
s/([#\n]+|.)(.*)/\2\1/

# keep rotating until we hit EOF
/^@/!brotate1
s/^@//

s/ ([Eudlr])/R\1/g
s/([Eudlr]) /\1L/g
s/S([Eudlr])/>\1/g
s/([Eudlr])S/\1</g
p

# mark as visited
y/UDLR/udlr/

/S/bbfs
p

:trace
# insert EOF marker
s/.*/&@/

:rotate2

# interleave first line with markers
s/^([^\n]*\n)([^\n]*\n)/\2\1\2/
:sub2
s/^([^\n@]*)@/\1/
s/^(=*)[^=\n]([^\n]*\n)/\1=\2/
tsub2
s/^(=*)\n/\1=/;s/^/=/
:interleave2
s/=((=[^=])+)/\1=/
tinterleave2
s/=//

s/^(v.*=)u([^=]*)$/\1^\2/
s/^(v.*=)d([^=]*)$/\1v\2/
s/^(v.*=)l([^=]*)$/\1<\2/
s/^(v.*=)r([^=]*)$/\1>\2/

s/^u(.*=\^[^=]*)$/^\1/
s/^d(.*=\^[^=]*)$/v\1/
s/^l(.*=\^[^=]*)$/<\1/
s/^r(.*=\^[^=]*)$/>\1/

# exit when end is reached
/E<|>E|^v(.*=E[^=]*)$|^E(.*=\^[^=]*)$/bbreak

s/=//g
# rotate queue
s/([#\n]+|.)(.*)/\2\1/

/^@/!brotate2
s/^@//

s/>u/>^/
s/>d/>v/
s/>l/></
s/>r/>>/

s/u</^</
s/d</v</
s/l</<</
s/r</></
p

btrace
:break

s/=//g
# rotate back
s/^([^@]*)@(.*)$/\2\1/
p

# delete wall
s/^#*\n//

# delete unused paths
s/[udlr]/ /g

# optional: colorize path
s/[v^<>]/\x1B[31m&\x1B[0m/g
s/E/\x1B[32mE\x1B[0m/g
s/E/@/

q