Hacker News Reader

Comment by jnotarstefano | Hacker News Reader

I apologize for the self promotion, but some people told me they immediately grasped the Havel-Hakimi Algorithm by solving this puzzle I made: http://jacquerie.github.io/hh/

View on HN

No need to apologize! I haven't heard of the Havel-Hakimi Algorithm before, and I don't have the time to actually try and solve your puzzle right now, but I appreciate the link and will check it out later.

Although just reading the description, I do have one question: What is a "degree sequence"? I going to go ahead and assume that it's https://en.wikipedia.org/wiki/Degree_(graph_theory)#Degree_s.... If that's correct, I'd encourage you to add a hyperlink to the term "degree sequence" with that URL, for people like me with zero background in graph theory.

Yes, that's what I meant with "degree sequence". Thanks for the suggestion! That description is more succinct than it needs to be.

Whenever a sequence is graphical, to construct a graph pick any arbitrary node, and connect it to the n other nodes with the largest current numbers (reducing their numbers by one, as the puzzle here does), where n is the number of the node in question. Then pick another arbitrary node, and do the same, iterating until you’ve gone through every node.

As always in these situations, finding an algorithm that works in every case you've tried is fairly straight-forward. Convincing yourself that it's going to work is not that hard.

That challenge is always to prove for definite that it will always work. The proof is in, well, the proof.

That was fun!

Reply on news.ycombinator.com