One person team, using C++.
full contains full round artifacts. lightning is the state of the repository at the end of the lightning round.
Breadth-first expansion from the starting room until all doors have been tested.
The task involves creating a graph from the fewest observations, where a guess is considered correct if no route would result in a different set of observations when compared to the original graph. Two difficulties:
- Each individual observation was not sufficient to uniquely identify a room.
- The graph was undirected, but we only know the door number from the departing room, and need to infer the door number on the arriving room.
I took a breadth-first approach to building the graph:
- Let Known rooms be the set of rooms that we know how to get to (initially just the starting room), and Complete rooms be the set of rooms where we have observations from all exiting doors (initially empty).
- For each known room, generate routes to expand from all its doors.
- If observations from this room match an existing complete room, the shortest path used to reach this room is added to the existing room, and the room is deleted.
- If observations from this room do not match an existing complete room, it is added as a new room in the complete room set, and all its neighbors are added to known rooms.
- Repeat steps 1-2 until all known rooms are empty and every room is complete.
The paths used to exit each room are just each door number repeated N times, where N is the number of rooms. I figured for a graph of size N, I am guaranteed to see a loop if I walk N steps.
The shortest path to reach each room is the sequence of doors. We know they are the shortest paths due to breadth-first expansion. It's possible to make a single directed graph connection from these paths -- the last character in the path identifies the departing door number of the previous room, and all the characters before that are used to lookup the index of the previous room.
This doesn't give us enough information to identify the arriving door for the current room (which is why I asked about the doors being symmetric). I added some heuristics to assign doors so that every door went somewhere, and with those heuristics I was able to solve all lightning round problems. All this was done in less than half a day since the start of the contest.
This breadth-first expansion is not optimal in terms of number of queries: I need (door count) * (room count) number of observations at a minimum, retrieved in number of batches equal to (maximum path length) + 1. A marginally better solution is to attach more steps to the fixed paths so that we get more observations per query due to the overlapping routes. An even better solution would be to create a long random route and add all rooms along it, then split the room at the point where subsequent observations diverged. But where would the split happen, and how could I uniquely identify the rooms in this approach? I spent the second half of the first day implementing various ideas and couldn't get them to work.
The new wrinkle added for the full round was the ability to vandalize rooms. With this ability comes the curse that subgraphs that would have otherwise produced identical observations can now be differentiated. The contest protocol was backward compatible, but obviously my lightning solution didn't work out of the box. Bummer.
The first thing I tried was to run the same solution on "aleph" problem, and what I observed was a fully connected 6-room graph, even though the expected number of rooms is 12. So some of those equal-looking exit doors will need to be differentiated using the new charcoal mechanism. The lightning solution was thus updated as follows:
- Each door requires multiple outgoing routes to make a room complete.
- The first outgoing route starts by going through the same door N number of times, and then takes a fixed number of random steps away from there. No relabeling was done on the first route.
- All subsequent routes start by changing the label of the starting room, followed by a fixed number of random steps that either go through a door or relabel the current room (label is randomly selected, so we might get the same label).
The new routes include more randomness because always going through the same door was likely to get me stuck in some room without exploring the full graph. This risk was also present in the lightning round, but luckily I managed to solve all lightning problems while remaining blissfully unaware of such issues. Anyways I did a lot of refactoring, added a lot more randomness, and spent a full two days doing that while still not solving the "aleph" problem.
At about 2am with ~3 hours left in the contest, I decided to give up. But I thought it was only fair that I have experienced all the problems offered by the judges. Surprisingly, the problems "vau", "zain", "hhet", "teth", and "iod" were all in different shapes that were more agreeable to my solver, and I was able to score points on all those in the next hour. I still wasn't able to solve "aleph", "beth", "gimel", "daleth", and "he" all the way to the bitter end.
I greatly enjoyed the problem this year. It's short and simple, almost zero overhead to get started (didn't need to implement a large VM or evaluate a complex language), focused on a single task, while still leaving lots of room for optimizations. The fact that it was also beautifully typeset also left a great impression.
Many thanks to the organizers for another great year!