The puzzle itself
Recently, I have encountered this little riddle on TedEd.
It might be more fun to watch the video than to read all this mumbling of mine, but nevertheless I’ll give you the rundown.
Suppose you’re a space policeman and you are chasing a smuggler. You have tracked the criminal to a system of 7 planets that are arranged in the following pattern. I will enumerate them starting from zero, we are programmers after all ;)
The criminal has landed on one of the planets, and you don’t know which one it is. Additionally, you have detected the incoming fleet of smugglers that are coming to save their comrade. You must apprehend him before they arrive. Basically, if both of you appear on the same planet at the same time, you have caught him.
You know three things though.
Your police cruiser is quite modern and it can jump to any planet in the system every hour. The smuggler is piloting an old vessel that can jump only to an adjacent planet every hour. Your jumps are simultaneous and you cannot meet or see each other in space. You have to meet on a planet.
The smugglers’ fleet arrives in 10 hours. Meaning, you can make only 10 jumps between planets. But bear in mind that after your 10th jump you can still check the planet you’ve landed onto, and if the smuggler happens to land there as well, you got him! Last-moment catch, essentially, but it still counts. In other words, you can check up to 11 planets.
The smuggler is a very nervous guy. He will make a jump every single hour, never waiting on the same planet.
Your task is to define your itinerary the way that, no matter where the smuggler is and how he moves, you will apprehend him in any case before the time runs out.
The Cheat Routine
You might want to solve this puzzle yourself. But let’s create a program that performs a bruteforce check of all possible combinations and yields the possible itineraries we can take. I can tell you right now: the first solution the program gave me is different from what they suggest in the video. This riddle has several solutions.
So, we need to know how many possible itineraries we can take. There are 7 possible destinations which we can visit 11 times (counting the starting point). Why 7, not 6? Because, unlike the criminal, we can choose to stay on the same planet, so the planet we are currently on is kinda a “destination” as well. Counting that is simple, it’s 711, or 1977326743. Whoa, just under two billion! That’s a lot, I’m telling you!
Not so many, really.
But before we jump into generating all the itineraries, let’s take a look at the map again. This planet system is essentially tri-symmetrical (or however it is called). It means, if we create a working itinerary starting at planet 0, this same solution will work for planets 4 and 6 as well. You just need to rotate it 120 degrees. Same for 1,3 and 5. And planet 2, well, everything’s simple, you can just go in any direction using the winning pattern, if there is one.
In other words, we need to check only the itineraries starting on planets 0, 1 and 2 and drop the calculation of all the others. Which makes the total number of combinations 847425747. Still a lot, but way better than it was!
So let’s create a function that makes all the possible combinations of numbers from 0 to 6 in a list of 11 elements. There might be a way to do it using the Python’s
itertools, but I haven’t quite figured out how to do it. If you know, tell me, I’m curious. So, I’ll just use vanilla Python.
This yields all the combinations that are possible. This approach may be confusing to some of you, and trust me, it was head-spinning to me when I invented it as well. The “it works and I have no idea why” moment 8)
Well, it is not really a function, it is a generator. And it has a generator in itself, which is… itself, called recursively. The most confusing thing to me at first was the
yield from statement. But all it does is essentially letting me avoid writing another
for loop explicitly, getting the next element from the generator for me and yielding it from the current generator. So it just goes deeper and deeper until it reaches the depth where our list is of length of 11 and there it is yielded! I use generators because I don’t feel like storing just under nine hundred million 11-element lists in my RAM, not to mention that I will need each one of them only once.
To be honest, this generator is a bit difficult to explain in a blog, so I suggest that you experiment with it before moving on so you would understand what exactly we are doing.
Also, many don’t recommend using a mutable structure as a default argument of a function, but for the purposes of this task we can do that, it’s more convenient this way.
Okay! But we said that we need only three starting points, right? Sure, let’s make a little filter now!
l is an empty list, it evaluates to false and therefore the maximum the outer generator will consider will be 2.
Finally, let’s assign it to something more readable.
Bear in mind that
police_gen is not a list, it’s a generator. We will call the
next function on it later to get the police itineraries to analyze.
Okay now! The criminal has less opportunities for maneuver. Now we need to generate his possible itineraries. First of all, let’s define the planets’ neighbours.
Now, the code that generates all that is going to be even more complicated, because we don’t just iterate over a range, we use the patterns above to define the combinations.
This time, I will save it to a tuple, because we are going to reuse these combinations. There aren’t many, actually, only 6144. Any modern computer can handle that.
Putting it all together
Now that we have both the policeman’s and the smuggler’s possible routes, we can take a police itinerary and check all the possible criminal’s routes with it. What are the conditions. If a criminal’s route intersects with a policeman’s route at any moment (so the planet indicies at the same positions in the two lists are equal), we may skip this route of the smuggler and check the next. But if at least one criminal’s route does not intersect with the policeman’s route, this policeman’s route is incorrect and we can skip it. So, here’s what it looks like
That’s all. You can run it and eventually it will print the results! Here’s the final program.
The only problem is that it will take forever to calculate. We can utilize the power of additional cores though.
Since we have created a function that takes every route of a policeman and processes it, we can map it to the sequence of itineraries.
I have split the police itineraries into chunks, each one million elements long. That is because the multiprocessing pool cannot take generators, it would resolve them into actual data structures and store them in memory anyway. So we shall do it manually to preserve RAM.
The final code:
One of the final results is
[0, 1, 2, 3, 2, 5, 1, 2, 3, 2, 5]. It’s a little bit different from what we see in the video, because they have managed to do this without travelling to outer planets whatsoever. But hey, this solution utilizes our ability to warp onto a non-adjacent planet only once, and it is legit as well 8)
Of course, the mechanism above is far from perfection and can probably optimized even further. Maybe it can even be implemented to be calculated on a GPU, this could be faster. Or not? If I get to trying it out eventually, I will write a post on that.
Thanks for reading, and I will see you eventually.