cup_of_tea (1st in rankings) and redvasily (2nd) have accepted to share their reviews for Kirk’s Quest with us. Thanks a lot guys and again, congratulations!
cup_of_tea‘s review:
My solution for the first problem is rather classical but valid, except that I included an unnecessary twist of complexity based on a wrong hypothesis.
Actually, I was naive enough to think that you faced a special case if when you fired on a mountain, it still remained the tallest one. But as only one shot was allowed by turn (back and forth), it became useless to focus on another mountain that did not have the tallest high during the same move.
My second solution is based on a simple heuristic:
During exploration, you should priorily look to unveil the nearest cells tagged with a question mark. This allows to have a moderate energy use to be able to explore the whole graph.
Second point, once you have located the control panel, you face two choices:
- either continue the exploration
- either activate the alarm and get back to the starting point
The first option should be favored when you are certain to have enough energy left to continue the exploration, and then to reach the control room and finally return to the starting point. This exploration allow you to be sure you identify the optimal path between the the control rool and the starting point, which does not necessarily correspond to the initial path.
Otherwise, if there are no zones left to explore or if your energy gauge is too low to make a detour, then the second option should be chosen.
To find the nearest points or the distance between two points, I have used a a classical breadth-first search algorithm with a queue, Dijkstra being not compulsory to use as all distances equal 1.
I was somewhat disturbed by this problem, because with the constraints that were stated, it was possible to face a graph that turned out to be impossible to fully explore with the given energy (so with chances to be unable to locate the control room or to go back even having found the shortest path), but final test cases did not use large numbers.
The challenge was interesting, but I would like the constraints to be more precise next time!
The heart of the solution is an algorithm that searches a shortest path from a given cell, to a cell that contains specified value (either ‘?’ or ‘C’). To find the shortest path I treated labyrinth as an implicitly defined graph where every cell is a vertex of a graph, all edges have length 1, and two vertexes are connected if they are on adjacent cells and they both can be walked through. After that I used a standard Dijkstra’s algorithm with some corners cut because of the nature of the problem. You can find it’s description here: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm , there’s even a nice animated gif giving a very good idea for how the algorithm works on a two dimensional map.
Perhaps I could’ve done something simpler, I think a standard breadth first search would’ve worked as well, and it’s easier to implement, but oh well.
Once I had this shortest path algorithm, the solution is easy.
My Kirk went through three phases:
– MAP
– CONTROL
– EXIT
In the map phases we check for a shortest path to any unknown cell ‘?’ while avoiding stepping on ‘C’ to avoid triggering alarm. Once there are no reachable ‘?’ elements – we have a full map, and switch to CONTROL phase.
In CONTROL phase Kirk simply follows the shortest path to ‘C’ cell, and once it’s reached switches to EXIT phase.
In EXIT phase Kirk simply follows the shortest path to the exit teleporter ‘T’.
The biggest catch in this problem is that you can’t switch to CONTROL phase before building a full map of the reachable part of the labyrinth, as it’s not guaranteed that by the time we discover control room ‘C’, we will have the shortest path between ‘T’ and ‘C’ discovered as well. It happened for me on test 5 I think, so I had to make some small changes to ensure that the whole map is explored before Kirk is sent to control room.
