Good evening!

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 ;)

There is a central planet and three lines of two planets each starting from it. And yes, I'm terrible at design.

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!

Police routes

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.

MIN = 0
MAX = 6
MAXLEN = 11

def range_permutations(l=[]):
	for i in range(MIN, MAX+1):
		ll = l + [i]
		if len(ll) < MAXLEN:
			yield from range_permutations(ll)
		else:
			yield ll

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!

def range_permutations(l=[]):
	# will prevent generation of lists
	# with first element higher than 2
	maximum = MAX if l else 2
	for i in range(MIN, maximum+1):
		ll = l + [i]
		if len(ll) < MAXLEN:
			yield from range_permutations(ll)
		else:
			yield ll

If 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.

police_gen = range_permutations()

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.

Criminal’s routes

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.

# connections between planets
NEIGH = (
	(1,),#0
	(0,2,),#1
	(1,3,5,),#2
	(2,4,),#3
	(3,),#4
	(2,6,),#5
	(5,),#6
)

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.

def _traverse(start, l=[]):
	ll = l + [start]
	if len(ll) < MAXLEN:
		for i in NEIGH[start]:
			yield from _traverse(i,ll)
	else:
		yield ll

def get_criminal_traverses():
	for start_i in range(len(NEIGH)):
		yield from _traverse(start_i)

# all possible combinations of movements criminals can make.
# they can travel only to adjacent planets
# and they MUST make a move every turn
criminal_traverses = tuple(get_criminal_traverses())

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

def test_po(po):
	"""
	Tests if the given police itinerary will result
	in an inevitable apprehension of the smuggler.
	Prints and returns the itinerary itself, if so.
	Returns None if not.
	"""
	for cr in criminal_traverses:
		# checking every element in both routes
		for i in range(MAXLEN):
			if po[i]==cr[i]:
				# caught, checking the next possible route of the criminal
				break
		else:
			# not caught, this policeman's strategy is bad
			break
	else:
		# every strategy works! This is the result
		print("result:", po)
		return po

for po in police_traverses_gen:
	test_po(po)

That’s all. You can run it and eventually it will print the results! Here’s the final program.

from multiprocessing import Pool, Queue
from datetime import datetime

MIN = 0
MAX = 6
MAXLEN = 11

# connections between planets
NEIGH = (
	(1,),#0
	(0,2,),#1
	(1,3,5,),#2
	(2,4,),#3
	(3,),#4
	(2,6,),#5
	(5,),#6
)

# all possible combinations of movements policemen can make
# they may travel to any planet and don't have to make a move on a turn
def range_permutations(l=[]):
	maximum = MAX if l else 2
	for i in range(MIN, maximum+1):
		ll = l + [i]
		if len(ll) < MAXLEN:
			yield from range_permutations(ll)
		else:
			yield ll

police_traverses_gen = range_permutations()

def _traverse(start, l=[]):
	ll = l + [start]
	if len(ll) < MAXLEN:
		for i in NEIGH[start]:
			yield from _traverse(i,ll)
	else:
		yield ll

def get_criminal_traverses():
	for start_i in range(len(NEIGH)):
		yield from _traverse(start_i)

# all possible combinations of movements criminals can make.
# they can travel only to adjacent planets
# and they MUST make a move every turn
criminal_traverses = tuple(get_criminal_traverses())

def test_po(po):
	"""
	Tests if the given police itinerary will result
	in an inevitable apprehension of the smuggler.
	Prints and returns the itinerary itself, if so.
	Returns None if not.
	"""
	for cr in criminal_traverses:
		# checking every element in both routes
		for i in range(MAXLEN):
			if po[i]==cr[i]:
				# caught, checking the next possible route of the criminal
				break
		else:
			# not caught, this policeman's strategy is bad
			break
	else:
		# every strategy works! This is the result
		print("result:", po)
		return po

for po in police_traverses_gen:
	test_po(po)

The only problem is that it will take forever to calculate. We can utilize the power of additional cores though.

Going multiprocessing

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.

counter = 0
done = False
while not done:
	src = []
	for _ in range(1000000):
		try:
			src.append(next(police_traverses_gen))
		except StopIteration:
			done = True

	with Pool(processes=PROCS) as p:
		r = p.map(test_po, src)

	counter += 1
	print(datetime.now().strftime('%D %H:%M:%S'), "Iteration:", counter)

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:

from multiprocessing import Pool, Queue
from datetime import datetime

PROCS = 8
MIN = 0
MAX = 6
MAXLEN = 11

# connections between planets
NEIGH = (
	(1,),#0
	(0,2,),#1
	(1,3,5,),#2
	(2,4,),#3
	(3,),#4
	(2,6,),#5
	(5,),#6
)

# all possible combinations of movements policemen can make
# they may travel to any planet and don't have to make a move on a turn
def range_permutations(l=[]):
	maximum = MAX if l else 2
	for i in range(MIN, maximum+1):
		ll = l + [i]
		if len(ll) < MAXLEN:
			yield from range_permutations(ll)
		else:
			yield ll

police_traverses_gen = range_permutations()

def _traverse(start, l=[]):
	ll = l + [start]
	if len(ll) < MAXLEN:
		for i in NEIGH[start]:
			yield from _traverse(i,ll)
	else:
		yield ll

def get_criminal_traverses():
	for start_i in range(len(NEIGH)):
		yield from _traverse(start_i)

# all possible combinations of movements criminals can make.
# they can travel only to adjacent planets
# and they MUST make a move every turn
criminal_traverses = tuple(get_criminal_traverses())

def test_po(po):
	"""
	Tests if the given police itinerary will result
	in an inevitable apprehension of the smuggler.
	Prints and returns the itinerary itself, if so.
	Returns None if not.
	"""
	for cr in criminal_traverses:
		# checking every element in both routes
		for i in range(MAXLEN):
			if po[i]==cr[i]:
				# caught, checking the next possible route of the criminal
				break
		else:
			# not caught, this policeman's strategy is bad
			break
	else:
		# every strategy works! This is the result
		print("result:", po)
		return po

counter = 0
done = False
while not done:
	src = []
	for _ in range(1000000):
		try:
			src.append(next(police_traverses_gen))
		except StopIteration:
			done = True

	with Pool(processes=PROCS) as p:
		r = p.map(test_po, src)

	counter += 1
	print(datetime.now().strftime('%D %H:%M:%S'), "Iteration:", counter)

In conclusion

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.