The Bridge - Episode 2 - Puzzle discussion

Puzzles
#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).

1 Like
#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.

2 Likes
#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

1 Like
#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

4 Likes
#34

Very frustrating having 100% pass in code IDE but not in Commit processā€¦
it is a timeout problem.
Could you publish an info to help us know if we need to rewrite or optimize when timeout occurs ?

#35

I was curious about that, since i got 100% without wait. Here is a level like you described it, that is not possible if wait is not an option:

2
1
.0.0ā€¦0
0000000
00000ā€¦
ā€¦0ā€¦0
2
0 0 1
0 3 1

The solution for the level above is ā€œWAITā€, ā€œJUMPā€, ā€œUPā€.

1 Like
#36

I tried DFS and BFS, i calculate the whole response during the first tour, but each time, it takes wayt too much time for the 12th testā€¦

#37

OMG, thanks so much. I did the opposite, always set X value from any bike, thus if last bike was deadā€¦
It took me ages to find my bug, as all tests pass, except the last two from the validation set.

#38

I had the same problem. Validation test 12 not finding a way. This comment helped me out. I donā€™t have any logic for determining the priority, but after changing the fixed priority I was able to make the IDE test 12 also fail to find a way. This made me realize that my nodes are not unique enough. Some nodes were skipped which werenā€™t actually processed before. Thanks for the push!

Aside from this, it would be nice if the description of the puzzle mentioned (or maybe it is a bug in the referee) that it is not enough to just cross the bridge. The motor has to end at least after the bridge and one more cell.
For example:
ā€¦ (Edit: There are 30 points here in editor, only when posted it is only 3, believe me)
This line above is the bridge. 30 points. The x indexes of the bridge go from 0 to 29. If the motor ends on x=30 after the last command, the game does not end. It only ends if x is 31 or more.

I saw a comment above about filling the end of the paths with 10 more points. No need for 10, 1 is enough.

#39

Hey, I have passed all validators on the IDE but failed the 2 lasts on the submit,
The thing is that I have no clues about what happened, I canā€™t import submits games, and I canā€™t make any custom game, any idea ?

#40

you have clues ā€¦
look better and youā€™ll see that in results there are replays for each validators (the real validators , in IDE there are only tests)

at worst custom games can be made on your computer to fix

#41

I saw that but itā€™s not helping without having my debug on it, normally I just import the play into the IDE to see what happened but there I canā€™t reproduceā€¦