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

A game based on the Havel-Hakimi algorithm

jacquerie.github.io

Post reply on HN
Print view View original

21–28 of 28 posts

Re: A game based on the Havel-Hakimi algorithm

#21

Post by MichaelAza »

DaCapoo wrote: post #13

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 The way that I see it is that…

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.

Re: A game based on the Havel-Hakimi algorithm

#22

Post by sfenu »

DaCapoo wrote: post #13

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 The way that I see it is that…

That's pretty much the Havel-Hakimi algorithm

Re: A game based on the Havel-Hakimi algorithm

#23

Post by cschmidt »

nanofortnight wrote: post #16
DaCapoo wrote: post #13

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

For the curious this Václav 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

Re: A game based on the Havel-Hakimi algorithm

#24

Post by just2n »

rbonvall wrote: post #15

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/ (Say goodbye to your productivity if you like puzzles).

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.

Re: A game based on the Havel-Hakimi algorithm

#25

Post by csense »

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

Post reply on HN