The Bridge - Episode 2 - Puzzle discussion


#21

I finished this puzzle with Dynamic Programming. It gives best plan (save most bike with minimal time) at 1st turn, and do no calculation in latter turns.

just a hint


#22

Just started this puzzle, but for some reason the first test keeps saying “mission failed” even though the motorbike doesn’t fall in the hole:

No matter whether I jump over it, or move up or down to avoid the hole, I keep getting “mission failed”. This is already within 10 turns, i.e. well within the allowde maximum of 50 turns.

WTF?


#24

Jace_TBL: Before the last turn, which lane was your motorbike on, what were its position and speed, and what action did you output?

I kept my motorbike in the third lane (lane index 2) all through test case 1. When I reached #10, my speed was 4, I jumped to #14 and did not fall into the hole.


#25

You did not provide any output in the last turn, so your code times out.


#26

Used simple brute force with a cutoff to solve this.
The amount of distinct states in this game is quite small: 500 (positions) * 50 (speeds) * 16 (bike configurations) = 400k.

So you can simply generate all possible states using a queue of candidate states and a set of visited states, like you do in BFS algorithms. Cutoff: abandon states if they have less than V bikes alive. Once you found a state that brings V or more bikes over the finish line, backtrack to print the solution.

This could be optimized a lot by expanding most promising states first (like in A* algorithm; this would require using a PriorityQueue to store states, with state.X as a key and sorted in reverse, so it would expand states closest to the finish line first).

UPD: actually implemented this optimization by simply changing ArrayQueue to PriorityQueue. The amount of states it enumerates to find a solution dropped A LOT (from 539 to 37 in the last test case).


#27

Really nice puzzle, it was fun solving it. I managed to solve it during the first turn using DFS in C++. Filling a vector of commands:

void dfs(vec commands) {
      simulate(commands);
      for each c in commands {
           newCommands = commands + c;
           dfs(newCommands);
      }
}

And each time the recursion function is invoked I reset the game to its initial state and simulate the commands form the vector one by one:

void simulate(vec commands) {
      resetToInitialState();
      for each c in commands {
           movebikes( c );
      }
}

I’m not sure if it is nice design, but it solved all test cases in several milliseconds each.


#28

Currently solving this puzzle in Java using simulation.

EDIT: Finally found the issue. There was an edge case when determining which game states to prioritize.

I pass all the test cases fine, but I’m getting strange results for the last validator.
Here are the replays:

Test: https://www.codingame.com/share-replay/405635268
Validator: https://www.codingame.com/share-replay/405634977

For some reason, it’s not making the necessary DOWN action on frame 7 (validator).
This corresponds to the UP action it performs in the corresponding test case.
I can tell it does consider the DOWN action from the 10th test case (obstacle course for 2 bikes): https://www.codingame.com/share-replay/405635664

Without access to the console, I can’t see my debug output to determine the source of the problem. My only lead is a warning that it could not find a winning state in time on the test case, defaulting to the farthest the bike made it. I suspect the same thing happened in the validator, but the farthest point was a loosing move.

Any tips?

Edit: on closer inspection, my simulation appears to fail for the test case version, it just so happens that the default action (WAIT) is the correct response. I guess I now have a lead.