The Name of the Binding
ICFP Programming Contest 2025

ADDENDUM

After the first twenty-four hours of the contest, contestants face a new complication. This addendum to the task description outlines this complication.

After the first day had passed and night fell heavy upon the abbey, William & Adso stole once more into the labyrinth. Their lantern cast long shadows, and in that flickering half-light they discovered that the library had deceived them more cunningly than before.

What seemed a familiar chamber was not the same, but its twin: mirrored halls and doubled rooms, reflections upon reflections. Some were copied twice, even thrice. William gravely concluded "This library is no single plan, but a tapestry of overlapping copies, each one indistinguishable to the eye!"

Adso trembled, for he could no longer trust even the stones beneath his feet. "If one chamber is indistinguishable from another, how can we hope to make an accurate map?"

William smiled. "Worry not, Adso; we shall lend each its own character."

William bade Adso carry with him a piece of charcoal. With it, the young monk might alter the label above each chamber, rewriting it to aid their search. In their route plans, such acts of graffiti are shown in square brackets. Thus a plan written as follows:

  2[3]12[0]
commands them to step first through door 2; then change the current chamber’s label to 3; then pass through door 1; then door 2; and finally replace that chamber's label with 0.

These label numbers must always remain within the monastic cipher of two-bit digits (03). If they return to that chamber again, they will find the altered label, their own mark staring back at them. Yet when the route plan ends, the vigilant librarian Alonzo restores every sign to its rightful state, as though no charcoal stroke had ever touched the stone.

But Alonzo’s watch has grown keener. To avoid his suspicion, William and Adso must now tread more lightly: each route plan may contain at most 6n door-steps before they must make their escape (where n is the number of rooms). Longer wanderings would surely draw the librarian’s eye.

image

The problems labelled aleph (ℵ), beth (ℶ) etc. cannot be correctly mapped without using charcoal marks, as they consist of two or even three copies that cannot be otherwise distinguished from one another, whereas in the original lightning round problems (labelled primus, secundus etc.), all rooms could be distinguished without using charcoal marks.

As before, solutions are marked "correct" if they are equivalent to the actual layout of the library. Equivalence is, as before, defined to be indistinguishability with respect to route plans. Only now, "route plans" may also include charcoal marks.