5 ms·

Interstellar puzzle based on graph theory

60 points by lovegrenoble 3y ago

dwpdwpdwpdwpdwp 3y ago
Nice. Made me nostalgic for http://planarity.net/ http://planarity.net/
pimlottc 3y ago
Request: add zoom in-out gestures so you don’t have to rearrange the entire graph when the points are close together
smitty1e 3y ago
Got two, then it got tough.
atum47 3y ago
I once had an ideia like that, haha. https://www.youtube.com/watch?v=mM3U74_CmK0 https://www.youtube.com/watch?v=mM3U74_CmK0
epistasis 3y ago
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...
- helf 3y ago
  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.
albert_e 3y ago
Does anyone else imagine the process of solving these puzzles as turning a crumpled trouser or t-shirt inside out?
- ironSkillet 3y ago
  For me I'm trying to visualize tetrahedral-like shapes and finding what needs to be the "inside" and "outside" of these to eliminate crossings.
  - albert_e 3y ago
    Yes that too. 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".
GauntletWizard 3y ago
There's a version of this puzzle included in Simon Tatham[1]'s Puzzles: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/untangle.html https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/unta... Available for all major platforms and a great way to waste time. [1] of Putty Fame
schoen 3y ago
Other games that do this: https://en.wikipedia.org/wiki/Planarity https://en.wikipedia.org/wiki/Planarity https://web.mit.edu/xiphmont/Public/gPlanarity.html https://web.mit.edu/xiphmont/Public/gPlanarity.html Untangle (in sgt-puzzles)
BugsJustFindMe 3y ago
It's a cute game, but I don't feel like it has any connection to graph theory except in the superficial aspect that there are nodes and edges.
- scherlock2 3y ago
  The game is laying out the graph so it’s planar, https://en.wikipedia.org/wiki/Planar_graph https://en.wikipedia.org/wiki/Planar_graph. Definitely related to graph theory.
- lovegrenoble 3y ago
  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.
alooPotato 3y ago
jeez that UI is frustrating. just make it bigger (full window)
nighthawk454 3y ago
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!)
chris_wot 3y ago
Click on the background and hold the mouse button down.
frowenz 3y ago
Same thing with the ability to choose initial number of points: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/untangle.html https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/unta...
michaelr1998 3y ago
got 10, mostly via brute force, in ~15 minutes
jsnell 3y ago
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. https://news.ycombinator.com/item?id=12937367 https://news.ycombinator.com/item?id=12937367 https://news.ycombinator.com/item?id=13116845 https://news.ycombinator.com/item?id=13116845 https://news.ycombinator.com/item?id=16459508 https://news.ycombinator.com/item?id=16459508 https://news.ycombinator.com/item?id=24050651 https://news.ycombinator.com/item?id=24050651 (That's just the ones with multiple comments. The submission history for this looks incredibly spammy.)
- karmakaze 3y ago
  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.
- forgotpwd16 3y ago
  >even the implementation had been ripped off uncredited Indeed it uses Tronix code (http://pulzed.com/demo/tronix11/ http://pulzed.com/demo/tronix11/) unmodified (in iframe, accessible in https://treksit.com/tron/ https://treksit.com/tron/). Albeit now it's mentioned in credits (https://treksit.com/credits.html 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".
lovegrenoble 3y ago
Based on the original version is http://planarity.net http://planarity.net by @tantalor
cognomano 3y ago
That was a good ride. I Want More!
helf 3y ago
[dead]
forgotpwd16 3y ago
Feels like trying to untangle my headphones (though tangled cords fall under knot theory). For anyone interested an algorithm for untangling a planar graph is shown at https://link.springer.com/article/10.1007/s00454-008-9130-6 https://link.springer.com/article/10.1007/s00454-008-9130-6 (preprint: https://arxiv.org/pdf/0709.0170.pdf https://arxiv.org/pdf/0709.0170.pdf).

60 points by lovegrenoble 3y ago

dwpdwpdwpdwpdwp 3y ago

Nice. Made me nostalgic for http://planarity.net/ http://planarity.net/

pimlottc 3y ago

Request: add zoom in-out gestures so you don’t have to rearrange the entire graph when the points are close together

smitty1e 3y ago

Got two, then it got tough.

atum47 3y ago

I once had an ideia like that, haha. https://www.youtube.com/watch?v=mM3U74_CmK0 https://www.youtube.com/watch?v=mM3U74_CmK0

epistasis 3y ago

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...

helf 3y ago
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.

albert_e 3y ago

Does anyone else imagine the process of solving these puzzles as turning a crumpled trouser or t-shirt inside out?

ironSkillet 3y ago
For me I'm trying to visualize tetrahedral-like shapes and finding what needs to be the "inside" and "outside" of these to eliminate crossings.
- albert_e 3y ago
  Yes that too. 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".

GauntletWizard 3y ago

There's a version of this puzzle included in Simon Tatham[1]'s Puzzles: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/untangle.html https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/unta... Available for all major platforms and a great way to waste time. [1] of Putty Fame

schoen 3y ago

Other games that do this: https://en.wikipedia.org/wiki/Planarity https://en.wikipedia.org/wiki/Planarity https://web.mit.edu/xiphmont/Public/gPlanarity.html https://web.mit.edu/xiphmont/Public/gPlanarity.html Untangle (in sgt-puzzles)

BugsJustFindMe 3y ago

It's a cute game, but I don't feel like it has any connection to graph theory except in the superficial aspect that there are nodes and edges.

scherlock2 3y ago
The game is laying out the graph so it’s planar, https://en.wikipedia.org/wiki/Planar_graph https://en.wikipedia.org/wiki/Planar_graph. Definitely related to graph theory.
lovegrenoble 3y ago
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.

alooPotato 3y ago

jeez that UI is frustrating. just make it bigger (full window)

nighthawk454 3y ago

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!)

chris_wot 3y ago

Click on the background and hold the mouse button down.

frowenz 3y ago

Same thing with the ability to choose initial number of points: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/untangle.html https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/unta...

michaelr1998 3y ago

got 10, mostly via brute force, in ~15 minutes

jsnell 3y ago

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. https://news.ycombinator.com/item?id=12937367 https://news.ycombinator.com/item?id=12937367 https://news.ycombinator.com/item?id=13116845 https://news.ycombinator.com/item?id=13116845 https://news.ycombinator.com/item?id=16459508 https://news.ycombinator.com/item?id=16459508 https://news.ycombinator.com/item?id=24050651 https://news.ycombinator.com/item?id=24050651 (That's just the ones with multiple comments. The submission history for this looks incredibly spammy.)

karmakaze 3y ago
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.
forgotpwd16 3y ago
>even the implementation had been ripped off uncredited Indeed it uses Tronix code (http://pulzed.com/demo/tronix11/ http://pulzed.com/demo/tronix11/) unmodified (in iframe, accessible in https://treksit.com/tron/ https://treksit.com/tron/). Albeit now it's mentioned in credits (https://treksit.com/credits.html 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".

lovegrenoble 3y ago

Based on the original version is http://planarity.net http://planarity.net by @tantalor

cognomano 3y ago

That was a good ride. I Want More!

helf 3y ago

[dead]

forgotpwd16 3y ago

Feels like trying to untangle my headphones (though tangled cords fall under knot theory). For anyone interested an algorithm for untangling a planar graph is shown at https://link.springer.com/article/10.1007/s00454-008-9130-6 https://link.springer.com/article/10.1007/s00454-008-9130-6 (preprint: https://arxiv.org/pdf/0709.0170.pdf https://arxiv.org/pdf/0709.0170.pdf).