Power of Thor - Episode 1 – solution CodinGame en C
On compare les coordonnées de Thor à celles de l'éclair : on ajoute N ou S si les Y diffèrent, puis E ou O (W) si les X diffèrent, on affiche la direction obtenue et on met à jour la position de Thor nous-mêmes, car le jeu ne la renvoie jamais. Avancer en diagonale tant que les deux axes diffèrent donne le chemin le plus court, donc on arrive toujours dans le nombre de tours autorisé.
L'énoncé
Thor se trouve sur une grille de 40 x 18 cases et doit rejoindre un éclair de puissance immobile. La première ligne donne X et Y de l'éclair, puis X et Y de départ de Thor. L'origine est le coin supérieur gauche : Y augmente vers le bas.
À chaque tour, le jeu envoie le nombre de déplacements restants, et on répond par l'une des huit directions N, NE, E, SE, S, SW, W ou NW. Thor perd s'il sort de la carte ou s'il épuise ses déplacements avant d'atteindre l'éclair.
La démarche, étape par étape
- Lire les positions une seule foisSeule la première ligne contient des coordonnées. On stocke la position de l'éclair et celle de Thor (ou simplement leur différence) dans des variables qu'on mettra à jour soi-même.
- Choisir la composante verticaleSi Thor est au-dessus de l'éclair (Y plus petit), on va au S ; s'il est en dessous, au N ; si les Y sont égaux, pas de composante verticale.
- Choisir la composante horizontaleMême logique sur X : E si l'éclair est à droite, W s'il est à gauche, rien s'ils sont alignés.
- Afficher puis mettre à jourOn concatène les deux parties, verticale d'abord, on affiche, puis on déplace d'une case les coordonnées mémorisées de Thor sur chaque axe utilisé. Sans cette mise à jour, Thor dépasse la cible car le code le croit toujours au départ.
Complexité
O(1) par tourO(1)Chaque tour, c'est deux comparaisons et deux incréments. Le nombre total de tours vaut max(|dx|, |dy|), la distance de Tchebychev entre Thor et l'éclair.
Code de la solution
Power of Thor - Episode 1 – C
Conserve les quatre coordonnées et met à jour X et Y de Thor après chaque déplacement. Le nombre de tours restants n'est pas lu ; CodinGame ne l'exige pas, mais le lire avec scanf est une meilleure habitude.
#include <stdlib.h>
#include <stdio.h>
int main(int argc, char** argv)
{
// Coordinates of the light and Thor
int lX, lY, tX, tY;
scanf("%d%d%d%d", &lX, &lY, &tX, &tY);
for (;;) {
if (tY < lY) {
printf("S");
tY++;
}
else if (tY > lY) {
printf("N");
tY--;
}
if (tX < lX) {
printf("E");
tX++;
}
else if (tX > lX) {
printf("W");
tX--;
}
printf("\n");
}
return EXIT_SUCCESS;
}
Power of Thor - Episode 1 – Java
Ne stocke que la différence éclair - Thor : deux variables suffisent et chaque comparaison se fait par rapport à 0. Une astuce qui divise par deux l'état à maintenir.
import java.util.*;
class Player {
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
/* We could store the coordinates of Thor and its target (4 vars)
Or like here, store the difference target - Thor (2 vars)
It is more efficient for comparisons and simpler*/
int diffX = in.nextInt();
int diffY = in.nextInt();
diffX -= in.nextInt();
diffY -= in.nextInt();
while (true) {
if (diffY > 0) {
System.out.print("S");
diffY--;
}
else if (diffY < 0) {
System.out.print("N");
diffY++;
}
if (diffX > 0) {
System.out.print("E");
diffX--;
}
else if (diffX < 0) {
System.out.print("W");
diffX++;
}
System.out.print("\n");
}
}
}
Power of Thor - Episode 1 – Python 3
Construit la réponse à partir de deux chaînes éventuellement vides et les affiche avec sep="" pour qu'un déplacement purement vertical ou horizontal ne donne qu'une lettre.
# lX, lY: coordinates of the light of power
# tX, tY: Thor's coordinates
lX, lY, tX, tY = [int(i) for i in input().split()]
# The light never moves, so the four numbers above are all we need.
# Each turn the game also sends the remaining number of moves; this code ignores it.
while (True):
# ch1 is the vertical part (N/S), ch2 the horizontal part (E/W).
# An empty string means "no move on that axis".
ch1 = ch2 = ""
# Y grows downward on CodinGame maps, so a light below Thor means going South.
if tY < lY:
ch1 = "S"
tY+=1
elif tY > lY:
ch1 = "N"
tY-=1
# Same idea on the X axis: light to the right means East.
if tX < lX:
ch2 = "E"
tX+=1
elif tX > lX:
ch2 = "W"
tX-=1
# Vertical letter first: the referee accepts "NE", not "EN".
print(ch1, ch2, sep="")
Erreurs fréquentes
- Ne pas mettre à jour ThorLe jeu n'envoie la position de Thor qu'une fois. Si on recalcule la direction à partir des valeurs initiales à chaque tour, Thor continue tout droit et sort de la carte.
- Inverser Nord et SudEn coordonnées écran, Y augmente vers le bas. Un éclair avec un Y plus grand que Thor est au Sud, pas au Nord. Se tromper fait sortir Thor par le haut de la carte.
- Écrire « EN » au lieu de « NE »L'arbitre ne connaît que les huit directions avec la lettre verticale en premier. « EN » ou « ES » est une action invalide qui termine la partie aussitôt.
- Avancer un axe après l'autreAller d'abord tout droit puis en diagonale (ou l'inverse) coûte |dx| + |dy| déplacements au lieu de max(|dx|, |dy|). Sur les tests où l'énergie est juste, Thor tombe à court.
Pour aller plus loin
Le nombre de déplacements nécessaires est la distance de Tchebychev max(|dx|, |dy|), et non la distance de Manhattan |dx| + |dy|, car un pas en diagonale réduit les deux écarts d'un coup. La règle gloutonne « diagonale tant que les deux axes diffèrent, puis tout droit » atteint exactement cette borne : chaque tour réduit de un le plus grand des deux écarts, c'est pourquoi Thor ne manque jamais d'énergie. La version Java montre une reformulation utile : au lieu de suivre deux positions, on suit le vecteur Thor → éclair et on le ramène à (0, 0). On retrouve cette idée dans Shadows of the Knight et dans beaucoup de puzzles de déplacement où seule la position relative compte.
Questions fréquentes
Pourquoi Thor sort-il de la carte avec ma solution ?
Le plus souvent, le code ne met pas à jour la position de Thor. Le jeu n'envoie que ses coordonnées de départ : c'est à vous de les modifier après chaque déplacement.
Dans quel sens est le Sud dans Power of Thor ?
Le Sud correspond à Y croissant. L'origine (0, 0) est le coin supérieur gauche de la carte, comme dans la plupart des repères écran.
Faut-il lire le nombre de tours restants ?
Il est envoyé à chaque tour mais inutile pour ce puzzle. Le lire reste une bonne pratique pour garder l'entrée synchronisée si vous ajoutez de la logique plus tard.