Coding Solution

The Paranoid Android – CodinGame solution in C

Mediumsimulationgreedygame loopinput parsingUpdated
Short answer

Store, for every floor, the column the clones must reach: the elevator position on each floor and the exit position on the exit floor. Each turn, look only at the leading clone: if it walks left while its target is to its right, or right while its target is to its left, answer BLOCK; in every other case, including when there is no clone (floor -1), answer WAIT.

The problem

Clones leave a generator on the bottom floor one after another and walk in a straight line, turning around only when they meet a blocked clone. Each floor has one elevator that carries a clone to the floor above, and the exit sits on the top floor. You are told the number of floors, the area width, the number of rounds, the exit position, the number of clones available and the position of every elevator.

Every turn you receive the floor, position and direction of the leading clone (or -1 -1 NONE if there is none) and must answer WAIT or BLOCK. A blocked clone stays in place as a wall that reverses the others. Guide at least one clone to the exit before running out of rounds or clones.

Approach, step by step

  1. Read the whole initialisation lineThe first line holds eight integers; only the number of floors, the exit floor and the exit position matter for this episode. Then read one line per elevator and store its position indexed by floor.
  2. Build a target per floortarget[f] is the elevator column on floor f, and target[exitFloor] is the exit column. With this array, every floor is the same sub-problem: reach a known column.
  3. Decide on the leading clone onlyIf the clone faces LEFT and pos < target, or faces RIGHT and pos > target, it is walking away from its goal, so BLOCK it. The clone behind it will bump into the blocked one and turn around in the right direction.
  4. Wait in every other caseWhen the clone is already heading towards its target, standing on it, or when there is no leading clone (floor -1), answer WAIT. Never block a clone that is on its target column: it is about to take the elevator.

Complexity

TimeO(1) per turn
SpaceO(F)

After an O(F) setup for the floor targets, each turn is a single comparison. F is the number of floors.

Solution code

Bug fixed in this version: The logic of the original C code is correct, but it calls strcmp() without including <string.h>. Older GCC versions only warn about the implicit declaration; GCC 14 and strict C99 builds reject it, so the code may not compile depending on the compiler. The replacement includes no extra header (it tests the first letter of the direction), reads all eight values by name and flushes stdout after each answer.

The Paranoid Android – C

#include <stdio.h>

int main(void) {
    int nbFloors, width, nbRounds, exitFloor, exitPos, nbClones, nbAddElevators, nbElevators;
    scanf("%d %d %d %d %d %d %d %d", &nbFloors, &width, &nbRounds, &exitFloor,
          &exitPos, &nbClones, &nbAddElevators, &nbElevators);

    /* target[f] = column the leading clone must reach on floor f */
    int target[nbFloors];
    target[exitFloor] = exitPos;
    for (int i = 0; i < nbElevators; i++) {
        int f, pos;
        scanf("%d %d", &f, &pos);
        target[f] = pos;
    }

    while (1) {
        int floor, pos;
        char dir[11];
        scanf("%d %d %10s", &floor, &pos, dir);

        /* block only a clone that walks away from its target */
        if (floor >= 0 && ((dir[0] == 'L' && pos < target[floor]) ||
                           (dir[0] == 'R' && pos > target[floor])))
            printf("BLOCK\n");
        else
            printf("WAIT\n");
        fflush(stdout);
    }
    return 0;
}

Common mistakes

Going further

The reason a single comparison is enough is that all clones leave the generator in the same direction and keep their direction when they ride an elevator. So each floor is entered exactly once by the leading clone, and at most one BLOCK per floor is ever needed: either the clone arrives facing its target and walks straight to it, or it arrives facing away and one sacrifice turns everybody behind it around. That gives an upper bound of one sacrificed clone per floor, which is why this greedy rule fits the clone budget of the tests. The hard sequel, "The Paranoid Android - One step further", breaks this property: some floors have several elevators or none, and you have to build extra elevators, so the problem turns into a shortest path search over (floor, position, direction) states.

FAQ

Why do I only need to look at the leading clone?

The clones behind the leader follow the same path a few cells later. Whatever you do to the leader (letting it pass or blocking it) decides the direction of the whole group on that floor.

What does the direction NONE mean?

It comes with floor -1 and position -1 when no clone is currently walking, typically at the start or right after a block. Answer WAIT and the next clone will appear.

How is this different from "One step further"?

In the sequel you can build additional elevators and some floors have several or none, so the greedy "block if walking away" rule is not enough and a graph search is needed.

Similar puzzles

★ 5.0 · 16 reviews · 928 users Add to Chrome