Maze Solving Via Text Editing

Linux scripters usually know about sed — the stream editor. It has a simple job: transform text as it whizzes from input to output. So if you wanted to solve a maze, this wouldn’t be the tool you’d think to use, right? Well, if you were [xsot], you’d disagree.

You build a maze using spaces for empty space and # for walls. There’s an S to mark the start position and an E to mark the end. Of course, the maze can also contain newlines. The sed script does an amazing job of solving the problem.

As the author points out:

The main difficulty lies in the lack of the luxuries usually provided in a regular programming language such as:

  • arithmetic
  • data types other than strings
  • more than 2 “variables”

Also, sed regex lacks features present in other regex systems such as PCRE (non-greedy matching, lookaheads, etc).

We will confess, we didn’t pull the whole 122 line script apart to understand it, but it looks like it replaces spaces with special marker characters that relate to the direction from the end to the start. The characters U, D, L, and R indicate the direction. Then it is able to select the closest character and replaces them with arrows (well, a letter v, a caret, and the less than and greater than signs).

A very unusual hack of using sed, we think. The output is even colorized and animated. Amazing.

We can’t say we’ve ever done anything this bizarre with a scripting command. We have looked at scripting many times, though, if you want to brush up. Probably the closest we’ve come is using bash scripts to process binary files.

18 thoughts on “Maze Solving Via Text Editing

    1. Oops, I first hit report instead of reply, the coffee hasn’t kicked in yet.

      As to “Why, oh why”:You can hack by using the best tool for the job but if hacking was limited to that then it would be called engineering. Why build a relay computer in the 21st century? Why design a computer language to be hard to use? Why build something from scratch when it would be cheaper and less time consuming to buy something better?

      There are many answer but the basic one is because it’s fun. Just do not forget that hackers are human and therefore diverse in their tastes and dislikes.

    2. “…the “Why, oh why” side of technology.”

      For the same reason we still have the likes of steam enthusiasts, sailors, morse code radio operators, equestrians, and runners. Just because it’s been superseded doesn’t mean it’s not interesting for a variety of reasons.

  1. “Dr. Walter Bishop : Peter, hold on to these tight. Anti-gravity osmium bullets. Shoot Observers with these and watch them float away like balloons.

    Peter Bishop : If we shoot ’em, they’re dead. Why’d we want ’em to float away?

    Dr. Walter Bishop : …Because it’s cool.

    Peter Bishop : That makes sense Walter.”

  2. The automaton is explained easily enough:
    – Starting at ‘E’, spread out into adjacent spaces,
    – It marks out the “wavefront” using uppercase letters,
    – Each letter indicates the direction (UDLR) it took to get there, but in reverse;
    (ie, showing the way back instead of the way forward)
    – As the wavefront moves, uppercase letters are replaced with lowercase ones,
    – Until the ‘S’ is found, at which point the algorithm changes,
    – The path to ‘S’ is followed back to ‘E’, changing the letters into arrows
    – Finally, all remaining search letters are replaced back with spaces.

    It’s not necessary to mark out the wavefront with capital letters. I’m guessing this was added for effect.

    You can imagine this algorithm as water pouring out from ‘E’. Once ‘S’ is reached, just follow back the path the water took to get there.

    Now, actually doing this in SED is another matter. I’m still not entirely sure how he’s searching up and down.

  3. This is very clever. I don’t think I would be able to do it.

    I have to ask. Is this really considered a maze? It is basically a path from S to E. Would this same algorithm work for a maze that has dead end paths that don’t lead to the E?

  4. The kind of fun thing is that, although the author wrote that it will only handle one S and one E, it will still find at least one shortest path between some S and E if there are multiples of either.

Leave a Reply to Thinkerer Cancel reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.