3 ms·

Breadth-First Numbering: A Small Exercise in Algorithm Design (2000) [pdf]

• taeric 12y ago
  As much as I love the exploration of blind spots that we all have, I am a little queasy on the implied distinction of programmers into "functional" and "non-functional." That is, it seems sad that we have programmers that would shun or pick tools strictly on their paradigm. And, knowing that such exist, it seems somewhat obvious that some massive blind spots would emerge.
• brandonbloom 12y ago
  Also good in the same category: Backtracking Iterators Jean-Christophe Filliâtre https://www.lri.fr/~filliatr/publis/enum2.pdf
• mdpopescu 12y ago
  So... this solution - http://pastebin.com/JzjdPDUh http://pastebin.com/JzjdPDUh - written using LinqPad is not as complex as his preferred one and doesn't do three passes as the one in figure 5. Why is the complex one better?
  • jonsen 12y ago
    The "complex one" is better because it is correct. I don't know C#, but as I read your program, I'm pretty sure it's wrong. It seems like you just do a depth first traversal. That way you can't get breadth first numbering all the way through without further "complexity". It's pure luck, that you get his small tree right. Try a bigger tree.
    • mdpopescu 12y ago
      I did try a bigger tree, it's still working correctly. (If it had been a depth-first search it would have been incorrect on that tree too - I know because I did write a depth-first search at first.)