Is this the dumbest way of solving a maze? We're starting at this orange point here
and we've got to find, like, how do we get to the exit? And my idea is that I'm going
to let a gas go here and then you know at some point one of the atoms of the gas is going to
reach the exit. (Brady: Just by sheer luck?) - By luck yeah. Gonna be basically moving
randomly. If I do more and more molecules than I would expect that
it would get- one would get there faster. I've released a poisonous gas here and then
eventually like a canary dies over here or something. And here they go,
so quite quickly they've spread out and they're going and they've got a few going around here.
After a while this is the one that's going to end up winning; it it got out there first, and this
is the path that it took the whole time. Spends a bunch of wasted time in here but here you go,
you've got a solution. It does some silly things like going up here when it didn't need to,
but you know
this is basically how to solve this maze. - (I love it Matt. I love the thought of there)
(was that one molecule there that was destined for greatness and it it didn't even know it
would be) (the one.) - Right, yeah.
- (You know what it reminds me of? Sperm going to the egg. Which sperm will become)
(a human?) - It's totally like that,
yeah. And it's just pure luck right? I think there's various metaphors that you can draw here,
like, you know everybody is just bumping around randomly but the one person that you know
became a billionaire or something, they wrote their autobiography,
how I got here all the great decisions I made to beat everybody - it was just random.
It's a bit of a sort of inside joke in that in computer science there's all these different
algorithms for doing things efficiently and, you know, solving mazes is a big um example of
like where you might apply these algorithms. - (Like the lightning algorithm we did in a
previous video?) Right, exactly; and that was you know finding the shortest path, like you find it
efficiently and what you get is the shortest path from the cloud that seeds the lightning all the
way down to the ground. But here, well one thing I've done is I've said the maze is actually going
to be this physical thing I don't- I've forgotten about the concept of like cells of the maze and
their adjacency, like where you can get to from each; and I've just said well there's a little
tiny molecule in there somewhere and it's moving around it doesn't even know when it's left one
cell and it's gone into the other. It's sort of a joke about
there might be like the most efficient way to do something but, hey this works. And maybe it's not
the dumbest way because it does work right? You could either create a computer, like
write all the code to solve this program, encode it in the transistors of the computer;
or I'm saying you know just release like a bad smell. You could maybe take this solution that we
found and improve it. Imagine that this orange squiggly path is actually a piece of string,
just pull it tight and then it would be a much better solution to the to the maze.
(It would also be interesting to see if you pulled that tight how long it is. How much)
(longer a path did it take than it had to?) - Yeah, one thing about this this maze is
that it doesn't have any kind of loops around it,
and that's kind of by design. And that means that works particularly well for
the string pulling type thing because you're not going to get a knot anywhere
and you're just going to prob- you'll get the- you will get the shortest path if you pull it tight.
Another thing you could do is model the interactions between molecules. Each one is its
individual little thing, it doesn't know about all the other molecules and it's just moving around;
in real life you might have some bouncing of those and that's I guess is like pressure and that would
help it expand out from the beginning and give you an even better solution, but obviously that's
harder to program because you gotta- am I bumping into this one? Am I bumping into that one? That
would be inefficient. And then another thing you could do is like do some kind of fluid dynamics
maybe? So if you had like some wind, just blow a hair dryer in here, it might help guide the
molecules out and the air from the hair dryer has to escape out here eventually because of pressure.
That might give you a faster solution. The first step is figuring out how to create a nice maze,
and I wanted that property where there's a path between every single point in the maze
and there's not going to be any loops. Going to have a network of points on a grid;
eventually I want to figure out what are the walls but I'm actually first going to think about what
are the paths that create the maze. What I want is to say that there's a path between
all points and I'm just going to just start and create random ones. So like, if I start drawing
in things here, what I'm doing is I'm adding edges not randomly - I'll add an edge if it's not going
to create a loop anywhere and I also want to make sure that I reach every single point.
You know, maybe I go here and I have- go down here and then here. These are paths; and now the walls
I could create walls that make these valid paths but they're going to be
on a grid that's sort of offset from this one. So for example I better have a wall
here, otherwise I should have had a line that connected those two. I need a wall here -
I'm just blocking the stuff off that needs to be blocked. But you can't go from here to here
without going around here, so there should be a wall there as well. Likewise there should be
a wall here, wall here; and now I'm just going to enclose the whole thing. And then I'm going
to add a little like goal at the end. Maybe you start here, and so the maze is actually kind of an
artifact of me having found this network of where you can go to from each point
which is called a tree. Tree is just a network where there's no loops in it. It means that you
end up having a nice maze, because if you have too many edges then you don't have very many walls.
In the code is I pick a width and a height and I create this
fully connected graph here, so that is- I'm just saying like what is the grid graph? That
means a graph where everything is connected to thing to the left, above, to the right, and down
but just for some fixed rectangular size. And then I assigned a random number to each of those edges
and then I asked Mathematica to find the tree that spans all of those points - meaning it visits
all of the vertices there that has the smallest total weight on all the edges. That's just a way
for it to come with a random maze each time. So for example, this was a potential edge I
could have picked but maybe it had a weight of 100; that means it had a cost basically of 100
whereas this one had 1 so that's why I picked, you know, these these ones, not that one. So if we do
that can you see we get this network of all the paths that you can take from each point?
I then have a nice guarantee that I can put a goal here and a start point there and I know
there's going to be a solution, because you can get to anywhere in the maze from anywhere else.
So now I've just got to figure out the step I did here when I went from the green pen to the brown
pen - what are the walls that make- make that? Not too much more code and you get this picture
here. So side by side here we've got the network and we've got the walls that should create that
network. You can kind of see it looks right; so for example here we've got a path from this point,
you can't get directly there you've got to go up and around and down which is correct - yeah,
up and around and down. So that's how we've created the the walls. Now all we've got to
do is simulate molecules inside this environment. - (Is that hard or easy?) Uh it's just - yeah. It
is hard or easy. There's a few tricks you gotta do to make it not just take forever; on the other
hand like I just gotta make one animation and post it on my Twitter so I don't really care if
it takes too long. So it's a bit of one of those things where I could optimise it and make it very
fast or I could, you know, solve the maze in a dumbest way. So I switched over to Python to start
stimulating the molecules; here's a code that does that. Imagine at each point I'm trying to figure
out, I've got a molecule here I'm just going to add a totally random direction. So each time it's
going to like take a tiny step in a new direction. And I just- I need to make sure that I'm not going
to cross a wall. I end up here and then if I go over here, hey that's a problem, I'm now
intersecting with the wall so I've got to go back. - (So these aren't like your)
(famous bouncing balls that only change direction when they hit a wall? They can
change direction) (whenever they want?) - They're moving every time step and that
that is um what's called Brownian
motion or just a random walk. You know, molecules dancing around; and then in real life that might
be because they're actually bouncing into smaller molecules, like these might be some heavier gas
in just the air bumping into the small molecules of the air, just making it look like hey they're
jittering around all the time. But I've got jittering around randomly all the time, but also
I've got to make sure - don't go into a wall. If it looks like you're going to go into a wall, just
reverse your direction and you won't hit the wall. So I programmed it so that each point I know what
are the nearby walls around there, and then I do some maths to say, hey am I actually intersecting?
So this block of code here, I'm saying I've got a point p and I've got some sort of structure that
tells me what are the walls that I've got going on, and I'm saying am I going to clip into the
walls or not? Now I run the code and it will just keep on simulating again and again and again. I
do them in big batches and then the first batch that has a winner in it I just stop computation.
So I'll show you what that looks like. - (But surely every batch will
eventually have a winner?) - Right, but I only- I do each batch for a fixed-
for a maximum length of time and then move on to the next batch. So there I've kind of guessed.
I've said, you know, 10,000 steps or whatever is probably going to be enough - or I've
kind of set a goal and I'm just going to simulate enough until I get to a solution.
- (Because presumably if you do an infinite number of batches eventually you'll get)
(one particle that just by luck, just perfectly) - Just goes the exact way, yeah, totally. I could
for example reject some of those solutions and say ah that's not good enough, and keep going keep
going keep going - I'll leave my computer running overnight. If I just run this, hopefully it still
works. I'm simulating a batch of I think 64 points for 45,000 time steps and I've got a progress bar
saying this is how long it's going to take. We're doing some screen recording to capture that,
so this is much slower than it usually is, but yeah I mean I would just run this,
leave it - computer beeps when it's find something and then I would bring
it back into Mathematica and do the animation. Let's look at how we do the- like draw everything
and draw the back trace and stuff. Once we've found a solution, my code there just outputs,
like here's all the paths, and I know that one of them won in the end. So first of all I've got to
figure out what what is the molecule that won? And also I've got to just draw them all going around
and everything like that. I'm loading in solutions that were found. We ended up running 1856
molecules would be in the animation, one of them got to the end. What I did was I set
it up so that this is the y = 0 line; so I find a solution just one that reaches a negative y value,
that's kind of an easy test for me. And then this code here is doing the animation.
Each molecule obviously just gets drawn as a little point here. And then we've done that check
to see which is the one that reaches a negative y value, and then that's the one that we've
realised is the winner and we trace it back to the beginning. Some people are like, well how do
you know that one was gonna win? Like how did you know to like put a circle around it? Well actually
I just kept running this program and I logged everything. When I'm creating these frames I'm
not running the simulation I'm just displaying the simulation. The simulation as you say is a file
that has logged all the other movements. - (So you could open up like, you know,
a spreadsheet or a log) (that would show the winning molecules path?)
- Yeah that's right, I basically stored a spreadsheet where I've got 1856 different
molecules; and then for each one of them got 4500 (x,y) coordinates - just massive loads and loads
of numbers. - (You know what my question- next question is don't you?) (I want to see the- I
want to see its log. I want to see the log of the winning ball - is that even) (possible to find?)
- The log of the winning ball? Yeah yeah that's that's possible to find.
- (Does he have a) (name or a number that winning ball?)
- Yeah he's got an index, so it's 1836. So if I look at the 1836th
thing here - here are all the points that, so the starting point was (1, 9) and then at the
end it's got a negative y value. - (That's his path.)
- So it won. - (That's- that doesn't look very
complicated) (for how wiggly his path was.) - I've cut out 4489
other points. And you can see that because here is its path.
- (Yeah, got a bit stuck there for a while) (didn't he?)
- Totally stuck there. Pick another number, we could we could compare how it did?
(How did ball 1 do?) - Yeah good good idea.
Red is the winner and blue is the first one. - (So ball one got stuck up there and just
hung around there for ages.) - Yeah that's right. Ball 2
did that, ball 3 did this, and obviously I kept simulating, kept simulating,
eventually I got to ball 1836 in the last batch. Here's 1835 - did that. Each one is just totally
random. So if I change this slider, click, here's all the different paths that were found.
(Let's see if we can find a really funny one where he got stuck badly.)
- That's not a great one, looks like it came down, was doing pretty straight
line stuff and then hung around in that area. The other one didn't get very far, the scale is
changing because it's fitting, but it's obviously just in the first 1, 2, 3, 4, 5, 6, 7, 8, 9ish.
(That's fascinating.) - And the winner.
The winner looks- I mean it's still doing something pretty dumb.
Look at these people in the gym, endlessly preening,
posing, and hopefully improving their bodies.
Go on big man! But do they ever give their brain a workout? If so, their mental gymnasiums
should be this: Brilliant. These courses, quizzes, and collections of problems are barbells for your
brain. They're interactive, carefully designed, and unlike a normal gym they're lots of fun.
So don't just sit there and let your brain turn to mush; give it a workout with Brilliant.
There's new content being added all the time and you can get 20% off a premium subscription
by going to brilliant.org/Numberphile. You can also give Brilliant as a gift to other people.
They're great people at Brilliant, and we also appreciate that they love supporting us
here at Numberphile, so thank you very much.