Our team usually starts the lightning round rather slow. We don't rush to fight for the top place, and (given we're in PST, and few of us didn't make the habit to schedule the day off when ICFPC is announced) we may have a ton of other things to do on Friday.
Still, we have a gang of hackers ready to push some code, we had a garage and few boxes of pizza, so we were a legit OG Bay Area startup team. Ready to move fast and break things!
Though, there wasn't a lot of things to break. As usual, first thing was to have some solution. Bold bet, I'd say. First we started with having a half-baked local implementation of a proper server, mining some examples, translating them to Graphviz for visualization (because it's rarely an ICFPC without someone deciding to convert some random data into dot format), and doing some other engineering tasks while procrastinating on the actual solution.
While we were discussing the problem, some thesis work we did back in university, and other random ideas, our remote R&D department was busy actually implementing something. After few hours we had a solution that tried to solve the problem using random walk, graph theory and a set of assumptions that allowed us to distinguish separate rooms in the library. Nothing too tricky (narrator: the person writing this still doesn't understand good half of the algorithm), but it worked fine on smaller tasks. Yay, we have a baseline.
Besides the baseline, we also had a very ceiling — a couple of teams had already scored 2 for every problem. It meant for us that: 1. the solution is discoverable without any reinforcement; 2. we don't have to push that much the first day, as someone already solved it fully, and if any tiebreakers — we don't have a chance for the first place anyway.
So, the rest (should I say "the most"?) of our team jumped on the very basic approach, so called "hash bfs". We decided to spend a ton of requests (and contest hosts AWS bill, sorry for that) to actually traverse the entire graph doing the regular breadth-first search. Still, the vanilla BFS wouldn't work, as we have vertices with same labels. So, we had an assumption that if we'll calculate a sequence of rooms that follow the room we're traversing when passing some predefined pseudo-random route as kind of a hash —it'll be unique enough for each room. Some polish, and we have a score of hundreds if not thousands — still better than nothing.
When we opened our eyes on Day 2, we were pleased that the task mostly remained the same. No space wars, no gambling bot, only a tiny addition that will still somehow work with our original approach (narrator: it took 45 hours to make it work).
The team dispersed and started working on different aspects of the problem. Finally, we have a room for everyone to explore, and a room for everyone to improve.
We've tried to play with some libraries that allowed to use Mealy or Moore machines. Well, they've allowed theoretically to build what do we want based on observations, but the interactive aspect and the trickier definition of observed versus real equivalence made it difficult to implement, so we gave up on that idea.
Another idea was to use some solver (say, Z3) — now it looks like a bright idea that would allow us to get close to the top of the board and spend a ton of time on microoptimizations and diminishing returns. Unfortunately, the performance of our implementation was subpar, so we couldn't chew through larger problems in a reasonable time. Sadly, one more thing we dropped.
In a meantime we were working on a tooling. It's great that we were able to create 3-4 different model hierarchies just in Python, so everyone had an opportunity to be represented in the final solution. Visualizer got more functional, we've added a web UI for it (still rendering into in-memory SVG from the Python backend because we lost a bit of trust in the vibecoding), made 4 different generators for multi-layered levels (and visualized helped to discover first 3 were broken; as well as visualizer itself), and so on. Now it's some real engineering!
All of those explorations required us to talk to the server from time to time. Of course we could've implemented some proxy allowing to batch requests, manage access rules, and do a ton of other enterprise level solutions. But well, there wasn't a client to send an invoice to, so we came up with a brilliant solution. Welcome to the slack channel #mutex-2025! If you want to play with server — you lock one. If you don't — you release it. Over the course of the contest, as more people wanted to contribute to the overall success, we've designed new functionality like weak locks, awaiting, and other concurrency primitives implemented in natural language and gentlemen's agreements.
The most important discovery on the third day was the fact that painting the very starting room in any other color was converting the task to the one from the lighting round. Basically, it was chaos monkey kicking the entire bucket of paint into the library doors. Boom!
Of course, the new task will have tighter constraints, and our initial algos were not great chewing through the data. Still, it allowed us to have non-zero solution to some of solutions. Then, at some point where we were still debugging a proper solution, we decided to hedge our risks, and slapped the same "bucket lemma" on top of our slow hash BFS algorithm from the day one. It was slightly worse than SAT solvers done by other teams (like 2-3 magnitudes worse), but it was a steep improvement over the zero baseline, and brought us from top 50-ish team to top 20-ish.