When I was younger and programmed in BASIC, there were some programs I kept coming back to, writing them many times over, each time with small variations. It was a part of my autodidactic journey towards programmerhood ââ¬â understanding algorithms, patterns, code smells and coding common sense by writing things over and over again.
One particular type of program I wrote was a program that drew labyrinths.
I still remember the different mode numbers for switching to graphic modes in
Turbo Basic and QBasic: SCREEN 7
switched to 320x200x16 EGA graphics, while SCREEN 8 gave you
640x200x16 (and thus, quite non-quadratic pixels). SCREEN 9 and
SCREEN 12 provided even higher resolutions... but it wasn't the
resolution that was the attractive part for me. It was speeding up the
algorithm.
By the time I finally learned about Big O notation, it made perfect sense due to experiences such as those I had with my labyrinth programs. In this post, I'll explain not only why my programs were slow, but how I later learned about real algorithms and data structures, went back and made my program fast, and found total happiness.
To make sure we're on the same page, let me specify what it is my programs did.
They built labyrinths which looked like this. It's an m
by n grid of N cells, totally surrounded by walls,
and with internal walls making sure there's exactly one way through the
structure from the lower left to the upper right. Each internal wall (that is,
each wall which is not part of the surrounding border) faces two cells. The
cells in themselves are wholly uninteresting; the information lies in which
walls are solid and which are passages.
> class Cell {}
>
> class Wall {
> has Cell $!cell1;
> has Cell $!cell2;
>
> has Bool $.solid = True;
> method true() { $.solid } # this way, walls boolify to $.solid
> }
>
> class Labyrinth {
> has Int $!height;
> has Int $!width;
> has Wall @!vertical-walls;
> has Wall @!horizontal-walls;
> }
When a program builds the labyrinth, it can start with an empty grid and keep adding walls, making sure that at least one way through the labyrinth remains. Another way to build a labyrinth to start with all walls in place, and then selectively remove walls, with the constant criterion that we do not introduce more than one passage through the whole labyrinth. In some sense, these approaches are duals to each other and equivalent. In this post, I will choose the latter approach, since that's how I've come to think about the algorithm.
So here's the general recipe we're going to follow: we start with all walls in place, and then randomly remove walls, with the added criterion that a wall is kept if removing it would introduce a second path through the labyrinth. This "second path" criterion can be reformulated like so: if we're about to remove some wall, which happens to lie between cells A and B, and our only concern is that we don't want to introduce multiple paths through the labyrinth, we're allowed to remove the wall if and only if cells A and B aren't already connected by some other means.
> class Labyrinth is also { # RAKUDO: Should be 'augment class'
> submethod BUILD (Int :$height, Int :$width) {
> $!height = $height; # RAKUDO: S06/Attributive parameters
> $!width = $width; # C<Int :$!height, Int :$!width>
>
> self.init-cells-and-walls();
>
> for @.random-wall-order -> $wall {
> if $wall.separates-different-areas() {
> $wall.remove();
> }
> }
> }
> }
It's this connectedness check that kills performance. At least it did for me in my teens. My programs used a metaphoric bucket of paint to mark cell A, and then the unpainted neighbours of cell A, and all their unpainted neighbours, and so on... until they either ran into cell B (at which point we know that A and B are connected), or they ran out of new neighbours to paint (at which point we know that A and B belong to distinct graph components). After each such painting spree, all cells were metaphorically scrubbed clean, so that the next round of painting would start from a clean slate.
Some big-O analysis explains why this method is slow. We want to try and remove
each wall exactly once, so that's one connectedness check per wall. Such a
check needs to traverse a bunch of cells, in the worst case all cells in the
labyrinth. Painting a cell takes constant time, so checking if A and B are
connected takes O(N) time units, N being the number
of cells in the labyrinth.
That's for one wall; the number of walls is proportional to the number of
cells, so that's an outer loop with O(N) iterations each doing the
O(N)-unit connectedness check. In toto, the tearing down of walls
takes O(Nò) time units. That's too slow.
(Why is it too slow? To get a feeling for what the O(Nò) tells us,
consider that doubling the number of cells in the labyrinth would make it four
times as slow. And that's doubling the cells, not one of the sides.
Were we to double both the height and the width of the labyrinth, it would have
four times as many cells, and the algorithm would be sixteen times as
slow. Exponents kill.)
My next idea was to label each cell with its own group number, and each time I
removed a wall, I'd let the cells on one side assimilate those on the other
side, so that the cells on both sides had the same group number. With this
method, the connectedness checking was cheap, but the joining of
groups suddenly took O(N) time units, as all the cells of one
group had to be traversed and relabeled. In rethinking the problem, I had lost
as much performance as I had won. Some hidden waterbed theory of minimal time
complexity seemed to have bitten me. At this point, I faltered and failed to
glimpse the beautiful solution, discussed below.
I called a few utility submethods in my BUILD method above, which
I haven't defined. They're not algorithmically challenging, but shoving them
away in their own submethods makes the BUILD submethod so much
more readable.
> class Labyrinth is also {
> method init-cells-and-walls() {
> my @cells = map { [map { Cell.new() }, ^$!width] }, ^$!height;
>
> @!vertical-walls =
> map -> $row {
> map -> $column {
> Wall.new(:cell1(@cells[$row][$column]),
> :cell2(@cells[$row][$column+1]))
> }, ^($!width-1) # off-by-one -- internal walls
> }, ^$!height
> ;
>
> @!horizontal-walls =
> map -> $row {
> map -> $column {
> Wall.new(:cell1(@cells[$row][$column]),
> :cell2(@cells[$row+1][$column]))
> }, ^$!width
> }, ^($!height-1) # off-by-one -- internal walls
> ;
>
> return;
> }
> }
By the way, I hope I'm not shocking you too much with those map
blocks. In Perl 6, map and for are semantically
equivalent. When I want to functionally transform a list of things, I still
prefer map.
> class Labyrinth is also {
> submethod random-wall-order() {
> return (@!vertical-walls, @!horizontal-walls).pick(*);
> }
> }
I'm translating this code from a Java program I had lying around. The corresponding Java method was a bit longer than the above. 哈哈
Now for the big revelation of this post: we can do better than the
O(Nò) calculated above, and with the addition of one simple trick.
No matter what we do, the O(N) walls still have to be traversed,
but if we can somehow reduce both the connectedness test and the joining of
groups to constant time ââ¬â constant time! ââ¬â the whole thing would only
take O(N) time units.
This is where the theory comes in. A few summers ago, I was basking in the sun on a piece of grass outside of a university building, reading Knuth's TAOCP. At one point, he discusses equivalence classes, and how the operations of joining and comparing members can be made efficient. It all hinged on each member of the equivalence class having the option to delegate decision-making to another member, one more central to the decision-making process (call it a "leader").
How are equivalence classes related to labyrinths, you ask? Well, that's the beauty of mathematics: all it does is provide us with tools to solve problems better. If we find a way to apply the tools to our problem space, it's like someone already did all the work for us. Specifically, if we can show that "A is connected with B" is an equivalence relation, we can think of each set of communicating cells in the labyrinth as an equivalence class, and then apply Knuth's trick to the program to make it fast.
What does it take to show that "A is connected with B" forms an equivalence
relation? An equivalence relation ~ has to satisfy three
properties: reflexivity, symmetry and transitivity. Or, in mathese, for any
members x, y and z, (1) x ~ x, (2) x ~ y ⇔ y ~ x, (3)
x ~ y & y ~ z ⇒ x ~ z. (Math alert: if I just lost you in a cloud
of boolean incantations, fear not! What the symbols represent is not
difficult, but neither are the symbols self-evident. The rest of the post can
be understood without this paragraph.) But all these happen to hold for our
connectedness relation: cells are connected to themselves; if one is connected
to another, the other is connected to the first; and if one is connected to a
second which is connected to a third, the first must be connected to the third
as well. QED.
Ok, so we're good to go. To make this work, each cell needs to keep track of
which leader cell it delegates to. Each cell starts out without a leader,
signified by the attribute being undef.
> class Cell is also {
> has Cell $.leader is rw;
> }
Cells with a leader delegate all their decisions (such as answering questions about connectedness) to that leader. In fact, since this may be done in several steps, we eventually end up with trees of cells, each tree with one cell at the root node which gets to make all the decisions. We call that cell the boss. We're never really interested in the middle managers, and in fact we can remove them as we find them, creating a totally flat hierarchy.
> class Cell is also {
> method boss() {
> defined $!leader ?? ($!leader = $!leader.boss()) !! self
> }
>
> method join(Cell $other-cell) {
> $other-cell.leader = self;
> }
> }
In words: to know who my boss is, ask my leader who its boss is. Make that my new boss. (That way, the hierarchy keeps flattening out.) If I don't have a leader, I'm my own boss. To join with another cell, tell it that I'm its leader now.
With the introduction of bosses, the connectedness and joining steps are easy to implement. This is more or less directly from Knuth's TAOCP, by the way:
> class Wall is also {
> method separates-different-areas {
> $!cell1.boss() !=== $!cell2.boss();
> }
>
> method remove() {
> $!cell1.boss().join( $!cell2.boss() );
> $!solid = False;
> }
> }
These two methods sure look fast, but how can we be sure? Maybe the
.boss calls take O(N) time units each, bringing the
total running performance down to O(Nò) again... but the
.boss calls turn out to be very fast in practice. For one thing,
we're no longer traversing all the cells within the same equivalence class;
we're just taking the shortest route to the cell in charge. Secondly, we're
even short-circuiting that route to one single step, so that subsequent
traversals through the same path will be faster. The result is that the
.boss calls run in (amortized) constant
time, making the total running time O(N).
[Update 2010-02-20: The above analysis is slightly weak, and doesn't tell the whole story, which I discovered only later by tips from others. If you're interested, you could start from the Wikipedia article on Disjoint-set data structures.]
And that's it! Well, um, we might want to print our labyrinth at some point. Stringifying a two-dimensional structure is not a pretty thing; there's too much going on, and the code looks nothing like the result. So please close your eyes (or look the other way) while reading this part:
> class Labyrinth is also {
> method Str() {
> my ($h, $v) = 0, 0;
> my $s = '+--' x ($!width-1) ~ "+ +\n"; # upper wall
> for ^$!height -> $row {
> $s ~= '| '; # left wall
> for ^($!width-1) -> $column {
> $s ~= @!vertical-walls[$v++] ?? '|' !! ' '; # inner v walls
> $s ~= ' ';
> }
> $s ~= "|\n"; # right wall
> $s ~= [~] map -> $column {
> $row == $!height-1 && $column != 0 # bottom wall
> || @!horizontal-walls[$h++] # inner h walls
> ?? '+--'
> !! '+ '
> }, ^$!width;
> $s ~= "+\n";
> }
> return $s;
> }
> }
Now we can simply print out an instance of a Labyrinth, and watch
the fruits of our work.
> my $labyrinth = Labyrinth.new( :height(10), :width(10) );
> say $labyrinth;
This blog post is written in "Literate Perl 6", inspired by several blog
posts in Literate
Haskell that I've seen over the years. If you have the module Perl6::Literate installed,
you can paste this whole blog post to a file, and run the file with
./perl6-literate <pastefile.lpl>. Your reward will be a
reasonably quickly generated labyrinth. On my computer, running the blog post
that way takes 31 seconds, 23 out of which are spent in parsing and converting,
and 8 in actually making the labyrinth.
I promised moritz_++ to make something pretty with SVG as well, so here's an SVG serializer for the labyrinth:
> use SVG; # requires the SVG.pm module, 'proto install svg'
>
> class Labyrinth is also {
> method svg() {
> my $f = 20; # scaling factor
> my @walls;
> my $style = 'stroke:black;stroke-width:1px;fill:none';
>
> my $v = 0;
> for ^$!height X ^($!width-1) -> $r, $c {
> if @!vertical-walls[$v++] {
> my $d = sprintf 'M %d %d L %d %d',
> ($c+1) * $f, $r * $f, ($c+1) * $f, ($r+1) * $f;
> push @walls, 'path' => [ :$d, :$style ];
> }
> }
>
> my $h = 0;
> for ^($!height-1) X ^$!width -> $r, $c {
> if @!horizontal-walls[$h++] {
> my $d = sprintf 'M %d %d L %d %d',
> $c * $f, ($r+1) * $f, ($c+1) * $f, ($r+1) * $f;
> push @walls, 'path' => [ :$d, :$style ];
> }
> }
>
> my ($x1, $x2, $x3) = $f, ($!width - 1) * $f, $!width * $f;
> my $y3 = $!height * $f;
> for "M 0 0 L 0 $y3", "M 0 0 L $x2 0",
> "M $x3 0 L $x3 $y3", "M $x1 $y3 L $x3 $y3" -> $d {
> push @walls, 'path' => [ :$d, :$style ];
> }
>
> my $picture = svg => [
> :xmlns<http://www.w3.org/2000/svg>,
> :width($!width * $f), :height($!height * $f),
> @walls,
> ];
> return SVG.serialize($picture);
> }
> }
If you change the line say $labyrinth; to say
$labyrinth.svg(), you'll get the SVG version of the labyrinth instead of
the ASCII version. The output will look something like this.
Cool post! I added your Perl6::Literate to the http://www.perlfoundation.org/perl6/index.cgi?perl6_modules_list
Re:Woow!
ihrd on 2009-09-02T06:15:47
Page name is changed:
http://www.perlfoundation.org/perl6/index.cgi?perl6_apps_and_modulesNice, a list of apps
masak on 2009-09-02T09:54:11
That's a brave thing to do, knowing that the work required updating and maintaining that list by hand will only become harder and harder, and eventually impossible.
:) If you want ideas for things you might have missed in that list, the projects.list file in proto should be fairly comprehensive.
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
Re:Very interesting
masak on 2009-09-02T10:14:38
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.
