The interviewing team drops you and three other SPARC applicants at different points on a flat desert island with a radius of at most 20 kilometres. You each have: (1) a perfect map of the island, a pencil, a ruler, and a pin, (2) a single-use scanner, which detects how far away you currently are from an enormous pile of treasure buried just below the surface, (3) a flare, which reveals your exact position to the others, and (4) a spool containing an infinite length of thread. In addition, you and only you have the ability to write a message of up to 300 characters which everyone else will read before landing, along with an explanation of the setup with all the information in this question. Your goal is to get the treasure as fast as possible. What message do you write and why? Assuming you all have a velocity of 5km/h, with your strategy, what’s the longest it could take to find the treasure, in the worst case scenario?
I'll refer to the team of applicants as a squad.
Let's assume our island is similar to a circle, given the mention of a radius. There's an ambiguity in the problem statement: how many times can you use the flare? Let's assume it's also single use. Let's assume each squad member knows their starting position and can pin it on the map.
Our strategy will be to scan at least 3 different positions, giving us 3 circles we can draw on the map representing the potential positions of the treasure. The intersection of the 3 circles will be the location of the treasure.
So, our circular island can be assimilated to a rectangle:
We divise this rectangle into 4 identical squares, and find their centers (i1, h1, g1, f1) using the ruler:
This gives the squad a shared division of the island into 4 quadrants with one center each.
Now when they're dropped, each squad member rushes to the center of the nearest quadrant, always keeping track of their exact position. The first to reach it goes exactly on the center of the quadrant, and then scans.
They read the result y in meters. Now, they take that number and divide it by 100.
They now place themselves t meters away from the center of the squadrant.
Let's check this distance won't be too much:
Using the pythagorean theorem we can see that the distance from the center of the square to the center of the circle is about
For R = 20, this is about 15 km. The longest distance to the treasure is thus 15 + 20 = 35 km, situated on the farthest point of the island on the line that links the center of the quadrant and the circle (E1 here):
So the maximum distance they'll need to walk to signal their scan is 35000m/100 ~= 350m.
When a flare is sent out, everyone measures and notes (with the pencil) the distance t to the center of the given quadrant, and finds the original y meters distance it corresponded to from the scanner. After sending out the flare, squad members can wait until at least 3 flares were sent (there are optimizations I could do here instead of making them wait, but I lacked space in my 300 character message).
In the end we'll get something like this on our map:
3 members of our squad emitted from different quadrants so the intersection the circles gives us the location of the treasure.
Once at least 3 positions have been broadcast, the squad converges onto the treasure location. They can calculate it precisely by going back to the scan results, finding the equations of the 3 circles they obtained and then solving for x and y, which is feasible with the pencil on the back of the map. Finding the treasure is then instantaneous.
Now, you might be wondering: what's the purpose of the fourth member? Human error and imprecisions are common, and this isn't exactly the simplest process. The fourth member's flare and scan allow to reduce the uncertainty around the location, especially if they do it when they're converging on the treasure.
Finally, one issue we haven't addressed is what happens if one of the squad members was on their way to a quadrant that has just been flared? Two strategies can resolve this:
Our message had to omit some unessential details that don't hinder the execution of the general process. It's also a bit clunky so that it can fit into 300 characters. I'm relying on the reasoning of our rational squad to infer other teammates behavior from their message and guess the little details that are implicit.
299 characters:
divide outer square of the circular island into 4 squares;go to center nearest square scan result y;walk t away where y=100t;if target square already flared,scan old flare location and walk t away from there;flare;When see flare;calculate y and draw its circle;treasure where 3 circles intersect
Now let's write an approximate simulation to see how our strategy performs for the worst case, where R = 20km. This simulation uses one or two heuristics because I didn't have time to code every detail, but the core of it is the same as the outlined strategy.
RADIUS = 20000
def random_point_in_disk # random point from uniform distribution of points on island disc
r = RADIUS * rand**0.5
theta = rand * 2 * Math::PI
[r * Math.cos(theta), r * Math.sin(theta)]
end
def distance(p1, p2) # distance between two points
return Math.sqrt((p1[0]-p2[0])**2 + (p1[1] - p2[1])**2)
end
def get_time_duration(dist) # convert distance to time at given velocity
km_h = 5.to_f
m_s = km_h / 3.6
return dist/m_s
end
def get_quadrant(p) # get nearest quadrant center to point P
return (QUADRANTS.sort_by { |q| distance(q, p)})[0]
end
def find_pos_on_line(starting_p, dest_p, t_elapsed)
# this gives us the position of the traveler at time t_elapsed on his travel between starting_p and dest_p
translation_v = [starting_p[0] - dest_p[0], starting_p[1] - dest_p[1]] # vector of distance between two points
proportion_traveled = t_elapsed / get_time_duration(distance(starting_p, dest_p)) # proportion of journey between points accomplished
return [starting_p[0] + translation_v[0] * proportion_traveled, starting_p[1] + translation_v[1] * proportion_traveled]
end
QUADRANTS = [[-RADIUS/2, -RADIUS/2], [RADIUS/2, -RADIUS/2], [-RADIUS/2, RADIUS/2], [RADIUS/2, RADIUS/2]] # center of each quadrants
class Simulation
attr_accessor :treasure, :people, :time
def initialize
@treasure = random_point_in_disk() # position of treasure
@people = (1..4).map { random_point_in_disk() } # initial position of people
@time = 0 # time to get treasure
end
def run
sorted_people = @people.sort_by { |p| distance(p, get_quadrant(p))} # people sorted by distance to closest quadrant
times = []
quadrants_flared = (1..4).map { 0 }
sorted_people[0,3].each_with_index do |p, i|
quadrant_i = QUADRANTS.find_index(get_quadrant(p)) # get index of current quadrant
curr_time = 0
if quadrants_flared[quadrant_i] == 1
# if the current quadrant has already been flared
# person has to go to the new flare location, causing a bit of time lag measured here as a heuristic
curr_time = 5*60
end
quadrants_flared[quadrant_i] = 1
curr_time += get_time_duration(distance(p, QUADRANTS[quadrant_i])) # add time to reach quadrant
times.append(curr_time)
@people[i] = QUADRANTS[quadrant_i] # update position (technically they moved to flare, but that's negligible here)
end
# we find the position of the last person that hasn't flared, at the time where all the others have flared
# since they won't continue to their quadrant but rather converge on the treasure
@people[3] = find_pos_on_line(@people[3], get_quadrant(people[3]), times[2])
@time = times[2] # we take the time needed for 3 flares to go off
@time += 60*30 # account for time elapsed due to reading instructions and figuring things out -> 30 min
@time += (@people.map { |p| get_time_duration(distance(p, @treasure)) }).min # we take the minimum time to reach the treasure point from each person's current location
end
end
(eval):1: warning: already initialized constant RADIUS (eval):1: warning: previous definition of RADIUS was here (eval):29: warning: already initialized constant QUADRANTS (eval):31: warning: previous definition of QUADRANTS was here
:run
Ok, we now have a working simulation that we can run with random initial conditions. Let's study its results a few times (100000):
times = []
(1..100000).each do
sim = Simulation.new
sim.run
times.append(sim.time)
end
def to_hours(time)
return "#{time/3600} (hours)"
end
puts "Min time: #{to_hours(times.min)}"
puts "Max time: #{to_hours(times.max)}"
puts "Avg time: #{to_hours(times.inject{ |sum, el| sum + el }.to_f / times.size)}"
Min time: 1.1280340629257999 (hours) Max time: 9.650624515488408 (hours) Avg time: 4.284871081916811 (hours)
These times are all calculated by taking into account some extra time for getting used to the instructions and then finding the precise location of the treasure (people aren't machines, so we account for errors).
The most important result is the average value of the searches which is about 4 hours. The worst case time seems to be around ~9-10 hours, which seems correct: everyone lands in the same quadrant, takes ~2 hours to get to the center, and then the treasure is on the other side, so it takes them ~7 hours to get to it. The remaining time is due to the time I accounted for human errors and such.
An alternate strategy would have been for each squad member to immediately scan, and then rush to the center of the circle. Once 3 have arrived, they can locate the treasure using their 3 results which they can shared. I was curious, so I implemented this simulation too to compare the results:
CENTER = [RADIUS, RADIUS]
class Simulation2
attr_accessor :treasure, :people, :time
def initialize
@treasure = random_point_in_disk()
@people = (1..4).map { random_point_in_disk() }
@time = 0
end
def run
times = @people.map { |p| get_time_duration(distance(p, CENTER)) }
@time = times.sort[2]
@time += 60*15 # account for time elapsed due to reading instructions and figuring things out, less because simpler
@time += get_time_duration(distance(@treasure, CENTER))
end
def display
puts "#{@time} seconds = #{@time / 60} minutes"
end
end
(eval):1: warning: already initialized constant CENTER (eval):1: warning: previous definition of CENTER was here
:display
times = []
(1..100000).each do
sim = Simulation2.new
sim.run
times.append(sim.time)
end
puts "Min time: #{to_hours(times.min)}"
puts "Max time: #{to_hours(times.max)}"
puts "Avg time: #{to_hours(times.inject{ |sum, el| sum + el }.to_f / times.size)}"
Min time: 5.160040130512952 (hours) Max time: 19.21000919182089 (hours) Avg time: 12.97076255918471 (hours)
Nice! Our solution is indeed better, and by quite a bit (9 hours better on average and 10 hours better on the worst case).
We've found and simulated a working and efficient solution to the problem, although I think it could still be improved with more time. Notably, only 3 flares / signals are actually crucial in our setup, although the 4th one helps with localization of the treasure at the end. Hope you enjoyed the writeup!