7 ms·
Maze-solving algorithm implemented in sed
- gerdesj 8y agoWhy not indeed. Great fun to play with
- nulldata 8y agoReminds me that I should probably finish my article on how I wrote a BrainF*ck interpreter in sed.
- BlackLotus89 8y agoThis I would like to see. Do you have the code somewhere right now or do you plan to release it with the article?
- gizmo385 8y agoIf 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/ https://github.com/kanaka/mal/ [2] https://github.com/kanaka/mal/tree/master/awk https://github.com/kanaka/mal/tree/master/awk
- kritixilithos 8y agoThere's even an implementation of lisp in sed :) https://github.com/shinh/sedlisp/ https://github.com/shinh/sedlisp/
- snazz 8y agoVery 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?
- jniedrauer 8y agoIt 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.
- cmiller1 8y agoIt's pretty nicely put together and commented, still trying to work through exactly how the interleave steps work though.
- davidten 8y agoI’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
- saevarom 8y agoI 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.
- kritixilithos 8y agoThat'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}`.
- bjoko 8y agoOn macOS: install gnu-sed via Homebrew.
- NeccoNeko 8y agoIt works with the GNU sed that ships with GitBash on Windows.
- Syzygies 8y agoAt 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.
- dang 8y agoWow. Can you say more about what it did?
- Syzygies 8y agoKodak'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.
- timvisee 8y agoYou, are a genius. I didn't know sed could do such things, awesome!
- zrobotics 8y agoThis, 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.
- jonahx 8y agoThe visualization is beautifully instructive, too -- the essence of the algorithm explained in about a second.
- loa-in-backup 8y agoIt would seem the site suffers from hug of death.
- rwmj 8y agoNice - 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/b8d80d3df90eaa32ef9886b87fe79205ede24b49/server/protostrings.sed#L33 https://github.com/libguestfs/nbdkit/blob/b8d80d3df90eaa32ef...
- w323898 8y agoBut is it faster than Rust?
- 4thaccount 8y agoAwesome :)
- anonair 8y agohttps://github.com/bolknote/SedChess https://github.com/bolknote/SedChess another one
- ape4 8y agoProbably BrainFuck would be easier, congrats.
- userbinator 8y agoIt reminds me of this (scroll down to "Regular Expression Pathfinding" section): http://realgl.blogspot.com/2013/08/battlecode.html 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.
- yawaramin 8y agoThat's amazing.
- orthecreedence 8y agoCool! Reminds me of an AWK-based music generator I used to listen to while programming: http://kmkeen.com/awk-music/ http://kmkeen.com/awk-music/ I love when people use tools for bizarre things outside their intended purposes.
- level3 8y agoFor 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 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.
- kritixilithos 8y agoAre you tails? Anyways, thanks for helping me tie with first place :)
- level3 8y agoNo, 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 :)
- kritixilithos 8y agoReached 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 :)