Don't Panic - Episode 2 - Puzzle discussion


#1

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


#2

I was wondering if, as in the above image, it was possible to send the robots in two different directions? And if possible: how?


#4

No it’s not possible, it’s just a key art :smile: Some clones are also closer to each other than they should be and first floor is missing its left “wall”.


#5

oh right! I should have noticed, thanks for the info :slight_smile:


#6

Got an issue with this - I am loosing by 1 turn - leading clone is on the elevator below exit at the last turn.

I think I use best path - first leading clone is blocked at the dispenser exit (BLOCK in first game turn), so each next clone go left to “elevator shaft”. Clones are blocked after elevator so the direction of next clones change and they enter next elevator up to 8th floor. On 8th floor leading clone is not blocked and proceeds to elevator on 9. When it reaches it I loose.
My commands are:
BLOCK
WAITx6
BLOCK
WAITx4
BLOCK
WAITx4
BLOCK
WAITx4
BLOCK
WAITx4
BLOCK
WAITx4
BLOCK
WAITx4
BLOCK
WAITx9
Is it not the best path?


#7

No it’s not. Remember a block makes you lose 3 turns so even if a path is longer (distance wise), you could reach the exit faster (turns wise) if it needs less blocks :wink:


#8

Or you can consider distance as actual distance + block * 3 to complete NewboO answer


#9

There is an error in the problem situation.

In the last tenth test nbTotalClones = 99 or 100, what led me to 10 minutes of debugging because I have used max values to fill my array.


#10

I saw a comment below about failing one of the tests by 1 move and I have a similar problem. Although in my case it looks like the test in question is different.

So, I just wanted to make sure - is the “Trap” test accurate? My solution uses the path on the right and frankly I struggle to find a better path by looking at the map. Same thing is true for the “Few Drones” test, but I’m off by more than 1 move there.

Please let me know if tests are OK and it’s just me.


#11

I just checked the validation again and everything works fine for me. About “trap” test, the path on the right isn’t the right choice.


#12

Can you give a hint on what algorithm to use? Graph search or dynamic programming?


#13

Graph search is enough. I used depth-first search during the contest but it’s best to do a breadth-first search.


#14

did you get 100% with graph search? both bfs/dfs time-out with python for me. i may need to optimize a bit but it fails on maybe problem 5-6 because of speed. i made some effort to do it with c++ but i guess if graph times out in python there must be a better way.


#15

Yes I got 100% with dfs in PHP so I guess it should be possible in Python too though I needed some good heuristics and optimization tricks to pass bigger tests.


#16

I’m having a lot of trouble determining a good Heuristic for this puzzle. I can solve all tests (including the large map “Few Clones” test), but not the “Giant Map” test. Looking at my execution time, the difference between Few Clones and Giant Map is huge despite the map sizes being comparable. So it must have to do with my Heuristic.

I’m using A* with a precalculated H value. My current almost-successful heuristic is 3dY + dX (dY and dX are X,Y distances from N to Exit), and it ignores direction. I just can’t find an efficient way to take into account pre-existing elevators and direction, so I assume on average it costs 3 turns to go up a floor compared to 1 turn to go left/right (despite it actually taking 4 if you’re building an elevator).

I’m doing this in Perl with Hashes (somewhat efficiently), but I truly think my heuristic is causing far more performance lag than code efficiency.

Any hints?


#17

I have a problem with this puzzle: i submitted my halfway done solution and next time i opened it I realized that no tests are passed. It turned out that init input #7 (number of elevators present) is zero all the time which seems invalid to me. Anyone experienced the same recently?


#18

Hi. I read some of you used graph search to solve this. How did you represent the map as a graph? How did you manage the possibility of building elevators?


#19

This is a late reply, but I think it is actually possible to send the robots in two directions, at least temporarily. Say the clones started on the far left, a block was created on the far right, and then an elevator built near the left but to the right of where they started. If enough space was between the block and the new elevator, there should be some clones caught in that space that would approach the elevator from the right and the rest would approach from the left. Thus some of them should go in a different direction when they get to the top of the elevator. I haven’t tested it, but it seems like it should work.

In the diagram below, S is start, B is the block, E is the new elevator created after the block. < and > are clones travelling to the left or right respectively.

  0 1 2 3 4 5 6 7 8 9
1 _ _ < _ > _ _ _ _ _
0 S _ > E < _ _ < > B

#20

Just solved it in C# (my first hard difficulty puzzle), it was quite challenging.

I did a DFS but I needed a lot of optimizations to pass the last three tests without timeouting. Funny I’ve actually thought about implementing an heuristic but actually just needed to switch the order of my DFS to pass.


#21

Finally, all tests passed with Java ! Quite challenging. I spend several nights to make all of them green.

The most difficult part is to prepare the right elevator graph.