Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Interstellar puzzle based on graph theory

treksit.com

Post reply on HN
Print view View original

11–20 of 27 posts

Re: Interstellar puzzle based on graph theory

#11

Post by ironSkillet »

albert_e wrote: post #7

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.

Re: Interstellar puzzle based on graph theory

#13

Post by nighthawk454 »

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

Re: Interstellar puzzle based on graph theory

#17

Post by scherlock2 »

BugsJustFindMe wrote: post #10

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.

Re: Interstellar puzzle based on graph theory

#18

Post by jsnell »

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

Re: Interstellar puzzle based on graph theory

#19

Post by lovegrenoble »

BugsJustFindMe wrote: post #10

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.

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.

Re: Interstellar puzzle based on graph theory

#20

Post by karmakaze »

jsnell wrote: post #18

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…

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.
Post reply on HN