Circle Puzzle

1. Turn the light OFF in the starting room to make an anchor.
2. Walk 1 room clockwise.
3. Turn ON any light we encounter.
4. Walk back to the starting room.
5. If the starting room light is still OFF, we haven’t completed a full circle.
6. Walk 2 rooms counterclockwise, turning ON any lights we encounter, then return.
7. Continue this process, doubling the distance and alternating direction each sweep ($1, 2, 4, 8, \dots$).
8. When we return to the starting room and find its light is ON, we’ll know our last sweep wrapped around and hit the starting room from behind. Since we turned on every room in that sweep, all lights are now on.

They gave the formula $2^{2 + \lceil \log_2 N \rceil} - 2$ as the maximum total steps taken before this process finishes. Where does this come from?

Well, during each sweep $i$ (for $i = 0, 1, 2, \dots$), we walk $2^i$ rooms outward and $2^i$ rooms back. This requires $2 \times 2^i$ steps.

We have to increase the sweep distance until it equals or exceeds the total number of rooms $N$. Let $k$ equal the index of this final sweep. The value of $k$ is the smallest integer where $2^k \ge N$, which means $k = \lceil \log_2 N \rceil$.

To find the total number of steps, sum the steps across all sweeps from $i=0$ to $k$:

$\sum_{i=0}^{k} 2 \times 2^i = 2 \sum_{i=0}^{k} 2^i$

This is geometric series, so:

$2(2^{k+1} - 1) = 2^{k+2} - 2$

Laslty, sub in $k = \lceil \log_2 N \rceil$ to get the final result.

$2^{2 + \lceil \log_2 N \rceil} - 2 < \boxed{8N}$

The overall algorithm works like this:

1. We’ll maintain a contiguous block of ON lights and surround this block with two OFF lights, which are our anchors.
2. In each phase, we push one anchor outward by a power of 2, turning lights ON as we walk, and we place a new OFF anchor at the end.
3. We then walk backward through the ON block to verify it’s still intact until we find the opposite anchor. If intact, push in the other direction, swapping every phase. But if our outward push is large enough to wrap around the entire circle, we’ll overwrite the opposite anchor, so the verification catches that. Then we just turn that last light ON to finish.

Now to find a bound, we’ll first define variables at each step:

Let N equal the total number of rooms in the palace.

1. After setting up the initial anchors as shown above, we’ll end on our right anchor with an ON block of size $B_0 = 1$.
2. Let’s start the expansion phases, indexed by i = 0, 1, 2, and so on.
3. During phase i, we push our active anchor outward by $S_i = 2^i$ rooms.
4. To verify the block, we’ll turn around and walk backward through our ON block until we hit an OFF light.
5. The number of steps to cross the block should be $B_i + S_i + 1$ (if it’s less, we know we’ve crossed the circle). In the usual case, we’ll update the block size for the next phase: $B_{i+1} = B_i + S_i$ and repeat the push with the other anchor ($S_{i+1}=2^{i+1}$ steps this time)
6. Let k be the phase where our push $S_k$ wraps around the ring. In that case, we overwrite the opposite anchor, leaving exactly one OFF light in the circle. So our verification will take N - 1 steps to find it. We turn it ON and report done.

Finally, we can calculate the total steps.

Initialization takes 2 steps.

In every phase $i$, we walk $S_i$ steps outward and $B_i + S_i + 1$ steps backward, giving a total of

$D_i = 2 * S_i + B_i + 1$

Since $B_{i+1} = B_i + S_i$, and $S_i = 2^i$, we know $B_{i+1} = B_i + 2^i$. With the base case B_0 = 1, we can solve the recurrence to find $B_i = 2^i$.

Substitute B_i into the total distance formula for each phase:

$D_i = 2 * 2^i + (2^i) + 1$

$D_i = 3 * 2^i + 1.$

Phase k is our last wrap-around phase. Since phase $k-1$ did not wrap around, the block size at the start of phase k must be strictly less than N, or $B_k = 2^k < N$

During phase k, we walk $S_k = 2^k$ steps outward and verify by walking backward until we hit the only remaining OFF light, which takes N - 1 steps. Thus total steps in phase k is

$D_{last} = 2^k + N - 1$

Now let’s sum the steps across the entire process.

Total = $2 + \sum_{i=0}^{k-1} (3 * 2^i + 1) + (2^k + N - 1)$

$= 2 + 3 * (2^k - 1) + k + 2^k + N - 1$

$= 4 * 2^k + k + N - 2$ From the fail condition of phase $k-1$, we know $2^k < N$. Substitute $2^k < N$ into the total equation, for $4 * 2^k < 4N$.

The term $k$ is propto $\log_2N$, so this term becomes negligible as $N$ grows.

Replacing $4 * 2^k$ with $4N$, we end with the very upper bound on the runtime:

Total $< 4N + N -2 < \boxed{5N}$ !!

(or $5N+\log_2N-2$ to be precise)

#include <bits/stdc++.h>
using namespace std;

// class helps to simulate an agent that only knows its local location/step cnt
struct State {
  int n,pos,steps;
  vector<int> a;
  
  State(int n) : n(n), pos(0), steps(0) {
    a.assign(n,0);
    for (int i=0; i<n; ++i) a[i]=rand()%2;
  }
  
  int read() { return a[pos]; }
  
  void write(int v) { a[pos]=v; }
  
  void move(int d) {
    ++steps;
    pos=((pos+d)%n+n)%n; // mod so it cycles
  }
  
  // verify everything is ON at the end
  bool check() {
    for (int x : a) if (x==0) return false;
    return true;
  }
};

int solve_8n(int n) {
  State s(n);
  s.write(0);
  int dist=1;
  int dir=1;
  while (1) {
    // walk fwd
    for (int i=0; i<dist; ++i) {
      s.move(dir);
      s.write(1);
    }
    // walk back
    for (int i=0; i<dist; ++i) {
      s.move(-dir);
    }
    if (s.read()==1) break;
    dist*=2;
    dir*=-1;
  }
  assert(s.check());
  return s.steps;
}

int solve_5n(int n) {
  State s(n);
  s.write(0);
  s.move(1); s.write(1);
  s.move(1); s.write(0);
  int B=1;
  int S=1;
  int dir=1;
  while (1) {
    s.write(1);
    for (int i=0; i<S; ++i) {
      s.move(dir);
      s.write(1);
    }
    s.write(0);
    int walked=0;
    while (1) {
      s.move(-dir);
      ++walked;
      if (s.read()==0) break;
    }
    int expected_gap=B+S+1;
    if (walked<expected_gap) {
      s.write(1);
      break;
    }
    B=B+S;
    S*=2;
    dir*=-1;
  }
  assert(s.check());
  return s.steps;
}

int main() {
  srand(time(0));
  vector<int> tests={10,50,100,1000,10000,100000,1000000,10000000};
  cout << "num of steps for each testcase and strategy: \n";
  cout << "N 8N 5N\n";
  for (int n : tests) {
    int s1=solve_8n(n);
    int s2=solve_5n(n);
    cout << n << ' ' << s1 << ' ' << s2 << ' ' << (s1>s2 ? "true" : "false") << '\n';
    assert(s1<=8*n);
    assert(s2<=5*n);
  }
}

num of steps for each testcase and strategy: 
N 8N 5N
10 62 44 true
50 254 182 true
100 510 361 true
1000 4094 3056 true
10000 65534 42780 true
100000 524286 362159 true
1000000 4194302 3097170 true
10000000 67108862 43554454 true

We can simply move in one direction, turning all the lights ON. In the first $256$ rooms, leave a random hash (generated w/ e.g. a coin), so we’ll know when we’ve come full circle.

• That’s as strong as SHA256, like bitcoin’s private keys, or the number of atoms in the universe! We almost certainly won’t come across our signature by accident.
• To be sure, once we hit our hash, we can just turn off the current room, walk backwards $N$ steps, and check if the light is off. If not, just keep searching this way and updating our guess for $N$.
• If the room designer isn’t an adversary, we could also just make our hash simply a line of $256$ ONs, instead of a random sequence.
• In practically every case, this is ~$2N$ steps.