Introduction
This comes from a well-liked question on the Math SE by RobAu and a more specific follow-up to that by Danikov.
There is a palace which is a grid of n × n rooms, which we will index using two coordinates 0 ≤ x,y < n. The rooms are organized in a torus topology, i.e. with wrap-around at the edges. So the room to the right of (n-1,3) is (0,3) again, and likewise for the y direction.
Two robots are placed into this grid, and their objective is to rendezvous. But the problem is that these only can can keep track of relative changes in position and orientation. So each robot has its own local coordinate system, where its initial position is called (0,0), but these two coordinate systems relate to one another in any of 4n2 possible ways, accounting for 4 possible relative rotations and n × n relative shifts. Each of these relations has equal probability.
The palace has no doors. The robots can move around the palace by teleportation. They move in a synchronized way, teleporting at exactly the same instant. To meet they either have to be in the same room at the same time, or to swap places during teleportation.
Challenge
Your task is to write a program for these robots, trying to minimize the expected time till rendezvous. The same program will be executed for both robots, and the robots have no way to distinguish which one is which. So we'll be executing two copies of your code in parallel.
Input
The only input is n, the size of the palace. In addition to that, the code has access to a random number generator, and the random numbers from one instance are assumed to be independent from those in the other instance. No other input or communication between the instances is allowed.
Output
The output of your code should be an infinite sequence of coordinate pairs, (x,y), indicating the target room for the next teleportation. The coordinates are relative to where the robot started, not relative to where he currently is located. Giving the same output repeatedly means you are staying put in a given room.
Framework
You are asked to evaluate your code yourself. Write or copy a framework which will randomly choose relative starting positions, execute two instances of your code in parallel, detect a successful rendezvous and report the time to rendezvous. Run that code a number of times, and compute the average and standard deviation of the time to rendezvous. See the section below for ready-to-copy code.
Submission
Your answer must include the code which constitutes the program for one robot. It must also include the average time to rendezvous and its standard deviation for the following setups:
- at least 1,000,000 runs for n = 2
- at least 100,000 runs for n = 64
- at least 10,000 runs for n = 256
You don't have to paste your framework by default, but be willing to provide it upon request. An explanation of what your code is doing and why you wrote it that way might bring upvotes.
Scoring
The title of best answer will go to the code with the minimal expected time to rendezvous for n = 64. I'll re-evaluate the top contenders myself, to make sure you included genuine results. The closer two competitors are, the more often I'll run their code to establish a reliable expected value from the average. This is an open-ended contest, so the title may be re-awarded when a better answer comes along.
Example frameworks
C++
You can use the following fixture if you like.
#include <random>
#include <iostream>
#include <iomanip>
#include <cmath>
constexpr int n = 64;
const int orientations[4][4] = {
{1, 0, 0, 1},
{0, 1, n - 1, 0},
{n - 1, 0, 0, n - 1},
{0, n - 1, 1, 0}
};
std::default_random_engine randEngine((std::random_device())());
std::uniform_int_distribution<int> randDist{0, n - 1};
std::uniform_int_distribution<int> randDist4{0, 3};
int rand() { return randDist(randEngine); }
typedef std::pair<int, int> pos_t;
class Robot {
public:
pos_t next() { return {rand(), rand()}; }
};
class Transform {
int dx, dy, ori;
public:
Transform() : dx{rand()}, dy{rand()}, ori{randDist4(randEngine)} { }
pos_t operator()(const pos_t& in) const {
int x = in.first, y = in.second;
const int *o = orientations[ori];
return { (o[0] * x + o[1] * y + dx) % n, (o[2] * x + o[3] * y + dy) % n };
}
};
unsigned long run() {
Transform tr;
pos_t p1{0, 0}, p2{0, 0};
p2 = tr(p2);
Robot r1, r2;
unsigned long t = 0;
while (p1 != p2) {
++t;
pos_t q1 = r1.next();
pos_t q2 = tr(r2.next());
if (p1 == q2 && p2 == q1) break;
p1 = q1;
p2 = q2;
}
// std::cout << std::setw(8) << t << "\n";
return t;
}
int main(int argc, char** argv) {
double sum = 0, sumSq = 0;
int report = 10;
for (int i = 1; ; ++i) {
double r = run();
sum += r;
sumSq += r*r;
if (i == report) {
double avg = sum / i;
double var = (sumSq - sum*avg) / (i - 1);
double sd = std::sqrt(var);
std::cout << std::setw(8) << i << " runs: Expected: "
<< std::fixed << std::setprecision(2) << avg
<< ", SD: "
<< std::fixed << std::setprecision(2) << sd
<< std::endl;
report *= 10;
}
}
}
In a submission you'd just paste the next function. A possible statistical report for the above could read:
n = 2: Expected 2.40, SD 2.68 in 10,000,000 runs
n = 64: Expected 4105.08, SD 4104.22 in 10,000,000 runs
n = 256: Expected 64911.36, SD: 65204.72 in 10,000 runs
Python, …
To be extended for other languages. Feel free to donate your own framework if you feel like it.
