We held the online qualification round for the Realtime Worlds Student Programming Contest last night. I’ll post separately about my experience of organising it, but for now wanted to give some analysis of the questions. For those who didn’t take part, there were 3 questions: Zombies (15 points), Concurrency (20 points) and Dungeons (65 points).
This was intended to be the easiest of the 3 questions. The question statement was a bit of a mouthful, making you work a little to see the point of the question – which is, essentially, the question of mating rabbits that led to the naming of the Fibonacci numbers. When I was at university, we had the great fortune of being supervised for one course by Tim Gowers. Now Professor Gowers is essentially the cleverest person you could ever meet; being taught by him was an incredibly humbling experience. He was a dreamy kind of genius, always wandering off the course content into places I couldn’t follow. I’m not sure I learned that much from him, except the fact that there are people several orders of magnitude smarter than I am :) Anyway, one day, there arose some kind of connection to the Fibonacci numbers, and my friend Mark mentioned the rabbits. “Rabbits?” said Professor Gowers, startled out of a higher plane of thought. Mark had to explain the rabbit problem and watched as Gowers thought about them dreamily, an almost child-like smile spreading across his face. It’s not often you get to teach something new to a genius!
So, if you haven’t heard of the rabbits problem, you’re in good company.
This was also intended to be pretty simple, although we suspected it was fractionally harder than Zombies, and the scores on the day bore that suspicion out. The question was designed around one very simple idea: we wanted a question that involved sorting a data set, because there aren’t many more fundamental topics in algorithms. So the idea is to sort all the log entries by time, giving a timeline of log-in and log-out events in the game. This is why we needed all the back-story about multiple servers – because you’d expect a single server log to be sorted by time already. Imagine the game’s a nightclub and you’re the bouncer. The sorted log events give you a continuous sequence of people joining and leaving. Just traverse that list of events, adding one for everyone that enters, and subtracting one for everyone that leaves – and you’re keeping track of the total number of people inside (the concurrency of the game). Going from there to the maximum is simple, provided you deal carefully with people leaving and arriving at the same time.
Now this was the monster question. Unlike the other questions, where we kind of started with the solution and worked backwards to design a question, this one just started with an interesting problem, that we didn’t know the solution to. As we got closer to the contest and had extra people proof-reading it, trying to solve it themselves, and producing test data, it gradually dawned on us that it was harder than we’d intended, but it was really too late to come up with anything else. The line of zeroes in the score column proved us right.
There are two key insights for me. Firstly, that players get stuck not so much by exploring the dungeon, but by wasting keys going nowhere new: the worst case scenario is where a player constantly uses their keys opening doors to rooms they already have access to, before they go anywhere new. Secondly, I find it helpful to think not in terms of paths through the dungeon (and algorithms that search possible paths), but sets of rooms.
So here’s my solution. Given a set of rooms S, assuming the player can reach them, they can get stuck in that set if the number of doors interconnecting rooms of S is greater than or equal to the total number of keys gained in the rooms of S. Now consider a graph, where a vertex represents a subset of the rooms – say, S(v) is the set of rooms represented by vertex v. In the largest dungeon with 20 rooms, the graph has 2^20 vertices, and a simple, practical way to represent them is just as bitsets stored as integers, with the ith bit representing the presence or absence of room i in the set. Let f(S) be the number of doors interconnecting rooms in S, minus the sum of the keys found in S. So you can get stuck in a set S if f(S) <= 0.
Now let’s put some edges into the graph. For two vertices u, v, we have an edge from u to v if and only if S(v) is S(u) plus a single extra room, r, and if there is at least one door from S(u) to r. Putting it all together, we can now search the graph (either breadth or depth first – not sure it matters much), starting with the vertex representing a single-room set, the starting room. Because of the way we’ve defined the edges, this search only reaches sets of rooms that are reachable by the player. And computing f(S) as we go is simple – for the starting room, f is just the number of keys in that room. When we traverse an edge u-v, we compute f incrementally – adding the number of keys found in the new room r, and subtracting the number of doors from S(u) to r. This search can terminate in a number of ways:
- The search is complete (i.e. no more edges to traverse), and we have not yet reached the vertex representing all rooms. This means the dungeon is disconnected, the player is unable to reach all rooms, and we output UNFAIR with the set of rooms we have reached so far.
- The search is complete (no more edges to traverse), and we have covered the vertex representing all rooms. This means it’s possible to complete the dungeon, and not possible to get stuck, so we output FAIR.
- The search reaches a vertex with f(S(v)) <= 0. This means we’ve found a reachable set of rooms where the player can run out of keys. We can terminate the search immediately and output UNFAIR with the set of rooms we’ve reached.
Implementation is left as an exercise – but there’s actually not much to it. Use the bitset/integer representation of vertices, and don’t explicitly build a data structure for the edges – just compute the set of reachable vertices on the fly at each step.