Strangely Consistent

Musings about programming, Perl 6, and programming Perl 6

You're in a space of twisty little mazes, all alike

It started with a mini-challenge on the #perl6 channel.

<masak> today's mini-challenge: a 4x4 grid has 24 internal walls. in the
        power set of these, some of the members are "mazes", by definition
        grids with a unique path between every two squares. how many mazes
        exist?

For example, here are four randomly selected solution mazes:

I have a hidden reason for posing this problem, but that's the subject of a future blog post. But for now, let me clarify by saying that I'm not just interested in counting the number of such mazes, I actually want to enumerate them — that is, I need to know what each maze looks like.

I have previous experience with building mazes, and I think it's a really fun domain. But the skills from that post teach us how to make a nice random maze. Here we want to make all mazes. Maybe the knowledge carries over somehow, but it's not clear to me how.

Upper bound

Instead, let's start over. The problem specification talks about a "power set" of 24 internal walls.

We could think of each internal wall being controlled by a bit of storage somewhere, a 0 indicating the absence of a wall and a 1 its presence. Together these 24 bits can be thought of as making up a bit string that completely determines the maze.

...which also means that we have an upper bound on the number of mazes, because there are only so many length-24 bit strings!

> 2 ** 24
16777216
> sub triples { $^s.flip.comb(/. ** 1..3/).flip }; Nil
> triples 2 ** 24
16 777 216

Wherever we are going with this, we won't exceed 16.8 million! Phew!

Nice

But we already know that this upper bound is not attained; the bit string of all 1s (illustrated above) fails the "unique path between every two squares" criterion of the problem statement.

In fact, here, let me generate 10 random 24-bit strings and draw them out in grid form:

These all fail the "unique path" criterion!

Fortunately for us, the number of "nice" mazes is rather smaller than 2 ** 24. Since I know what the number is, I would expect there to be one correct maze, on average, for every 167 randomly generated grids. (I just tested this experimentally. In a sequence of randomly generated grids, the first correct maze was number 111.)

Ok, at this point in our investigations, we are at the "I don't know what a correct maze is, but I know one when I see one!" stage. It's a nice stage to be in. So many unexplored avenues! Our ignorance is like a fog, surrounding us, waiting for our sharp observational skills to dispel it! Let's dig beneath the surface.

Why do the above mazes fail the "unique path" criterion? Perhaps if we can describe the vices they commit, we can start laying down the law about how a maze must look to be a member of our club. I see two such vices:

Goldilocks

We might be tempted to conclude from the above that there is a certain Goldilocks number of internal walls that a grid must have in order to be a correct maze.

...and, in fact, there is! It must have 9 walls. As weak evidence of this, here are the four random mazes again. Yep, they all have 9 internal walls.

This is because a correct maze induces a spanning tree on the graph of the grid — and vice versa. The spanning tree is simply our branching structure of corridors that form between our walls.

Our whole problem can now be restated as "enumerate all possible spanning trees on a 4x4 grid". But Wikipedia also informs us that "for a connected graph with V vertices, any spanning tree will have V − 1 edges". We have 16 vertices, so 15 edges. But "edge" here is "edge in the spanning tree", which corresponds to "no wall" for us. So out of 24 possible walls, our mazes must have 24 - 15 = 9.

This also means that, thanks to the binomial theorem, we've lowered our upper bound to 1.3 million.

> sub postfix:<!>($n) { [*] 2..$n }; Nil
> sub choose($n, $k) { $n! / ($k! * ($n - $k)!) }; Nil
> choose(24, 9)
1307504
> triples choose(24, 9)
1 307 504

While 9 walls is a necessary criterion, it's not a sufficient one. Here are 10 random grids with 9 walls:

Of these, only the upper right one is a correct maze. It's not just how many walls you have, it's how you place them, too!

(If we generate a random 9-walled grid, we're now down to a 1-in-13 chance that the grid is also accidentally a well-formed maze.)

At least we can be a bit clever when searching for bit strings. Instead of iterating through all 16.7 million of them, we can iterate through only the 1.3 million with nine 1s in them. Order-of-magnitude speedup? Yes, please! The below code for doing so is inspired by MJD's post, from nine years ago, about enumerating strings of things.

my $s = "0" x 15 ~ "1" x 9;
say $s;

repeat until $s eq "1" x 9 ~ "0" x 15 {
    $s ~~ s[ .* <( 01 (.*) ] = "10" ~ $0.comb.sort.join;
    # possibly do other things to verify that it's a maze
    say $s;
}

One

It was somewhere around here that I got a promising insight, and thought I had solved the whole problem when I really hadn't.

Here was my (wrong) idea: in every correct maze, the walls form chains which protrude from the outer wall, and then just end. If we could take such a maze and start to "unravel" it at the fringes, peeling away walls which are at the end of such chains, and we do this over and over, eventually we'll be left with a grid with no inner walls.

Here, an example with a correct maze:

But in a grid with cycles, the process of unraveling would eventually stabilize with internal walls still remaining:

The (wrong) way I used to decide whether an edge was at the fringe of an edge was to ask whether it had less than two edges neighboring it. In a cycle, edges would constantly protect each other by being surrounded on two sides by a neighbor edge. But fringe edges would unravel and eventually we'd be left with nothing. (This way of thinking assumed that the big outer edge was a single edge in terms of being able to neighbor other edges. Except that it never gets removed.)

Here is my first attempt. I've lightly sprinkled comments around the source; hopefully enough. The first script finds all the mazes. The second one removes duplicates in terms of rotation and reflection symmetries. The third one draws the mazes.

As you can see, it took more than two and a half hours to find all the solutions using this script. Which would be more acceptable if it didn't also arrive at the wrong answer.

Two

After a day or so of these ideas sloshing around in my head, I came up with a better, faster algorithm: if we can find the correctness of the mazes by unraveling them back to the empty grid, we could also run this process in reverse, successively growing all correct mazes in generations from 1..9 (walls), each new generation adding all correct walls to all the mazes of the previous generation.

Here is the script to do that. It basically scavenges the old script for ideas. Because it would be much slower not to, this script now removes symmetric duplicates as part of generating the mazes. The idea of what constitutes a "correct" addition of a wall is exactly the same as before: a wall can be added if that spot has one neighboring wall.

I also uncovered a string-handling bug in MoarVM as part of writing this. Under certain circumstances, substr on a string built using x gives the wrong answer. Internally, MoarVM uses something called ropes to represent strings. Among other things, MoarVM ropes can encode repetitions such as the ones x creates, to reduce memory footprint and computation. But something throws substr off the scent in this particular case. And my toy problem helped discover it. ♥

Bug still open as of this writing, looking for someone willing to tackle a ropey problem.

<jnthn> Too bad it gets the wrong answer, rather than getting into an
        infinite loop
<jnthn> Then we coulda said it had enough rope to hang itself...

I didn't see the error of my ways until Mouq++ actually dug up a few mazes that my algorithm didn't produce. Common to all these mazes was that they had "corners" in the maze: points where a single wall chain branched out in two different directions. Here, have a few examples.

My algorithm would fail to produce any of these, for the simple reason that my 1-neighbor criterion was flawed.

Einstein has been remembered for the quote "Everything should be made as simple as possible, but no simpler." Actually, what he really said was "The supreme goal of all theory is to make the irreducible basic elements as simple and as few as possible without having to surrender the adequate representation of a single datum of experience." (See Wikiquote.) But history seems to have applied the spirit of his own words to his quote and produced the former soundbite from Einstein's longer version.

<masak> oh, it's lovely to be wrong :>

It says something about my TV habits that I can't really think of the quote nowadays without Jesse Pinkman appearing in my mind and appending "...bitch" to the quote. (Either the long one or the short one.) Especially when I commit a modeling error like the one with the mazes.

Three

When I arrived at my first two solutions, I was kind of relieved that I could phrase it only in terms of the internal walls of the maze. I didn't have to deal in the nine vertices between the walls — or so I thought. It turns out that this simplification was of the kind that made the solution a bit simpler than possible. (Bitch.)

(I'm sure this isn't the first time I make this exact mistake. I come back to thinking about mazes and maze generation every few years, and I recognize this failure mode in previous code I've written. This is the first time I've taken the time to analyze it, though.)

So my third solution introduces the notion of points joining together the walls. The algorithm now turns into this: for an empty grid, all nine internal points are active. As we fill out the grid, one by one these points will toggle from active to inactive by having a wall touch the point. We still proceed in generations from an empty grid to a completed maze. But now, the criterion for where we may put a new wall is this: a wall goes between an inactive point (that already touches a wall) and an active point (that doesn't). (Again, the outer wall is treated a bit specially, this time as a tenth "point" that's always active no matter how many walls attach to it.)

Viewed a bit differently, the algorithm does a breadth-first search on the graph induced by the points (including the outer wall) and the internal walls. But it does the breadth-first search non-deterministically, in all possible ways. Each time it "finds a neighbor point" it hasn't visited yet, it leaves a wall between the old point and the new. Each maze ends up representing one possible BFS with the outer wall as starting point.

The resulting algorithm runs in little under 15 minutes. Which is quite an improvement in running time — besides being correct, I mean.

Kudos go to moritz++ for realizing that the whole thing runs faster if the qw lists of numbers are hyper-numified instead of being implicitly cast each time they're used.

Answer

So... how many correct 4x4 mazes are there? The short answer is 12600.

I don't know about you, but I didn't expect there to be that many. Yes, that's after removing rotation and reflection duplicates. For comparison, there's only one maze of size 1x1, only one maze of size 2x2, and only 28 mazes of size 3x3.


All of the 3x3-mazes, up to reflection and rotation.

But apparently there's a lot of new wiggle room for the walls once you increase it to 4x4.

I rendered an image of all 12600 4x4 mazes, but it would be foolish to try to put it here in the blog post. But I can link you to it. (Warning: 3.7 MB .png file. timotimo++ for helping shrink it from its original 4.4 MB.)

Of the 12600 mazes, 112 have a reflectional symmetry. Which means that if we count all reflections and rotations as distinct, we have (12600 - 112) * 8 + 112 * 4 = 100352 mazes. (Here's the script that finds the symmetries.)

Epilogue

It seems that more and more often, I encounter these kinds of problems where the problem domain is essentially a "space" of objects, and any algorithm has to loop over the objects in some intelligent manner. The last time this happened to me in a toy problem setting, I was counting configurations on a hex cell board. But I find it increasingly happen to me in less hobby-oriented domains, too. Often enough, the challenge is being able to navigate a giant code base or data model, or to extract some subset of it, or to classify parts of it on the fly. My brain, perhaps addled by category theory at this point, increasingly thinks about these problems as happening in a "phase space", each point representing some object of interest.

I wonder if I could go back and describe to my 15-year-old self what it's like to discover and explore these spaces. I wonder if he'd understand and be as hooked on it as I am. The thrilling aspects are really in finding appropriate names for new entities and relationships in the artificial universe, and then building an understanding out of these named concepts, constructing ever-higher towers of composite concepts to explain ever-larger clusters of relations. I am Adam, my artificial universe is the garden of Eden, and the objects are species to be tagged and classified.

And here I could wax poetic about the suggestive power of language, and the importance of actually evolving a language for your domain, both nouns and verbs. But we'll save that too for some other post.

Cycles

The solution I ended up with avoids cycles using "positive" filtering, creating partial results without cycles until we arrive at full mazes. It is possible to use "negative" filtering too, by first building a list of all the "fundamental cycles" in 4x4-space, and then finding all (9-wall) grids that don't contain one of the fundamental cycles. The promising thing about this is that the question "does it contain this cycle?" can be formulated as a bitwise +& and the maze bit vectors (and fundamental cycle bit masks) can be represented as native ints, making this potentially quite fast.

How can we build a list of fundamental cycles? Basically by doing one depth-first search at every internal point (and once for the outer wall), backtracking each time we find a cycle. I'm intrigued that it turns out that when we're looking for (cycle-free) mazes we need to use BFS, but when we're looking for cycles we end up with DFS. I wonder if there's some really deep duality that can explain why that is. (If you know, get in touch.) There are 627 fundamental cycles on a 4x4 grid. (Here's another image that doesn't fit.)

Unfortunately, the fun ended there. Rakudo doesn't support native arrays yet, so I have nowhere fast to put my 627 native ints. Right now the algorithm runs in 38 minutes, which is not an improvement on the 14 minutes of solution three. We'll see if that balance changes once we get native arrays.

And now, I will consider mazes as being flushed out of my system, for now. Hopefully I'll be able to get back to blogging about macros.

Feedback on "Macros: Placeholdeeers!"

These comments pertain to this pooost.

Macros: Placeholdeeers!

Alternative blog post title: finally, a rant about the {{{ }}} syntax.

The macro blog post train lumbers on. Remember, the goal here is to view macros from all perspectives, or at least all of them that somehow pertain to Perl 6. There's a whole lotta perspectives! Together they will form a "cloud" of suggestions, forces, and decisions... and then, magically, something wildly appropriate will crystallize out of the chaos, suggesting a way forward.

In the meantime, it will seem like I'm recklessly firing RFCs on myself until I'm buried under them. What can I say? You need a lot of different parts to build a... SPACESHIP!

Today's episode brings you vanviegen's macro proposal from our friends over at the CoffeeScript world. You should read the OP in that one, but as a public service, I will also translate allsome of the Coffee code snippets into Highly Plausible Perl 6.

# optionally compiled debug info
macro debug(*@args) {
    if (DEBUGGING) {            # it's a constant defined somewhere
        Q::Call.new(
            Q::Literal.new(     # (handwave)
                "debugImpl"
            )
        )
    }
}

vanviegen's proposal doesn't have a notion of quasi blocks. At first I thought that was pretty lame, and clearly not a step up from what we already have implemented. But then...

# mandatory swap example
macro swap($a, $b) {
    Q.codeToNode({
        my ($x, $y) = $y, $x;
    }).subst(
        '$x' => $a,         # o.O
        '$y' => $b,
    );
}

...uuummmm.

Hold on just a minute. Let's all freeze our immediate reaction, and render that in Current Actual Perl 6:

# mandatory swap example
macro swap($a, $b) {
    quasi {
        ({{{$a}}}, {{{$b}}}) = {{{$b}}}, {{{$a}}};
    }
}

(Which works, by the way.)

Ok, so here's my reaction:

Ok, enough making fun of our own choices. I think what we're seeing here is an interesting solution, but I don't think we should rush to adopt it wholesale. I'll try to be more clear, or at least less circumscript, in what follows.

But I also think I've figured out something about templating syntax.

All templating syntax sucks.
    — masak's Deplorable Truth About Templating Syntax

It doesn't matter what you do: your templating syntax is going to suck. The template placeholders are a kind of out-of-band signaling, OK. "Hey hey, a thing gets inserted here!" You need a syntax for the placeholders. The syntax cannot blend in too naturally into the surrounding text because (a) if people don't notice them then we have a problem, and (b) if they're too close to normal syntax then there are also parsing collisions.

So you have to make them stand out, which means making them look somehow unnatural. Visual pills. Ugly. I guess that's what we went for with the {{{ }}} syntax: maximal ugly. Something that would never, ever be confused with sane and decent code. Someone might at some point find a reason to write two opening braces in normal code. But three? So it's collision-safe. And ugly.

Don't believe me when I say that all templating syntax sucks? Fine, I'll bring you examples:

Anyway, you can't go right with a templating system. It's like the Prime Directive in Star Trek. The string would be better off if you left it in its natural state, but for one reason or another, you just have to inject those out-of-band placeholders and mess things up a bit. Just a little, because things will be "better". After which... things are not in a natural state any more. Your string is full of percents, your HTML no longer validates, your Python has braces, and your Perl 6 has a lot of braces.

But v's macro system offers an interesting alternative. No quasi quotes, no unquoting. Nothing needs to be out-of-band anymore. Things are injected from the outside.

I'm going to list what I perceive as pros and cons of this proposal. In increasing complexity order, so pros and cons will interleave.

Pro: No more {{{ }}}. Yay!

Pro: No more quasi blocks. Actually, this one deserves a bit more than just a "Yay!" — quasis are currently our way to represent code as ASTs, but it's like Perl 6's quasis bypass the standard way in Perl to quote code:

    AST form    ........^..................^........
                        |                  |
    lambda form ........|..................|........
                        |
    real code   ........|...........................
                p6's current way      v's codeToNode

Rakudo's quasi implementation has already validated how much quasis piggyback on blocks/lambdas. v's macro system validates that in a more direct way.

Con: There are now extra moving parts. We have to make up new variables $x and $y just so we can substitute them. The reader is expected to mentally do the substitution in .subst to see what the eventual code will be.

Pro: There's a neat sleight-of-hand that goes on there that you won't have thought about until I point it out: we feel like we're swapping out variables, but what we're really doing is substituting pieces of AST. It's that subtle difference between "the value in $x" (which does not even enter into the picture on this level), "the variable $x" (the thing we feel we're manipulating), and "the piece of AST denoting the variable $x" (the thing we are actually manipulating).

Con: We're finding $x and $y using short strings of text. Eww. It's partly a scoping thing. $x and $y are already out of scope, and so we cannot refer to them directly. It's partly a convenience thing. Strings are the simplest way to state what we are looking for. In fact, we don't really have a symbol type in Perl 6 that we could use instead. But it still feels wrong.

Pro: The code inside of the block is really undisturbed. Plus, I could imagine someone using this to her advantage, naming the variables in suggestive ways to either show their symmetry with the things we want to substitute, or show their function as placeholder variables. I would take the undisturbed swap statement any day over the hectic mess of triple braces.

Pro: It strikes me that we don't need to substitute just variables, we could substitute operators, too. Still need to figure out a way to accept them into the macro in the first place, though.

Con: Does this whole thing remind you of beta reduction in lambda calculus? Yeah, me too. The thing we run into then is capture-avoiding substitutions. To give a concrete example:

my $greeting = Q.valToNode("OH HAI");
Q.codeToNode({
    say $s;
    sub foo($s) {
        say $s;
    }
    foo("two!");
}.subst(
    '$s' => $greeting,
);

When this AST is injected and executed, it should print "OH HAI" and then "two!" (because $s got substituted once), not print "OH HAI" and then fail to dispatch (becase $s got substituted three times).

So the thing about capture-avoiding substitutions can be summarized as "shallow occurrences are fine, but hands off if nested blocks bind something". This is not so much a show-stopper as a "must think about this" and "must write tests that melt brain".

Con: The thing that truly bothers me, though, is this:

macro example($in1, $in2) {
    Q.codeToNode({
        say $x;
        say $y;
    }).subst(
        '$x' => $in1,
        '$y' => $in2,
    );
}

my $x = 5;
my $y = 42;
example($y + $y, $x);

I guess I would expect this code to spit out first 84 and then 5. But I fear it might well embark on a holy journey of infinite substitution, or maybe compromise somehow and output 10 and 5 or something. Someone is welcome to explain to me how my worries are unfounded. But from what I can see, this macro system suffers from the kind of naming clashes that gensymming seeks to avoid.

So... that's where I'll leave things today. I still think that this fairly simple macro system is interesting in what it teaches us about our own.

By the way, it's quite amazing how close it is to Perl 6's own macro system. I've studied a fair number of them at this point, and this one is very close. Which is kinda weird, with Perl 6 being what it is mixing compile and runtime, and CoffeeScript being what it is, compiling down to JavaScript and then getting out of the way.

Maybe we will ditch quasi blocks. Maybe we'll keep them. Either way, it's clear that we will get rid of the {{{ }}} syntax in favor of something else. This blog post shows the contours of that other thing, but the contours still remain fuzzy.

Not addressed by this proposal

Identified in a previous post.

Addressed (yay!) by this proposal