CodinGame

 

CodinGame Results

There was another coding contest today. I did a little better than last time. This time I came in at #231. Better, but I still didn't manage to pass all the tests.
    The problem involves stopping a tribble from escaping. We have a maze with multiple exits. You can block as many exits as you want, but while you are doing that the tribble is on the move, so you need to figure out which exits are closer and close them first. The tribble is naturally psychic and so knows the quickest route to any and all of the exits.
    For the first set of tests this was sufficient. With the second set of trials things got a little dicier. Seems there are spots in the maze that have two exits, so if the tribble manages to get to one of these spots, you lose. You can block one of the exits, but while you are doing that the tribble has gotten out the other one, so you need to keep the tribble from getting to one of these spots, which means looking ahead.
    It took me a while to recognize what the problem was, and a while longer to come up with a plan to handle it, and by that time I was out of time.
    My general plan was to:

1. Count the number of exits attached to each point. It might be zero, one, two, or more.
2. Maintain my original plan: see if there are any exits adjacent to the tribble's current position and if so block it. If there is more than one exit, give up. You've already lost.
3. If we are safe for the moment we need to look ahead. Starting from the tribble's current location, go to each of the adjacent locations and see how many exits they connect to. If you have one that has more than one, then you need to block the tribble from getting to that point.

I think that would probably have been sufficient for this contest. The problem could be made much worse by having multiple paths to points that lead to multiple exits. On one hand it's kind of tempting to try out each and every path through the maze to see which ones you might need to block and which ones you can ignore, but for even a medium size maze that approach could quickly consume all of your resources.
    So I'm thinking you need to cast a gradually widening net. Since we have already counted the number of exits at each point, we know how far afield we have to go. If there is only one exit, then we only need to look at adjacent points. That was the situation in the first test. If the maximum number of exits is two, then you only need to look at your adjacent locations. If the maximum is higher, than you will need to search farther. A list of locations you have visited could prevent you from going in circles. Simply clear it at the start of each search, and mark off each node as you visit it. Recursion might be the answer if going farther than two links away.