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.


#29

Hello,

I think my script has an error somewhere but I can’t find where…
The test 12 running very well and others too.
But on the validator 12, the motorBike seems to do not see hole.
My motorBike is going up first to avoid the first holes and then it does speeds and jumping.

I tried many things, but I do not see any error in my code.
In the TEST 12, I printed all possible ways and any of them indicates the speed action or jump action.

Can someone help me ?


#30

For me, that validator exposed an edge case in my simulation that caused me to not find any valid states. Triple-check your code, I’m almost certain there’s an edge case somewhere.


#31

No There is an error in the validator.

I resolve the issue by returning the X position, Speed and Y position with my script and it works fine.

I think the results return by the validator are not good in validator 12


#32

You’d think one of the 1.8k people who solved it already would have complained.

Looks fine to me


#33

I think I can conceive of a test case where WAIT is useful where JUMP isn’t. Consider the case where there are 2 bikes, one on the topmost and one on the bottommost lane, and you must sacrifice the top one to make the UP command work, otherwise the upcoming holes will kill both.

Another wrinkle you might or might not encounter depending on how you’ve sequenced/prioritized the moves, is how UP/DOWN work when speed = 0