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

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

cs.tufts.edu

40 pointsmr_golyadkin5 comments

Also good in the same category:

    Backtracking Iterators
    Jean-Christophe Filliâtre
    https://www.lri.fr/~filliatr/publis/enum2.pdf

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.

So... this solution - 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?

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.

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

Reply on news.ycombinator.com