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