Folding a cube without hardcoding the folds

My Advent of Code 2022 repository has two commits. The first, on 21 December 2022, is days one to twenty-one, a December’s worth of #%% cell-mode Python written at speed, no README, and, across 2,775 lines, not one explanatory comment. The second is dated 21 August 2023 and says day 22 and 23. Eight months later. Day 22 part 2 is the reason.

The puzzle gives you a map: a rectangle of spaces, dots and hashes that happens to be a cube net, plus a sequence of moves like 10R5L5R10L4R5L5. Part 1 is a flat wrap: walk off the right edge, reappear on the left edge of the same row. Part 2 says the map is really the surface of a cube, so walking off an edge should put you on whichever face is glued to that edge once the paper is folded up, facing in whatever direction the fold leaves you facing.

That change turns a twenty-line problem into a geometry problem, and the standard way people solve it is by hand. You print the net, you fold a piece of paper, you work out which edge meets which, and you write down fourteen cases. It works. It is what most people do, and I do not think worse of anyone for it. But it is an hour of error-prone bookkeeping that solves exactly one input, and the thing I wanted was code that would take any net and work it out. This post is about that code, and about the fact that, reading it back to write this, I found it does not actually work, and exactly where it stops working.

The sample net

Here is the whole dataset, exactly as it appears in the source:

# 2022/day22_pt2.py L15-30
test_data="""
        ...#
        .#..
        #...
        ....
...#.......#
........#...
..#....#....
..........#.
        ...#....
        .....#..
        .#......
        ......#.

10R5L5R10L4R5L5
"""

Sixteen characters wide at its widest, twelve rows tall, ninety-six dots and hashes. Six faces of four-by-four. The real input is the same shape of thing at fifty-by-fifty, laid out as a different net entirely, which is the whole difficulty, because a solution tuned to the picture above tells you nothing about the one you were actually given.

Part 1, and the shape of the easy version

Part 1 needs none of this. You walk, and when you fall off the drawn region you keep going until you come back onto it. My own part 1 (2022/day22.py) is more elaborate than it needed to be: it precomputes, per row and per column, the first and last drawn cell and a sorted list of wall positions, then jumps the entire move distance in one go and uses bisect to find the first wall in the way.

# 2022/day22.py L76-84
def landmine_check(prev_v, next_v, landmines, direction_ax):
    if len(landmines) <= 0: return next_v
    idx = bisect.bisect(landmines, prev_v)
    if direction_ax > 0:
        if idx < len(landmines):
            next_v = min(next_v, landmines[idx]-1)
    elif idx>0:
        next_v = max(next_v, landmines[idx-1]+1)
    return next_v

landmines is what past-me called walls, which tells you roughly the mood of that December. The bisect is a real optimisation for a move of length 10,000 on a 200-wide map, and completely pointless for the input sizes the puzzle actually uses. It is the kind of thing you write at 6am.

There is a fourth file in that directory, day22_hyper.py, sixty-one lines, which solves part 1 by the obvious method: step one cell at a time, and on a space, keep stepping:

# 2022/day22_hyper.py L34-38
while True:
    nr = (nr + dr) % len(grid)
    nc = (nc + dc) % len(grid[0])
    if grid[nr][nc] != " ":
        break

Part 1 wraps in the plane. Part 2 wraps on a cube, and none of the above survives it.

The approach I abandoned

The first thing I reached for was the thing everyone reaches for: a description of an edge pairing as data. Both part-2 files still carry it, commented out, at the bottom:

# 2022/day22_pt2.py L115-131 (commented out in the source)
class Connection:
    def __init__(self, block_size, connecting_axis=0, invert=False, swap_axis=False):
        self.invert = invert
        self.connecting_axis = connecting_axis
        self.swap_axis = swap_axis
        self.block_size = block_size
    def wrap(self,v):
        # TODO maybe there is a case for -v
        if self.invert:
            return self.block_size-v
        return v-block_size
    def __call__(self, pos):
        pos = list(pos)
        pos[self.connecting_axis] = self.wrap(pos[self.connecting_axis])
        if self.swap_axis:
            pos = reversed(pos)
        return tuple(pos)

That is the hand-tabulated approach in its natural form. A Connection is three booleans and an axis: which coordinate is the one that wraps, whether it runs backwards on the far side, and whether the two coordinates swap. Given the fourteen of them, walking off an edge is a dictionary lookup. It is a perfectly reasonable design: more or less what a careful hand-tabulated solution looks like once you stop writing if statements and start writing data.

The interesting part is where it stops. Immediately below the class is the function that was supposed to produce those objects:

# 2022/day22_pt2.py L141-147 (commented out; this is the end of the file)
def get_connection_fn(face_i, face_j):
    r_y, r_x = get_rotations(face_i, face_j)
    if abs(r_x)!=1 and abs(r_y)!=1: return None
    if abs(r_y)==1:
        conn_ax = 0
        inv = r_y<0

It ends there. Mid-if, no return, and then the file is over. That is the moment I gave up on deriving the pairings from the net layout and went looking for a way to derive them from the solid. The # TODO maybe there is a case for -v two functions earlier is the same feeling written down: the sign conventions were multiplying and I had no principle to settle them with.

The honest summary of the trade is this. Hand-tabulating fourteen pairings for one net is about an hour of careful work with a piece of paper, and when you are done you are done: no geometry, no matrices, nothing to get subtly wrong at 90° instead of −90°. The general version needs an idea before it needs any code, and if you get the idea slightly wrong you get a plausible-looking answer that is completely false. The rest of this post is a demonstration of exactly that failure mode, in my own file.

Six faces out of a rectangle of dots

Before any of the geometry, the net has to be chopped up, and this part of the source is both short and right. The face size is not given by the puzzle, but it is implied: six faces of $n \times n$ cells means the number of drawn cells is $6n^2$ , so $n = \sqrt{\text{cells}/6}$ .

# 2022/day22_pt2.py L41-60
l_map_dta = map_dta.split("\n")
total_h = len(l_map_dta)
total_w = max((len(l) for l in l_map_dta))
map_cntr = collections.Counter(map_dta)
total_blocks = map_cntr["."]+map_cntr["#"]
block_size = int((total_blocks/6)**0.5)
mesh = [[None]*int(total_w/block_size) for _ in range(int(total_h/block_size))]
mesh_landmines = {}
for i, mesh_row in enumerate(mesh):
    for j, mesh_el in enumerate(mesh_row):
        start_y = i*block_size
        start_x = j*block_size
        if start_x >= len(l_map_dta[start_y]) or l_map_dta[start_y][start_x] == " ": continue
        mesh_idx = len(mesh_landmines)
        mesh[i][j] = mesh_idx
        mesh_face_landmines = set()
        for y,ln in enumerate(l_map_dta[start_y:start_y+block_size]):
            for x,c in enumerate(ln[start_x:start_x+block_size]):
                if c=="#": mesh_face_landmines.add((y,x))
        mesh_landmines[mesh_idx] = mesh_face_landmines

mesh comes out as a small grid of face indices and Nones. For the sample above:

[[None, None,    0, None],
 [   1,    2,    3, None],
 [None, None,    4,    5]]

mesh_landmines[i] is the set of wall cells inside face i, in that face’s own local coordinates. From here on nothing needs to look at characters again. The problem is six labelled squares in a small grid, and the question is which square meets which once you fold.

Every angle is a multiple of 90°

Here is the idea that makes the general solution worth having. Folding a cube net only ever turns things by right angles. So every rotation matrix you will ever need has $\cos\theta \in \{0, \pm 1\}$ and $\sin\theta \in \{0, \pm 1\}$ , which means every matrix entry is an integer, every product of them is an integer, and two orientations are either equal or they are not. No floating point, no epsilon, no abs(a - b) < 1e-9 anywhere. That is not a micro-optimisation; it is what makes the whole approach checkable, because “does this face’s orientation match that one” is ==.

The source encodes an angle as a small integer number of quarter turns and looks the trigonometry up:

# 2022/day22_pt2 copy.py L73-87
@lru_cache
def get_sin_cos_angle(angle):
    if angle ==0: # 0 deg
        cos_a = 1
        sin_a = 0
    elif angle ==1: # 90 deg
        cos_a = 0
        sin_a = 1
    elif angle ==2: # 180 deg
        cos_a = -1
        sin_a = 0
    elif angle ==2: # -90 deg
        cos_a = 0
        sin_a = -1
    return cos_a, sin_a

Then three rotations and a way to apply all three:

# 2022/day22_pt2 copy.py L89-116
def rx(angle, vector):
    ca, sa = get_sin_cos_angle(angle)
    x,y,z = vector
    return (
        ca*x-sa*y,
        sa*x+ca*y,
        z,
    )

def ry(angle, vector):
    ca, sa = get_sin_cos_angle(angle)
    x,y,z = vector
    return (
        ca*x+sa*z,
        y,
        -sa*x+ca*z,
    )

def rz(angle, vector):
    ca, sa = get_sin_cos_angle(angle)
    x,y,z = vector
    return (
        x,
        ca*y-sa*z,
        sa*y+ca*z,
    )
def apply_rolls(rolls, vector):
    return rz(rolls[2],ry(rolls[1],rx(rolls[0], vector)))

Look at what rx does: it mixes $x$ and $y$ and leaves $z$ alone. That is a rotation about the $z$ axis. And rz mixes $y$ and $z$ and leaves $x$ alone: a rotation about the $x$ axis. Funny thing to notice rereading this: the names of the first and third functions are swapped with respect to what they actually do. On its own that is only cosmetic, since apply_rolls composes all three anyway. It matters because the same file then takes a vector in the net’s coordinates and adds it componentwise to a triple of angles, and whether component 0 means “turn about $x$ ” or “turn about $z$ ” is precisely the thing that determines whether that is legitimate.

Rolling the cube

The idea in the file is genuinely the right one, so it is worth stating cleanly before I take it apart. Put a cube on the net, sitting on face 0. Roll it one cell at a time to each neighbouring face. Every roll is a 90° tip about the shared edge. When the cube arrives at face $i$ , the cube face touching the paper is the cube face that net square $i$ becomes, and the accumulated rotation tells you which one and which way up. Do a breadth-first search over the net and every face gets an orientation. Nothing about the particular net is written down anywhere.

Rolling the cube over the net and folding the net onto the cube are the same computation seen from two sides: one leaves the printing on the inside, the other on the outside, and they glue the same edges to the same edges. The widget below shows the fold, because a fold is what you can watch.

Here is the search, which is thirteen lines:

# 2022/day22_pt2 copy.py L121-134
rolls = [None]*6
rolls[0] = (0,0,0)
to_explore = [0]
while to_explore:
    j = to_explore.pop(0)
    pos_j = get_mesh_face_idx(j)
    for i in range(6):
        if i==j: continue
        if rolls[i] is not None: continue
        pos_i = get_mesh_face_idx(i)
        diff = (pos_i[1]-pos_j[1], pos_i[0]-pos_j[0], 0)
        if abs(diff[0])+abs(diff[1]) != 1: continue
        rolls[i] = rotation_mod(*tuple_sum(rolls[j],apply_rolls(rolls[j], diff)))
        to_explore.append(i)

diff is the step from face j to face i in the plane of the net: (±1, 0, 0) or (0, ±1, 0). The abs(diff[0])+abs(diff[1]) != 1 line is the “are these two squares actually adjacent” test. rotation_mod is (x+1)%4-1, which folds each angle into −1…2 so that orientations compare equal.

And the last line is where it goes wrong.

Where it stops working

rolls[i] = rotation_mod(*tuple_sum(rolls[j], apply_rolls(rolls[j], diff))) reads: take the parent’s angle triple, add to it the parent’s rotation applied to the step direction, and normalise. The intuition is defensible: rotate the step into the cube’s own frame so you learn which axis the roll happens about, then bump that axis’s angle by a quarter turn.

The intuition does not survive contact with matrix multiplication. apply_rolls defines a triple $(a,b,c)$ to mean $R_z(c)\,R_y(b)\,R_x(a)$ , the file’s own convention, whatever the function names say. Adding one to $a$ , the innermost angle, is a right-multiplication: $R_z(c) R_y(b) R_x(a{+}1) = R\cdot R_x(1)$ . Adding one to $c$ , the outermost, is a left-multiplication. Adding one to $b$ , the middle angle, is neither: it splices a rotation into the middle of a product, which is not the composition of anything with anything. A roll is a single 90° turn about one axis; composing it with the orientation you already have is one matrix multiply, and there is no way to spell that as “increment one Euler angle” in general.

You do not need the theory to see it fail. Run those thirteen lines on the sample net, then feed each resulting triple through the file’s own apply_rolls and ask where it sends the outward normal (that is, which side of the cube each net square lands on):

net square	`rolls[i]`	face of the cube it lands on
A	`(0, 0, 0)`	`(0, 0, 1)`
B	`(0, 0, 1)`	`(0, 1, 0)`
C	`(0, 1, 1)`	`(0, 1, 0)`
D	`(0, 1, 0)`	`(-1, 0, 0)`
E	`(0, 2, 0)`	`(0, 0, -1)`
F	`(-1, 2, 0)`	`(0, 0, -1)`

Six squares, four distinct sides. B and C both claim (0,1,0); E and F both claim (0,0,-1). B and C are adjacent squares in the net, so this is not a subtle failure: two squares sharing an edge have been folded onto the same face of the cube. On the 2‑3‑1 net that most real day-22 inputs use it is worse: three distinct sides out of six.

The repair: carry the matrix, not the angles

The fix keeps the entire idea and throws away only the arithmetic. Instead of an angle triple per face, carry the rotation itself. Instead of adding, multiply.

Folding face $i$ up from its parent $j$ is a 90° turn about the crease they share. If $\mathbf{d}$ is the step from $j$ to $i$ in the plane of the net and $\hat{\mathbf{z}}$ points out of the paper, the crease runs along $\hat{\mathbf{z}} \times \mathbf{d}$ , and a $90°$ turn about that line swings the child square out of the plane. Which of the two signs you pick only decides whether the printing ends up on the inside or the outside of the finished cube; I fold away from the reader so the letters stay visible.

Folding one square onto its parent. The crease is the shared edge, the axis is z × d, and the turn is a quarter, always, for every crease in every net.

A 90° rotation about an integer axis $\mathbf{a}$ is Rodrigues’ formula with $\sin\theta = 1$ and $\cos\theta = 0$ substituted by hand, which leaves $R = I + K + K^2$ where $K$ is the cross-product matrix of $\mathbf{a}$ , every entry a 0 or a ±1. In my TypeScript reimplementation (src/widgets/folding-a-cube/fold.ts, which is what drives the widget below) that is:

export function rotAxis90(a: Vec3): Mat3 {
  const [x, y, z] = a;
  return [
    [1 - y * y - z * z, -z + x * y, y + x * z],
    [z + x * y, 1 - x * x - z * z, -x + y * z],
    [-y + x * z, x + y * z, 1 - x * x - y * y],
  ];
}

and the search is the same breadth-first walk over the net as the original, except that what travels along an edge is a crease rather than a sum of angles. The BFS records one, in the flat net’s own coordinates:

// src/widgets/folding-a-cube/fold.ts L241-243
const d: Vec3 = [dc, dr, 0];
axis[i] = cross([0, 0, 1], d);
through[i] = [Math.max(c, nc) - originCol, Math.max(r, nr) - originRow, 0];

and the composition is one line, applied in order of depth so a face’s parent is always already placed:

// src/widgets/folding-a-cube/fold.ts L280-288
function facesAt(tree: Tree, alpha: number): Aff[] {
  const theta = (alpha * Math.PI) / 2;
  const out: Aff[] = new Array(6);
  out[0] = { m: IDENT.map((r) => [...r]) as Mat3, t: [0, 0, 0] };
  for (const i of tree.order) {
    if (i === 0) continue;
    out[i] = affCompose(out[tree.parent[i]], creaseAff(tree.axis[i], tree.through[i], theta));
  }
  return out;
}

Because each crease is expressed in the flat net’s coordinates and then composed under the parent’s transform, the whole thing is an animation for free. alpha is 1 for the answer and every entry comes out an integer; feed it anything between 0 and 1 and every crease opens together, from flat paper to a closed cube. That is the only place a float appears in any of this, and it exists purely so there is something to watch.

Run that on the sample net and the six squares land on six different sides: (0,0,1), (0,-1,0), (-1,0,0), (0,1,0), (0,0,-1), (1,0,0), which is a cube. Getting six distinct normals is also the validity check: if two squares want the same side, the shape you drew is not a cube net, and the code says so without a table of legal shapes anywhere.

Left: the day 22 sample net, six four-by-four faces lettered A to F, each a different colour, with wall cells drawn as dark squares. Right: the same six faces part-way through folding into a cube, each face keeping its colour and letter. — InteractiveNet folder

Paint something that is not a net and the right-hand panel tells you so. Switch on show edge pairings and the seven glued pairs get a colour each, on both the flat net and the cube. That overlay, and the table under it, is the artefact I actually wanted in 2023: paste in your own map, get out the fourteen directed edge transitions, and go and write the boring version of the solution with the bookkeeping already done. Face placements opens the other table: where each square lands, as the integer axes and normal it ends up with. That is the accumulated rotation the original was trying to keep in three numbers, written as the thing it actually is.

Walking off an edge

Once the faces are placed, the walk needs no case analysis either. Put the cube at $[0,2N]^3$ in doubled integer coordinates, so a cell centre is always at an odd coordinate and a cube edge at an even one. Then stepping off the side of a face is two moves:

one unit along your heading, which lands you exactly on the cube’s edge;
one unit against the normal of the face you were on, which lands you on the centre of the first cell of the next face.

And the face you have arrived on is simply the one whose outward normal is the direction you were walking; your new heading is the negative of the old face’s normal. That is the entire wrap rule, and it is the same three lines regardless of which of the eleven nets you were handed.

Turning the corner of a cube in doubled integer coordinates. Every quantity in the picture is an integer vector; nothing is measured.

// src/widgets/folding-a-cube/fold.ts
const D = add(scale(g.U, w.du), scale(g.V, w.dv));   // heading, in cube coordinates
const P = add(cellPoint(f, w.face, w.u, w.v), sub(D, g.n));
const nd: Vec3 = [-g.n[0], -g.n[1], -g.n[2]];        // the new heading
for (const h of f.faces) {
  if (!eq3(h.n, D)) continue;                        // the face you walked towards
  const rel = sub(P, scale(h.O, 2 * N));
  const nu = (dot(rel, h.U) - 1) / 2;
  const nv = (dot(rel, h.V) - 1) / 2;
  ...
}

Every value there is an integer. eq3 is three === comparisons. There is no tolerance anywhere in the file, which is what I meant at the top about the 90°-only structure being the thing that makes this checkable rather than merely clever.

Does it actually work?

Three checks. The first two you can run yourself in the widget above.

The published sample answer. Feeding the sample map and 10R5L5R10L4R5L5 through the folder, the walk finishes at row 5, column 7, facing up, for a password of $1000 \times 5 + 4 \times 7 + 3 = 5031$ , the number the puzzle statement gives for that example. Press Run the sample path in the widget and watch it get there; the marker turns yellow on the step where it wraps.

The eleven nets. There are 35 free hexominoes and exactly eleven of them fold into a cube. The widget’s net picker does not contain a list of eleven shapes. It enumerates all 35 hexominoes by growth, hands each one to the same foldNet used for everything else, and keeps whichever ones do not throw:

// src/widgets/folding-a-cube/nets.ts
export function cubeNets(): NetChoice[] {
  const out: NetChoice[] = [];
  for (const cells of hexominoes()) {
    try {
      foldNet(netFromCells(cells));
    } catch {
      continue; // not a net: two of its squares wanted the same side of the cube
    }
    const laid = layout(cells);
    out.push({ cells: laid, net: netFromCells(laid), family: family(cells), /* … */ });
  }
  …
}

It returns eleven, in the expected families: six of the 1‑4‑1 shape, three 2‑3‑1, one 2‑2‑2 and one 3‑3. Getting the right number out of a routine that has never been told what the right number is, is about as good a test as this kind of code gets. It takes about 40 ms, which is why it is done at load rather than baked into a constant.

Great circles. Walk straight ahead on a cube and after four faces you are back where you started, facing the way you set off. Across all eleven nets, all six faces and all four headings (264 walks), stepping $4N$ times returns the walker to precisely its starting cell and heading. That is a property of the solid, not of my code, which is exactly what makes it a good assertion: nothing in the folder was written with it in mind, and any error in a single edge pairing breaks it immediately.

The one most real day-22 inputs arrive as is a 2‑3‑1:

 ##
 #
##
#

and the same code folds it, pairs its edges and walks it with no special case, which was the entire point of the exercise, eight months late.

What I would do differently

The idea was right and the arithmetic was wrong, and the reason the arithmetic stayed wrong is that there was no check anywhere that could have caught it. Six faces landing on four sides of a cube is not a subtle numerical drift; it is an obvious, immediate contradiction, and one assertion (are these six normals distinct?) would have printed it out in 2023. I had the sample net, I had a published answer for it, and I had a property (len(set(normals)) == 6) that costs one line. I wrote none of them, and what I did instead was stop.

That is the pattern I keep finding in this repo when I read it back. The two other posts I have written from Advent of Code solutions land on the same shape of lesson from different directions: in Complex numbers are the right type for a grid I had built a 301-line N-dimensional vector class before noticing the standard library already shipped the type I wanted, and in Dijkstra when you are not allowed to go straight the fix was not a new algorithm but noticing that the node was never the cell. All three are the same failure of attention, and only the cube one is an outright bug: it is the bug precisely because it is the only one of the three that never got a check written against it.

The generalisation is still worth it, incidentally. Not because it is faster (folding six faces is microseconds either way, and this was never a candidate for anything but plain JavaScript) but because the general version is checkable. “Does this net fold?” and “do these six faces land on six different sides?” are questions you can ask a rolling cube. There is nothing to ask a table of fourteen numbers you wrote out by hand except whether you copied it correctly.