Coding Solution

The Bridge - Episode 2 – solution CodinGame en Java

DifficileDFSbacktrackingsimulationgame tree searchMis à jour le
Réponse courte

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

  1. É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.
  2. É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.
  3. 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.
  4. 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.
  5. 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é

TempsO(5^d · M · S)
MémoireO(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

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.

Puzzles similaires

★ 5,0 · 16 avis · 928 utilisateurs Ajouter à Chrome