The Bridge - Episode 2 - Puzzle discussion

Puzzles
#1

Feel free to send your feedback or ask some help here!

fileservlet?id=1255458512928856×430
1 Like
#2

Test 8 doesn’t require any sacrifice, despite what is written.

#3

There seems to be an error in the Java version. Appears if tested, before changing anything. C# code works that way, so Java should also work.

“Exception in thread “main” java.util.InputMismatchException
at java.util.Scanner.throwFor on line 909
at java.util.Scanner.next on line 1530
at java.util.Scanner.nextInt on line 2160
at java.util.Scanner.nextInt on line 2119
at Player.main on line 22”

#4

If you submit a code for this problem then come back to this puzzle, now when you switch language and come back to java, the code generated automatically will be correct (copy paste your code somewhere if you already made modifications you want to conserve).
The way we get data for this language was wrong, that’s why you got this error.

#5

Congrats and thanks to the codingame team for this nice site ! I’m having a lot of fun playing with the puzzles :wink:

Here are a few minor notes for this one :

  • tests 3 and 4 need one additional move after the road end
  • test 7 also asks for a move if the bikes are at the very end
  • and agree with ElderBug, the sacrifice is actually not mandatory for test 8

I also noticed that steering up/down at speed 0 is accepted and makes the bikes slide. Not sure whether it’s a wanted behavior though.

#6

I just noticed that it is possible to move up or down between holes, as in step 8/9 of the replay below

This seems consistent with the puzzle statement, but looks weird all the same :slight_smile:

#7

Found a little bug in the challenge details ( before clicking to solve it ) :

This easy puzzle is the first of a series of two proposed during the past contest “Skynet Revolution”.

It should be “This diificult puzzle” and also later in the details text it references “the second puzzle Skynet - The Bridge” while the second puzzle is actually this one.

Not important matter but should be notified ^^

#8

Salut tout le monde. J’ai mis le temps sur celui-lĂ , et en fait, je ne sais toujours pas pourquoi ça a marchĂ©. 100% avec tous les points. J’ai un peu bidouillĂ© l’ordre d’exploration des branches, exploration limitĂ©e Ă  une profondeur de 3. Avec une profondeur de 2, le rĂ©sultat est de 79%, ce qui est normal, mais par contre, si j’augmente la profondeur, je descends en dessous de 50%, et pas Ă  cause du time out. Les motos deviennent bĂȘtes, tombent tout droit dans les trous ou alors ralentissent avant de sauter un long prĂ©cipice. Le pire, c’est que sur un test, une des motos fait tout le parcours en zigzag, passe tous les trous, et tout et tout, et au dernier saut, elle s’arrĂȘte avant le trou et ne bouge plus
(en Ă©crivant cette phrase, ça me fait penser Ă  qq chose genre la limite de la piste
) Bref, il doit y avoir un (ou des) gros bug(s) dans mes choix
 Ou bien alors, c’est une trop bonne IA qui a beaucoup d’humour. Mais bon, c’était mon premier backtracking, et dĂ©jĂ  ça marche, alors, je vais me faire la main sur les exos suivants, et je reviendrai plus tard pour comprendre ce qui se passe
 A+ et fĂ©licitations Ă  l’équipe CG !!!

1 Like
#9

Passed with backtracking. But it’s more of a bruteforce because performance is not really a concern. You only need to plan 3 turns ahead to pass all. If I may give a tip: Make your representation of the bridge longer by like 10 squares, fill with non-holes, this will save you headaches cause the map they give you is kinda smaller than the actual bridge, just extend with non-holes.

2 Likes
#10

Your advice about the 10 extra cells is very useful and avoided me the headache ! Thank you :wink:

#11

I am trying to simulate every case with every motorbike. So I have a root node with the initial state, then 6 child nodes each with one different command. I have a function I called explore that propagates the game state from one node to its children, checks all bikes movements, then if the remaining bikes number falls under the threshold, it deletes the node.

I would like to ask if that can be a strategy to solve it, and also, I would need help on how to simulate

If I output now “JUMP”, does the bike start its jump from the current cell or from the next cell ? If I output “SPEED”, does the x add SPEED amount starting from the current cell or from the next cell ? I am confused


Please help, thank you :slight_smile:

#12

Although this answer comes late, it might help other people as well.
Yes, a strategy as you mentioned will solve the puzzle. I used a heap queue, but as the search space is small, any queue or stack should work.
SPEED will first add one to the current speed and then perform the movement.
JUMP will jump from the current cell. A bike at position 3 and speed 4 will ignore the fields 4, 5, and 6 (landing at 7)

1 Like
#13

Another small tip: You don’t even have to consider WAIT as you can replace WAIT with JUMP and the outcome will be the same
 and it looks amusing too. If you are doing a recursive depth limited search then this will reduce the width of the tree.

5 Likes
#14

I agree with Agade, but because I was searching 4 moves ahead I needed to extend the road by more than 10 (test 7 kept failing so I upped the extra road to 30 more spaces and then it worked fine).

Another tip that took me ages to debug
 I was reading the bikes X from the X value of the first bike, which is fine as long as that bike is alive, after that the X value stays at the square where the bike died. So either keep track of the current X value of the living bikes in your own variable, or else read the bike data in but filter out the dead bikes before reading the X value.

4 Likes
#15

Thanks for the tip! My solution passed every test in IDE but when I submited it, it failed on the last test. Then I excluded WAIT option and my code finally passed all the tests even after being submitted.

#16

It seems that 150ms limit is way too generous. My code in C calculated several DFS instances for possible combinations of bike sacrifices to the ‘bike safe’ point in total for less than in 0.1ms time. Building the action graph took about 0.3ms. I used ‘clock()’ function for time measurement.

#17

sir?? did someone here use c language in the bridge?? i need help in this game in my assignment

1 Like
#18

I finally managed the 100 %. I basically did backtracking for every single bike. For each bike i took the result and tested the rest of the bikes to see if they would survive. Then i picked the solution with least casualties.

Make sure that when you backtrack that you update the bikes x and y coordinates.

Great puzzle.

#19

great, i managed to pass this with 100%. so basically all i did was pass this with a backtracking algo for all bikes, which means calculate all possiblities in the future right at starting position, store all future values in a vector, then spend it each loop.

#20

Or just add handling for being beyond the map to your checks of the bridge. You also need something like this for some of the tests that require you to move beyond the map, which was the only time I ever sent wait action.

I used a DFS with a priority queue that prioritized distance over number of remaining motorcycles. It searched until the end of the map and wouldn’t have played well with padding.