ICFPC 2025

This repository contains our solutions for the ICFPC 2025 contest.

---

Solutions

Lightning Division

We treated each room as a state, the door number as input, and the first 2 bits of the room label as output, modeling the labyrinth as a Moore-style finite-state machine (Moore machine). To reconstruct the map, we applied Angluin's L* algorithm. When the closedness condition failed, we added the offending word to the set of access strings $S$. When the consistency condition failed, we added the offending suffix to the set of distinguishing suffixes $E$. We used W-method and RS-method for counterexample checking. Any discovered counterexample was added to $S$ or $E$, and the learning process restarted.

We also optimized the following hyperparameters using Optuna:

• Maximum word length used in the W-method for counterexample checking.
• Probability of adopting words generated by the W-method as counterexamples.
• Maximum length of words generated by the RS-method.
• Number of words generated by the RS-method.

---

Full Division

After estimating the quotient graph using the Lightning Division's learned model, we restored duplicated rooms via a depth-first search (DFS). The algorithm proceeds as follows:

1. Define a room group to contain an original room and all its copies.
2. Identify each room group by the node ID in the quotient graph.
3. Upon entering a room, read its label.
4. If the label remains unchanged, treat the room as newly encountered: change its label to (original_label + number_of_rooms_found_in_same_group_so_far + 1) % 4.
5. Move through an adjacent door.
6. Determine which copy this room corresponds to—represented as a new vertex (quotient_graph_node_id, index_within_group). Add an edge from the previous room to this one in the graph.
7. If all doors of a visited room have been explored, backtrack.
8. Once every door in the labyrinth has been explored, reconstruct the full map from the built graph.

We also utilized a SAT solver to aid in estimating the quotient graph.

---

Setup (Python Virtual Environment)

At the root of the repository, run:

$ python3 -m venv venv
$ source venv/bin/activate

This activates a shared virtual environment where you can install necessary modules.

---

Acknowledgments

"Special thanks to William for bravely mapping the mirrored corridors of Ædificium, and to Adso for faithfully recording every altered glyph—even when Alonzo hurried to erase them."