I'm Putting On My Top Hat, Tying Up My White Tie, Brushing Out My Tails -- In That Order

re: I'm Putting On My Top Hat, Tying Up My White Tie, Brushing Out My Tails -- In That Order

Matthew Rodatus — Tue, 30 Nov 2010 12:17:03 GMT

Under step four, the call to visit, you have this:

visit(dependencies, dependencies[dependency][child], list, dead);

Should the second argument be simply child, instead of dependencies[dependency][child]? The latter doesn't make any sense to me, and the former seems to work.

Matthew

The former does not work; did you actually try it? It gives the output "tophat, 0, bowtie, socks, pocketwatch, vest, shirt, 1, shoes, cufflinks, gloves, tailcoat, underpants, trousers", which first, has you putting on your vest before your shirt, and second, has mysteriously gained items "0" and "1" for some strange reason. That is completely and utterly broken.

What you have forgotten is that the "for-in" loop does not give you the members of a collection (as the foreach loop does in C#). It gives you the indicies of the members of the collection. "child" is an index into an array; zero or one, in this case.

- Eric

Optimal Dressing, or A challenge to Eric Lippert | MikeSchinkel.com

Optimal Dressing, or A challenge to Eric Lippert | MikeSchinkel.com — Sun, 15 Jun 2008 08:14:26 GMT

PingBack from http://mikeschinkel.com/blog/optimaldressingorachallengetoericlippert/

How Not To Teach Recursion

Fabulous Adventures In Coding — Thu, 11 Oct 2007 21:39:53 GMT

A Joel On Software reader asked the other day for examples of recursive functions other than old chestnuts

Recursion, Part Zero

Fabulous Adventures In Coding — Fri, 07 Sep 2007 01:59:21 GMT

I’ve mentioned recursive programming techniques several times over the years in this blog ( Topological

re: I'm Putting On My Top Hat, Tying Up My White Tie, Brushing Out My Tails -- In That Order

Mike Schinkel — Fri, 19 Mar 2004 06:28:00 GMT

http://blogs.xtras.net/mikes/PermaLink,guid,57000f55-832e-47e7-9895-2658d4e65d52.aspx

re: I'm Putting On My Top Hat, Tying Up My White Tie, Brushing Out My Tails -- In That Order

Brian Butler — Thu, 18 Mar 2004 16:00:00 GMT

Thanks for another great article, Eric. I had to solve a similar problem last year using XSL and thought the solution was particularly elegant. Given a list of documents, some of which should be read before others:

<page id="A" name="Page 1"/>
<page id="B" name="Page 2">
<prereq id="A"/>
</page>

This transform outputs a valid reading order. In my case I needed to detect circular references and also be able to deal with references to documents not on the list.

<xsl:template name="prereq_sort">
<xsl:param name="unsorted"/>
<xsl:variable name="invalid" select="$unsorted[prereq/@id=$unsorted/@id]" />
<xsl:variable name="valid" select="$unsorted[count(.|$invalid)!=count($invalid)]" />
<xsl:if test="count($valid)=0">No valid pages - possible circular reference!</xsl:if>


<xsl:for-each select="$valid">
<xsl:value-of select="@name" />
</xsl:for-each>


<xsl:if test="count($valid)>0 and count($invalid)>0">
<xsl:call-template name="prereq_sort">
<xsl:with-param name="unsorted" select="$invalid"/>
</xsl:call-template>
</xsl:if>
</xsl:template>

re: I'm Putting On My Top Hat, Tying Up My White Tie, Brushing Out My Tails -- In That Order

Dan Shappir — Thu, 18 Mar 2004 13:21:00 GMT

Indeed, a nice sample. Although your implementation obviously works, the dead variable should be initialized to {}, not to []. This is because it's used as a set, not as an array. Also, in real life (as opposed to an online sample) I would define the visit() function inside topSort() so that it does not pollute the global scope. Done this way, you also avoid the need to pass list and dead as parameters because they are in the closure - less typing and also slightly better performance I believe.

Other examples

Robert Hahn — Wed, 17 Mar 2004 13:27:00 GMT

Hi, Eric.

I understand the code you're setting up well enough, and I agree that it's a quite elegant solution.

But (and there always seems to be one) I think the example makes me think that 80% of the hard work has to be done by the programmer in creating the dependency graph. Because of the example chosen, all it looks like on first inspection is that you are merely serializing a data structure. And you know what? Maybe that's the point - but it seems to me that a trick that requires 80% effort to set up isn't a real productivity enhancer.

So while typing this, I realized that there was another example that people may relate to that may show the value of this useful function.

Consider a software application that is extensible with plug-ins. If some of the plug-ins are dependent on others, then a partial sort is required to determine the order in which they are loaded so that errors can be prevented. Further, since this application has an active plugin developer community, the list of plug-ins is always growing.

The advantages of using a partial sort algorithm as described becomes clear: the dependency graph is much easier to maintain over time than a compiled list -- especially once the number of plugins reaches a large number (50-100). Finally, if someone only wanted to install a subset of plug-ins, they could query the dependency graph with that subset to realize the ordering of their subset.

This example also highlights why you need to be careful of cycles, so I'm looking forward to seeing what you'll say about cycle detection. All I know is that it's a hard problem (if it wasn't, then Go would be a lot easier to write AI opponents for).