You're in a space of twisty little mazes, all alike
strangelyconsistent.org
You're in a space of twisty little mazes, all alike
1–10 of 18 posts
Re: You're in a space of twisty little mazes, all alike
#2Now watch this question pop up on technical interviews everywhere for days because people read about it here.
Re: You're in a space of twisty little mazes, all alike
#3this is known as a uniform 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...
Here is a nice visualization of Wilson's algorithm using d3.js by Michael Bostock (NY Times) http://bl.ocks.org/mbostock/11357811
Re: You're in a space of twisty little mazes, all alike
#4this is known as a uniform 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... Here is a nice visualization of Wilson's algorithm using d3.js by Michael Bostock (NY Times) http://bl.ocks.org/mbostock/11357811
The number of such mazes is also on OEIS under A007341: http://oeis.org/A007341
Re: You're in a space of twisty little mazes, all alike
#5It 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=...
Re: You're in a space of twisty little mazes, all alike
#6Now watch this question pop up on technical interviews everywhere for days because people read about it here.
That'd be great for those of us who read it and a going to interviews.
Re: You're in a space of twisty little mazes, all alike
#7[deleted]
Re: You're in a space of twisty little mazes, all alike
#8Re: You're in a space of twisty little mazes, all alike
#9Re: You're in a space of twisty little mazes, all alike
#10Earlier quoted context omitted.
That'd be great for those of us who read it and a going to interviews.
Which is exactly what makes it a terrible interview question.
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.