Shadows of the Knight - Episode 1 – CodinGame solution in C
Maintain the rectangle of cells where the bomb can still be, starting with the whole building. Each turn, use the direction you receive to shrink it (U sets the bottom bound to y - 1, D sets the top bound to y + 1, no vertical letter fixes y, and the same for L and R on x), then jump to the centre of the remaining rectangle. Both axes are halved at the same time, so you need about log2(max(W, H)) jumps.
The problem
Batman is in a building of W x H windows and must find the window where the bomb is hidden before a limited number of jumps runs out. Each turn the game tells you the direction of the bomb relative to your current window (U, UR, R, DR, D, DL, L or UL) and you answer with the coordinates of the next window to jump to.
Coordinates start at (0, 0) in the top-left corner, so 'up' means a smaller y. W and H can be as large as 10,000, and the number of jumps allowed is close to the minimum, so you need a strategy that discards about half of the remaining cells on each axis every turn.
Approach, step by step
- Keep a bounding boxStore xMin, xMax, yMin, yMax, initialised to 0, W - 1, 0, H - 1. The bomb is always inside this box, and the box only ever shrinks.
- Update the vertical boundsIf the direction contains U, the bomb is above you: yMax = y - 1. If it contains D, yMin = y + 1. If it contains neither, the bomb is on your row: yMin = yMax = y.
- Update the horizontal boundsSame logic on x: L gives xMax = x - 1, R gives xMin = x + 1, and no horizontal letter means xMin = xMax = x. Both axes are processed independently from the same hint.
- Jump to the centreMove to ((xMin + xMax) / 2, (yMin + yMax) / 2). Whatever the next hint is, at least half of the remaining range on each unresolved axis is eliminated.
Complexity
O(log max(W, H)) turns, O(1) per turnO(1)Each axis is a separate binary search and both progress in parallel on every jump, so the number of turns is that of the larger dimension, not the sum of both.
Solution code
Bug fixed in this version: The algorithm is correct, but the direction is read with scanf("%s") into char BD[2]. Two-letter directions such as "UR" need 3 bytes including the terminating '\0', so every diagonal hint writes one byte past the buffer (AddressSanitizer reports a stack-buffer-overflow). It usually works by luck, but it is undefined behaviour. The replacement uses a 4-byte buffer with a width limit and strchr to test the letters.
Shadows of the Knight - Episode 1 – C
#include <stdio.h>
#include <string.h>
int main(void) {
int W, H, turns, x, y;
scanf("%d %d %d %d %d", &W, &H, &turns, &x, &y);
/* the bomb is somewhere in [xMin, xMax] x [yMin, yMax] */
int xMin = 0, xMax = W - 1;
int yMin = 0, yMax = H - 1;
char dir[4]; /* up to 2 letters + '\0' */
while (scanf("%3s", dir) == 1) {
if (strchr(dir, 'U')) yMax = y - 1;
else if (strchr(dir, 'D')) yMin = y + 1;
else yMin = yMax = y;
if (strchr(dir, 'L')) xMax = x - 1;
else if (strchr(dir, 'R')) xMin = x + 1;
else xMin = xMax = x;
x = (xMin + xMax) / 2;
y = (yMin + yMax) / 2;
printf("%d %d\n", x, y);
fflush(stdout);
}
return 0;
}
Common mistakes
- Forgetting to lock an axisWhen the hint is just 'L' or 'R', the bomb is on your current row. If you do not set yMin = yMax = y, you keep wasting jumps searching vertically and run out of turns.
- Updating bounds to y instead of y - 1Writing yMax = y after a 'U' keeps the current row, which you already know is wrong. On narrow ranges the centre then stays on the same cell and the search gets stuck in a loop.
- Inverting up and downy grows downwards in this puzzle. Treating U as 'increase y' sends Batman the wrong way on the very first jump.
- Searching one axis after the otherFinishing the horizontal search before starting the vertical one costs log2(W) + log2(H) jumps, which exceeds the limit on large buildings. Shrink both axes on every turn.
Going further
The reason this fits within the jump limit is that a single hint carries information about both axes at once: 'UR' is really two independent answers, 'smaller y' and 'larger x'. Treating them separately turns the problem into two ordinary binary searches that run in parallel, so the cost is ceil(log2(max(W, H))) turns rather than the sum of the two logarithms. Note also that the hint is relative to your current window, not to the previous one, so jumping to the exact centre of the box is optimal for this episode. Episode 2 removes the direction and only says WARMER, COLDER or SAME, which forces you to search one axis at a time and to choose jump targets by reflection around the middle of the interval, a much harder problem.
FAQ
Is Heat Detector the same puzzle as Shadows of the Knight Episode 1?
Yes. CodinGame renamed Heat Detector to Shadows of the Knight - Episode 1; the rules, inputs and test cases are the same.
Why does my Batman run out of jumps?
Most often an axis is not locked when the hint has no letter for it, or the bounds are set to x or y instead of x - 1 / x + 1, so the box does not shrink.
Should I round the centre up or down?
Either works as long as you exclude the current cell when updating bounds. Integer division (rounding down) is the simplest and always lands inside the box.