Spinning Robots

Ok, that was quite the break from blogging. Time to solve out the robot chasing puzzle I put up last time.

First of all, it is easiest to work in polar coordinates, r and θ, the robot starts at r=0 and moves along θ=θ₀ and you start at r=r₀ and θ=0 The robots path given

r(t) = v_rt
θ(t) = θ₀

We get to pick our r(t) and θ(t) and choose a path such that we will meet up with the robot path for any arbitrary value of θ₀.

First of all, we might as well move straight to the robot, assuming that θ₀ is 0. We move toward r=0 and would meet the robot at r=r₀*(v_r/(v_p+v_r)) This value, which I will call R, will be our effective starting point.

Next, we must move outward in a spiral, such that our r(t) continues to match the robot r(t), but our value of θ takes on all values between 0 and 2π. This is simple enough, find r(t) and θ(t) such that:

r'(t) = v_r
(r(t)θ'(t))²+r'(t)² = v_p²

Solving it out, you get

r(t) = v_rt+R
θ(t) = √(v_p²/v_r²-1)ln((v_rt+R)/R)

Note the problem we would have if the robot were faster than the player. Anyway, since the logarithm is unbounded from above, you know that this θ will eventually reach 2π, solving the problem. This also finds the smallest disc you can solve the problem on, since you just find that t where θ is 2π and put it back into r.

Not too tricky of a problem once you hit on the solution really, but at first it did look somewhat impossible.

Robot Chasing

New puzzle time, because I actually have more than one in mind and I don't want to forget them.

I found this one somewhere random on the internets, I'll try to dig it up agian when I do the solution:

You are playing a game where you have to catch a robot. You and the robot are on an infinite 2-dimensional plane and you can see where the robot is. When the game starts the lights will be turned off and the robot will select a random direction and move in that direction at a constant speed. You may move around, and your top speed is some number which is greater than the robots constant speed (call them v_r and v_p for the robot speed and the player speed if you like). You naturally cannot see or hear the robot once the game begins. Find a strategy that guarantees you will find the robot.

So you must find a path (x(t), y(t)) which starts at a point (x₀, y₀) which never has a speed exceeding v_p and that path much intersect the robots path such that there is a t where they meet.

As a bonus problem, assume the game is played on a disc of radius R, with the robot starting in the center of the disc and the player on some point a distance P away from the robot. If the robot reaches the edge of the disc it escapes and the player loses. What is the smallest R for which your strategy works?

Robots On A Circle

Alright, time for the solution to the robots on a sphere problem.

It is something of a neat problem, because many people get tripped up right away with the following idea:

If both robots start on opposite sides of the planet facing opposite directions, they will stay that way forever, always mirroring eachothers moves and never finding eachother, no matter what their program is.

This argument actually seems pretty rock-solid, and I spent some time wondering why this problem has such a blatant hole in it, but there is a way out, if you know that the robots are going to start in such a configuration, the solution is this:

Each robot takes a 90 degree turn right, and then moves forward.

This will cause the robots to turn and face eachother, and move forward until they meet 'halfway' (grab a convenient sphere and try it out if you don't believe me). It becomes clear that any solution that is going to cover the extreme case of robots on the opposite side of the planet is going to need to refer to handedness somewhere, using the word 'right' or 'left'.

Now, we may assume that the robots drop off their flags as soon as they land (waiting will not really help anything), and it is easy to see that any two distinct points on the sphere uniquely define a circle on that sphere. The circle can be found by taking the set of points that are equal distance from each of the two points. In the case where the two points are antipodal, the circle that results is the 'equator'. Now that the robots have found a circle that they agree upon (they can find eachothers flags easily, given their own size and the radius of the planet), we just need them to get walking along that circle in opposite directions. Have them travel along the circle with their own flag on the right, this will result in the going opposite directions along the circle, they will meet up eventually.

Robots On A Sphere

So, the blog seems to be reverting to a semi-weekly thing (where semi-weekly means every other week, not twice a week, which is apparently semi-standard english (where semi-standard means half standard, not twice standard, at least I'm consistent)). Anyway, I first found this puzzle on the xkcd forums:

Two robots are being sent to a planet, and you will have to write an algorithm for the robots to find eachother. The planet is a perfect, featureless sphere of known radius, and the robots are of a size epsilon (epsilon is small compared to the size of the planet). The robots each have a single flag that they can place anytime at their location that cannot be moved once placed. The robots have no sight range and can only find something by bumping into it, but they can tell the difference between their own flag, the other robots flag, and the other robot. Each robot must be given the exact same deterministic program, the robots will land somewhere randomly on the planet and will them just follow their program. Find an algorithm that guarantees that the robots can find eachother.

The hardest part is dealing with the fact that both robots must be given the same program. You may assume for simplicity that the robots already have a simple program for searching out an area (were you able to keep one robot stationary while the other moves, this problem would be trivial, as it is easy to search the entire planet surface given its radius and the robots size) so you don't need to write out such an algorithm explicitly.