Fun. I gave up when the number got to 9, because the cluster got messy. :(
A game based on the Havel-Hakimi algorithm
11–20 of 28 posts
Re: A game based on the Havel-Hakimi algorithm
#12If you want to reach people in the wide wide world, explain what a degree sequence is in the first paragraph! This is your chance for a bit of mathevangelism!
Re: A game based on the Havel-Hakimi algorithm
#13I have not looked over the Havel-Hakimi algorithm yet, but here's the best way I've found to solve these (with 100% success rate so far)
1. Pick the node with the highest degree 2. Make all the connections for that node until it has a value of zero by connecting it with the highest-value node that it isn't already connected to
For example, in this scenario: http://i.imgur.com/O8MlWzz.png
The way that I see it is that since the highest-degree node needs to make X number of connections, ensure it can make all of those connections before worrying about anything else. In this case, that means start by connecting the 4 to the next highest value node - the 3, then the 2, then the other 2, then the 1.
This leaves the following situation: http://i.imgur.com/9vZjafr.png
It's kind of easy to see where it goes from there. Sure this is a simple example, but as I said it's worked 100% of the time I've tried it.
Re: A game based on the Havel-Hakimi algorithm
#14Crazy I just came across a game with the same exact mechanic in the last week. Can't find it again though.
Re: A game based on the Havel-Hakimi algorithm
#15It reminds me of the 'bridges' game from Simon Tatham's Portable Puzzle Collection. It has the additional restriction that edges cannot cross each other.
http://www.chiark.greenend.org.uk/~sgtatham/puzzles/
(Say goodbye to your productivity if you like puzzles).
Re: A game based on the Havel-Hakimi algorithm
#16I have not looked over the Havel-Hakimi algorithm yet, but here's the best way I've found to solve these (with 100% success rate so far) 1. Pick the node with the highest degree 2. Make all the connections for that node until it has a value of zero by connecting it with the highest-value node that it isn't already connected to For example, in this scenario: http://i.imgur.com/O8MlWzz.png The way that I see it is that…
The above algorithm was proven to work for all degree sequences by Václav in 1955: https://eudml.org/doc/19050 (Non-English)
Re: A game based on the Havel-Hakimi algorithm
#17Crazy I just came across a game with the same exact mechanic in the last week. Can't find it again though.
A friend pointed out that http://www.kongregate.com/games/ewmstaley/strand has a similar mechanic. I wasn't aware of this game when I created mine, though.
Re: A game based on the Havel-Hakimi algorithm
#18Crazy I just came across a game with the same exact mechanic in the last week. Can't find it again though.
A friend pointed out that http://www.kongregate.com/games/ewmstaley/strand has a similar mechanic. I wasn't aware of this game when I created mine, though.
Here is another one, http://www.conceptispuzzles.com/index.aspx?uri=puzzle/hashi but not the one I am thinking of.
Re: A game based on the Havel-Hakimi algorithm
#19It reminds me of the 'bridges' game from Simon Tatham's Portable Puzzle Collection. It has the additional restriction that edges cannot cross each other. http://www.chiark.greenend.org.uk/~sgtatham/puzzles/ (Say goodbye to your productivity if you like puzzles).
Wow. And everyone thought 2048 was addictive.
Re: A game based on the Havel-Hakimi algorithm
#20needs an animation for when you complete a graph.
reward my success!