FAILURE MAP
← Case archive

FA-88451 / Mesh topology invariants / Open access

Repeated directed half-edges overwrite each other · case 01

A mesh with two faces using the same directed edge is accepted and navigation silently follows the later face.

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

ROOT CAUSE

The duplicate check is missing when inserting half-edges.

VERIFIED REPAIR

Reject any directed half-edge seen before, across all faces.

Unsuccessful approach: Checking only duplicates within the same face misses the flipped-neighbour case.

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])
            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]]], ['flipped duplicate', [[[[0, 1, 2], [0, 1, 3]], [[0, 1]]]], ['duplicate-halfedge', [0, 1]]], ['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]]]], ['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]]]]]
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 fixtureActualExpectedOutcome
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[[1, [1, 3], [3, 0], None]]['duplicate-halfedge', [0, 1]]Failed
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 / d83aa235ae256903be17993910db59f84b2748c23cfa176519ab61b0a77ea35d

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 and H[h][0]==fi: 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]]], ['flipped duplicate', [[[[0, 1, 2], [0, 1, 3]], [[0, 1]]]], ['duplicate-halfedge', [0, 1]]], ['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]]]], ['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]]]]]
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 fixtureActualExpectedOutcome
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[[1, [1, 3], [3, 0], None]]['duplicate-halfedge', [0, 1]]Failed
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 / 09962319d9fedbf838a6449e88089239e421376c08e55d7c96ffcf0f6442fff6

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]]], ['flipped duplicate', [[[[0, 1, 2], [0, 1, 3]], [[0, 1]]]], ['duplicate-halfedge', [0, 1]]], ['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]]]], ['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]]]]]
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 fixtureActualExpectedOutcome
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 / a7c347e219c2840e59c184b96ea0ead1e5ebc9c29eba6e3e8f123800f1c95813

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.310235+00:00.

Case digest / 61c476f8b5935afc36d1891b073c95ebae20c69f40f98349d0723bc2832be634