Shadows of the knight 2


The aim of this puzzle is to find bombs in a grid in a few steps, only knowing if you are getting closer or further away at each step.

Difficulty: Very hard · Skills: binary search, interactive search, distance reasoning, candidate filtering

What this puzzle tests in a coding interview

Shadows of the Knight episode 2 is an interactive search where the only feedback is warmer, colder or same. It tests whether you can turn relative distance feedback into a halving strategy, handling each axis separately and coping with jumps near the edges.

How to solve it, step by step

  1. Keep a set of candidate columns and a set of candidate rows, starting with the whole building.
  2. After each jump, filter the candidates on the current axis: keep those closer to the new position for WARMER, closer to the previous one for COLDER, and equidistant for SAME.
  3. Choose the next position as the mirror of the previous one around the centre of the remaining range, so the bisector splits the candidates in half.
  4. Clamp the jump inside the building and handle the special cases at the edges to avoid jumping to the same position.
  5. Once one column remains, move to it and repeat the same process on the rows until the bomb is found.

Time and memory complexity

Each axis is halved roughly every turn, so the number of turns is about O(log W + log H), and filtering lists costs O(W + H) memory and time per turn.

Traps to avoid

Tip for a timed test

Solve the X axis first and only then the Y axis; one dimension at a time makes the feedback unambiguous and the code much shorter.

Python

import sys, math

w,h = [int(i) for i in input().split()]
input() # number of turns before game over is useless
x0,y0 = [int(i) for i in input().split()]

# x0 y0 will be used to store the previous position
# and x y the current position
x,y = x0,y0

# xs*ys is the area where the bomb could be
# we'll first narrow down the area to a column by dichotomy on xaxis
# then to a single windows by dichotomy on yaxis
xs, ys = range(w), range(h)


def narrow(x0,y0,x,y,xs,ys,info):
    print("narrow : x0={}, y0={}, x={}, y={}, info={}".format(x0,y0,x,y,info), file=sys.stderr)
    # xaxis dichotomy
    if len(xs) != 1:
        if info == "UNKNOWN":
            pass
        elif info == "SAME":
            xs = [i for i in xs if abs(x0-i) == abs(x-i)]
        elif info == "WARMER":
            xs = [i for i in xs if abs(x0-i) > abs(x-i)]
        else:
            xs = [i for i in xs if abs(x0-i) < abs(x-i)]
    #yaxis dichotomy
    else:
        if info == "UNKNOWN":
            pass
        elif info == "SAME":
            ys = [i for i in ys if abs(y0-i) == abs(y-i)]
        elif info == "WARMER":
            ys = [i for i in ys if abs(y0-i) > abs(y-i)]
        else:
            ys = [i for i in ys if abs(y0-i) < abs(y-i)]
    print(xs, file=sys.stderr)
    print(ys, file=sys.stderr)
    return xs,ys


while 1:
    info = input()
    # uses infos to narrow the area where the bomb could be
    xs,ys = narrow(x0,y0,x,y,xs,ys,info)
    # chooses the new location so that it allows to split the area in half next turn
    x0,y0 = x,y
    # dichotomy along x axis
    if len(xs) != 1:
        # the bisection between x0 and x should cut the area in 2 so:
        # (x + x0)/2 = (xs[0] + xs[-1])/2
        # little trick
        if (x0 == 0 and len(xs) != w):
            x = (3*xs[0] + xs[-1])//2 - x0
        elif (x0 == w-1 and len(xs) != w):
            x = (xs[0] + 3*xs[-1])//2 - x0
        else:
            x = xs[0] + xs[-1] - x0
        
        # to avoid fixed points
        if x == x0:
            x+=1
        x = min(max(x, 0), w-1)
 
    else:
    # transition to second dichotomy
        if x != xs[0]:
            x = x0 = xs[0]
            print(x, y)
            info = input()
        # finishing
        if len(ys) == 1:
            y = ys[0]
        # dichotomy along y axis
        else:
            if (y0 == 0 and len(ys) != h):
                y = (3*ys[0] + ys[-1])//2 - y0
            elif (y0 == h-1 and len(ys) != h):
                y = (ys[0] + 3*ys[-1])//2 - y0
            else:
                y = ys[0] + ys[-1] - y0
            y = min(max(y, 0), h-1)
    
    print(x, y)