Maze-solving algorithm implemented in sed(devpost.com) |
Maze-solving algorithm implemented in sed(devpost.com) |
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.
I love when people use tools for bizarre things outside their intended purposes.
[1] https://github.com/kanaka/mal/ [2] https://github.com/kanaka/mal/tree/master/awk
He says that the code on Github is actually broken but he forgot in what way.. I still think it’s pretty cool though
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.
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 :)
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.
Nice meeting a fellow golfer, this was fun :)
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}`.