What do you think the system for Brepth-First is? How do you even define the first step? “Check the first element two levels down”? It just gets weirder from there. If you extend the tree down one more level, what do you think the diagram would look like? It’s not at all clear to me how it would work.
Down two, and then up to the next non-exhausted node.
But it’s bouncing back to earlier nodes to check lower depths. After it goes two down the right hand branch, it doesn’t go back up, it goes down to an earlier node on the left branch. Plus, it doesn’t always go down two. The very first time it goes up, it then goes down only one.
I don’t think the first move is from the root to the left-most 2nd child; I think that does traverse through the leftmost first child like a conventional DFS. Admittedly his notation is a little ambiguous. Aside from that quibble. …
I spent some time trying to sort out the algorithm. What follows is not fully debugged, but it gives what I think is the flavor of the algorithm.
Notice the tree is not binary although he never shows us how the algorithm would react when it gets to the 3-child node.
The best I can come up with is start from a typical DFS algorithm. But at each node, before traversing to any child thereof, make a decision and do one of these three things:
- Traverse into the leftmost not-yet-visited child like a normal DFS.
- Enqueue a task for later to enter that leftmost not-yet-visited child and immediately traverse upwards as if the current node is childless or already fully explored.
- Enqueue a task for later to enter that leftmost not-yet-visited child then dequeue the first task in queue and pick up the traversal from there
As best I can tell, the decision of which of those 3 branches to take is probabilistic. If you ever get to the last node of the conventional DFS, then choice 1 becomes inoperative and by bumbling randomly around between choices 2 and 3 you’ll eventually drain the queue and have seen every node.
Conversely Deadth-first is just silly, a prelude to the punch line: Bread-first.
On looking further, brepth isn’t doing what I thought it would be doing. Every node can be mapped to a sequence of positive integers, and there’s a standard systematic way to list a set of sequences of positive integers (that is, a mapping from such sequences to integers). And it would make sense to use such a mapping, in a case where the breadth, depth, or both might plausibly be (countably) infinite. But that search order would go something like
Root
1
11
2
111
12
21
3
1111
112
etc.: That is, first do all of the sequences with a sum of 1, then all of the ones with a sum of 2, then all with a sum of 3, and so on.
But the XKCD brepth goes
Root
1
11
12
111
112
2
21
121
122
In other words, it doesn’t hit node 2 until after it’s gone both deeper and broader than it should in 1’s descendants.
And deadth, I think, is completely dysfunctional: It even revisits already-visited nodes.
The punchline is weak, too, because both “depth” and “breadth” end in “th”, and thus, any sort of portmanteau of the two should also end in “th”.
Overall, I think this is one of Munroe’s weaker contributions.
I think the idea is getting progressively more absurd. Brepth-first looks just plausible enough to be real if you don’t look to closely. Deadth-first is clearly chaotic. Bread-first is simply delicious.
The joke would have worked better if Breadth-first were called Width-first, so the final panel could have been Breadth-first.
@tofor: Yeah. The whole point is the descent into anarchy.
Ref @Chronos’ reasonable objections … As with many of Munroe’s comics, the reader needs to be taking it just the right amount of silly vs. serious to “get” the meta-joke that’s really the point. If you (any you) are in a different-enough silly/serious frame of mind than he was, the whole thing falls flat.
Apparently I’m Lawful Good. That arrangement of eggs both keeps the center of gravity as close to the geometric center as possible, and minimizes the moment of inertia, both of which make it easier to get the carton out of the fridge without dropping.
Chaotic Neutral sure looks awfully systematic, though.
It’s maximizing entropy.
My technique is True Neutral. But I leave the carton in the fridge and just reach into it to grab the one or two I need from the front = right in his pic. So the arrangement happens by default, not by design.
But back when I routinely pulled the carton out, I used @Chronos’ technique for the same reasons.
Pro-tip: Picking up a carton expecting Lawful Neutral when you actually have True Neutral can result in Chaotic Evil, but not all neatly contained in a disposable carton. Don’t ask; it wasn’t pretty. 
I got a laugh out of yesterday’s:
All good, I imagine … I’ve had a few Cosmic Crisps recently and they are damn near perfect.
On the one hand, this business of new varieties and buzz-worthy apples is ridiculous. But on the other hand, Cosmic Crisps are freakin’ delicious.
What category does it fall into when, once you’ve got no more than 6 eggs left, you put them all in one side and cut the other side off to make them easier to grab and take up less room in the fridge?
ETA: Not that I really grok these designations anyway. I assume they’re from LARPing or something like that.
My son explained they refer to D&D character rules but does not think the joke works at any level as one who plays.
In the 1/10,000 scale world, wouldn’t people have to sit, lie down, or crawl not just regularly, but pretty much all the time? You can’t breathe the air 10 miles up for more than seconds without blacking out, IIRC.
I’ll take your word for it, but references to chaotic good, lawful neutral, etc. seemed to suddenly be everywhere fairly recently - starting maybe 5-6 years ago? - but I’d never been aware of them before then. And of course D&D has been around since the 1970s.