Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
sed maze solver

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.

###############################
# # # # # #
# S # # #
# # # # # #
### ##### ##### ##### ##### ###
# # # # # #
# # #
# # # # # #
### ##### ################# ###
# # # # # #
# # # E #
# # # # # #
###############################
: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
@jsjohnst

This comment has been minimized.

Copy link

jsjohnst commented Jan 8, 2019

FYI for anyone trying this, you need GNU sed for it to work. If using macOS, you'll need to install gnu-sed from Homebrew and then invoke via gsed rather than sed.

@daidoji

This comment has been minimized.

Copy link

daidoji commented Jan 9, 2019

This is awesome, can you walk through how it works for us among the sed users whose knowledge stops at about s/foo/bar/g?

@NLDev

This comment has been minimized.

Copy link

NLDev commented Jan 9, 2019

This is amazing

@josephgrossberg

This comment has been minimized.

Copy link

josephgrossberg commented Jan 13, 2019

@daidoji 👍 -- even comments in the code would be great!

@jnguyen1098

This comment has been minimized.

Copy link

jnguyen1098 commented Jan 3, 2020

No way...

@arjamizo

This comment has been minimized.

Copy link

arjamizo commented Jan 12, 2020

woops, once again I have this feeling

once again somebody has impressed me on the Internet

gratz

@grimnar

This comment has been minimized.

Copy link

grimnar commented Jan 13, 2020

just wow, amazing

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.