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.
Hackaday: showcase of the “Why, oh why” side of technology.
Not so! We’ve already got a blanket answer for every “why” — for the challenge/fun of doing it.
With that out of the way, we can move straight on to the “how”. :)
The answer is, of course, “Because we can.” :D
“because it’s fun” or “seems like it’s going to be fun” is also a good reason to start a project.
Because someone said it’s impossible or (even worse) that you can’t do it.
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.
“…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.
Could have used a 555?
Jokes aside, it’s sed to the sed being abused like that. Said script should be deleted.
This is not abuse. Tetris or 2048 in SED – this is abuse. (https://github.com/themattrix/sed2048 )
or this shooter (though it was made in Bash – https://github.com/vaniacer/piu-piu-SH )
“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.”
Neat!
just used the first ascii maze generator from my search results to generate one. Works fine for like 20×20 mazes. Let’s see how long it will take for a 69×69 maze.
I am using this generator: https://www.thenerdshow.com/maze.html (changed the start and end ascii signs on line 125 to S/E)
Very cool and absolutely necessary. Reminds me of a 1991 vi macro that does the same :-)
When he creates a sed script that can beat rogue, call me.
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.
Great description!
Sounds like “shortest path finder” here: http://www.astrolog.org/labyrnth/algrithm.htm#solve
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?
It’s easy enough to try and you’ll have fun doing so.
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.