Interstellar puzzle based on graph theory | Hacker News Reader

Interstellar puzzle based on graph theory

treksit.com

60 pointslovegrenoble25 comments

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

>even the implementation had been ripped off uncredited

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

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.

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.

The game is laying out the graph so it’s planar, https://en.wikipedia.org/wiki/Planar_graph. Definitely related to graph theory.

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.

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 (preprint: https://arxiv.org/pdf/0709.0170.pdf).

There's a version of this puzzle included in Simon Tatham[1]'s Puzzles: 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

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.

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

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

Other games that do this:

https://en.wikipedia.org/wiki/Planarity

https://web.mit.edu/xiphmont/Public/gPlanarity.html

Untangle (in sgt-puzzles)

I once had an ideia like that, haha.

https://www.youtube.com/watch?v=mM3U74_CmK0

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

Click on the background and hold the mouse button down.

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

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

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

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.

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

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

That was a good ride. I Want More!

Got two, then it got tough.

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

Reply on news.ycombinator.com