(d|br)e(p|ad)th first search

« previous post | next post »

Today's xkcd:

Mouseover tag: "A death-first search is when you lose your keys and travel to the depths of hell to find them, and then if they're not there you start checking your coat pockets."

There are other tree-search algorithms, e.g. "Monte Carlo tree search", "Depth-first iterative-deepening", etc., so I'm a little surprised that the terms brepth-first and deadth-first haven't already been claimed by some clever computer scientists. "Death-first search" has of course been a trope for four millennia or so, ever since Enkidu went looking for Gilgamesh's pikku and mikku.


  1. Jarek Weckwerth said,

    January 6, 2021 @ 7:03 am

    But does that RegEx really produce bread? ;)

  2. Philip Taylor said,

    January 6, 2021 @ 7:07 am

    I don't think so — but (d|br)e(p|ad)(th)? might …

    [(myl) You'd need to add something to make (th) optional, and also avoid "brep" and "dep" as outputs, etc. — or reconfigure the whole automaton. ]

  3. Sean Richardson said,

    January 6, 2021 @ 9:39 am

    Knowing that I've been able to read regex since I was a kid in the 70s, and recognizing before clicking through from email, I still wanted to see "breath" in there too, so I wasn't surprised to see "death" in the mouseover.

    There must be a thesis still available to someone using this as a jumping-off point for explorations of modelling the intuitions of fluent speakers and readers of Modern English about how remnant Old English endings combine.

  4. Theophylact said,

    January 6, 2021 @ 1:01 pm

    There's a wonderful bakery in DC called Bread Furst (the owner is Mark Furstenberg).

  5. Haamu said,

    January 6, 2021 @ 3:46 pm

    Bread-first search describes my preferred approach after being handed a restaurant menu. (In that sense, these days it’s a term of purely historical interest.)

  6. Rick Rubenstein said,

    January 6, 2021 @ 4:24 pm

    He doesn't mention the optimal A* algorithm, which is where you throw your data into the supermassive black hole in the center of the Milky Way and hope the answer pops out as Hawking radiation.

  7. Philip Taylor said,

    January 6, 2021 @ 5:09 pm

    "[(myl) You'd need to add something to make (th) optional, and also avoid "brep" and "dep" as outputs, etc. — or reconfigure the whole automaton. ]"

    Ah, does the interrogative after "(th)" not accomplish the first — I thought that "?" indicated zero or one occurrences, but I am not a regular (groan) writer of rexeps … As to 'avoid "brep" and "dep" as outputs', is that necessary ? If I understood the first question correctly, it was whether the regexp could produce "bread" rather than whether it could produce only "bread".

  8. AntC said,

    January 6, 2021 @ 5:30 pm

    Re the -th suffix, I have a friend whose idiolect has 'heighth', or possibly spelt 'heightth'

    Etymonline says of -th (2) "Sometimes in English reduced to -t, especially after -h- (as in height)." "Milton used highth and heighth is still colloquial in English." If it's colloquial, I've only heard this one person use it, not any others of their family.

  9. maidhc said,

    January 6, 2021 @ 8:27 pm

    Lots of people say "highth". I haven't observed it to be regional in the US, but it is not uncommon. Your fourth-grade teacher would probably correct you, even though it is really more logical.

    At one time the -t forms were used in the north of England and the -th forms in the south.

    More here.

  10. Brett said,

    January 6, 2021 @ 10:07 pm

    This was Monday's xkcd, not Wednesday's. On the day it came out, I kept having to edit out statements on Explain xkcd that described the graph as a "balanced binary tree." The following was also my work: "The nature of the 'deadth-first' algorithm is unclear and inefficient, since it searches the same nodes multiple times before moving to an entirely different region of the tree."

  11. Stephen L said,

    January 7, 2021 @ 11:39 pm

    totally off-topic, I'm sorry, but someone linked me to this video which I find highly amusing – a Liverpudlian footballer after being on loan to Marseille for six months


    It might be of entertainment or interest to others here…

RSS feed for comments on this post