
You're in a space of twisty little mazes, all alike - kamaal
http://strangelyconsistent.org/blog/youre-in-a-space-of-twisty-little-mazes-all-alike
======
mrcactu5
this is known as a uniform spanning tree
[https://en.wikipedia.org/wiki/Spanning_tree](https://en.wikipedia.org/wiki/Spanning_tree)

these can be sampled using Wilson's algorithm for Loop-Erased Random Walks
[https://en.wikipedia.org/wiki/Loop-
erased_random_walk#The_un...](https://en.wikipedia.org/wiki/Loop-
erased_random_walk#The_uniform_spanning_tree)

Here is a nice visualization of Wilson's algorithm using d3.js by Michael
Bostock (NY Times)
[http://bl.ocks.org/mbostock/11357811](http://bl.ocks.org/mbostock/11357811)

~~~
9ac345a5509a
The number of such mazes is also on OEIS under A007341:
[http://oeis.org/A007341](http://oeis.org/A007341)

------
jerf
It seems like it would be way easier to think about it the opposite way...
pick a space, start enumerating the possible connections it can have to its
neighbors recursively, with a simple algorithm that won't pick already picked
neighbors, and then read the bit string off the result. That's easily done by
starting with all 1s, and then setting to 0 the bit corresponding to the
choice you just made.

Either direction is of course the same in theory, of course.

More excitingly than that, you may be able to contribute to OEIS now, if you
can work yourself out a few more terms:
[https://oeis.org/search?q=1%2C1%2C28%2C12600&sort=&language=...](https://oeis.org/search?q=1%2C1%2C28%2C12600&sort=&language=english&go=Search)

------
jdjdps
I like the epilogue. I too wish I could go back to my younger self and
describe this understanding. I would try to explain to myself that each
pattern can be seen as an object in and of itself. That an algorithm is a way
to move between these objects in a specific way that marries with a particular
human goal. I would try to explain that each step of an algorithmic process
combined can be seen independently of time as a pattern in and of itself and
as such is itself an object. A process is a noun, a thing just as much as a
chair or a lightbulb. I would say that in order to find an algorithm to solve
a goal, all one needs to do is imagine the shape formed by this goal and
construct that shape from the shapes that are readily available to you. Be
them finger movements on an abacus or bitwise operations in a computer memory.
And then I would explain that the universe can be seen in this way. The entire
thing as a single object out there in phase space. I would tell myself that I
suspected that all possible shapes exist, that the shape of your life exists
only as much as the shape of a thing that you imagine while dreaming. This was
the understanding I have been searching for since my early teens. It is such a
joy to have found it, I like to think my younger self would have cherished it
as much. But I may have discarded them as the ramnlings of an old fool.

------
asdftemp
[https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem](https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem)
?

~~~
kmill
Implementation:
[https://gist.github.com/kmill/f4f47913d036fce687bc](https://gist.github.com/kmill/f4f47913d036fce687bc)

Though it counts reflections as distinct.

------
VieElm
Now watch this question pop up on technical interviews everywhere for days
because people read about it here.

~~~
drabiega
That'd be great for those of us who read it and a going to interviews.

~~~
JoshTriplett
Which is exactly what makes it a terrible interview question.

~~~
thaumasiotes
[http://www.phdcomics.com/comics/archive.php?comicid=993](http://www.phdcomics.com/comics/archive.php?comicid=993)

I don't see why that makes it a terrible interview question, though. Maybe you
want to hire people who read about this kind of thing for fun. They may also
have read about other things.

Colleges pick their students based on basic vocabulary and 9th grade math
questions.

~~~
joshuapants
> Maybe you want to hire people who read about this kind of thing for fun.
> They may also have read about other things.

Maybe, though I'd be shocked if the typical hiring process were that nuanced.

~~~
thaumasiotes
Effective practices can work even if you have no idea why you're doing it that
way. In fact, I'd say that that state of affairs is more the norm than the
exception.

------
comrh
Interesting post, something people often ignore is talking about the failures
that got them to the solution but this is usually the real interesting stuff!

------
nobrains
The answer from the post: [http://strangelyconsistent.org/blog/images/all-
the-4x4-mazes...](http://strangelyconsistent.org/blog/images/all-
the-4x4-mazes.png)

