Back in grad school I made many visualization for pairwise gene interactions, in SVG and canvas and other web tech, and the best part was always taking a layout and making it planar. So satisfying. And probably just as insightful as most hairball gene network displays...
Edit: shoot, there's only 20 of them in this. Maybe I should see if any of that old code still runs...
Yeah, I didn't realize there were only 20 until I hit 20 and it didn't give me any more shapes :( I thoroughly enjoyed the ~20 minutes it gave me lol. I need more.
In most cases I was able to imagine the nodes as lying on a fabric (stiched in the form of a tube) that can be turned inside out.
And there are two "ends" to this.
There is one subset of points that describes the upper opening of the tube, and there is another subset that describes the lower opening.
Our job is to arrange the points such that we are looking down through the upper opening and can see all the way through into the empty space through the lower opening.
In this solved state, the upper opening becomes the outermost permit error of the solved graph, and lower opening becomes the inner most / smallest enclosed space inside the solved graph. Rest of the points are just extra points on the fabric itself that should "stay in view".
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints.
Made it to level 7 so far. A heuristic that's working for me is take the node with the most crossing edges and move it to the other side of the crossed edge. Iterating on that tends to lead to a solution.
Since the answer criteria is a layout with no edges crossing, the graphs must be planar. There's probably some primitive graph layout algorithm similar to this heuristic (along with a whole bunch of better ones that are less-suited for doing manually!)
This has been on the frontpage half a dozen times over the years. I don't entirely understand why, because it's not a novel game to start with, and based on the earlier HN threads even the implementation had been ripped off uncredited.
It's kinda fun, like ironing laundry, but I lost count of levels and they were getting longer, but not particularly harder. The biggest challenge is that I can't use the whole screen area to make inner space.
26 comments
[ 2.9 ms ] story [ 53.1 ms ] threadhttps://www.youtube.com/watch?v=mM3U74_CmK0
Edit: shoot, there's only 20 of them in this. Maybe I should see if any of that old code still runs...
In most cases I was able to imagine the nodes as lying on a fabric (stiched in the form of a tube) that can be turned inside out.
And there are two "ends" to this.
There is one subset of points that describes the upper opening of the tube, and there is another subset that describes the lower opening.
Our job is to arrange the points such that we are looking down through the upper opening and can see all the way through into the empty space through the lower opening.
In this solved state, the upper opening becomes the outermost permit error of the solved graph, and lower opening becomes the inner most / smallest enclosed space inside the solved graph. Rest of the points are just extra points on the fabric itself that should "stay in view".
Available for all major platforms and a great way to waste time.
[1] of Putty Fame
https://en.wikipedia.org/wiki/Planarity
https://web.mit.edu/xiphmont/Public/gPlanarity.html
Untangle (in sgt-puzzles)
Since the answer criteria is a layout with no edges crossing, the graphs must be planar. There's probably some primitive graph layout algorithm similar to this heuristic (along with a whole bunch of better ones that are less-suited for doing manually!)
https://news.ycombinator.com/item?id=12937367
https://news.ycombinator.com/item?id=13116845
https://news.ycombinator.com/item?id=16459508
https://news.ycombinator.com/item?id=24050651
(That's just the ones with multiple comments. The submission history for this looks incredibly spammy.)
Indeed it uses Tronix code (http://pulzed.com/demo/tronix11/) unmodified (in iframe, accessible in https://treksit.com/tron/). Albeit now it's mentioned in credits (https://treksit.com/credits.html) that "web app is based" on it, it'll have been more appropriate to say "web app is using code from".
For anyone interested an algorithm for untangling a planar graph is shown at https://link.springer.com/article/10.1007/s00454-008-9130-6 (preprint: https://arxiv.org/pdf/0709.0170.pdf).