Skip to content

Instantly share code, notes, and snippets.

@xsot
Last active November 6, 2022 15:05
  • Star 189 You must be signed in to star a gist
  • Fork 5 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save xsot/99a8a4304660916455ba2c2c774e623a to your computer and use it in GitHub Desktop.
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
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
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?

@NullDev
Copy link

NullDev commented Jan 9, 2019

This is amazing

@josephgrossberg
Copy link

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

@jnguyen1098
Copy link

No way...

@arjamizo
Copy link

woops, once again I have this feeling

once again somebody has impressed me on the Internet

gratz

Copy link

ghost 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