4 ms·

Treksit – Graph theory game

73 points by thenormal 10y ago

thenormal 10y ago
Easy peasy puzzle
- tptacek 10y ago
  Easy peasy? Isn't graph planarity NP-complete?
  - gravypod 10y ago
    Yea the problems were completely no problem! Jokes asside there is a large difference between spacial thinking in the human brain and computationally intense tasks.
  - quantumtremor 10y ago
    Definitely not. Here's a nice algorithm that will actually compute the embedding as well: https://en.wikipedia.org/wiki/Fáry's_theorem https://en.wikipedia.org/wiki/Fáry's_theorem. However straight line embeddings by Fary's theorem can sometimes be much larger than necessary, more recent advancements in computational geometry can compute embeddings with guarantees of much smaller drawings (small wrt the area of the bounding box of the drawn graph).
  - deleted 10y ago
    [deleted]
  - Someone 10y ago
    The player doesn't have to decide whether the graph is planar, but has to find a planar embedding of a planar graph. That's fairly easy; a greedy algorithm that removes crossings at every move mostly seems to do the trick. I think a more interesting game would be to have the player decide whether a graph is planar, with more points scored (or lost, if he answers incorrectly) the fewer moves he makes.
  - GFK_of_xmaspast 10y ago
    Are you thinking graph isomorphism?
  - karlding 10y ago
    No, graph planarity can be determined using Kuratowski's theorem, which essentially states that a graph is planar if and only if it doesn't contain K_{5} or K_{3, 3}. I believe the planarity test algorithm has been improved, such that it can be done in O(n) using the edge addition method [1]. [1] http://www.drdobbs.com/planarity-by-edge-addition/184406070 http://www.drdobbs.com/planarity-by-edge-addition/184406070
subim 10y ago
Fun! This is similar to Simon Tatham's Untangle (http://www.chiark.greenend.org.uk/~sgtatham/puzzles/ http://www.chiark.greenend.org.uk/~sgtatham/puzzles/ and the sgt-puzzles package on Debian systems).
- tantalor 10y ago
  Original version is http://planarity.net/ http://planarity.net/, made by me! I rewrote it in JavaScript a few years back: https://github.com/tantalor/raphael.planarity https://github.com/tantalor/raphael.planarity
  - thebrainkid 10y ago
    I wanted to say thanks for your game! I loved it when it first came out!
jakubp 10y ago
Nice. Went through maybe first 8-10, but it becomes boring without some kind of 'progress bar'. How long before something happens? Will it become harder with time, or what? A commentary or some hint at what's next would be interesting :)
tantalor 10y ago
Looks like this is just a mashup of Tronix by Danijel Duraković with some other visual effects. http://pulzed.com/demo/tronix11/ http://pulzed.com/demo/tronix11/
pbhjpbhj 10y ago
J age 11yo says it's "cool-a-rooney". Personally I liked it, but the instructions were too terse to get us started properly and the hyperspeed thing is a little strange, I assume it's just a distraction? One problem we had was that J opened the menu at the bottom of the [small] playing area, that covered the "right arrow" that moves on to the next map. It wasn't obvious how to get back to playing, the "play" button didn't close the menu and the collapse arrow wasn't visually apparent.
- swergi 10y ago
  Press the same button to collapse.
johnhenry 10y ago
I'm more impressed by the background than the game itself, though both are well done.
pimlottc 10y ago
Nifty. The arbitrary size of the playfield (and its invisible border) was annoying at times, though. More suggestions: * A reset button when things get too messed up * A "check my work" button that highlights errors, which can be hard to see when there get to be a lot of points and edges * Ability to select and drag multiple points (particularly useful when you need to shift an entire section over to have more room to work * A clearer explanation of the UI (I was reluctant to click on the diamond icons for fear of losing my progress) * Some sort of ending (even just a "Congratulations" message)
- bjackman 10y ago
  There is a reset button if you click the upward-pointing arrow at the bottom of the playfield then the "play" icon. Also loved this game. Found it challenging - seems like a good starting point is to find the nodes with the least links and put them around the edge, maintaining all the symmetries you can. Love the feeling of inversion that you get when you eliminate a load of crosses in one move.
dharma1 10y ago
loved it. it's interesting how quickly the brain develops a sort of intuition how to solve them after a few levels. Would be good if there was a leaderboard with times
am185 10y ago
what happens after 20? there was nothing?
applecrazy 10y ago
I was doing a puzzle and it showed me a button to a "restricted area"- is this normal?
wodenokoto 10y ago
Nice game, but as others have mentioned, the game area is way too small, and you need to able to move the entire graph as one, as you often get points placed towards a corner when you are trying out different positions of points. Also the "restricted area" link with the "Bonus" alt-text feels like it takes you on a bit of a spammy ride. I tried it, and it took me to a site that said something about randomly generated music and a link with the text "show me something cool", which took me to yet another page, in yet another window with a bunch of animated dots. Completely irrelevant and distracting.
skottk 10y ago
And here I thought that my years fighting with UML modeling tools would go completely wasted.

73 points by thenormal 10y ago

thenormal 10y ago

Easy peasy puzzle

tptacek 10y ago
Easy peasy? Isn't graph planarity NP-complete?
- gravypod 10y ago
  Yea the problems were completely no problem! Jokes asside there is a large difference between spacial thinking in the human brain and computationally intense tasks.
- quantumtremor 10y ago
  Definitely not. Here's a nice algorithm that will actually compute the embedding as well: https://en.wikipedia.org/wiki/Fáry's_theorem https://en.wikipedia.org/wiki/Fáry's_theorem. However straight line embeddings by Fary's theorem can sometimes be much larger than necessary, more recent advancements in computational geometry can compute embeddings with guarantees of much smaller drawings (small wrt the area of the bounding box of the drawn graph).
- deleted 10y ago
  [deleted]
- Someone 10y ago
  The player doesn't have to decide whether the graph is planar, but has to find a planar embedding of a planar graph. That's fairly easy; a greedy algorithm that removes crossings at every move mostly seems to do the trick. I think a more interesting game would be to have the player decide whether a graph is planar, with more points scored (or lost, if he answers incorrectly) the fewer moves he makes.
- GFK_of_xmaspast 10y ago
  Are you thinking graph isomorphism?
- karlding 10y ago
  No, graph planarity can be determined using Kuratowski's theorem, which essentially states that a graph is planar if and only if it doesn't contain K_{5} or K_{3, 3}. I believe the planarity test algorithm has been improved, such that it can be done in O(n) using the edge addition method [1]. [1] http://www.drdobbs.com/planarity-by-edge-addition/184406070 http://www.drdobbs.com/planarity-by-edge-addition/184406070

subim 10y ago

Fun! This is similar to Simon Tatham's Untangle (http://www.chiark.greenend.org.uk/~sgtatham/puzzles/ http://www.chiark.greenend.org.uk/~sgtatham/puzzles/ and the sgt-puzzles package on Debian systems).

tantalor 10y ago
Original version is http://planarity.net/ http://planarity.net/, made by me! I rewrote it in JavaScript a few years back: https://github.com/tantalor/raphael.planarity https://github.com/tantalor/raphael.planarity
- thebrainkid 10y ago
  I wanted to say thanks for your game! I loved it when it first came out!

jakubp 10y ago

Nice. Went through maybe first 8-10, but it becomes boring without some kind of 'progress bar'. How long before something happens? Will it become harder with time, or what? A commentary or some hint at what's next would be interesting :)

tantalor 10y ago

Looks like this is just a mashup of Tronix by Danijel Duraković with some other visual effects. http://pulzed.com/demo/tronix11/ http://pulzed.com/demo/tronix11/

pbhjpbhj 10y ago

J age 11yo says it's "cool-a-rooney". Personally I liked it, but the instructions were too terse to get us started properly and the hyperspeed thing is a little strange, I assume it's just a distraction? One problem we had was that J opened the menu at the bottom of the [small] playing area, that covered the "right arrow" that moves on to the next map. It wasn't obvious how to get back to playing, the "play" button didn't close the menu and the collapse arrow wasn't visually apparent.

swergi 10y ago
Press the same button to collapse.

johnhenry 10y ago

I'm more impressed by the background than the game itself, though both are well done.

pimlottc 10y ago

Nifty. The arbitrary size of the playfield (and its invisible border) was annoying at times, though. More suggestions: * A reset button when things get too messed up * A "check my work" button that highlights errors, which can be hard to see when there get to be a lot of points and edges * Ability to select and drag multiple points (particularly useful when you need to shift an entire section over to have more room to work * A clearer explanation of the UI (I was reluctant to click on the diamond icons for fear of losing my progress) * Some sort of ending (even just a "Congratulations" message)

bjackman 10y ago
There is a reset button if you click the upward-pointing arrow at the bottom of the playfield then the "play" icon. Also loved this game. Found it challenging - seems like a good starting point is to find the nodes with the least links and put them around the edge, maintaining all the symmetries you can. Love the feeling of inversion that you get when you eliminate a load of crosses in one move.

dharma1 10y ago

loved it. it's interesting how quickly the brain develops a sort of intuition how to solve them after a few levels. Would be good if there was a leaderboard with times

am185 10y ago

what happens after 20? there was nothing?

applecrazy 10y ago

I was doing a puzzle and it showed me a button to a "restricted area"- is this normal?

wodenokoto 10y ago

Nice game, but as others have mentioned, the game area is way too small, and you need to able to move the entire graph as one, as you often get points placed towards a corner when you are trying out different positions of points. Also the "restricted area" link with the "Bonus" alt-text feels like it takes you on a bit of a spammy ride. I tried it, and it took me to a site that said something about randomly generated music and a link with the text "show me something cool", which took me to yet another page, in yet another window with a bunch of animated dots. Completely irrelevant and distracting.

skottk 10y ago

And here I thought that my years fighting with UML modeling tools would go completely wasted.