Maze-solving algorithm implemented in sed | Hacker News Reader

Maze-solving algorithm implemented in sed

devpost.com

189 pointszwliew33 comments

At Kodak in the 1970's, my father devised the "Bayer filter" used in digital cameras. At the time, he wrote a research system for image processing in sed.

Wow. Can you say more about what it did?

Kodak's goal was to keep customers happy while selling less silver. Less silver means more grain, so they envisioned digital methods for reducing grain, before printing photographs at some centralized facility (obviously not the pocket I keep my phone in). So the sed program did various convolutions on rather coarse images, for playing with ideas.

My dad's other contribution that stuck was ordered dithering: Bit patterns for various gray levels that worked well next to each other, without edge artifacts at the transitions. Long ago replaced by other methods for higher resolutions, but last seen as part of the DEC logo on their product boxes.

I'm sure that choosing characters to represent gray levels in this sed program got him thinking in that direction. I've never been good at complicated, but he taught me to see simple.

This, this is actual hacking. Absolutely useless, and not at all the correct tool for the job, but exceedingly clever. Shame I can't get the code to work for me on Debian.

The visualization is beautifully instructive, too -- the essence of the algorithm explained in about a second.

Cool! Reminds me of an AWK-based music generator I used to listen to while programming: http://kmkeen.com/awk-music/

I love when people use tools for bizarre things outside their intended purposes.

Reminds me that I should probably finish my article on how I wrote a BrainF*ck interpreter in sed.

This I would like to see. Do you have the code somewhere right now or do you plan to release it with the article?

If you're interested in things being implemented in non-standard languages, I would check out the Make-A-LISP project on Github [1]. Someone even took it upon themselves to write an implementation in AWK :) [2]

[1] https://github.com/kanaka/mal/ [2] https://github.com/kanaka/mal/tree/master/awk

There's even an implementation of lisp in sed :) https://github.com/shinh/sedlisp/

Very cool. For those of you who know sed well, can you actually read the source of this program and understand it, or does it look like garblygook?

It doesn't look that complicated compared to normal sed usage. It's just a series of find/replace for the most part. That said, regex is always pretty hard to read, and putting it together like this is impressive to say the least.

It's pretty nicely put together and commented, still trying to work through exactly how the interleave steps work though.

I’m one of the organizers of Hack N Roll and personally know the guy who built this.

He says that the code on Github is actually broken but he forgot in what way.. I still think it’s pretty cool though

I tried running this on a Mac but got an error. Assumed it was because of some sed version difference. Perhaps the code on Github is just broken.

That's probably because you used BSD sed. Running it on my BSD sed also gives an error, presumably because it thinks the `}` is a part of the label in `binput}`.

However it works fine in GNU sed, and now that you mention it, GNU sed's extensions were not used, like the `-z` flag to slurp all input in one "line" to avoid `:input;$!{N;binput}`.

On macOS: install gnu-sed via Homebrew.

It works with the GNU sed that ships with GitBash on Windows.

You know how artists will use a bunch of plates (or other objects) to make a giant version of the Mona Lisa or something like that to make a photographic mosaic? It's like that. Each line makes sense, but you've got to have some real vision to make this happen, and it's really difficult (nearly impossible) to see the big picture by just looking at a small part.

For reference, here’s a code golf challenge for maze solving. It’s an “endless” challenge (meaning none of the code submissions are viewable) but the shortest sed solution is currently 98 bytes.

http://golf.shinh.org/p.rb?maze+solving

Not quite as hard as the OP, though, since the conditions are slightly easier: only 3 inputs are tested, all of them are the same size, and all of them have exactly one solution.

If I remember right, my overall approach was pruning dead-ends instead of a breadth-first search.

Are you tails? Anyways, thanks for helping me tie with first place :)

No, I’m clock. As you can see, my sed skills aren’t as good as tails :)

Now that I’m 10 bytes behind I might have to give it another try. Though I haven’t golfed in years :/

EDIT: Well, I checked my old code and found a few places to optimize. Now down to 95 bytes :)

Reached 96 bytes (now where would that last byte be hmmmm). And as you can see, my sed skills aren't as good as yours either :)

Nice meeting a fellow golfer, this was fun :)

Nice - I've been getting overly familiar with sed recently because it's one of the few tools that we can trust to be installed for our minimal-dependency NBD server. Unfortunately we also need to work across Linux, FreeBSD and OpenBSD. However I've not needed to write anything as large as this maze-solver. It's text hacks like: https://github.com/libguestfs/nbdkit/blob/b8d80d3df90eaa32ef...

https://github.com/bolknote/SedChess another one

It reminds me of this (scroll down to "Regular Expression Pathfinding" section):

http://realgl.blogspot.com/2013/08/battlecode.html

tl;dr: competition counts cycles but excludes certain standard library functions, one of which is a regex matcher, so someone naturally decides to use it for much of his algorithm.

Why not indeed. Great fun to play with

You, are a genius. I didn't know sed could do such things, awesome!

It would seem the site suffers from hug of death.

That's amazing.

Probably BrainFuck would be easier, congrats.

Awesome :)

But is it faster than Rust?

Reply on news.ycombinator.com