How to unlock all the chests in the treasure trove?

Question

Heard the following problem in Google Code Jam. The competition has ended now, so it's okay to talk about it https://code.google.com/codejam/contest/2270488/dashboard#s=p3

Following an old map, you have stumbled upon the Dread Pirate Larry's secret treasure trove!

The treasure trove consists of N locked chests, each of which can only be opened by a key of a specific type. Furthermore, once a key is used to open a chest, it can never be used again. Inside every chest, you will of course find lots of treasure, and you might also find one or more keys that you can use to open other chests. A chest may contain multiple keys of the same type, and you may hold any number of keys.

You already have at least one key and your map says what other keys can be found inside the various chests. With all this information, can you figure out how to unlock all the chests?

If there are multiple ways of opening all the chests, choose the "lexicographically smallest" way.

For the competition there were two datasets, a small dataset with troves of at most 20 chests, and a large dataset with troves as big as 200 chests.

My backtracking branch-and-bound algorithm was only fast enough to solve the small dataset. What's a faster algorithm?

Answer 1

I'm not used to algorithm competitions. I was a bit disturbed about this question: to cut branches in the branch & bound general algorithm, you need to have an idea of the general input you'll have.

Basically, i looked at some of the inputs that were provided in the small set. What happen in this set is that you end up in paths where you can't get any key of some type t: all the remaining keys of this type t are all in chests which have a lock of the same type t. So you are not able to access them anymore.

So you could build the following cut criterion: if there is some chest of type t to be opened, if all remaining keys of types t are in those chests and if you don't have anymore key of this type, then you won't find a solution in this branch.

You can generalize the cut criterion. Consider a graph, where vertices are key types and there is an edge between t1 and t2 if there are still some closed chest in t1 which have a key of type t2. If you have some key of type t1, then you can open one of the chests of this type and then get at least a key to one of the chests accessible from the outgoing edges. If you follow a path, then you know you can open at least one chest of each lock type in this path. But if there is no path to a vertex, you know there is no way you will open a chest represented by this vertex.

There is the cuting algorithm. Compute all reachable vertices from the set of vertices you have a key in your posession. If there are unreachable vertices for which there are still closed chest, then you cut the branch. (This means you backtrack)

This was enough to solve the large set. But i had to add the first condition you wrote:

if any(required > keys_across_universe):
    return False

Otherwise, it wouldn't work. This means that my solution is weak when the number of keys is very close to the number of chests.

This cut condition is not cheap. It can actually cost O(N²). But it cut so much branches that it is definetely worth it... provided the data sets are nice. (fair ?)