5 ms·

A game based on the Havel-Hakimi algorithm

88 points by jnotarstefano 12y ago

ajanuary 12y ago
A greedy algorithm seems to be successful with the graphs in this game. Pick the node with the highest degree, connect it to the other nodes with the highest degrees, repeat.
- PeterSmit 12y ago
  Or connect the node with the highest degree with the node with the lowest degree.
  - ajanuary 12y ago
    I just tried this and several times the highest degree was already connected with the lowest degree, so I either had to pick another highest degree node (if there was a tie), pick the next highest degree and connect it with the lowest degree, or pick the next lowest degree and connect it with the highest degree. They all seemed to work out okay. I find it interesting that yours appears simpler on the face of it, but has more edge cases. Seems like mine would be simpler if you were actually writing out the steps properly.
  - darkmighty 12y ago
    Not only that but also connect the highest with greatest connectivity to the lowest with greatest connectivity to avoid "orphan" nodes.
- dangerlibrary 12y ago
  A naive greedy algorithm will eventually find a situation where the two nodes with the highest degrees are already connected. Another place where a simple greedy algorithm falls down is a field of many nodes with the same degree, where the greedy algorithm doesn't give information about which two to connect. I think the problem is a bit deeper than it seems in the first few iterations.
  - ajanuary 12y ago
    You're correct, I didn't specify it well enough. Pick the node with the highest unassigned degree, connect it to the other unconnected nodes with the highest unassigned degrees (where unassigned degree is the difference between the target degree and the degree of edges we've assigned in previous iterations) I don't fully understand your second point. If there isn't a requirement to create a connected graph it can pick arbitrarily between nodes of equal unassigned degrees. [1] My brain is too tired to come up with a better term than unassigned
- gjm11 12y ago
  This is in fact the Havel-Hakimi algorithm.
NoodleIncident 12y ago
This is nice! I got stuck and gave up when there got to be nodes with 6s on them, but that's just because I'm in class. Given that the only reason to select an edge right now is to delete it, perhaps the delete action could be mapped to a click, rather than a click plus a backspace. Also, a reset level button would be nice.
devilshaircut 12y ago
Pretty fun game. Clever way to scout internships as well. Hah!
NaNaN 12y ago
Fun. I gave up when the number got to 9, because the cluster got messy. :(
kaitai 12y ago
If 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!
DaCapoo 12y ago
I 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 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 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.
- nanofortnight 12y ago
  The above algorithm was proven to work for all degree sequences by Václav in 1955: https://eudml.org/doc/19050 https://eudml.org/doc/19050 (Non-English)
  - cschmidt 12y ago
    For the curious this Václav Havel http://en.wikipedia.org/wiki/V._J._Havel http://en.wikipedia.org/wiki/V._J._Havel is not the better known Czech politician of the same name http://en.wikipedia.org/wiki/V%C3%A1clav_Havel http://en.wikipedia.org/wiki/V%C3%A1clav_Havel
- MichaelAza 12y ago
  My intuition on this was similar - Pick the highest degree node and connect it to a node of the same degree if available or to one with the next-highest degree, preferring nodes with less connections over those with more. Repeat. Worked for me so far, and I'm about 6 levels in with the largest node being 8.
- sfenu 12y ago
  That's pretty much the Havel-Hakimi algorithm
sitkack 12y ago
Crazy I just came across a game with the same exact mechanic in the last week. Can't find it again though.
- jnotarstefano 12y ago
  A friend pointed out that http://www.kongregate.com/games/ewmstaley/strand http://www.kongregate.com/games/ewmstaley/strand has a similar mechanic. I wasn't aware of this game when I created mine, though.
  - sitkack 12y ago
    Here is another one, http://www.conceptispuzzles.com/index.aspx?uri=puzzle/hashi http://www.conceptispuzzles.com/index.aspx?uri=puzzle/hashi but not the one I am thinking of. http://en.wikipedia.org/wiki/Hashiwokakero http://en.wikipedia.org/wiki/Hashiwokakero
rbonvall 12y ago
It 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/ http://www.chiark.greenend.org.uk/~sgtatham/puzzles/ (Say goodbye to your productivity if you like puzzles).
- snake_plissken 12y ago
  Wow. And everyone thought 2048 was addictive.
- just2n 12y ago
  This needs a donate button. There's more fun here than in most AAA titles. Hell, you could turn all of these into Android/iOS apps and make millions.
spot 12y ago
needs an animation for when you complete a graph. reward my success!
csense 12y ago
This should keep a completed level on the screen until you click to advance. Also, deleting links needs some work: I think the hit detection is too small. Also, a mouse-only way to delete would be nice -- how about right clicking? Double clicking would be another possibility (and I assume more touch friendly).
tn13 12y ago
Within 3 minutes of playing this game I was able to see what Havel-Hakimi algorithm is.
btkostner 12y ago
Congrats. You just showed maths far better than any of my high school classes.
kaahne 12y ago
Pretty fun game. I thought that greedy algorithm would not work with this problem, so I wrote a basic genetic algorithm to find a solution, refining it as I went. Bit of overkill, but fun game overall !

88 points by jnotarstefano 12y ago

A greedy algorithm seems to be successful with the graphs in this game. Pick the node with the highest degree, connect it to the other nodes with the highest degrees, repeat.

PeterSmit 12y ago
Or connect the node with the highest degree with the node with the lowest degree.
- ajanuary 12y ago
  I just tried this and several times the highest degree was already connected with the lowest degree, so I either had to pick another highest degree node (if there was a tie), pick the next highest degree and connect it with the lowest degree, or pick the next lowest degree and connect it with the highest degree. They all seemed to work out okay. I find it interesting that yours appears simpler on the face of it, but has more edge cases. Seems like mine would be simpler if you were actually writing out the steps properly.
- darkmighty 12y ago
  Not only that but also connect the highest with greatest connectivity to the lowest with greatest connectivity to avoid "orphan" nodes.
dangerlibrary 12y ago
A naive greedy algorithm will eventually find a situation where the two nodes with the highest degrees are already connected. Another place where a simple greedy algorithm falls down is a field of many nodes with the same degree, where the greedy algorithm doesn't give information about which two to connect. I think the problem is a bit deeper than it seems in the first few iterations.
- ajanuary 12y ago
  You're correct, I didn't specify it well enough. Pick the node with the highest unassigned degree, connect it to the other unconnected nodes with the highest unassigned degrees (where unassigned degree is the difference between the target degree and the degree of edges we've assigned in previous iterations) I don't fully understand your second point. If there isn't a requirement to create a connected graph it can pick arbitrarily between nodes of equal unassigned degrees. [1] My brain is too tired to come up with a better term than unassigned
gjm11 12y ago
This is in fact the Havel-Hakimi algorithm.

NoodleIncident 12y ago

This is nice! I got stuck and gave up when there got to be nodes with 6s on them, but that's just because I'm in class. Given that the only reason to select an edge right now is to delete it, perhaps the delete action could be mapped to a click, rather than a click plus a backspace. Also, a reset level button would be nice.

devilshaircut 12y ago

Pretty fun game. Clever way to scout internships as well. Hah!

NaNaN 12y ago

Fun. I gave up when the number got to 9, because the cluster got messy. :(

kaitai 12y ago

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

DaCapoo 12y ago

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

nanofortnight 12y ago
The above algorithm was proven to work for all degree sequences by Václav in 1955: https://eudml.org/doc/19050 https://eudml.org/doc/19050 (Non-English)
- cschmidt 12y ago
  For the curious this Václav Havel http://en.wikipedia.org/wiki/V._J._Havel http://en.wikipedia.org/wiki/V._J._Havel is not the better known Czech politician of the same name http://en.wikipedia.org/wiki/V%C3%A1clav_Havel http://en.wikipedia.org/wiki/V%C3%A1clav_Havel
MichaelAza 12y ago
My intuition on this was similar - Pick the highest degree node and connect it to a node of the same degree if available or to one with the next-highest degree, preferring nodes with less connections over those with more. Repeat. Worked for me so far, and I'm about 6 levels in with the largest node being 8.
sfenu 12y ago
That's pretty much the Havel-Hakimi algorithm

sitkack 12y ago

Crazy I just came across a game with the same exact mechanic in the last week. Can't find it again though.

jnotarstefano 12y ago
A friend pointed out that http://www.kongregate.com/games/ewmstaley/strand http://www.kongregate.com/games/ewmstaley/strand has a similar mechanic. I wasn't aware of this game when I created mine, though.
- sitkack 12y ago
  Here is another one, http://www.conceptispuzzles.com/index.aspx?uri=puzzle/hashi http://www.conceptispuzzles.com/index.aspx?uri=puzzle/hashi but not the one I am thinking of. http://en.wikipedia.org/wiki/Hashiwokakero http://en.wikipedia.org/wiki/Hashiwokakero

rbonvall 12y ago

It 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/ http://www.chiark.greenend.org.uk/~sgtatham/puzzles/ (Say goodbye to your productivity if you like puzzles).

snake_plissken 12y ago
Wow. And everyone thought 2048 was addictive.
just2n 12y ago
This needs a donate button. There's more fun here than in most AAA titles. Hell, you could turn all of these into Android/iOS apps and make millions.

spot 12y ago

needs an animation for when you complete a graph. reward my success!

csense 12y ago

This should keep a completed level on the screen until you click to advance. Also, deleting links needs some work: I think the hit detection is too small. Also, a mouse-only way to delete would be nice -- how about right clicking? Double clicking would be another possibility (and I assume more touch friendly).

tn13 12y ago

Within 3 minutes of playing this game I was able to see what Havel-Hakimi algorithm is.

btkostner 12y ago

Congrats. You just showed maths far better than any of my high school classes.

kaahne 12y ago

Pretty fun game. I thought that greedy algorithm would not work with this problem, so I wrote a basic genetic algorithm to find a solution, refining it as I went. Bit of overkill, but fun game overall !