The refusal that reads the list once

Five ways of saying no to a crease pattern were ranked here once already, and the ranking was by what each costs and by what each says no to first. A sweep over pairs of creases catches two drawn across one another; a pass over the vertices catches an angle or a count; a walk over the panels catches a pattern whose two routes to the same panel disagree; a pass over the crease list catches letters that contradict themselves; and an enumeration of every ordering of the panels catches everything else it can reach.

Run all five over the four test populations and the tally was five, nought, nought, nought, six. The fourth had nothing to fire on.

That has changed, and the change is instructive about both the test and the population.

Why only one #

The tally is worth reading carefully first, because the number that changed is small and the reason it is small is the finding. Thirty-three patterns became thirty-eight, and the layer refusal went from nought to one. Twenty-two refused by nothing became twenty-six. Nothing else moved: the crossing sweep still catches five, the vertex pass and the panel walk still catch none, and the search still catches six.

The patches are the patterns whose letters can contradict themselves, and only one of the five does. That is not a weak result; it is a result about the builder rather than about the test.

The tessellation builder does not draw the letters on. It propagates the vertex conditions to a fixed point, branches where propagation stalls, and takes what comes back. What came back on the square patch was a lettering that satisfied every condition and forced a circle of twenty-eight panels — so the builder now checks, and where it finds a circle it redraws with the branch order randomised until it finds a lettering without one.

Four of the five patches find a clean lettering within forty draws. The rhombille does not, and it is the one the ladder catches. So the ladder is reporting, accurately, that this collection now ships one pattern whose own letters are provably inconsistent — and that it ships four more that were in that state until the builder was taught to check.

The cost, in the units each test spends #

Ranking tests by cost usually means timing them, and timing them is the wrong measurement for a ranking meant to hold on somebody else’s machine. What can be counted instead is the primitive work each does.

On the rhombille patch: the crossing sweep compares 39,621 pairs of creases, the vertex pass visits 126 vertices, the panel walk places 157 panels, the layer pass reads 282 creases, and the ordering search is refused past two million nodes without deciding anything.

Two things fall out of that table which a stopwatch would have hidden.

The crossing sweep is quadratic, and on a large pattern it is by a wide margin the most expensive of the four cheap tests — a hundred and forty times the layer pass on the rhombille. It is also the one that fires most often, which is why it sits at the top of the ladder and why the ranking by what fires first and the ranking by what costs least are not the same ranking. On the small patterns everybody times, sixty-six pairs is nothing and the discrepancy is invisible.

And the search is not slow, it is absent. Five of the six patterns here defeat it: it does not return a worse answer more slowly, it returns no answer at all after spending its whole budget. A cost table that reported seconds would show it as the slowest row; what it actually is, is a row with nothing in it.

Where the costs cross #

The two rankings — cheapest first, and most-likely-to-fire first — agree on small patterns and diverge on large ones, and it is worth saying where.

At twelve creases the sweep is sixty-six comparisons and the layer pass is twelve reads, a ratio of five and a half. At two hundred and eighty-two creases the sweep is thirty-nine thousand and the pass is two hundred and eighty-two, a ratio of a hundred and forty. The sweep grows as the square of the crease count and everything else here grows linearly, so the gap widens without limit.

That has a consequence for what order the tests should actually be run in, and it is not the order the ladder is drawn in. The ladder is ordered by cost as measured on the patterns anybody had, which were small. On the patterns this collection now draws, the right order is the layer pass first, then the vertices, then the panels, then the crossing sweep — and the crossing sweep last of the four, despite being the one that fires most.

Nothing has been reordered, because on every pattern here all four together take less time than reading the file, and because the ladder is a piece of exposition rather than a pipeline. It is worth knowing that the exposition’s order is a fact about a bygone size.

The three cheap tests cost one number #

The cost table has an identity hiding in it, and pulling it out turns the crossing point from an observation about one pattern into a statement about every pattern.

On the rhombille the vertex pass visits 126 vertices, the panel walk places 157 panels and the layer pass reads 282 creases. Those first two sum to 283, which is the crease count plus one — and that is not an accident of this pattern. It is Euler’s formula for a plane graph with its outer face set aside: vertices plus panels equals creases plus one.

So the three linear tests together always cost

$$V + F + E = 2E + 1$$

primitive operations, whatever the pattern is. On the rhombille that is 565, and the three measured numbers add to exactly 565.

Which puts the crossing at five creases #

The sweep costs $E(E-1)/2$. Setting that against $2E+1$ and solving, the two are equal at about five creases, and beyond that the sweep is the larger.

So the crossing sweep has cost more than all three other cheap tests combined on every crease pattern anybody has ever drawn. Not on large ones: on all of them. A pattern with six creases is already past the point, and the smallest object in this collection has twelve.

That is a stronger statement than the ratio the essay gives, and it says the discrepancy between the two rankings was never a large-pattern phenomenon. It was invisible because sixty-six comparisons and twenty-five operations are both instantaneous, not because they were close.

What the redraw loop actually spends #

The same arithmetic prices the builder’s search, and the number is worth having because it is the concrete case for cheapness.

Forty redraws of the rhombille’s letters cost forty layer passes: 11,280 crease reads. Running the whole three-test linear ladder forty times costs 22,600 operations.

One crossing sweep costs 39,621.

So the builder’s entire forty-draw search for a clean lettering is cheaper than checking once whether any two creases cross. That is the case for the layer pass belonging inside a construction rather than after it, made in the units the construction spends — and it is why the ordering of the ladder as exposition and the ordering as a pipeline are worth keeping apart.

It also says what a pipeline should do with the sweep. Run it once, on the drawing, before any letter exists; nothing in the redraw loop can move a crease, so nothing in the loop can make two creases cross that did not cross before.

What linear buys that polynomial does not #

The layer pass is the only one of the five that is linear in the drawing, and the practical difference that makes is not speed.

It is that the test can be run inside a loop. The tessellation builder redraws its letters up to forty times looking for a clean one, and each redraw has to be tested; forty passes over two hundred and eighty-two creases is nothing, and forty crossing sweeps of thirty-nine thousand pairs would be a noticeable fraction of the build. The test is cheap enough to be part of a construction rather than a check applied to its output, and that is a different role.

The same property makes it usable as a filter in front of the search. Where both apply, the layer pass either refuses in one pass or hands the pattern on, and the handing on costs nothing — so there is no case in which running it first is worse than not.

A third role is the one it is doing in this collection’s own gates. A check that costs one pass can be run over every pattern the site draws, on every build, without anybody noticing — and a check that is run on every build is a check that catches a regression on the day it lands rather than at the next audit. The vertex conditions have that property and are run that way; the ordering search does not and is not.

What it refuses, which is the part that matters #

A cost ranking is only interesting alongside a coverage ranking, and the two do not agree.

The letters catch a small and variable share of the failures on any pattern where the complete answer is available: none of the twelve on a fold-and-cut triangle, four of the two hundred and forty-eight on a square twist. On patterns where the complete answer is not available they catch everything that is going to be caught, because nothing else runs.

So the honest description of the layer pass is not a fast version of the search. It is a different refusal that happens to be cheap, catching a class of failure — a chain of panels whose letters send it round — that the search would also catch, and missing everything the search catches by geometry. Two refusals that refuse differently is the account of how far apart they are.

What a no is worth without a reason #

There is a quality to a refusal beyond soundness and cost, and the five here differ in it more than they differ in either.

A refusal that hands back a reason is worth more than one that hands back a verdict. The vertex pass names the vertex and the condition; the crossing sweep names the two creases and where they cross; the layer pass names the panels in the chain. The panel walk names how far the two routes disagreed. The search names nothing useful: it says that every one of some enormous number of orderings broke some rule, and the rule and the ordering differ from one to the next.

That matters for repair, and it matters for whether a finding can be written down. A near miss is nearly as rare could be written because the geometric refusals come with a number attached. The circle in the letters comes with eight panels attached, which is why it can be traced with a finger on a printed sheet.

The search’s silence on this point is not a shortcoming of the implementation. A negative answer from an exhaustive search genuinely has no short certificate — that is roughly what the problem being hard means — and a refusal with a reason is therefore a refusal that has found something structural. Which is a way of saying that the cheap tests are cheap because they are looking for something specific, and the expensive one is expensive because it is not looking for anything.

The shape of a good cheap test #

There is a pattern in which cheap tests are worth having, and this collection now has five data points for it.

A cheap test earns its place when it is sound — never saying no about a pattern that folds — and when its cost is low enough that it can be run on inputs the complete test cannot be run on at all. Both halves are required. A cheap test that is merely faster on inputs the complete test handles is a convenience; a cheap test that is unsound is worse than nothing, because a wrong no is indistinguishable from a right one.

Of the five here, four are sound by construction and one — the search — is complete as well, on the range it reaches. The interesting position is the layer pass’s: sound, linear, and with a coverage that depends on a structural property of the pattern rather than on its size. A pattern with no closed chain of panels is one the layer pass can never refuse, whatever is wrong with it.

What each test would have to be given #

There is a way of reading the five that says what each is really consulting, and it explains the coverage differences better than the cost table does.

The crossing sweep is given the drawing and nothing else — coordinates and segments, no letters. The vertex pass is given the drawing and the letters, one neighbourhood at a time. The panel walk is given the drawing and computes where the paper goes, without consulting a letter. The layer pass is given the letters and the panel adjacency, and never asks where anything landed. Only the search is given the folded state entire: which panels overlap which, and by how much.

So the layer pass is the one test that reads the letters globally and the geometry not at all. That is exactly why it catches what it catches — a contradiction among the letters, anywhere in the sheet — and exactly why it is blind to what it is blind to, which is every failure that depends on two panels happening to lie over one another.

Put that way the ladder is not a ranking by strength at all. It is a list of the ways a crease pattern can be looked at, ordered by how much of it each way needs to see.

The fifth test that is not on the ladder #

One thing this collection can do to a crease pattern is missing from the five, and its absence is deliberate rather than an oversight.

Folding it. A sheet of paper answers the whole question — every condition, every overlap, every ordering — in about four minutes and with no budget. It is complete where the search is not, it costs nothing that scales with the pattern, and it is the only method here that can certify a tessellation patch.

It is not on the ladder because it is not a computation and the ladder is a ranking of computations. But its existence is why every figure in this collection is printable at true scale, and it is worth remembering when reading a table of refusals that the most capable instrument in the subject is a reader with a sheet of paper.

What is still missing from the ladder #

Two gaps, both worth naming rather than leaving as silence.

There is no cheap test between the layer pass and the search. The gap in cost between them is the gap between reading a list and exploring a factorial space, and there is nothing in between: no polynomial test in this collection catches a failure of the non-crossing rules. That is where the hardness of the problem actually bites, and the twenty-six patterns refused by nothing in the ladder above are mostly patterns waiting on a search that will not finish.

And there is no test at all for the direction that would matter most. Every one of the five says no or says nothing. None of them says yes about a pattern too large to search, so a tessellation patch that has a consistent lettering, places perfectly and passes every condition is still a pattern this collection cannot certify as foldable. A reader who folds one has better evidence than any of this machinery can produce.

That last figure is the one to keep. A refusal reporting zero looks like a refusal that is not needed, and here it was a refusal whose test set had been built entirely out of patterns that could not exhibit the fault. The count went from nought to one by adding five patterns, and it would have gone higher by adding five that had not been repaired first.