Subtitles section Play video
-
Their fall from the tower sends Ethic and Hedge
-
spinning into the rapids of a river of pure energy.
-
This torrent flows from the Bradbarrier all the way to Huxenborg.
-
There an entire city's worth of factories
-
build the robots and house the Node of Memory,
-
the last of the three powerful artifacts Ethic needs to collect.
-
After a long day and a longer night
-
they find themselves in a canyon of brick and steel.
-
Just when they're about to reach the end of the line,
-
a rope catches them.
-
Their savior, Lemma, has been waiting for them.
-
When Ethic claimed the Node of Creation from the forest tower,
-
radios all across the land came back to life.
-
Adila, the resistance leader, immediately started contacting her allies,
-
none more important than Lemma,
-
a brilliant scientist working from within Huxenborg to bring down the machines.
-
Unfortunately, the radios also tipped off the robots.
-
So they've taken defensive measures
-
to protect the final artifact in its home in the very heart of the city.
-
There's only one way to get there: the gauntlet of forking paths.
-
It's a deadly series of luminous conveyors that wind underneath Huxenborg.
-
Starting from the current position,
-
each section runs for a distance, then splits in two.
-
Every branch does the same thing, again and again.
-
There are thousands of branches.
-
Only one path leads to the artifact; all the others to destruction.
-
Fortunately, the Node of Creation has granted Hedge a strange power:
-
he can produce slightly smaller versions of himself.
-
Each version can do only two things: radio information back to its parent,
-
and produce slightly smaller versions of itself…
-
which can do the same two things, as can their children,
-
for as many generations as needed.
-
A patrol is closing in on their position, so Ethic's time is limited.
-
What instructions should she give Hedge to find the one safe path?
-
Pause the video to figure it out yourself.
-
Hint in 3
-
Hint in 2
-
Hint in 1
-
Programmers have an elegant tool in their arsenal called recursion.
-
Recursion is when you have a set of instructions that refers back to itself.
-
It's like using a word in its own definition,
-
except where that's frowned upon, this is incredibly effective.
-
Recursion involves repetition, but in a different way than loops.
-
Where a loop takes one action and repeats it again and again,
-
recursion will start an action, and before it's finished, use it again,
-
and before that's finished, use it again, and so on.
-
It keeps doing this until some end state is reached.
-
It then passes the information back up, layer after layer,
-
until it reaches the top and ends the cycle.
-
Recursion is ideal for problems that involve self-similarity,
-
where each part resembles the larger whole.
-
Like, for example, a deadly defense system designed to end any person or thing
-
who dares tread upon it.
-
Pause the video to figure it out yourself.
-
Solution in 3
-
Solution in 2
-
Solution in 1
-
Ethic's conundrum seems sprawling on the surface,
-
but there's a remarkably simple solution to it using recursion.
-
In order to find it, let's first look at the simplest version of this puzzle:
-
what if the entire maze were just two paths?
-
If Hedge copies himself, the copy that goes the wrong way will be destroyed.
-
So the other one, which will reach the artifact,
-
can radio back the path it took, and then no matter which way is correct,
-
that's the answer Hedge will receive.
-
This is called the "base case" of the recursion.
-
Now, suppose the maze branches twice from the starting point,
-
and at every intersection, Hedge's copies—
-
let's call them Twig 1 and Twig 2—
-
make more copies— let's call them Leaves 1 through 4.
-
Three Leaves will be destroyed.
-
The one that reaches the artifact will radio back the right answer,
-
but only to its parent.
-
So if Twig 1 or 2 is waiting at an intersection
-
and hears something over the radio,
-
that's the right way to go to the artifact from where it is.
-
To tell Hedge the right answer from his perspective,
-
the Twig should say which way it went,
-
and then the route it just heard over the radio.
-
This same process will work no matter how many times the maze branches.
-
Any answer a copy hears on the radio
-
must be the way to the control room from its location,
-
and if it then adds the branch it took,
-
it can tell its parent how to get there as well.
-
We can sum up the instructions in an action called Pathfinder
-
that every version of Hedge will follow:
-
1. If you've reached the artifact,
-
radio to your parent whether you got there by going left or right.
-
2. When you reach an intersection, move off the conveyor
-
and send new copies down the left and right paths.
-
Have them each run Pathfinder.
-
This is where recursion comes in,
-
and this may happen many times before the last instruction triggers, which is:
-
3. If you hear anything over the radio, you should radio to your parent
-
whether you got to your spot by going left or right,
-
then repeat everything you just heard.
-
Pathfinder is an example of what programmers call functions,
-
subroutines, or procedures.
-
No matter the terminology, the idea is the same—
-
it's a set of instructions given a label so that it can be easily reused—
-
perhaps even by itself.
-
And in our case that'll work perfectly—
-
an entire network of paths mapped using just three instructions.
-
So here's what happens.
-
By the time the patrol rounds the corner, Ethic and Lemma have improvised disguises.
-
They try to confuse the bots long enough to buy Hedge time.
-
Finally, Hedge's radio crackles to life with a series of directions.
-
The three dive onto the conveyor and flee for their lives,
-
with a squadron of enforcer bots in hot pursuit.