FA-88456 / Mesh topology invariants / Open access

Queries for absent half-edges return the reversed half-edge · case 01

Asking for a non-existent direction silently returns data for its twin.

Verified by executionVariant 1 · 7 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

A missing half-edge query falls back to (b,a).

VERIFIED REPAIR

Return null when the queried directed half-edge does not exist.

Unsuccessful approach: Returning an empty list is not the null sentinel.

Case contract

Input [faces, queries]. Build half-edges (f[i], f[i+1 mod n]) with face index, next and prev half-edges. A repeated directed half-edge returns ["duplicate-halfedge", [a,b]]. For each query (a,b) return null if it is not a half-edge, else [face, next, prev, twin] with twin [b,a] when that directed half-edge exists, else null.

Why this case matters

Mesh processing pipelines (remeshing, export, simulation, printing) trust these topological counts and adjacency answers; a wrong invariant silently accepts broken meshes or rejects valid ones.

1 / The failure

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    faces,queries=x
    H={}
    for fi,f in enumerate(faces):
        n=len(f)
        for i in range(n):
            h=(f[i],f[(i+1)%n])
            if h in H: return ['duplicate-halfedge',list(h)]
            H[h]=(fi,(f[(i+1)%n],f[(i+2)%n]),(f[(i-1)%n],f[i]))
    out=[]
    for a,b in queries:
        h=(a,b)
        if h not in H and (b,a) in H: h=(b,a)
        if h not in H:
            out.append(None)
            continue
        fi,nx,pv=H[h]
        tw=[b,a] if (b,a) in H else None
        out.append([fi,list(nx),list(pv),tw])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['quad pair', [[[[0, 1, 2, 3], [3, 2, 4, 5]], [[0, 1], [2, 3], [3, 2], [4, 5], [1, 0]]]], [[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], None]], ['triangle pair', [[[[0, 1, 2], [2, 1, 3]], [[1, 2], [2, 1], [3, 2], [0, 1]]]], [[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]], ['triangle then quad', [[[[0, 1, 2], [2, 1, 3, 4]], [[1, 3], [3, 4], [2, 1], [4, 2]]]], [[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]], ['quad then triangle', [[[[0, 1, 2, 3], [3, 2, 4]], [[0, 1], [2, 4], [3, 2], [2, 3]]]], [[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]], ['tetrahedron', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], [[0, 2], [2, 0], [1, 3], [3, 1]]]], [[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]], ['flipped duplicate', [[[[0, 1, 2], [0, 1, 3]], [[0, 1]]]], ['duplicate-halfedge', [0, 1]]], ['quad diagonal not twin', [[[[0, 1, 2, 3], [0, 2, 4]], [[0, 2], [2, 4], [1, 2]]]], [[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]]], [['quad then triangle', [[[[0, 1, 2, 3], [3, 2, 4]], [[0, 1], [2, 4], [3, 2], [2, 3]]]], [[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]], ['tetrahedron', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], [[0, 2], [2, 0], [1, 3], [3, 1]]]], [[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]], ['flipped duplicate', [[[[0, 1, 2], [0, 1, 3]], [[0, 1]]]], ['duplicate-halfedge', [0, 1]]], ['quad diagonal not twin', [[[[0, 1, 2, 3], [0, 2, 4]], [[0, 2], [2, 4], [1, 2]]]], [[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]], ['pentagon', [[[[0, 1, 2, 3, 4]], [[3, 4], [4, 0], [0, 4]]]], [[0, [4, 0], [2, 3], None], [0, [0, 1], [3, 4], None], None]], ['cube', [[[[0, 3, 2, 1], [4, 5, 6, 7], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]], [[0, 3], [3, 0], [4, 5], [7, 6]]]], [[0, [3, 2], [1, 0], [3, 0]], [5, [0, 4], [7, 3], [0, 3]], [1, [5, 6], [7, 4], [5, 4]], [4, [6, 2], [3, 7], [6, 7]]]], ['missing queries', [[[[0, 1, 2], [2, 1, 3]], [[0, 3], [3, 0], [2, 0]]]], [None, None, [0, [0, 1], [1, 2], None]]]], [['quad pair', [[[[0, 1, 2, 3], [3, 2, 4, 5]], [[0, 1], [2, 3], [3, 2], [4, 5], [1, 0]]]], [[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], None]], ['triangle pair', [[[[0, 1, 2], [2, 1, 3]], [[1, 2], [2, 1], [3, 2], [0, 1]]]], [[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]], ['triangle then quad', [[[[0, 1, 2], [2, 1, 3, 4]], [[1, 3], [3, 4], [2, 1], [4, 2]]]], [[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]], ['quad then triangle', [[[[0, 1, 2, 3], [3, 2, 4]], [[0, 1], [2, 4], [3, 2], [2, 3]]]], [[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]], ['pentagon', [[[[0, 1, 2, 3, 4]], [[3, 4], [4, 0], [0, 4]]]], [[0, [4, 0], [2, 3], None], [0, [0, 1], [3, 4], None], None]], ['cube', [[[[0, 3, 2, 1], [4, 5, 6, 7], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]], [[0, 3], [3, 0], [4, 5], [7, 6]]]], [[0, [3, 2], [1, 0], [3, 0]], [5, [0, 4], [7, 3], [0, 3]], [1, [5, 6], [7, 4], [5, 4]], [4, [6, 2], [3, 7], [6, 7]]]], ['missing queries', [[[[0, 1, 2], [2, 1, 3]], [[0, 3], [3, 0], [2, 0]]]], [None, None, [0, [0, 1], [1, 2], None]]]], [['quad pair', [[[[0, 1, 2, 3], [3, 2, 4, 5]], [[0, 1], [2, 3], [3, 2], [4, 5], [1, 0]]]], [[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], None]], ['triangle then quad', [[[[0, 1, 2], [2, 1, 3, 4]], [[1, 3], [3, 4], [2, 1], [4, 2]]]], [[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]], ['quad then triangle', [[[[0, 1, 2, 3], [3, 2, 4]], [[0, 1], [2, 4], [3, 2], [2, 3]]]], [[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]], ['tetrahedron', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], [[0, 2], [2, 0], [1, 3], [3, 1]]]], [[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]], ['flipped duplicate', [[[[0, 1, 2], [0, 1, 3]], [[0, 1]]]], ['duplicate-halfedge', [0, 1]]], ['quad diagonal not twin', [[[[0, 1, 2, 3], [0, 2, 4]], [[0, 2], [2, 4], [1, 2]]]], [[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]], ['pentagon', [[[[0, 1, 2, 3, 4]], [[3, 4], [4, 0], [0, 4]]]], [[0, [4, 0], [2, 3], None], [0, [0, 1], [3, 4], None], None]]], [['quad pair', [[[[0, 1, 2, 3], [3, 2, 4, 5]], [[0, 1], [2, 3], [3, 2], [4, 5], [1, 0]]]], [[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], None]], ['triangle pair', [[[[0, 1, 2], [2, 1, 3]], [[1, 2], [2, 1], [3, 2], [0, 1]]]], [[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]], ['flipped duplicate', [[[[0, 1, 2], [0, 1, 3]], [[0, 1]]]], ['duplicate-halfedge', [0, 1]]], ['quad diagonal not twin', [[[[0, 1, 2, 3], [0, 2, 4]], [[0, 2], [2, 4], [1, 2]]]], [[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]], ['pentagon', [[[[0, 1, 2, 3, 4]], [[3, 4], [4, 0], [0, 4]]]], [[0, [4, 0], [2, 3], None], [0, [0, 1], [3, 4], None], None]], ['cube', [[[[0, 3, 2, 1], [4, 5, 6, 7], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]], [[0, 3], [3, 0], [4, 5], [7, 6]]]], [[0, [3, 2], [1, 0], [3, 0]], [5, [0, 4], [7, 3], [0, 3]], [1, [5, 6], [7, 4], [5, 4]], [4, [6, 2], [3, 7], [6, 7]]]], ['missing queries', [[[[0, 1, 2], [2, 1, 3]], [[0, 3], [3, 0], [2, 0]]]], [None, None, [0, [0, 1], [1, 2], None]]]]]
for label, args, expected in fixtures[N-1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
quad pair	`[[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], [0, [1, 2], [3, 0], [0, 1]]]`	`[[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], None]`	Failed
triangle pair	`[[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]`	`[[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]`	Passed
triangle then quad	`[[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]`	`[[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]`	Passed
quad then triangle	`[[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]`	`[[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]`	Passed
tetrahedron	`[[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]`	`[[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]`	Passed
flipped duplicate	`['duplicate-halfedge', [0, 1]]`	`['duplicate-halfedge', [0, 1]]`	Passed
quad diagonal not twin	`[[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]`	`[[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]`	Passed

SHA-256 / 6986d5df10374237776ab94b1c8f35ca1b180f0172596bac6d68bb6883a8bf49

2 / The unsuccessful fix

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    faces,queries=x
    H={}
    for fi,f in enumerate(faces):
        n=len(f)
        for i in range(n):
            h=(f[i],f[(i+1)%n])
            if h in H: return ['duplicate-halfedge',list(h)]
            H[h]=(fi,(f[(i+1)%n],f[(i+2)%n]),(f[(i-1)%n],f[i]))
    out=[]
    for a,b in queries:
        h=(a,b)
        if h not in H:
            out.append([])
            continue
        fi,nx,pv=H[h]
        tw=[b,a] if (b,a) in H else None
        out.append([fi,list(nx),list(pv),tw])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['quad pair', [[[[0, 1, 2, 3], [3, 2, 4, 5]], [[0, 1], [2, 3], [3, 2], [4, 5], [1, 0]]]], [[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], None]], ['triangle pair', [[[[0, 1, 2], [2, 1, 3]], [[1, 2], [2, 1], [3, 2], [0, 1]]]], [[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]], ['triangle then quad', [[[[0, 1, 2], [2, 1, 3, 4]], [[1, 3], [3, 4], [2, 1], [4, 2]]]], [[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]], ['quad then triangle', [[[[0, 1, 2, 3], [3, 2, 4]], [[0, 1], [2, 4], [3, 2], [2, 3]]]], [[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]], ['tetrahedron', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], [[0, 2], [2, 0], [1, 3], [3, 1]]]], [[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]], ['flipped duplicate', [[[[0, 1, 2], [0, 1, 3]], [[0, 1]]]], ['duplicate-halfedge', [0, 1]]], ['quad diagonal not twin', [[[[0, 1, 2, 3], [0, 2, 4]], [[0, 2], [2, 4], [1, 2]]]], [[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]]], [['quad then triangle', [[[[0, 1, 2, 3], [3, 2, 4]], [[0, 1], [2, 4], [3, 2], [2, 3]]]], [[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]], ['tetrahedron', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], [[0, 2], [2, 0], [1, 3], [3, 1]]]], [[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]], ['flipped duplicate', [[[[0, 1, 2], [0, 1, 3]], [[0, 1]]]], ['duplicate-halfedge', [0, 1]]], ['quad diagonal not twin', [[[[0, 1, 2, 3], [0, 2, 4]], [[0, 2], [2, 4], [1, 2]]]], [[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]], ['pentagon', [[[[0, 1, 2, 3, 4]], [[3, 4], [4, 0], [0, 4]]]], [[0, [4, 0], [2, 3], None], [0, [0, 1], [3, 4], None], None]], ['cube', [[[[0, 3, 2, 1], [4, 5, 6, 7], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]], [[0, 3], [3, 0], [4, 5], [7, 6]]]], [[0, [3, 2], [1, 0], [3, 0]], [5, [0, 4], [7, 3], [0, 3]], [1, [5, 6], [7, 4], [5, 4]], [4, [6, 2], [3, 7], [6, 7]]]], ['missing queries', [[[[0, 1, 2], [2, 1, 3]], [[0, 3], [3, 0], [2, 0]]]], [None, None, [0, [0, 1], [1, 2], None]]]], [['quad pair', [[[[0, 1, 2, 3], [3, 2, 4, 5]], [[0, 1], [2, 3], [3, 2], [4, 5], [1, 0]]]], [[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], None]], ['triangle pair', [[[[0, 1, 2], [2, 1, 3]], [[1, 2], [2, 1], [3, 2], [0, 1]]]], [[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]], ['triangle then quad', [[[[0, 1, 2], [2, 1, 3, 4]], [[1, 3], [3, 4], [2, 1], [4, 2]]]], [[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]], ['quad then triangle', [[[[0, 1, 2, 3], [3, 2, 4]], [[0, 1], [2, 4], [3, 2], [2, 3]]]], [[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]], ['pentagon', [[[[0, 1, 2, 3, 4]], [[3, 4], [4, 0], [0, 4]]]], [[0, [4, 0], [2, 3], None], [0, [0, 1], [3, 4], None], None]], ['cube', [[[[0, 3, 2, 1], [4, 5, 6, 7], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]], [[0, 3], [3, 0], [4, 5], [7, 6]]]], [[0, [3, 2], [1, 0], [3, 0]], [5, [0, 4], [7, 3], [0, 3]], [1, [5, 6], [7, 4], [5, 4]], [4, [6, 2], [3, 7], [6, 7]]]], ['missing queries', [[[[0, 1, 2], [2, 1, 3]], [[0, 3], [3, 0], [2, 0]]]], [None, None, [0, [0, 1], [1, 2], None]]]], [['quad pair', [[[[0, 1, 2, 3], [3, 2, 4, 5]], [[0, 1], [2, 3], [3, 2], [4, 5], [1, 0]]]], [[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], None]], ['triangle then quad', [[[[0, 1, 2], [2, 1, 3, 4]], [[1, 3], [3, 4], [2, 1], [4, 2]]]], [[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]], ['quad then triangle', [[[[0, 1, 2, 3], [3, 2, 4]], [[0, 1], [2, 4], [3, 2], [2, 3]]]], [[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]], ['tetrahedron', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], [[0, 2], [2, 0], [1, 3], [3, 1]]]], [[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]], ['flipped duplicate', [[[[0, 1, 2], [0, 1, 3]], [[0, 1]]]], ['duplicate-halfedge', [0, 1]]], ['quad diagonal not twin', [[[[0, 1, 2, 3], [0, 2, 4]], [[0, 2], [2, 4], [1, 2]]]], [[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]], ['pentagon', [[[[0, 1, 2, 3, 4]], [[3, 4], [4, 0], [0, 4]]]], [[0, [4, 0], [2, 3], None], [0, [0, 1], [3, 4], None], None]]], [['quad pair', [[[[0, 1, 2, 3], [3, 2, 4, 5]], [[0, 1], [2, 3], [3, 2], [4, 5], [1, 0]]]], [[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], None]], ['triangle pair', [[[[0, 1, 2], [2, 1, 3]], [[1, 2], [2, 1], [3, 2], [0, 1]]]], [[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]], ['flipped duplicate', [[[[0, 1, 2], [0, 1, 3]], [[0, 1]]]], ['duplicate-halfedge', [0, 1]]], ['quad diagonal not twin', [[[[0, 1, 2, 3], [0, 2, 4]], [[0, 2], [2, 4], [1, 2]]]], [[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]], ['pentagon', [[[[0, 1, 2, 3, 4]], [[3, 4], [4, 0], [0, 4]]]], [[0, [4, 0], [2, 3], None], [0, [0, 1], [3, 4], None], None]], ['cube', [[[[0, 3, 2, 1], [4, 5, 6, 7], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]], [[0, 3], [3, 0], [4, 5], [7, 6]]]], [[0, [3, 2], [1, 0], [3, 0]], [5, [0, 4], [7, 3], [0, 3]], [1, [5, 6], [7, 4], [5, 4]], [4, [6, 2], [3, 7], [6, 7]]]], ['missing queries', [[[[0, 1, 2], [2, 1, 3]], [[0, 3], [3, 0], [2, 0]]]], [None, None, [0, [0, 1], [1, 2], None]]]]]
for label, args, expected in fixtures[N-1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
quad pair	`[[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], []]`	`[[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], None]`	Failed
triangle pair	`[[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]`	`[[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]`	Passed
triangle then quad	`[[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]`	`[[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]`	Passed
quad then triangle	`[[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]`	`[[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]`	Passed
tetrahedron	`[[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]`	`[[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]`	Passed
flipped duplicate	`['duplicate-halfedge', [0, 1]]`	`['duplicate-halfedge', [0, 1]]`	Passed
quad diagonal not twin	`[[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]`	`[[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]`	Passed

SHA-256 / 0880c8d9db50f6c135ab32649f5103ae2f98e72536c647956eafcd7c656200cb

3 / The verified repair

Exit 0

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    faces,queries=x
    H={}
    for fi,f in enumerate(faces):
        n=len(f)
        for i in range(n):
            h=(f[i],f[(i+1)%n])
            if h in H: return ['duplicate-halfedge',list(h)]
            H[h]=(fi,(f[(i+1)%n],f[(i+2)%n]),(f[(i-1)%n],f[i]))
    out=[]
    for a,b in queries:
        h=(a,b)
        if h not in H:
            out.append(None)
            continue
        fi,nx,pv=H[h]
        tw=[b,a] if (b,a) in H else None
        out.append([fi,list(nx),list(pv),tw])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['quad pair', [[[[0, 1, 2, 3], [3, 2, 4, 5]], [[0, 1], [2, 3], [3, 2], [4, 5], [1, 0]]]], [[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], None]], ['triangle pair', [[[[0, 1, 2], [2, 1, 3]], [[1, 2], [2, 1], [3, 2], [0, 1]]]], [[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]], ['triangle then quad', [[[[0, 1, 2], [2, 1, 3, 4]], [[1, 3], [3, 4], [2, 1], [4, 2]]]], [[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]], ['quad then triangle', [[[[0, 1, 2, 3], [3, 2, 4]], [[0, 1], [2, 4], [3, 2], [2, 3]]]], [[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]], ['tetrahedron', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], [[0, 2], [2, 0], [1, 3], [3, 1]]]], [[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]], ['flipped duplicate', [[[[0, 1, 2], [0, 1, 3]], [[0, 1]]]], ['duplicate-halfedge', [0, 1]]], ['quad diagonal not twin', [[[[0, 1, 2, 3], [0, 2, 4]], [[0, 2], [2, 4], [1, 2]]]], [[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]]], [['quad then triangle', [[[[0, 1, 2, 3], [3, 2, 4]], [[0, 1], [2, 4], [3, 2], [2, 3]]]], [[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]], ['tetrahedron', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], [[0, 2], [2, 0], [1, 3], [3, 1]]]], [[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]], ['flipped duplicate', [[[[0, 1, 2], [0, 1, 3]], [[0, 1]]]], ['duplicate-halfedge', [0, 1]]], ['quad diagonal not twin', [[[[0, 1, 2, 3], [0, 2, 4]], [[0, 2], [2, 4], [1, 2]]]], [[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]], ['pentagon', [[[[0, 1, 2, 3, 4]], [[3, 4], [4, 0], [0, 4]]]], [[0, [4, 0], [2, 3], None], [0, [0, 1], [3, 4], None], None]], ['cube', [[[[0, 3, 2, 1], [4, 5, 6, 7], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]], [[0, 3], [3, 0], [4, 5], [7, 6]]]], [[0, [3, 2], [1, 0], [3, 0]], [5, [0, 4], [7, 3], [0, 3]], [1, [5, 6], [7, 4], [5, 4]], [4, [6, 2], [3, 7], [6, 7]]]], ['missing queries', [[[[0, 1, 2], [2, 1, 3]], [[0, 3], [3, 0], [2, 0]]]], [None, None, [0, [0, 1], [1, 2], None]]]], [['quad pair', [[[[0, 1, 2, 3], [3, 2, 4, 5]], [[0, 1], [2, 3], [3, 2], [4, 5], [1, 0]]]], [[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], None]], ['triangle pair', [[[[0, 1, 2], [2, 1, 3]], [[1, 2], [2, 1], [3, 2], [0, 1]]]], [[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]], ['triangle then quad', [[[[0, 1, 2], [2, 1, 3, 4]], [[1, 3], [3, 4], [2, 1], [4, 2]]]], [[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]], ['quad then triangle', [[[[0, 1, 2, 3], [3, 2, 4]], [[0, 1], [2, 4], [3, 2], [2, 3]]]], [[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]], ['pentagon', [[[[0, 1, 2, 3, 4]], [[3, 4], [4, 0], [0, 4]]]], [[0, [4, 0], [2, 3], None], [0, [0, 1], [3, 4], None], None]], ['cube', [[[[0, 3, 2, 1], [4, 5, 6, 7], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]], [[0, 3], [3, 0], [4, 5], [7, 6]]]], [[0, [3, 2], [1, 0], [3, 0]], [5, [0, 4], [7, 3], [0, 3]], [1, [5, 6], [7, 4], [5, 4]], [4, [6, 2], [3, 7], [6, 7]]]], ['missing queries', [[[[0, 1, 2], [2, 1, 3]], [[0, 3], [3, 0], [2, 0]]]], [None, None, [0, [0, 1], [1, 2], None]]]], [['quad pair', [[[[0, 1, 2, 3], [3, 2, 4, 5]], [[0, 1], [2, 3], [3, 2], [4, 5], [1, 0]]]], [[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], None]], ['triangle then quad', [[[[0, 1, 2], [2, 1, 3, 4]], [[1, 3], [3, 4], [2, 1], [4, 2]]]], [[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]], ['quad then triangle', [[[[0, 1, 2, 3], [3, 2, 4]], [[0, 1], [2, 4], [3, 2], [2, 3]]]], [[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]], ['tetrahedron', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], [[0, 2], [2, 0], [1, 3], [3, 1]]]], [[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]], ['flipped duplicate', [[[[0, 1, 2], [0, 1, 3]], [[0, 1]]]], ['duplicate-halfedge', [0, 1]]], ['quad diagonal not twin', [[[[0, 1, 2, 3], [0, 2, 4]], [[0, 2], [2, 4], [1, 2]]]], [[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]], ['pentagon', [[[[0, 1, 2, 3, 4]], [[3, 4], [4, 0], [0, 4]]]], [[0, [4, 0], [2, 3], None], [0, [0, 1], [3, 4], None], None]]], [['quad pair', [[[[0, 1, 2, 3], [3, 2, 4, 5]], [[0, 1], [2, 3], [3, 2], [4, 5], [1, 0]]]], [[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], None]], ['triangle pair', [[[[0, 1, 2], [2, 1, 3]], [[1, 2], [2, 1], [3, 2], [0, 1]]]], [[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]], ['flipped duplicate', [[[[0, 1, 2], [0, 1, 3]], [[0, 1]]]], ['duplicate-halfedge', [0, 1]]], ['quad diagonal not twin', [[[[0, 1, 2, 3], [0, 2, 4]], [[0, 2], [2, 4], [1, 2]]]], [[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]], ['pentagon', [[[[0, 1, 2, 3, 4]], [[3, 4], [4, 0], [0, 4]]]], [[0, [4, 0], [2, 3], None], [0, [0, 1], [3, 4], None], None]], ['cube', [[[[0, 3, 2, 1], [4, 5, 6, 7], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]], [[0, 3], [3, 0], [4, 5], [7, 6]]]], [[0, [3, 2], [1, 0], [3, 0]], [5, [0, 4], [7, 3], [0, 3]], [1, [5, 6], [7, 4], [5, 4]], [4, [6, 2], [3, 7], [6, 7]]]], ['missing queries', [[[[0, 1, 2], [2, 1, 3]], [[0, 3], [3, 0], [2, 0]]]], [None, None, [0, [0, 1], [1, 2], None]]]]]
for label, args, expected in fixtures[N-1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
quad pair	`[[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], None]`	`[[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], None]`	Passed
triangle pair	`[[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]`	`[[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]`	Passed
triangle then quad	`[[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]`	`[[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]`	Passed
quad then triangle	`[[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]`	`[[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]`	Passed
tetrahedron	`[[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]`	`[[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]`	Passed
flipped duplicate	`['duplicate-halfedge', [0, 1]]`	`['duplicate-halfedge', [0, 1]]`	Passed
quad diagonal not twin	`[[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]`	`[[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]`	Passed

SHA-256 / a7633e6133f07e3f13f09ccf157578abcc58372cbf4d44395103dc8dd5d6506c

Verification & scope

Pure combinatorial teaching model over integer face lists with a stipulated contract; no geometry kernel or file format is implied. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:51:08.306963+00:00.

Case digest / 9072106005b115f3369010fc6f3a9b1c94e2ea4ea6ab6196989b02d76fc62909