Lord Vultare has stolen Archimedes’s heat ray 🔥🔥
… and it’s up to Leonardo to take back the weapon before Lord Vultare uses it to seige the kingdom 🏟. Both Lord Vultare and Leonardo are still in the Phantom Zone, but Lord Vultare has already started making his way back to our world! The Phantom Zone has many intersecting dimensions and time streams, so Leonardo can’t just run up to Lord Vultare because they are seperated by time and space. Luckily, Leonardo has the Antikythera that allows him to instantaneously travel through time 🕰 and space 🌌. He can catch up to Lord Vultare near-instantly, but he can only travel in a specific combination of dimensions and time moments relative to his current dimension and time. These moves are summarized as moving +/-3 dimensions and +/-1 moments, or, +/-1 dimensions and +/-3 moments.
The Phantom Zone has a finite number of dimensions and time frames though, given as DIMENSIONS dimensions and MOMENTS moments, and nobody can exist beyond those bounds. Given that Leonardo starts in the d dimension and m moment, and Lord Vultare is in x dimension and y moment, what is the minimum sequence of moves does he have to take to catch Lord Vultare?
Leonardo can move the following ways to get to Vultare:
- 1 dimension forward and 3 moments after
- 1 dimension forward and 3 moments before
- 1 dimension backward and 3 moments after
- 1 dimension backward and 3 moments before
- 3 dimensions forward and 1 moment after
- 3 dimensions forward and 1 moment before
- 3 dimensions backward and 1 moment after
- 3 dimensions backward and 1 moment before
It’s guaranteed that
12 <= DIMENSIONS <= 24
12 <= MOMENTS <= 24
0 <= d < DIMENSIONS
0 <= m < MOMENTS
0 <= p < DIMENSIONS
0 <= q < MOMENTS
The following functions generate the Phantom Zone and initial placement of Leonardo and his nemesis.
import random
import numpy as np
def phantom_zone():
DIMENSIONS = random.randint(12,24)
MOMENTS = random.randint(12,24)
d = random.randint(0, DIMENSIONS-1)
m = random.randint(0, MOMENTS-1)
p = random.randint(0, DIMENSIONS-1)
q = random.randint(0, MOMENTS-1)
return (DIMENSIONS, MOMENTS, d, m, p, q)
def in_zone(d, m, D, M):
return d >= 0 and m >= 0 and d < D and m < M
Approach
This first approach to consider is to preemptively explore possible moves. Think of it the Phantom Zone as a general 2-dimensional space. From the starting point, branch out and visit all reachable points. Leonardo also have to keep track of the number of move’s he would have made up to those points. Then from those points, generate the next level of reachable points and account for the incremental move.
A queue structure is good for this approach. We can enqueue into it each generation of reachable points, and since the order of the queue elements are “first element in: first element out”, we’ll visit points in the general order of increasing levels.
As a minor optimization, Leonardo will take moves that bring him toward Vultare in either dimenion or moment. He will enqueue any set of “good moves” based on relative position.
forward_dimensions = [(1,3), (1,-3), (3,1), (3,-1)]
forward_moments = [(1,3), (-1,3), (3,1), (-3,1)]
backward_dimensions = [(-1,3), (-1,-3), (-3,1), (-3,-1)]
backward_moments = [(1,-3), (-1,-3), (3,-1), (-3,-1)]
all_moves = [(-1,3), (-1,-3), (-3,1), (-3,-1), (1,3), (1,-3), (3,1), (3,-1)]
Let’s see how exploring all_moves does.
random.seed(1)
def do_it():
DIMENSIONS, MOMENTS, d, m, p, q = phantom_zone()
moves = [] # treat as queue
visited = np.array([[False]*MOMENTS]*DIMENSIONS)
count = 0
loops = 0
while loops < 50000:
if d==p and m==q:
break
for _d, _m in all_moves:
loops += 1
peek_d, peek_m = d + _d, m + _m
if in_zone(peek_d, peek_m, DIMENSIONS, MOMENTS) and not visited[peek_d][peek_m]:
visited[peek_d][peek_m] = True
moves.append((peek_d, peek_m, count+1))
if moves:
d, m = moves[0][0], moves[0][1]
count = moves[0][2]
moves.pop(0)
return (DIMENSIONS, MOMENTS, d, m, p, q, loops, count)
(DIMENSIONS, MOMENTS, d, m, p, q, loops, count) = do_it()
print(f"DIMENSIONS: {DIMENSIONS}, MOMENTS: {MOMENTS}")
print(f"Leonardo starts at dimension {d}, moment {m}")
print(f"Vultare is at dimension {p} moment {q}")
print(f"Leonardo explored {loops} possible moves and found he could take a minimum of {count} moves to reach Vultare.")
DIMENSIONS: 14, MOMENTS: 21
Leonardo starts at dimension 4, moment 3
Vultare is at dimension 4 moment 3
Leonardo explored 288 possible moves and found he could take a minimum of 3 moves to reach Vultare.
Now let’s see how well he does when exploring moves that generally are in the direction of his goal.
random.seed(1)
def do_it_better():
DIMENSIONS, MOMENTS, d, m, p, q = phantom_zone()
moves = [] # treat as queue
visited = np.array([[False]*MOMENTS]*DIMENSIONS)
count = 0
loops = 0
while loops < 50000:
if d==p and m==q:
break
good_moves = []
if p > d:
good_moves.extend(forward_dimensions)
elif p < d :
good_moves.extend(backward_dimensions)
if q > m:
good_moves.extend(forward_moments)
elif q < m:
good_moves.extend(backward_moments)
for _d, _m in good_moves:
loops += 1
peek_d, peek_m = d + _d, m + _m
if in_zone(peek_d, peek_m, DIMENSIONS, MOMENTS) and not visited[peek_d][peek_m]:
visited[peek_d][peek_m] = True
moves.append((peek_d, peek_m, count+1))
if moves:
d, m = moves[0][0], moves[0][1]
count = moves[0][2]
moves.pop(0)
return (DIMENSIONS, MOMENTS, d, m, p, q, loops, count)
(DIMENSIONS, MOMENTS, d, m, p, q, loops, count)= do_it_better()
print(f"DIMENSIONS: {DIMENSIONS}, MOMENTS: {MOMENTS}")
print(f"Leonardo starts at dimension {d}, moment {m}")
print(f"Vultare is at dimension {p} moment {q}")
print(f"Leonardo explored {loops} possible moves and found he could take a minimum of {count} moves to reach Vultare.")
DIMENSIONS: 14, MOMENTS: 21
Leonardo starts at dimension 4, moment 3
Vultare is at dimension 4 moment 3
Leonardo explored 196 possible moves and found he could take a minimum of 3 moves to reach Vultare.
Some thoughts…
Looks like selectively moving in the direction of the Vultare reduces the number of moves explored. Let’s check across a few different scenarios where the Phantom Zone and people are arranged differently. I’ll generate different results using different seeds.
for timeline in range(10):
random.seed(timeline)
print(f"timeline: {timeline}")
result1 = do_it()
random.seed(timeline) # make sure to reset simulation
result2 = do_it_better()
print(f"\t{result1}\n\t{result2}")
if result1[6] > result2[6]:
print(f"\tDid it better!")
timeline: 0
(18, 24, 8, 16, 8, 16, 720, 5)
(18, 24, 8, 16, 8, 16, 620, 5)
Did it better!
timeline: 1
(14, 21, 4, 3, 4, 3, 288, 3)
(14, 21, 4, 3, 4, 3, 196, 3)
Did it better!
timeline: 2
(12, 13, 10, 0, 2, 11, 50000, 5)
(12, 13, 10, 0, 2, 11, 50004, 7)
timeline: 3
(15, 21, 5, 19, 5, 19, 944, 5)
(15, 21, 5, 19, 5, 19, 740, 5)
Did it better!
timeline: 4
(15, 16, 7, 4, 7, 4, 520, 4)
(15, 16, 7, 4, 7, 4, 432, 4)
Did it better!
timeline: 5
(21, 16, 14, 7, 14, 7, 328, 3)
(21, 16, 14, 7, 14, 7, 196, 3)
Did it better!
timeline: 6
(24, 21, 8, 1, 8, 1, 1248, 6)
(24, 21, 8, 1, 8, 1, 1172, 6)
Did it better!
timeline: 7
(17, 14, 1, 1, 1, 1, 904, 5)
(17, 14, 1, 1, 1, 1, 804, 5)
Did it better!
timeline: 8
(15, 17, 3, 1, 3, 1, 368, 3)
(15, 17, 3, 1, 3, 1, 200, 3)
Did it better!
timeline: 9
(19, 21, 4, 5, 4, 5, 576, 3)
(19, 21, 4, 5, 4, 5, 324, 3)
Did it better!
Better, mostly
So, 9 of 10 timelines played out where the optimized search did a fewer number of move searches (looks like approximately 100 moves less average).
In timeline 2, the players and zone configuration was such that the limit of 50000 iterations was reached at some point, and the first approach gave the lower number of moves.
Improvements?
The search was essentially a breadth first search with some backtracking. What other heuristics could Leonardo use to cut off a branch path that is not worth exploring (ie he is searching too deep down a path)?🌌