Coding Solution

Shadows of the Knight - Episode 2 – CodinGame solution in Python

Hardbinary searchgeometryinteractiveperpendicular bisectorUpdated
Short answer

Search one axis at a time. Keep the range of columns that can still hold the bomb and jump to the mirror image of your position around the centre of that range: the perpendicular bisector of the move then cuts the range in half, and WARMER, COLDER or SAME tells you which half (or which exact column) to keep. Once one column remains, do the same along y, and avoid wasting turns at the grid edges by aiming at a quarter of the range instead of its centre when you stand on a border.

The problem

Batman stands in a building of W x H windows (up to 10,000 x 10,000) and must reach the window hiding a bomb within a limited number of jumps. Unlike the first episode, the device does not give a direction: after each jump it only says whether he is now closer to the bomb than at his previous position (WARMER), farther (COLDER) or at the same distance (SAME). The first answer is UNKNOWN.

Each turn you print the coordinates of the next window. Distances are Euclidean, and the jump budget is close to log2(W) + log2(H), so a naive walk or a sloppy halving runs out of turns.

Approach, step by step

  1. Understand what one answer tells youMoving from P to Q and hearing WARMER means the bomb is strictly on Q's side of the perpendicular bisector of PQ, COLDER means P's side, SAME means exactly on it. If P and Q share the same y, that bisector is the vertical line x = (Px + Qx) / 2.
  2. Binary search on x firstKeep the candidate columns [lo, hi] and jump to x' = lo + hi - x, so that the bisector falls on the middle of the range. Keep the half indicated by the answer; SAME pins the column exactly when x + x' is even.
  3. Never stand still and stay in the gridClamp the target to [0, W - 1], and if it equals your current position move by one: a jump of length zero always answers SAME and teaches nothing, which is how simple implementations loop forever.
  4. Use the edge trickWhen you stand on column 0 or W - 1 and the range is already narrowed, aim at the first or last quarter of the range instead of its centre. A full mirror from an edge tends to throw the next mirror outside the grid, where clamping wastes a whole turn.
  5. Switch to yWith one column left, move onto it and binary search the rows the same way. For the transition move, filter the rows with the full squared distances, since both coordinates may change on that jump.

Complexity

TimeO((log W + log H) * (W + H))
SpaceO(W + H)

The number of turns is about log2(W) + log2(H) plus a couple of extra moves. The Python version filters candidate lists each turn for clarity; storing only lo and hi would make each turn O(1).

Solution code

Bug fixed in this version: The original Python code can loop forever. On the y axis it computes y = ys[0] + ys[-1] - y0 without the "avoid fixed points" check it has on the x axis, so when the current row is already the centre of the candidate rows it jumps to the same window, receives SAME, keeps all rows and repeats. Reproduced in a local simulator on a 3 x 3 grid starting at (1, 1) with the bomb at (0, 0), and on a 50 x 50 grid. The replacement uses one helper for both axes, always moves, and was checked on random grids up to 10,000 x 10,000 (at most about log2(W) + log2(H) + 3 jumps).

Shadows of the Knight - Episode 2 – Python

w, h = map(int, input().split())
input()  # number of turns: not needed
x, y = map(int, input().split())

xs = list(range(w))  # columns that may still hold the bomb
ys = list(range(h))  # rows that may still hold the bomb
prev = None          # previous position, None before the first move
phase_x = True       # was the last move made while searching the column?


def next_coord(cands, cur, size):
    """Pick the next coordinate on one axis.

    Mirroring cur around the centre of the candidates puts the bisector of
    the move right in the middle of them. When we stand on a grid edge and
    the search is already narrowed, aim at the first or last quarter
    instead: the full mirror would usually land outside the grid next turn.
    """
    lo, hi = cands[0], cands[-1]
    if cur == 0 and (lo, hi) != (0, size - 1):
        nxt = (3 * lo + hi) // 2 - cur
    elif cur == size - 1 and (lo, hi) != (0, size - 1):
        nxt = (lo + 3 * hi) // 2 - cur
    else:
        nxt = lo + hi - cur
    nxt = max(0, min(size - 1, nxt))
    if nxt == cur:  # never stand still: SAME would then teach nothing
        nxt = cur + 1 if cur + 1 < size else cur - 1
    return nxt


while True:
    info = input()
    if prev is not None and info != "UNKNOWN":
        px, py = prev
        if phase_x:
            # y did not change, so only the x distance matters
            d = lambda i: (i - px) ** 2 - (i - x) ** 2
            if info == "WARMER":
                xs = [i for i in xs if d(i) > 0]
            elif info == "COLDER":
                xs = [i for i in xs if d(i) < 0]
            else:
                xs = [i for i in xs if d(i) == 0]
        else:
            # column is known: compare the full squared distances
            bx = xs[0]
            d = lambda j: ((px - bx) ** 2 + (py - j) ** 2) - ((x - bx) ** 2 + (y - j) ** 2)
            if info == "WARMER":
                ys = [j for j in ys if d(j) > 0]
            elif info == "COLDER":
                ys = [j for j in ys if d(j) < 0]
            else:
                ys = [j for j in ys if d(j) == 0]

    if len(xs) > 1:
        phase_x = True
        nx, ny = next_coord(xs, x, w), y
    else:
        phase_x = False
        nx = xs[0]
        if len(ys) == 1:
            ny = ys[0]
        else:
            ny = next_coord(ys, y, h)

    prev = (x, y)
    x, y = nx, ny
    print(x, y)

Common mistakes

Going further

The geometry is the real key: the device answers "which side of the perpendicular bisector of my last jump is the bomb on", so every jump is a cut of the plane by a line you choose. Searching axis by axis makes those lines vertical, then horizontal, which turns the problem into two 1D searches where the cut point is the midpoint between your old and new positions. That is why the target is the mirror lo + hi - x rather than the centre of the range itself: you do not jump to the middle, you jump so that the middle lies halfway between where you were and where you land. The price is that the landing point can be far from the candidates, sometimes outside the building, and the edge trick of the original author (aim at a quarter of the range when standing on a border) is what keeps the total close to the theoretical log2(W) + log2(H). Simulating your bot offline against random bombs, including 3 x 3 grids, is the fastest way to find stalls.

FAQ

Why not jump straight to the middle of the remaining range?

The answer compares your new distance with your previous one, so the cut happens halfway between the two positions. To cut the range in the middle you must land at the mirror of your current position around that middle.

How many turns does a good solution need?

About ceil(log2 W) + ceil(log2 H), plus one or two moves for the transition between axes and the final jump. Our replacement stayed within three extra jumps of that bound on random tests.

Is distance Manhattan or Euclidean?

Euclidean. With one coordinate fixed it does not matter, but on a diagonal move you must compare squared Euclidean distances.

Similar puzzles

★ 5.0 · 16 reviews · 928 users Add to Chrome