The Bridge - Episode 2 – solution CodinGame en Java
On simule les motos exactement comme le jeu et on lance un parcours en profondeur sur les commandes à chaque tour : on essaie SPEED, JUMP, UP, DOWN et SLOW, on élague tout état avec moins de V motos en vie, et on renvoie la première commande qui mène à un état au-delà de la fin de la route. On cherche d'abord une séquence qui sauve toutes les motos, puis on se rabat sur le minimum V.
L'énoncé
Un groupe de 1 à 4 motos roule sur un pont à quatre voies criblé de trous. Chaque tour, on envoie une commande commune à toutes les motos : SPEED, SLOW, JUMP, WAIT, UP ou DOWN. Une moto avance de la vitesse courante et est perdue si elle roule sur un trou, sauf si elle a sauté, auquel cas seule sa case d'arrivée compte.
On connaît tout le tracé du pont dès le début, puis chaque tour la vitesse et la position et l'état de chaque moto. Il faut amener au moins V motos au-delà de la fin de la route. Un changement de voie déplace la moto en diagonale : les cases devant elle sur l'ancienne voie et sur la nouvelle jusqu'à sa case d'arrivée doivent toutes être sans trou.
La démarche, étape par étape
- Écrire un simulateur exactOn code une fonction par commande qui prend un état (vitesse et positions des motos) et renvoie l'état suivant. La fidélité compte plus que la rapidité : une seule règle fausse sur les changements de voie pousse la recherche vers des coups fatals.
- Éliminer les commandes inutilesWAIT n'est jamais meilleur que JUMP à la même vitesse, car les deux atteignent la même case mais un saut ne vérifie que la case d'arrivée. SLOW jusqu'à la vitesse 0 est aussi inutile, donc le facteur de branchement est au plus 5.
- Parcours en profondeur avec élagageDepuis l'état courant, on essaie chaque commande récursivement. On abandonne une branche dès que moins de motos que la cible sont en vie, et on s'arrête dès qu'une moto dépasse la fin de la route : cette branche est gagnante.
- Bien ordonner les coupsEssayer SPEED en premier permet à la recherche d'atteindre la fin de la route en peu de tours et de trouver vite une séquence gagnante. UP, DOWN et SLOW sont rarement nécessaires : les tester en dernier garde l'arbre exploré petit.
- Privilégier le sauvetage de tout le mondeOn lance d'abord la recherche avec la cible M et on ne se rabat sur la cible V que si aucun coup ne sauve toutes les motos. On relance la recherche à chaque tour depuis l'état réel envoyé par l'arbitre plutôt que de rejouer un plan mémorisé.
Complexité
O(5^d · M · S)O(d · M)d est le nombre de tours explorés, M le nombre de motos et S la vitesse (cases vérifiées par coup). L'élagage des branches perdantes et la croissance rapide de la vitesse gardent d petit, si bien que la borne exponentielle est rarement approchée.
Code de la solution
The Bridge - Episode 2 – Java
Chaque commande est une petite sous-classe Action dont apply() renvoie null pour les coups impossibles ou sans intérêt (UP quand une moto est sur la voie 0, SLOW sous la vitesse 2). winningMove() est le DFS récursif et renvoie le nom de la première commande d'une séquence gagnante.
import java.util.*;
import java.io.*;
import java.math.*;
/** Class representing a motorbike. A motorbike has 3 properties :
* <ul>
* <li> Its X and Y coordinates on the road
* <li> A boolean A true if and only if the motorbike is activated
* </ul>
*/
class Moto {
int X;
int Y;
boolean A;
public Moto(int X, int Y, boolean A){
this.X = X;
this.Y = Y;
this.A = A;
}
public Moto(Moto m){
this.X = m.X;
this.Y = m.Y;
this.A = m.A;
}
}
/** This class represents a step of the run, ie the positions of the
* motorbikes, and their speed
*/
class State {
Moto[] motos;
int s;
public State(Moto[] motos, int s) {
this.motos = motos;
this.s = s;
}
public State(State s) {
this.motos = new Moto[s.motos.length];
for (int i = 0; i < s.motos.length; i++)
this.motos[i] = new Moto(s.motos[i]);
this.s = s.s;
}
}
class Player {
/* Returns true if there is a hole between the moto m
* and its next position on the lane
*/
static public boolean willFall (Moto m, int s, String lane){
// The area to examine go from the moto to
// either the end of the road, or the next position
for (int x = m.X+1; x <= Math.min(m.X+s, lane.length()-1); x++)
if (lane.charAt(x) == '0')
return true;
return false;
}
/* Put the moto on its next position
* or disactivates it if it is going to fall in a hole
*/
static public void move (Moto m, int s, String lane) {
if (willFall(m, s, lane))
m.A = false;
else
m.X += s;
}
/** This inner abstract class represents an action (slow, speed, etc).
* the name should be the string to print to perform this action.
* the function 'apply' applies the action to a state and returns the new state.
* it should also returns null if the action can't be performed, or will lead
* to a useless, or already encoutered state, for performance purposes
*/
static abstract class Action {
protected String name;
/** Applies the action to state 's' and returns the new state*/
abstract public State apply(State s);
}
static class SPEED extends Action {
public SPEED(){
this.name = "SPEED";
}
public State apply(State s){
State s2 = new State(s);
// increases speed by one, and moves each bike
s2.s++;
for (Moto m : s2.motos)
if (m.A)
move(m, s2.s, lanes[m.Y]);
return s2;
}
}
static class SLOW extends Action {
public SLOW(){
this.name = "SLOW";
}
public State apply(State s){
if (s.s < 2)
return null;
else {
State s2 = new State(s);
// decreases speed by one and moves each bike
s2.s--;
for (Moto m : s2.motos)
if (m.A)
move(m, s2.s, lanes[m.Y]);
return s2;
}
}
}
static class UP extends Action {
public UP(){
this.name = "UP";
}
public State apply(State s){
if (s.s == 0)
return null;
// if moving UP is not possible
for (Moto m : s.motos)
if (m.A && m.Y == 0)
return null;
State s2 = new State(s);
// for each bike, if there is a hole on the concerned area of the current lane
// disactives the bike, else, moves it up, and moves it forward
for (Moto m : s2.motos)
if (m.A)
if (willFall(m, s2.s-1, lanes[m.Y]))
m.A = false;
else {
m.Y--;
move(m, s2.s, lanes[m.Y]);
}
return s2;
}
}
static class DOWN extends Action {
public DOWN(){
this.name = "DOWN";
}
public State apply(State s){
if (s.s == 0)
return null;
// if moving DOWN isnt possible
for (Moto m : s.motos)
if (m.A && (m.Y == 3))
return null;
State s2 = new State(s);
// for each bike, if there is a hole on the concerned area of the current lane
// disactives the bike, else, moves it down, and moves it forward
for (int i = 0 ; i < s2.motos.length ; i++){
Moto m = s2.motos[i];
if (m.A)
if (willFall(m, s2.s-1, lanes[m.Y]))
m.A = false;
else
{
m.Y++;
move(m, s2.s, lanes[m.Y]);
}
}
return s2;
}
}
static class JUMP extends Action {
public JUMP(){
this.name = "JUMP";
}
public State apply(State s){
if (s.s == 0)
return null;
State s2 = new State(s);
// for each bike, if there is a hole at the landing spot, disactives it
// else, places it on the landing spot
for (Moto m : s2.motos)
if (m.A)
if (m.X+s2.s < lanes[m.Y].length() && lanes[m.Y].charAt(m.X+s2.s) == '0')
m.A = false;
else
m.X += s2.s;
return s2;
}
}
/** array of possible actions */
private static final Action[] instructions = { new SPEED(), new JUMP(),
new UP(), new DOWN(), new SLOW() };
/** lanes of the road*/
private static String lanes[] = new String[4];
/** If it is possible to win from state 's', this functions returns the
* string to print to do so. Else, it returns null.
* Winning means leading a minimum amount of 'min' bikes to the end */
public static String winningMove(State s, int min){
/* If the number of active motorbikes is 0, this state is lost, returns null
if the x of an active motorbike is greater than the length of the lane,
this state is won, returns "WAIT" */
int nbOfA = 0;
int x = 0;
for (Moto m : s.motos)
if (m.A) {
nbOfA++;
x = m.X;
}
if (nbOfA < min)
return null;
if (x >= lanes[0].length())
return "WAIT";
// tries each possible instruction, calling recursively winningMove
// on all the next states.
// If one of the calls returns a winning instruction, returns it,
// else returns null
for (Action a : instructions) {
State s2 = a.apply(s);
if (s2 != null && winningMove(s2, min) != null)
return a.name;
}
return null;
}
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
// amount of motorbikes, and minimum amount of survivors
int M = in.nextInt();
int V = in.nextInt();
in.nextLine();
// Initializes lanes of the road
for (int i = 0; i < 4; i++)
lanes[i] = in.nextLine();
int speed;
Moto[] motos = new Moto[M];
State s = null;
while(true){
// creates the current state
speed = in.nextInt();
in.nextLine();
for (int i = 0; i < M; i++) {
motos[i] = new Moto(in.nextInt(), in.nextInt(), (in.nextInt() == 1));
in.nextLine();
}
s = new State(motos, speed);
/* Search for a move saving all the bikes (for the 3rd achievement)
and if it is not possible, for a move saving the minimum amount of bikes*/
String str = winningMove(s, M);
if (str != null)
System.out.println(str);
else
System.out.println(winningMove(s, V));
}
}
}
Erreurs fréquentes
- Ne vérifier les trous que sur la case d'arrivéeHors d'un JUMP, chaque case entre l'ancienne et la nouvelle position compte. L'oublier fait croire au simulateur que des motos survivent alors que l'arbitre les détruit.
- Mauvaise règle de changement de voiePour UP et DOWN, la moto vérifie sa voie actuelle sur les cases avant sa colonne d'arrivée, puis la nouvelle voie jusqu'à la case d'arrivée incluse. Ne vérifier que la nouvelle voie est le bug de simulation le plus fréquent.
- Changement de voie au bordUP depuis la voie 0 ou DOWN depuis la voie 3 ne peut pas déplacer tout le groupe. Ce code traite simplement une telle commande comme indisponible, ce qui évite de modéliser un cas limite de travers ; quel que soit votre choix, le simulateur doit reproduire ce que fait réellement l'arbitre.
- Vitesse 0À vitesse 0, rien ne bouge : JUMP, UP et DOWN n'ont aucun effet et la recherche peut boucler. Il faut interdire SLOW quand la vitesse vaut 1 et toujours gérer le début de partie où la vitesse est 0.
Pour aller plus loin
Le DFS brut a un point faible : quand sauver toutes les motos est impossible, la première recherche avec la cible M doit épuiser tout l'arbre avant de se rabattre sur V, et c'est là que le temps peut exploser sur les longs ponts. Deux corrections peu coûteuses aident. D'abord, mémoriser les états perdants : la clé (vitesse, x du groupe, voies des motos vivantes) décrit entièrement l'avenir, donc un ensemble de clés perdantes déjà visitées empêche la recherche de réexplorer des situations identiques atteintes par des ordres de commandes différents. Ensuite, plafonner la vitesse : une vitesse supérieure à la longueur restante du pont n'est jamais utile, donc SPEED peut être élagué au-delà. Avec cela, même un ordre de coups naïf n'explore que quelques milliers d'états par tour.
Questions fréquentes
Pourquoi WAIT n'est-il jamais nécessaire ?
JUMP à la même vitesse arrive sur la même case et n'exige que la sûreté de cette case, alors que WAIT exige que toutes les cases du trajet soient sûres. JUMP est toujours au moins aussi bon.
Faut-il calculer tout le plan une fois au départ ?
C'est possible, mais recalculer depuis l'état envoyé par l'arbitre à chaque tour est plus sûr : si votre simulateur diffère légèrement du vrai jeu, vous vous rattrapez au lieu de suivre un plan cassé.
BFS vaut-il mieux que DFS ici ?
BFS trouve la séquence gagnante la plus courte mais garde des niveaux entiers de l'arbre en mémoire. Toute séquence gagnante est acceptée, donc un DFS avec un bon ordre de coups est plus simple et plus rapide.