The Bridge - Episode 2 – CodinGame solution in Java
Simulate the motorbikes exactly as the game does and run a depth-first search over the commands each turn: try SPEED, JUMP, UP, DOWN and SLOW, prune any state with fewer than V bikes alive, and output the first command that leads to a state past the end of the road. Search first for a line that saves all bikes, then fall back to the minimum V.
The problem
A group of 1 to 4 motorbikes rides on a four-lane bridge full of holes. Every turn you send one command shared by all bikes: SPEED, SLOW, JUMP, WAIT, UP or DOWN. A bike moves forward by the current speed and is lost if it rides over a hole, unless it jumped, in which case only its landing cell matters.
You know the full bridge layout from the start, plus each turn the speed and every bike's position and status. You must bring at least V bikes past the end of the road. Changing lanes moves a bike diagonally: the cells in front of it on the old lane and on the new lane up to its landing cell both have to be free of holes.
Approach, step by step
- Write an exact simulatorEncode one function per command that takes a state (speed and bike positions) and returns the next state. Accuracy matters more than speed here: a single wrong rule on lane changes makes the search choose fatal moves.
- Drop useless commandsWAIT is never better than JUMP at the same speed, because both reach the same cell but a jump only checks the landing cell. SLOW to speed 0 is also useless, so the branching factor is at most 5.
- Search depth-first with pruningFrom the current state, try each command recursively. Abandon a branch as soon as fewer than the target number of bikes are alive, and stop as soon as one bike passes the end of the road: that branch is a win.
- Order the moves wellTrying SPEED first means the search reaches the end of the road in few turns and finds a winning line quickly. UP, DOWN and SLOW are rarely needed, so testing them last keeps the explored tree small.
- Prefer saving everybodyRun the search with target M first and only fall back to target V if no move saves all bikes. Re-run the search every turn from the real state sent by the referee instead of replaying a stored plan.
Complexity
O(5^d · M · S)O(d · M)d is the number of turns explored, M the number of bikes and S the speed (cells checked per move). Pruning dead branches and the fact that speed grows quickly keep d small, so the exponential bound is rarely approached.
Solution code
The Bridge - Episode 2 – Java
Each command is a small Action subclass whose apply() returns null for impossible or pointless moves (UP when a bike is on lane 0, SLOW below speed 2). winningMove() is the recursive DFS and returns the name of the first command on a winning line.
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));
}
}
}
Common mistakes
- Checking holes only on the landing cellOutside a JUMP, every cell between the old and new position counts. Forgetting this lets the simulator believe bikes survive while the referee destroys them.
- Wrong lane-change ruleFor UP and DOWN, the bike checks its current lane for the cells before its landing column, then the new lane up to and including the landing cell. Checking only the new lane is the most common simulation bug.
- Lane changes at the edgeUP from lane 0 or DOWN from lane 3 cannot move the whole group. This code simply treats such a command as unavailable, which avoids modelling an edge case wrongly; whatever you choose, your simulator must match what the referee really does.
- Speed 0At speed 0 nothing moves, so JUMP, UP and DOWN achieve nothing and the search could loop. Forbid SLOW when the speed is 1 and always handle the start-of-game case where the speed is 0.
Going further
The plain DFS has one weak spot: when saving every bike is impossible, the first search with target M must exhaust the whole tree before falling back to V, and that is where time can explode on long bridges. Two cheap fixes help. First, memoise failed states: the key (speed, x of the group, lanes of the alive bikes) fully describes the future, so a visited set of losing keys stops the search from re-exploring identical situations reached through different command orders. Second, cap the speed: a speed larger than the remaining length of the bridge is never needed, so SPEED can be pruned beyond it. With these, even a naive move order explores only a few thousand states per turn.
FAQ
Why is WAIT never needed?
JUMP at the same speed lands on the same cell and only requires that cell to be safe, while WAIT requires every cell on the way to be safe. JUMP is always at least as good.
Should I compute the whole plan once at the start?
You can, but recomputing from the state the referee sends each turn is safer: if your simulator differs slightly from the real game, you recover instead of following a broken plan.
Is BFS better than DFS here?
BFS finds the shortest winning sequence but stores whole levels of the tree in memory. Any winning line is accepted, so DFS with good move ordering is simpler and faster.