Don't Panic - Episode 2 - Puzzle discussion

Puzzles
#22

We have for “The Paranoid Android - One step further”

Output for one game turn
A single line (including newline character) to indicate which action to take:
Either the keyword WAIT to do nothing.
or the keyword BLOCK to block the leading clone.

It should be added to the rules:
or ELEVATOR!

7 Likes
#23

Hello, guys. I’ve managed to get to Test #7 and now I have a problem. Can anybody give me a hint about non-placed elevators? What is the most effective way to figure out the places where elevators should be built?

#24

sometimes you should build an elevator to avoid taking an existing one because that existing one might lead you to a path beyond the exit.

#25

I’m stuck on #4, I’ve been trying a Djikstra implementation, but I don’t seem to be able to figure out how to make the algorithm overwrite lower costs from previous paths that turn out to be impossible.
In the case of test #4, it would start by building an elevator right away when it shouldn’t, which causes my map to be filled with low values that can’t be overwritten by paths that are more expensive but actually possible …
Does anyone have any idea ?

#26

The “ELEVATOR” Action is missing in the action-summary.

3 Likes
#27

The validators seem identical to the tests but I seem to fail the last three validators even though I passed the matching tests.
Any idea what is happening?

Edit:
Found the difference - an empty floor was added up top.
It was very hard to spot and I wasted quite some time debugging thin air.
An output window for the validators would do wonders.

#28

Use the share replay of the validators and you will be able to use the output window.

3 Likes
#29

That’s a pro tip.
Thanks.

#30

Why do the number of turns on a given level change? E.g. on the giant map I used to pass with 109 turns, but now I only have 89… what determines the number of turn per given level?

#33

This puzzle gave me some hard time. I think it was for me most time spent on some puzzle so far (even I did few very hard ones). I tried multiple approaches (including GA) until I found something that worked so I would like to share some hints to help struggling.

I tried A* search algorithm at beginning but couldn’t find the way how to deal with missing elevators or how to include direction change in search. Then I switched to genetic algorithm where I fought how to represent solution how to quickly simulate it and how to evaluate fitness correctly. I learned a lot but found out that for problems that you can’t generate correct solutions, GA approach is not feasible. Because sometimes best solution was incorrect from the beginning and never reach the exit, though it had high fitness.

So I switched back to A* search and did some modifications and improvements and it passed all tests. Here is what I suggest:

  1. Analyse the grid and get rid of dead-end elevators and positions.
  2. Map the grid to A* model that will include direction. That way A* algo will consider different cost for direction change. So for one position there exists 2 nodes in A* model: one with left, one with right.
  3. Consider floors that must have elevator build into A* model. In such floors A* algorithm can move up freely otherwise only if there is elevator

With those points I was able use A* and find paths to exit and map it to commands on first round. The cons of this approach is that you must execute algorithm more times. One for approaching exit from right, one from left. And for some cases(if you must find floor with elevators where new optimized elevator needs to be build) it must be executed repeatedly until it finds solution that matches criteria. So really quick A* implementation is needed.

Hope it helps someone

12 Likes
#34

I’m passing the last test case while using ~350 ms on the first turn, but the constraint said max 100 ms? Is this a bug? I got 100%, but it feels like i cheated somehow…

#35

You typically get a lot more time on the first turn. “It’s not a bug, it’s a feature”.

#37

I finished with a simple BFS, and help from the general chat.

The factors defining a node in my BFS are:

  1. x-coordinate
  2. y-coordiante
  3. direction
  4. elevators_left
  5. clones_left
  6. time

A simple BFS with this technique (of course, without visiting already seen nodes) passed all test cases easily.

At each node, I try the following possibilities:

  1. Add a node in x + direction with: time+1
  2. Add a node in x - direction with: time + 3, clones_left - 1, direction = - direction
  3. Add a node in y+1 with: time + 3, clones_left - 1, elevators_left - 1
  4. And of course, if node is an elevator, bypass all these and simply increment y and time

Hope it helps someone :slight_smile:

11 Likes
#38

I’m wondering if you could help provide some tips on how you are optimizing/filtering your search.

I ended up with a BFS solution which sounds similar to yours with two different implementations. One is with a standard Queue and one is the same algorithm with a Priority_Queue sorted by distance to the exit. The Priority_Queue solves most of the problems in 0.5->2 milliseconds with a couple in the 10-15 ms range. But, it blows up exponentially on the last 3 tests and times out. I hard coded the Trap test on my PC and it doesn’t even come close to finishing in the 1 second limit for the first frame. The Queue implementation is a bit slower in all cases, but always finds the optimal path.

I can’t completely eliminate previously visited nodes since certain indirect paths are either optimal or certain direct paths end up running out of elevators or clones. However, I have pruned down unnecessary work as far as I can think of and I’ve moved pretty much all allocations and other “time wasters” out of the main loop.

Any tips are appreciated. Thanks!

1 Like
#39

My search prevents repeating rooms by a 5D boolean array (5 dimensions mentioned in my previous post), and also by disabling less - useful rooms (e.g. same time, but less elevators left). I actually slightly modified my BFS. I have an array of nodes, from 0 to maxTime. I add a node to the array, depending on the time when it is visited. This, I believe will slightly reduce number of nodes. Hope it helps :slight_smile:

1 Like
#40

Point me, please, why this condictions dont work:
if ((clone_floor != exit_floor) and (clone_floor == floor.index(clone_floor)) and (clone_pos > elevators[floor.index(clone_floor)]) and (direction == “RIGHT”)):
print(“BLOCK”)

elif ((clone_floor != exit_floor) and (clone_floor == floor.index(clone_floor)) and (clone_pos < elevators[floor.index(clone_floor)]) and (direction == “LEFT”)):
print(“BLOCK”)
I`m check, floor.index(clone_floor), elevators[floor.index{clone_floor)] are positions of elevators on floor where is clone.

#41

Have you taken into account of the new rule that a floor can now have more than one elevator or no elevator at all? You cannot compare a single clone_pos position against an array of multiple elevator positions.

#42

A* algorithm is doing well. TAN NETWORK puzzle is a good place to practice it if you are not familiar with the concept.

A few tips:

  • the algorithm should operate on four dimensions: x, y, number of extra elevator left (If extra elevator is build, you can treat this like entering the third dimension n-elevator deep) and direction of the bot
  • The cost of reaching the goal is the time to reach the goal. You need to remember that changing the direction of the bot is an additional cost of 3
  • You can assume that extra elevator can be build only under the exit, existing elevator or under other optional elevator

Great puzzle

4 Likes
#43

How to define where i must set additional lift? I try to define distance to near lift and if it more than preset distance than I set up additional lift. But it work only work 8 cases. For 9 and 10 it doesn’t work, because on every floor preset distance may be changes.

#44

Similarly, this line is wrong:

nbAdditionalElevators : not used for this first question, value is always 0