Mars Lander - Episode 2 – solution CodinGame en Java
On repère d'abord le segment plat, puis chaque tour on choisit un comportement selon la situation du module : hors de la zone, on freine s'il va trop vite ou dans le mauvais sens, sinon on s'incline d'environ 21° vers la zone à pleine puissance pour avancer sans perdre d'altitude ; au-dessus de la zone, on annule la vitesse horizontale en orientant la poussée contre le vecteur vitesse, puis on se redresse à 0° pour la descente finale. L'angle qui annule une vitesse vaut asin(hSpeed / speed) en degrés.
L'énoncé
Le terrain est une ligne brisée d'au plus 30 points sur une carte de 7000 × 3000 m, avec exactement un segment plat d'au moins 1000 m de large. Le module démarre loin de cette zone, souvent avec une vitesse horizontale initiale, sous une gravité martienne de 3,711 m/s².
Chaque tour, on envoie une rotation (de −90 à 90 degrés) et une puissance (de 0 à 4). Le jeu limite les variations à 15° et un niveau de puissance par tour. Pour réussir, il faut toucher la zone plate avec un angle de 0, une vitesse verticale d'au plus 40 m/s et une vitesse horizontale d'au plus 20 m/s, sans épuiser le carburant.
La démarche, étape par étape
- Repérer la zone platePendant la lecture du relief, on compare la hauteur de chaque point à celle du précédent : deux points consécutifs de même y définissent le x gauche, le x droit et l'altitude du segment d'atterrissage.
- Se placer au-dessus de la zoneSi le module est hors du segment et s'en éloigne, ou dépasse environ 80 m/s à l'horizontale, on freine. S'il se dirige vers la zone trop lentement, on s'incline vers elle à la puissance 4. Entre les deux, on vole à plat en puissance 3 ou 4 pour tenir l'altitude.
- Freiner en poussant contre la vitesseL'angle asin(hSpeed / |v|) en degrés oriente la poussée à l'opposé du mouvement : un angle positif pousse vers les x négatifs, donc un module qui va vers la droite reçoit un angle positif. Avec la puissance 4, c'est la façon la plus rapide de perdre de la vitesse.
- Planer pendant le déplacement latéralIncliné de θ à la puissance 4, le module a une poussée verticale de 4·cos θ. Avec θ = acos(3.711 / 4) ≈ 21,9°, elle compense exactement la gravité : le module se déplace latéralement à altitude constante au lieu de descendre.
- Approche finaleUne fois au-dessus de la zone avec des vitesses sûres, on passe à l'angle 0 avec juste assez de puissance pour garder la vitesse verticale sous 40 m/s. Près du sol, on force l'angle 0 pour que la limite de 15° par tour ne laisse pas le module incliné au contact.
Complexité
O(N) setup, O(1) per turnO(1)On ne conserve du relief que le segment d'atterrissage. Chaque tour se résume à quelques comparaisons et un appel trigonométrique.
Code de la solution
Mars Lander - Episode 2 – Java
Le module est encapsulé dans une classe MarsLander dotée de petites méthodes prédicats (isOverTarget, goesInWrongDirection, goesTooFastHorizontally...), si bien que la boucle principale se lit comme l'arbre de décision. Des marges de sécurité de 5 m/s sur les vitesses et de 20 m sur l'altitude absorbent le retard dû aux limites de rotation et de puissance.
import java.math.*;
import java.util.*;
class MarsLander {
private static final int Y_MARGIN = 20;
private static final int SPEED_MARGIN = 5;
private static final int MAX_DY = 40;
private static final int MAX_DX = 20;
private static final double GRAVITY = 3.711;
private int x, y, dx, dy, fuel, angle, power;
private int targetL, targetR, targetY;
public MarsLander() {}
public void init (int x, int y, int dx, int dy, int fuel, int angle, int power) {
this.x = x;
this.y = y;
this.dx = dx;
this.dy = dy;
this.fuel = fuel;
this.angle = angle;
this.power = power;
}
public void setTarget(int targetL, int targetR, int targetY) {
this.targetL = targetL;
this.targetR = targetR;
this.targetY = targetY;
}
public boolean isOverTarget() {
return targetL <= x && x <= targetR;
}
public boolean isFinishing() {
return y < targetY + Y_MARGIN;
}
public boolean hasSafeSpeed() {
return Math.abs(dx) <= MAX_DX - SPEED_MARGIN &&
Math.abs(dy) <= MAX_DY - SPEED_MARGIN;
}
public boolean goesInWrongDirection() {
return (x < targetL && dx < 0) || (targetR < x && dx > 0);
}
public boolean goesTooFastHorizontally() {
return Math.abs(dx) > 4*MAX_DX;
}
public boolean goesTooSlowHorizontally() {
return Math.abs(dx) < 2*MAX_DX;
}
/**
* returns the best angle to slow down marse lander
* (the angle directing thrust in the opposition direction to the mvmt)
*/
public int angleToSlow() {
double speed = Math.sqrt(dx*dx + dy*dy);
return (int) Math.toDegrees(Math.asin((double)dx / speed));
}
/**
* returns the exact angle to compensate gravity while
* going toward target
*/
public int angleToAimTarget() {
int angle = (int) Math.toDegrees(Math.acos(GRAVITY / 4.0));
if (x < targetL)
return -angle;
else if (targetR < x)
return angle;
else
return 0;
}
/**
* returns the thrust power needed to aim a null vertical speed
*/
public int powerToHover() {
return (dy >= 0) ? 3 : 4;
}
}
class Player {
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
MarsLander ship = new MarsLander();
int N = in.nextInt();
// Looking for the landing area
int landX, landY, prevX, prevY;
prevX = prevY = -1;
for (int i = 0; i < N; i++) {
landX = in.nextInt();
landY = in.nextInt();
if (landY == prevY) {
ship.setTarget(prevX, landX, landY);
} else {
prevX = landX;
prevY = landY;
}
}
for (;;) {
/* The flight follows 2 steps :
- first the rover goes over the landing zone by
-- slowing if it goes faster than 4*MAX_HS, or in the wrong direction
-- accelerating while hovering until it reaches 2*MAX_HS if it goes in the right direction
-- waiting hovering if it has a speed between 2*MAX_HS and 4*MAX_HS
- then it slows down to meet speed specification (going back
to step 1 if it goes out of the landing zone)
*/
ship.init(in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt());
if (!ship.isOverTarget()) {
if (ship.goesInWrongDirection() || ship.goesTooFastHorizontally())
System.out.println(ship.angleToSlow() + " 4");
else if (ship.goesTooSlowHorizontally())
System.out.println(ship.angleToAimTarget() + " 4");
else
System.out.println("0 " + ship.powerToHover());
}
else {
if (ship.isFinishing())
System.out.println("0 3");
else if (ship.hasSafeSpeed())
System.out.println("0 2");
else
System.out.println(ship.angleToSlow() + " 4");
}
}
}
}
Erreurs fréquentes
- Inverser le signe de l'angleDans Mars Lander, une rotation positive incline le module vers la gauche, donc la poussée s'exerce vers les x négatifs. Si le module accélère quand il devrait freiner, il suffit d'inverser le signe.
- Ignorer les limites par tourOn peut demander n'importe quelle valeur, mais le jeu ne bouge que de 15° et d'un niveau de puissance par tour. Un module qu'on fait passer de 60° à 0° au dernier moment se pose encore incliné : il faut planifier le redressement quelques tours avant le contact.
- S'incliner à la puissance 3 en déplacement4·cos θ doit rester au-dessus de 3,711 pour ne pas descendre. À la puissance 3, la moindre inclinaison fait perdre de l'altitude, ce qui écrase le module sur les tests avec relief élevé.
- Ne vérifier que la position horizontaleCertains tests placent des montagnes entre le départ et la zone. Descendre avant d'atteindre la partie plate mène droit dans le relief : on garde son altitude jusqu'à être au-dessus du segment.
- Division entière dans l'angle de freinagedx / speed en entiers vaut 0 la plupart du temps. Il faut convertir en double avant d'appeler asin.
Pour aller plus loin
Plutôt que de deviner les seuils, on peut raisonner en distance de freinage. À pleine puissance avec une inclinaison θ, la décélération horizontale vaut 4·sin θ m/s², au plus 4 m/s² à l'horizontale, mais alors on tombe, donc en pratique 2 à 3 m/s². S'arrêter depuis une vitesse horizontale h demande environ h² / (2a) mètres : à 60 m/s et 2,5 m/s², cela fait près de 720 m, ce qui explique pourquoi entrer dans une zone de 1000 m à plus de 60 m/s déborde souvent. Vérifier « distance au bord opposé > h² / (2a) + marge » avant d'engager la descente est plus robuste que des paliers de vitesse fixes, et c'est exactement le raisonnement qu'exige Mars Lander Episode 3, où la zone se rejoint à travers des grottes et où les seuils aveugles ne fonctionnent plus.
Questions fréquentes
Pourquoi 21 degrés dans Mars Lander ?
acos(3.711 / 4) ≈ 21,9° est la plus grande inclinaison à laquelle la pleine poussée compense encore la gravité : le module peut se déplacer latéralement sans perdre de hauteur. Arrondir à 21 conserve une petite marge vers le haut.
Faut-il un algorithme génétique pour l'Episode 2 ?
Non. Un contrôleur à base de règles comme celui-ci passe tous les tests. Les algorithmes génétiques deviennent intéressants dans l'Episode 3, où le relief est bien plus hostile.
Pourquoi mon module s'écrase-t-il avec de bonnes vitesses mais un angle non nul ?
L'angle doit valoir exactement 0 au contact, et il ne peut changer que de 15° par tour. Il faut demander 0° plusieurs tours avant d'atteindre le sol.