Shadows of the Knight - Episode 2 – solution CodinGame en Python
On cherche un axe à la fois. On conserve l'intervalle de colonnes pouvant encore contenir la bombe et on saute au symétrique de sa position par rapport au centre de cet intervalle : la médiatrice du déplacement coupe alors l'intervalle en deux, et WARMER, COLDER ou SAME indique quelle moitié (ou quelle colonne exacte) garder. Quand il ne reste qu'une colonne, on recommence sur y, et on évite de perdre des tours aux bords de la grille en visant un quart de l'intervalle plutôt que son centre quand on se tient sur une bordure.
L'énoncé
Batman se trouve dans un immeuble de W x H fenêtres (jusqu'à 10 000 x 10 000) et doit atteindre celle qui cache une bombe en un nombre limité de sauts. Contrairement au premier épisode, le détecteur ne donne pas de direction : après chaque saut, il indique seulement si Batman est maintenant plus près de la bombe qu'à sa position précédente (WARMER), plus loin (COLDER) ou à la même distance (SAME). La première réponse est UNKNOWN.
Chaque tour, on affiche les coordonnées de la prochaine fenêtre. Les distances sont euclidiennes et le budget de sauts est proche de log2(W) + log2(H) : une marche naïve ou une dichotomie approximative épuise les tours.
La démarche, étape par étape
- Comprendre ce qu'apprend une réponsePasser de P à Q et entendre WARMER signifie que la bombe est strictement du côté de Q par rapport à la médiatrice de PQ, COLDER du côté de P, SAME exactement dessus. Si P et Q ont le même y, cette médiatrice est la droite verticale x = (Px + Qx) / 2.
- Dichotomie sur x d'abordOn garde les colonnes candidates [lo, hi] et on saute en x' = lo + hi - x, pour que la médiatrice tombe au milieu de l'intervalle. On garde la moitié indiquée par la réponse ; SAME fixe la colonne exactement quand x + x' est pair.
- Ne jamais rester sur place et rester dans la grilleOn borne la cible à [0, W - 1], et si elle coïncide avec la position actuelle on se décale d'une case : un saut de longueur nulle répond toujours SAME et n'apprend rien, c'est ainsi que les implémentations simples bouclent à l'infini.
- Utiliser l'astuce de bordQuand on se tient sur la colonne 0 ou W - 1 et que l'intervalle est déjà réduit, on vise le premier ou le dernier quart de l'intervalle plutôt que son centre. Un symétrique complet depuis un bord projette souvent le symétrique suivant hors de la grille, où le bornage gaspille un tour entier.
- Passer à yAvec une seule colonne restante, on s'y place et on dichotomise les lignes de la même façon. Pour le déplacement de transition, on filtre les lignes avec les distances au carré complètes, puisque les deux coordonnées peuvent changer sur ce saut.
Complexité
O((log W + log H) * (W + H))O(W + H)Le nombre de tours est d'environ log2(W) + log2(H) plus quelques déplacements. La version Python filtre des listes de candidats à chaque tour pour la lisibilité ; ne garder que lo et hi rendrait chaque tour en O(1).
Code de la solution
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)
Erreurs fréquentes
- Traiter SAME comme « aucune information »SAME est la réponse la plus précise possible : la bombe est exactement sur la médiatrice, donc la colonne vaut (x + x') / 2. Si x + x' est impair, SAME est impossible sur cet axe, ce qui fait un bon test de cohérence.
- Sauter sur sa propre positionQuand x est déjà le centre de l'intervalle, le symétrique est x lui-même. Sans décalage d'une case, on reçoit SAME indéfiniment et on dépasse le temps, souvent sur de petites grilles comme 3 x 3.
- Borner sans compenserSi le symétrique sort de la grille et qu'on le borne simplement, la médiatrice peut tomber hors de l'intervalle candidat et le tour est perdu. Répété sur une grande grille, le symétrique brut est monté à 35 sauts sur 8000 x 8000 dans nos essais, contre 29 avec l'astuce de bord.
- Se déplacer en diagonale pendant la recherche 1DSi y change pendant qu'on cherche x, la médiatrice n'est plus verticale et la simple comparaison sur x est fausse. Il faut garder y fixe pendant la phase x, ou filtrer avec les distances au carré complètes.
Pour aller plus loin
La géométrie est la vraie clé : le détecteur répond « de quel côté de la médiatrice de mon dernier saut se trouve la bombe », donc chaque saut est une coupe du plan par une droite que l'on choisit. Chercher axe par axe rend ces droites verticales, puis horizontales, ce qui transforme le problème en deux recherches 1D où le point de coupe est le milieu entre l'ancienne et la nouvelle position. C'est pourquoi la cible est le symétrique lo + hi - x et non le centre de l'intervalle : on ne saute pas au milieu, on saute pour que le milieu se trouve à mi-chemin entre le point de départ et le point d'arrivée. Le prix à payer est que le point d'arrivée peut être loin des candidats, parfois hors de l'immeuble, et l'astuce de bord de l'auteur d'origine (viser un quart de l'intervalle quand on est sur une bordure) est ce qui maintient le total proche du log2(W) + log2(H) théorique. Simuler son bot hors ligne contre des bombes aléatoires, y compris sur des grilles 3 x 3, est le moyen le plus rapide de repérer les blocages.
Questions fréquentes
Pourquoi ne pas sauter directement au milieu de l'intervalle restant ?
La réponse compare la nouvelle distance à la précédente, donc la coupe se fait à mi-chemin entre les deux positions. Pour couper l'intervalle en son milieu, il faut atterrir au symétrique de sa position actuelle par rapport à ce milieu.
Combien de tours faut-il à une bonne solution ?
Environ ceil(log2 W) + ceil(log2 H), plus un ou deux déplacements pour la transition entre les axes et le saut final. Notre remplacement est resté à moins de trois sauts de cette borne sur des tests aléatoires.
La distance est-elle de Manhattan ou euclidienne ?
Euclidienne. Avec une coordonnée fixe cela ne change rien, mais sur un déplacement diagonal il faut comparer des distances euclidiennes au carré.