Slash Boxes
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
More | Login | Reply
Loading... please wait.
  • Cool post! I added your Perl6::Literate to the []

  • You know, if you swap the word "labyrinth" for "molecule" and "cell" for "atom" and "wall" for "bond"....

    The whole flattening hierarchy approach also sounds a bit like a data structure I read about on wikipedia called a "disjoint-set forest" (link []).

    Anyway, it seems like the method works because labyrinths (and molecules!) have a restricted dimension. For labyrinths in 100 dimensions, the equivalence classes would have few members, and the complexity would again be closer to O(N^2). I guessing, of course :)

    • Even in a moderately "small" labyrinth in 100 dimensions, the distinction between O(N) and O(N^2) won't be your biggest concern... :)

  • For people with their own copy of TAOCP, you'll find the algorithm used for Cell.join as Algorithm E in section 2.3.3. Knuth uses the word "parent" instead of "leader", and he checks for the case where cells A and B are the same cell, but otherwise the details match.