As usual, our codingteam was participating in the annual ICFP contest.

See our submission here.

Team

This year, our team was smaller than usual: Minoru decided to skip this year. And I think we felt his absence :(

So, the team was finalized as me, Foxtran, Gsomix, and Portnov.

I decided to change the structure of my reports this time: instead of just the chronicles, I will extract the information on the task and the way we (tried to) solve it into separate sections. We'll see how it goes.

Preparation

Before the contest, we've had a vote on what technology to use this year (because it's not a Haskell year), and F# won the vote. But a couple of weeks ago, we've been discussing the upcoming contest with Gsomix who suggested we use Scala. I decided to change my own vote in Scala (and Gsomix's!) favor, and so, the Scala year it is.

Previously I've been unsure if Scala 3 ecosystem is mature enough, and while I still have my doubts, I need to say it's not that bad.

This time, I started the preparation, set up the project repository and CI just a week ahead of the contest time. And apparently I didn't do a very good job of notifying my team members of that: Portnov had issues setting up Scala during the contest.

Anyway, when the contest started, we've had our team assembled and ready for the task. And the task has been dropped.

Task

You can read the task specification available in our repository (mirrored in case it becomes unavailable from the contest site).

I seriously recommend taking a look at that PDF because of how beautiful it is. Just look at this typesetting, the images, the fonts. Absolute awesomeness! It totally reconstructs the feeling of reading, like, an 18th century folio.

So, we control a group of characters who visit a linked graph of rooms, each room having 6 doors. At each step, we can choose a door number and walk through it, and after going through, we'll get the 2-bit room label of the target room. All the doors are 2-way (though there's no way of knowing through which door we entered the room, we need to guess), and since the room number in most tasks is more than 4, there's also no way of exactly identifying a room — we have to guess on room identity bny the set of connections it has.

I was quite quick to recognize that this task can create maps that are impossible to exactly figure out. Imagine this:

Here, you cannot guess what is happening in room B after you go through the door I: the "mirrored" copy of the library is indistinguishable from the "normal" one.

My understanding, though, is that the tasks published during the first 24 hours of the contest weren't that complicated. But after 24 hours from the start of the contest, an addendum to the specification has been made, targeting this exact problem. Now, it is possible to mark certain rooms during the exploration, rewriting their labels. So, you can mark the bottom left A room, and in this way distinguish it from the top right A room — figuring out that there is a mirrored copy of a part of the library.

You can make several trips through the same library, but each trip will start from the same room. And you have to make up your mind on the exact plan (a sequence of doors you enter) before taking a trip.

The less trips you make before figuring out the exact full map of the library — the better score you get.

You can re-generate and restart exploration of any task as many times as you wish, only the best result will affect your score.

During the first 24 hours of the contest (traditionally know as the lightning round), some of the simpler tasks were available. And after the lightning round has been finished, more tasks were published.

The easiest one consisted of mere 3 rooms, while the harder one (presumably impossible to solve without markings) consisted of, I think, about 90 rooms (sadly, can't check right now, because the task list has been hidden after the contest finished).

Solutions

We've been working on several solutions.

My focus was into something that I'll call the "rule engines" — programs we can feed the existing information on library layout, and they will figure out what possible graphs can satisfy the known conditions. I've been thinking and working on a Scala solution specialized for our situation, but then eventually switched to implementing a solution in miniKanren framework, and its implementation known as clojure.core.logic. Sadly, none of this worked out: I didn't manage to finish it in time, and even when I did after the end of the contest, my solution was never able to finish even on the simple task :( Not sure if there's some fundamental problem with approach, or just with my code. The readers are welcome to decide for themselves.

Gsomix worked on integrating an external SAT solver into our solution: the idea was that by encoding each step of our route room in a specific way, and adding equations describing the problem space, we can invoke an external program that will provide us the encoded result of the possible door connections. After seeing posts from other teams, I conclude this was the solution, but sadly we didn't manage to pull it off. We started working on SAT quite late in the contest timeline, and lacked time necessary to think through all the encoding schemes and implement them.

Portnov worked on a solver using dynamic programming, involving algorithms from the scala-graph library. My understanding is that he tried building the map while traversing the route, guessing which room might correspond to an already known one, and "forking" them if a contradiction has been found.

And Foxtran has implemented the most fruitful solution in Fortran (if we remember correctly, there were no other teams proclaiming Fortran as their instrument of choice, so there's that!): my understanding is that it tried somewhat directed random search. It tries to connect doors in a room matrix in different configurations until it somehow clicks and works out. Which sound really crazy to me, it would never properly work. But apparently it did? Perhaps the problem is my misunderstanding of how "directed" the random search was, but my Fortran understanding doesn't help to figure it out. Go any try figure it out for yourself!

I believe that of all our solutions, we only managed to submit two tasks using the Fortran solver, and one simple task was solved manually.

Chronicles

Day 0 (2025-09-05)

The contest started with Portnov struggling with his JVM and SBT installations. What a bummer SBT doesn't have a wrapper script similar to gradlew!

I have registered the team and started slowly reading the specification, commenting on various peculiarities I found, including the problem with mirrored labyrinth (which was later clarified that the lightning round tasks have no such labyrinths that are impossible to properly map without the ability to leave markings — so the problem wasn't practical at the moment).

We have found quite inconvenient that the server is stateful (you send /select command, and then you are supposed to provide a solution in a separate request), so several persons cannot solve different tasks in parallel, which is especially important at the beginning of the contest.

Portnov proposed us to quickly read Algebraic Topology by Allen Hatcher. I have even opened that, but quickly came to the conclusion that my understanding of the corresponding math is not nearly enough to make any sense of the book :(

I propose the analytical idea I will be working through the remaining contest: what if we imagine a manifold of all the possible graphs, then apply constraints from the known routes we have walked through, and see if the constrained manifold only contains one exact library? My further work on clojure.core.logic and such was done in the direction of this solution, as I imagine it at least.

I have also concluded that for "loopback" doors (doors leading from the room back to itself), it's impossible to figure out which door connects to which one (if there are several such doors in the same room), so the cheapest solution is to always consider such doors "short-circuited", leading to themselves (allowed by the specification). This idea I have later implemented in my clojure.core.logic solution, and perhaps it has even reduced the set of goals I produce.

We've discussed some ideas with Portnov, alongside the more constructive approach (when we try to construct the labyrinth on the go, as we traverse the route). He has also found that our labyrinth is in fact a multigraph (as several edges might be between the same nodes).

We've discussed with Gsomix some preferences we've had on types in our Scala solution: I insisted on ignoring the IO errors when talking to the server, and only exposing the "unsafe", exception-throwing interface without wrapping the results into Either type. (Which was the right idea, we never had issues with server API.)

I called our type for server Ædificium, and was criticized for it (non-ASCII letter caused problems). I do not accept such critique, though. A man should live in style and die in style. For cases when accessibility is important, there's val AEdificium = Ædificium — but I see it was never used by anybody in our project.

I have implemented a solver stub that calls the API in series of /explore and then /guess, but didn't implement any of the steps in between yet.

Portnov implemented a local server (generating random labyrinths) to use instead of the official API.

Foxtran implemented random route generator in Scala, and asked me to help with its integration with the rest of the code.

I have started thinking about miniKanren and looking for its implementations in Scala or Java (imagine that: they are all dead! The only useful implementation in JVM ecosystem you can quickly get from a Maven repository is the clojure.core.logic!). So, decided to postpone this for now. And started working on my "rule engine" (essentially, a reimplementation of a specialized part of the general logic engine, though I didn't recognize it just yet).

Portnov thinks about implementing some depth-first search based on the constructive solution.

Foxtran asked me to help with applying a route to a known labyrinth map, which I implemented.

Day 1 (2025-09-06)

Portnov invented a way to convert the multigraph to… just a graph: we need to make each door a separate graph node.

Gsomix implemented a way to add and run the alternative solvers through our CLI.

Foxtran tried implementing basic solver in our main solver stub, but didn't finish. Portnov refactored it for a bit.

Gsomix starts working on SAT integration.

I have started working on the "rule engine" or "fact engine" as I call it. Thinking about Prolog and miniKanren in background.

The addendum (with a new bunch of tasks, and now the ability to mark the rooms during the routing — though the markings have to fit into the same 4 bits, so they aren't the superpower) has been dropped after the first 24 hours have been passed since the start of the contest.

At the end of the day, I decided to start working on integrating the real miniKanren implementation (clojure.core.logic): implementing stuff on my own seems too tedious (there's a lot of stuff in logic engines). I used clojure.core.logic 13 years ago while implementing a simple task, so it's a freshly familiar approach to me.

Day 2 (2025-09-07)

Everybody keeps working of their stuff, nothing too interesting happened.

Foxtran has finally switched into writing Fortran code.

I am writing macros in Clojure for the first time in my life! It's not trivial but fun.

Day 3 (2025-09-08)

I keep working on solution in clojure.core.logic. One particularly hilarious problem I encountered was with evaluation order (or I thought so!). I found that this code works somewhat:

(run* [rooms-q]
  (fresh [l a b c d]
    (let [room1 {:label l
                 :doors [{:room a :door b} {:room c :door d}]}]
      (== l 1)
      (== a 1)
      (== b 2)
      (== c 3)
      (== d 4)
      (== rooms-q [room1])
    )
  )
)

while this doesn't:

(run* [rooms-q]
  (fresh [l a b c d]
    (let [room1 {:label l
                 :doors [{:room a :door b} {:room c :door d}]}]
      (== rooms-q [room1])
      (== l 1)
      (== a 1)
      (== b 2)
      (== c 3)
      (== d 4)
    )
  )
)

The real problem was that run* (and many other clojure.core.logic functions and macros) want goals as arguments, and will only take into account the goals directly provided to them. Any additional statements you write inside of let (such as (== l 1)) have no effect!

After I figured that out, I started struggling with grouping all my goals to somehow shove them into one great conde, and occasionally found very useful (but unfortunately not documented) functions and* and or*.

Sadly, I didn't manage to finish these experiments in time, and the contest has been ended, with us solving a mere couple of tasks.

But even when I finished my work and my logical program didn't immediately fail, it still didn't finish in several hours, while solving the simplest of tasks with just 3 rooms, the probatio. So, nope, my approach didn't work out. It's still unknown what caused the problem here: my misunderstanding of the logical engine, some issue in the engine itself, or maybe a bug in my code.

Conclusion

This was a nice contest, and the organizers did a very good job on everything!

There were some problems we experienced during the contest:

1. The stateful server that's impossible to work with in parallel is quite inconvenient, especially during the first hours of the contest.
2. I have to admit I didn't quite like this year's task. It was barely possible to solve "partially" and get at least some score; only the fully correct solutions were accepted — which caused us too much time to work on, and demotivated the team.

Nevertheless, I was happy to see my team again, and would like to say thanks to the people organized the contest! I absolutely loved how the contest was presented, PDFs were very pleasant to read, and the provided task server worked very well.

Again, if you wish to read the code, then see our submission here.