broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    faces=x
    link={}
    for f in faces:
        for i in range(3):
            v=f[i]
            a=f[(i+1)%3]
            b=f[(i+2)%3]
            link.setdefault(v,[]).append((a,b))
    out={}
    for v in sorted(link):
        es=link[v]
        deg={}
        for a,b in es:
            deg[a]=deg.get(a,0)+1
            deg[b]=deg.get(b,0)+1
        if any(d>2 for d in deg.values()):
            out[str(v)]='nonmanifold'
            continue
        adj={}
        for a,b in es:
            adj.setdefault(a,[]).append(b)
            adj.setdefault(b,[]).append(a)
        start=next(iter(adj))
        stack=[start]
        seen={start}
        while stack:
            u=stack.pop()
            for w in adj.get(u,[]):
                if w not in seen:
                    seen.add(w)
                    stack.append(w)
        if len(seen)!=len(es): out[str(v)]='nonmanifold'
        elif all(d==2 for d in deg.values()): out[str(v)]='interior'
        else: out[str(v)]='boundary'
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior'}], ['disk', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]]], {'0': 'interior', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary'}], ['fan', [[[0, 1, 2], [0, 2, 3], [0, 3, 4]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], {'0': 'nonmanifold', '1': 'nonmanifold', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['octahedron', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior'}], ['torus', [[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior', '6': 'interior', '7': 'interior', '8': 'interior'}]], [['fan', [[[0, 1, 2], [0, 2, 3], [0, 3, 4]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], {'0': 'nonmanifold', '1': 'nonmanifold', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['octahedron', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior'}], ['torus', [[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior', '6': 'interior', '7': 'interior', '8': 'interior'}], ['open cylinder', [[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary'}], ['triangle grid', [[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'interior', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}], ['double disk pinch', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [0, 6, 7], [0, 7, 8], [0, 8, 6]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}]], [['tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior'}], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['open cylinder', [[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary'}], ['triangle grid', [[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'interior', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}], ['double disk pinch', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [0, 6, 7], [0, 7, 8], [0, 8, 6]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}], ['single triangle', [[[0, 1, 2]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary'}], ['two triangles sharing edge', [[[0, 1, 2], [2, 1, 3]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary'}]], [['tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior'}], ['disk', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]]], {'0': 'interior', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary'}], ['fan', [[[0, 1, 2], [0, 2, 3], [0, 3, 4]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], {'0': 'nonmanifold', '1': 'nonmanifold', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['double disk pinch', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [0, 6, 7], [0, 7, 8], [0, 8, 6]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}], ['two triangles sharing edge', [[[0, 1, 2], [2, 1, 3]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary'}]], [['fan', [[[0, 1, 2], [0, 2, 3], [0, 3, 4]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], {'0': 'nonmanifold', '1': 'nonmanifold', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['octahedron', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior'}], ['torus', [[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior', '6': 'interior', '7': 'interior', '8': 'interior'}], ['open cylinder', [[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary'}], ['triangle grid', [[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'interior', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}]]]
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)

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    faces=x
    link={}
    for f in faces:
        for i in range(3):
            v=f[i]
            a=f[(i+1)%3]
            b=f[(i+2)%3]
            link.setdefault(v,[]).append((a,b))
    out={}
    for v in sorted(link):
        es=link[v]
        deg={}
        for a,b in es:
            deg[a]=deg.get(a,0)+1
            deg[b]=deg.get(b,0)+1
        if any(d>2 for d in deg.values()):
            out[str(v)]='nonmanifold'
            continue
        adj={}
        for a,b in es:
            adj.setdefault(a,[]).append(b)
            adj.setdefault(b,[]).append(a)
        start=next(iter(adj))
        stack=[start]
        seen={start}
        while stack:
            u=stack.pop()
            for w in adj.get(u,[]):
                if w not in seen:
                    seen.add(w)
                    stack.append(w)
        if len(seen)*2<len(adj): out[str(v)]='nonmanifold'
        elif all(d==2 for d in deg.values()): out[str(v)]='interior'
        else: out[str(v)]='boundary'
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior'}], ['disk', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]]], {'0': 'interior', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary'}], ['fan', [[[0, 1, 2], [0, 2, 3], [0, 3, 4]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], {'0': 'nonmanifold', '1': 'nonmanifold', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['octahedron', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior'}], ['torus', [[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior', '6': 'interior', '7': 'interior', '8': 'interior'}]], [['fan', [[[0, 1, 2], [0, 2, 3], [0, 3, 4]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], {'0': 'nonmanifold', '1': 'nonmanifold', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['octahedron', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior'}], ['torus', [[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior', '6': 'interior', '7': 'interior', '8': 'interior'}], ['open cylinder', [[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary'}], ['triangle grid', [[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'interior', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}], ['double disk pinch', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [0, 6, 7], [0, 7, 8], [0, 8, 6]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}]], [['tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior'}], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['open cylinder', [[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary'}], ['triangle grid', [[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'interior', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}], ['double disk pinch', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [0, 6, 7], [0, 7, 8], [0, 8, 6]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}], ['single triangle', [[[0, 1, 2]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary'}], ['two triangles sharing edge', [[[0, 1, 2], [2, 1, 3]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary'}]], [['tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior'}], ['disk', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]]], {'0': 'interior', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary'}], ['fan', [[[0, 1, 2], [0, 2, 3], [0, 3, 4]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], {'0': 'nonmanifold', '1': 'nonmanifold', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['double disk pinch', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [0, 6, 7], [0, 7, 8], [0, 8, 6]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}], ['two triangles sharing edge', [[[0, 1, 2], [2, 1, 3]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary'}]], [['fan', [[[0, 1, 2], [0, 2, 3], [0, 3, 4]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], {'0': 'nonmanifold', '1': 'nonmanifold', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['octahedron', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior'}], ['torus', [[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior', '6': 'interior', '7': 'interior', '8': 'interior'}], ['open cylinder', [[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary'}], ['triangle grid', [[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'interior', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}]]]
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)

prompt:
Ordinary boundary vertices are flagged non-manifold.

Input: triangle faces. For each referenced vertex v, its link is the set of opposite edges of incident triangles. v is "nonmanifold" if a link vertex has degree above 2 or the link graph is disconnected, "interior" if every link vertex has degree 2, else "boundary". Return {vertex string: class}.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    faces=x
    link={}
    for f in faces:
        for i in range(3):
            v=f[i]
            a=f[(i+1)%3]
            b=f[(i+2)%3]
            link.setdefault(v,[]).append((a,b))
    out={}
    for v in sorted(link):
        es=link[v]
        deg={}
        for a,b in es:
            deg[a]=deg.get(a,0)+1
            deg[b]=deg.get(b,0)+1
        if any(d>2 for d in deg.values()):
            out[str(v)]='nonmanifold'
            continue
        adj={}
        for a,b in es:
            adj.setdefault(a,[]).append(b)
            adj.setdefault(b,[]).append(a)
        start=next(iter(adj))
        stack=[start]
        seen={start}
        while stack:
            u=stack.pop()
            for w in adj.get(u,[]):
                if w not in seen:
                    seen.add(w)
                    stack.append(w)
        if len(seen)!=len(adj): out[str(v)]='nonmanifold'
        elif any(d==2 for d in deg.values()): out[str(v)]='interior'
        else: out[str(v)]='boundary'
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior'}], ['disk', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]]], {'0': 'interior', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary'}], ['fan', [[[0, 1, 2], [0, 2, 3], [0, 3, 4]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], {'0': 'nonmanifold', '1': 'nonmanifold', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['octahedron', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior'}], ['torus', [[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior', '6': 'interior', '7': 'interior', '8': 'interior'}]], [['fan', [[[0, 1, 2], [0, 2, 3], [0, 3, 4]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], {'0': 'nonmanifold', '1': 'nonmanifold', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['octahedron', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior'}], ['torus', [[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior', '6': 'interior', '7': 'interior', '8': 'interior'}], ['open cylinder', [[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary'}], ['triangle grid', [[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'interior', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}], ['double disk pinch', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [0, 6, 7], [0, 7, 8], [0, 8, 6]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}]], [['tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior'}], ['torus', [[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior', '6': 'interior', '7': 'interior', '8': 'interior'}], ['open cylinder', [[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary'}], ['triangle grid', [[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'interior', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}], ['double disk pinch', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [0, 6, 7], [0, 7, 8], [0, 8, 6]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}], ['single triangle', [[[0, 1, 2]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary'}], ['two triangles sharing edge', [[[0, 1, 2], [2, 1, 3]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary'}]], [['tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior'}], ['disk', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]]], {'0': 'interior', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary'}], ['fan', [[[0, 1, 2], [0, 2, 3], [0, 3, 4]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], {'0': 'nonmanifold', '1': 'nonmanifold', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['triangle grid', [[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'interior', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}], ['two triangles sharing edge', [[[0, 1, 2], [2, 1, 3]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary'}]], [['fan', [[[0, 1, 2], [0, 2, 3], [0, 3, 4]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], {'0': 'nonmanifold', '1': 'nonmanifold', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['octahedron', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior'}], ['torus', [[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior', '6': 'interior', '7': 'interior', '8': 'interior'}], ['open cylinder', [[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary'}], ['double disk pinch', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [0, 6, 7], [0, 7, 8], [0, 8, 6]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}]]]
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)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    faces=x
    link={}
    for f in faces:
        for i in range(3):
            v=f[i]
            a=f[(i+1)%3]
            b=f[(i+2)%3]
            link.setdefault(v,[]).append((a,b))
    out={}
    for v in sorted(link):
        es=link[v]
        deg={}
        for a,b in es:
            deg[a]=deg.get(a,0)+1
            deg[b]=deg.get(b,0)+1
        if any(d>2 for d in deg.values()):
            out[str(v)]='nonmanifold'
            continue
        adj={}
        for a,b in es:
            adj.setdefault(a,[]).append(b)
            adj.setdefault(b,[]).append(a)
        start=next(iter(adj))
        stack=[start]
        seen={start}
        while stack:
            u=stack.pop()
            for w in adj.get(u,[]):
                if w not in seen:
                    seen.add(w)
                    stack.append(w)
        if len(seen)!=len(adj): out[str(v)]='nonmanifold'
        elif len(es)>=3: out[str(v)]='interior'
        else: out[str(v)]='boundary'
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior'}], ['disk', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]]], {'0': 'interior', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary'}], ['fan', [[[0, 1, 2], [0, 2, 3], [0, 3, 4]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], {'0': 'nonmanifold', '1': 'nonmanifold', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['octahedron', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior'}], ['torus', [[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior', '6': 'interior', '7': 'interior', '8': 'interior'}]], [['fan', [[[0, 1, 2], [0, 2, 3], [0, 3, 4]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], {'0': 'nonmanifold', '1': 'nonmanifold', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['octahedron', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior'}], ['torus', [[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior', '6': 'interior', '7': 'interior', '8': 'interior'}], ['open cylinder', [[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary'}], ['triangle grid', [[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'interior', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}], ['double disk pinch', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [0, 6, 7], [0, 7, 8], [0, 8, 6]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}]], [['tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior'}], ['torus', [[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior', '6': 'interior', '7': 'interior', '8': 'interior'}], ['open cylinder', [[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary'}], ['triangle grid', [[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'interior', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}], ['double disk pinch', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [0, 6, 7], [0, 7, 8], [0, 8, 6]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}], ['single triangle', [[[0, 1, 2]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary'}], ['two triangles sharing edge', [[[0, 1, 2], [2, 1, 3]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary'}]], [['tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior'}], ['disk', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]]], {'0': 'interior', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary'}], ['fan', [[[0, 1, 2], [0, 2, 3], [0, 3, 4]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], {'0': 'nonmanifold', '1': 'nonmanifold', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['triangle grid', [[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'interior', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}], ['two triangles sharing edge', [[[0, 1, 2], [2, 1, 3]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary'}]], [['fan', [[[0, 1, 2], [0, 2, 3], [0, 3, 4]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], {'0': 'nonmanifold', '1': 'nonmanifold', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['octahedron', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior'}], ['torus', [[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior', '6': 'interior', '7': 'interior', '8': 'interior'}], ['open cylinder', [[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary'}], ['double disk pinch', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [0, 6, 7], [0, 7, 8], [0, 8, 6]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}]]]
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)

prompt:
Boundary vertices with more than one incident triangle are reported interior.

Input: triangle faces. For each referenced vertex v, its link is the set of opposite edges of incident triangles. v is "nonmanifold" if a link vertex has degree above 2 or the link graph is disconnected, "interior" if every link vertex has degree 2, else "boundary". Return {vertex string: class}.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    faces=x
    link={}
    for f in faces:
        for i in range(3):
            v=f[i]
            a=f[(i+1)%3]
            b=f[(i+2)%3]
            link.setdefault(v,[]).append((a,b))
    out={}
    for v in sorted(link):
        es=link[v]
        deg={}
        for a,b in es:
            deg[a]=deg.get(a,0)+1
            deg[b]=deg.get(b,0)+1
        if any(d>2 for d in deg.values()):
            out[str(v)]='nonmanifold'
            continue
        adj={}
        for a,b in es:
            adj.setdefault(a,[]).append(b)
            adj.setdefault(b,[])
        start=next(iter(adj))
        stack=[start]
        seen={start}
        while stack:
            u=stack.pop()
            for w in adj.get(u,[]):
                if w not in seen:
                    seen.add(w)
                    stack.append(w)
        if len(seen)!=len(adj): out[str(v)]='nonmanifold'
        elif all(d==2 for d in deg.values()): out[str(v)]='interior'
        else: out[str(v)]='boundary'
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior'}], ['disk', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]]], {'0': 'interior', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary'}], ['fan', [[[0, 1, 2], [0, 2, 3], [0, 3, 4]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], {'0': 'nonmanifold', '1': 'nonmanifold', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['octahedron', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior'}], ['torus', [[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior', '6': 'interior', '7': 'interior', '8': 'interior'}]], [['fan', [[[0, 1, 2], [0, 2, 3], [0, 3, 4]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], {'0': 'nonmanifold', '1': 'nonmanifold', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['octahedron', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior'}], ['torus', [[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior', '6': 'interior', '7': 'interior', '8': 'interior'}], ['open cylinder', [[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary'}], ['triangle grid', [[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'interior', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}], ['double disk pinch', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [0, 6, 7], [0, 7, 8], [0, 8, 6]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}]], [['tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior'}], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['open cylinder', [[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary'}], ['triangle grid', [[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'interior', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}], ['double disk pinch', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [0, 6, 7], [0, 7, 8], [0, 8, 6]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}], ['single triangle', [[[0, 1, 2]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary'}], ['two triangles sharing edge', [[[0, 1, 2], [2, 1, 3]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary'}]], [['tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior'}], ['disk', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]]], {'0': 'interior', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary'}], ['fan', [[[0, 1, 2], [0, 2, 3], [0, 3, 4]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], {'0': 'nonmanifold', '1': 'nonmanifold', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['triangle grid', [[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'interior', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}], ['two triangles sharing edge', [[[0, 1, 2], [2, 1, 3]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary'}]], [['fan', [[[0, 1, 2], [0, 2, 3], [0, 3, 4]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], {'0': 'nonmanifold', '1': 'nonmanifold', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['octahedron', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior'}], ['torus', [[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior', '6': 'interior', '7': 'interior', '8': 'interior'}], ['open cylinder', [[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary'}], ['double disk pinch', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [0, 6, 7], [0, 7, 8], [0, 8, 6]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}]]]
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)

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    faces=x
    link={}
    for f in faces:
        for i in range(3):
            v=f[i]
            a=f[(i+1)%3]
            b=f[(i+2)%3]
            link.setdefault(v,[]).append((a,b))
    out={}
    for v in sorted(link):
        es=link[v]
        deg={}
        for a,b in es:
            deg[a]=deg.get(a,0)+1
            deg[b]=deg.get(b,0)+1
        if any(d>2 for d in deg.values()):
            out[str(v)]='nonmanifold'
            continue
        adj={}
        for a,b in es:
            adj.setdefault(a,[]).append(b)
            adj.setdefault(b,[])
        start=min(adj)
        stack=[start]
        seen={start}
        while stack:
            u=stack.pop()
            for w in adj.get(u,[]):
                if w not in seen:
                    seen.add(w)
                    stack.append(w)
        if len(seen)!=len(adj): out[str(v)]='nonmanifold'
        elif all(d==2 for d in deg.values()): out[str(v)]='interior'
        else: out[str(v)]='boundary'
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior'}], ['disk', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]]], {'0': 'interior', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary'}], ['fan', [[[0, 1, 2], [0, 2, 3], [0, 3, 4]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], {'0': 'nonmanifold', '1': 'nonmanifold', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['octahedron', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior'}], ['torus', [[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior', '6': 'interior', '7': 'interior', '8': 'interior'}]], [['fan', [[[0, 1, 2], [0, 2, 3], [0, 3, 4]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], {'0': 'nonmanifold', '1': 'nonmanifold', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['octahedron', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior'}], ['torus', [[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior', '6': 'interior', '7': 'interior', '8': 'interior'}], ['open cylinder', [[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary'}], ['triangle grid', [[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'interior', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}], ['double disk pinch', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [0, 6, 7], [0, 7, 8], [0, 8, 6]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}]], [['tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior'}], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['open cylinder', [[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary'}], ['triangle grid', [[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'interior', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}], ['double disk pinch', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [0, 6, 7], [0, 7, 8], [0, 8, 6]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}], ['single triangle', [[[0, 1, 2]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary'}], ['two triangles sharing edge', [[[0, 1, 2], [2, 1, 3]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary'}]], [['tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior'}], ['disk', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]]], {'0': 'interior', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary'}], ['fan', [[[0, 1, 2], [0, 2, 3], [0, 3, 4]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], {'0': 'nonmanifold', '1': 'nonmanifold', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['triangle grid', [[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'interior', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}], ['two triangles sharing edge', [[[0, 1, 2], [2, 1, 3]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary'}]], [['fan', [[[0, 1, 2], [0, 2, 3], [0, 3, 4]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], {'0': 'nonmanifold', '1': 'nonmanifold', '2': 'boundary', '3': 'boundary', '4': 'boundary'}], ['octahedron', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior'}], ['torus', [[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]]], {'0': 'interior', '1': 'interior', '2': 'interior', '3': 'interior', '4': 'interior', '5': 'interior', '6': 'interior', '7': 'interior', '8': 'interior'}], ['open cylinder', [[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]]], {'0': 'boundary', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary'}], ['double disk pinch', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [0, 6, 7], [0, 7, 8], [0, 8, 6]]], {'0': 'nonmanifold', '1': 'boundary', '2': 'boundary', '3': 'boundary', '4': 'boundary', '5': 'boundary', '6': 'boundary', '7': 'boundary', '8': 'boundary'}]]]
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)

prompt:
Boundary fans whose start vertex is not the path tail are reported disconnected.

Input: triangle faces. For each referenced vertex v, its link is the set of opposite edges of incident triangles. v is "nonmanifold" if a link vertex has degree above 2 or the link graph is disconnected, "interior" if every link vertex has degree 2, else "boundary". Return {vertex string: class}.

split: open-access


prompt:
On quads and pentagons the next half-edge points back into the wrong corner.

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.

split: open-access


prompt:
prev returns the twin direction of the real previous half-edge.

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.

split: open-access


prompt:
Boundary half-edges report a twin.

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.

split: open-access


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

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.

split: open-access


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

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.

split: open-access


prompt:
Quad vertices gain the diagonal corner as a neighbour.

Input: polygon faces. Neighbours of a vertex are the other endpoints of its edges (consecutive face corners, skipping coincident pairs). Boundary vertices are endpoints of edges used by exactly one face. Irregular vertices have valence != 6 (interior) or != 4 (boundary). Return [{vertex: valence}, irregular count, sorted boundary vertices].

split: open-access


prompt:
Faces with a repeated corner raise the valence and create a fake boundary edge.

Input: polygon faces. Neighbours of a vertex are the other endpoints of its edges (consecutive face corners, skipping coincident pairs). Boundary vertices are endpoints of edges used by exactly one face. Irregular vertices have valence != 6 (interior) or != 4 (boundary). Return [{vertex: valence}, irregular count, sorted boundary vertices].

split: open-access


prompt:
Half the boundary vertices are treated as interior and judged against valence 6.

Input: polygon faces. Neighbours of a vertex are the other endpoints of its edges (consecutive face corners, skipping coincident pairs). Boundary vertices are endpoints of edges used by exactly one face. Irregular vertices have valence != 6 (interior) or != 4 (boundary). Return [{vertex: valence}, irregular count, sorted boundary vertices].

split: open-access


prompt:
Regular boundary vertices of a triangle grid are counted as irregular.

Input: polygon faces. Neighbours of a vertex are the other endpoints of its edges (consecutive face corners, skipping coincident pairs). Boundary vertices are endpoints of edges used by exactly one face. Irregular vertices have valence != 6 (interior) or != 4 (boundary). Return [{vertex: valence}, irregular count, sorted boundary vertices].

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    faces,a,b=x
    adj={}
    opp=[]
    ecount={}
    for f in faces:
        for i in range(3):
            u,v=f[i],f[(i+1)%3]
            adj.setdefault(u,set()).add(v)
            adj.setdefault(v,set()).add(u)
            k=(min(u,v),max(u,v))
            ecount[k]=ecount.get(k,0)+1
        if a in f and b in f:
            opp.append([w for w in f if w!=a and w!=b][0])
    k=(min(a,b),max(a,b))
    if k not in ecount: return [False,'no-edge']
    if not set(opp)<=(adj[a]&adj[b]): return [False,'link']
    bnd=set()
    for (u,v),c in ecount.items():
        if c==1: bnd.update((u,v))
    if a in bnd and b in bnd and ecount[k]!=1: return [False,'boundary']
    if not bnd and len(adj)<=4: return [False,'minimal']
    return [True,'ok']
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['disk spoke', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 0, 1]], [True, 'ok']], ['disk rim', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 1, 2]], [True, 'ok']], ['fan interior edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 0, 2]], [False, 'boundary']], ['fan missing edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 1, 3]], [False, 'no-edge']], ['tetrahedron edge', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], 0, 1]], [False, 'minimal']], ['octahedron edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 0, 1]], [True, 'ok']], ['open tetra cap', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1]], 1, 2]], [False, 'link']]], [['fan missing edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 1, 3]], [False, 'no-edge']], ['tetrahedron edge', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], 0, 1]], [False, 'minimal']], ['octahedron edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 0, 1]], [True, 'ok']], ['octahedron reversed', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 5, 2]], [True, 'ok']], ['open tetra cap', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1]], 1, 2]], [False, 'link']], ['two triangles shared edge', [[[[0, 1, 2], [2, 1, 3]], 1, 2]], [False, 'boundary']], ['torus edge', [[[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]], 0, 1]], [False, 'link']]], [['octahedron reversed', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 5, 2]], [True, 'ok']], ['open tetra cap', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1]], 1, 2]], [False, 'link']], ['two triangles shared edge', [[[[0, 1, 2], [2, 1, 3]], 1, 2]], [False, 'boundary']], ['two triangles rim edge', [[[[0, 1, 2], [2, 1, 3]], 0, 1]], [True, 'ok']], ['torus edge', [[[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]], 0, 1]], [False, 'link']], ['cylinder rung', [[[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]], 0, 5]], [False, 'boundary']], ['strip over-constrained', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 4]], 1, 3]], [False, 'link']]], [['open tetra cap', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1]], 1, 2]], [False, 'link']], ['torus edge', [[[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]], 0, 1]], [False, 'link']], ['cylinder rung', [[[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]], 0, 5]], [False, 'boundary']], ['strip over-constrained', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 4]], 1, 3]], [False, 'link']], ['grid diagonal', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 0, 4]], [True, 'ok']], ['grid interior spoke', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 4, 5]], [True, 'ok']], ['rotated face order', [[[[2, 0, 1], [3, 0, 2]], 0, 2]], [False, 'boundary']]], [['disk spoke', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 0, 1]], [True, 'ok']], ['disk rim', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 1, 2]], [True, 'ok']], ['fan interior edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 0, 2]], [False, 'boundary']], ['open tetra cap', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1]], 1, 2]], [False, 'link']], ['torus edge', [[[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]], 0, 1]], [False, 'link']], ['grid interior spoke', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 4, 5]], [True, 'ok']], ['rotated face order', [[[[2, 0, 1], [3, 0, 2]], 0, 2]], [False, 'boundary']]]]
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)

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    faces,a,b=x
    adj={}
    opp=[]
    ecount={}
    for f in faces:
        for i in range(3):
            u,v=f[i],f[(i+1)%3]
            adj.setdefault(u,set()).add(v)
            adj.setdefault(v,set()).add(u)
            k=(min(u,v),max(u,v))
            ecount[k]=ecount.get(k,0)+1
        if a in f and b in f:
            opp.append([w for w in f if w!=a and w!=b][0])
    k=(min(a,b),max(a,b))
    if k not in ecount: return [False,'no-edge']
    if len(adj[a]&adj[b])>2: return [False,'link']
    bnd=set()
    for (u,v),c in ecount.items():
        if c==1: bnd.update((u,v))
    if a in bnd and b in bnd and ecount[k]!=1: return [False,'boundary']
    if not bnd and len(adj)<=4: return [False,'minimal']
    return [True,'ok']
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['disk spoke', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 0, 1]], [True, 'ok']], ['disk rim', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 1, 2]], [True, 'ok']], ['fan interior edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 0, 2]], [False, 'boundary']], ['fan missing edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 1, 3]], [False, 'no-edge']], ['tetrahedron edge', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], 0, 1]], [False, 'minimal']], ['octahedron edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 0, 1]], [True, 'ok']], ['open tetra cap', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1]], 1, 2]], [False, 'link']]], [['fan missing edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 1, 3]], [False, 'no-edge']], ['tetrahedron edge', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], 0, 1]], [False, 'minimal']], ['octahedron edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 0, 1]], [True, 'ok']], ['octahedron reversed', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 5, 2]], [True, 'ok']], ['open tetra cap', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1]], 1, 2]], [False, 'link']], ['two triangles shared edge', [[[[0, 1, 2], [2, 1, 3]], 1, 2]], [False, 'boundary']], ['torus edge', [[[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]], 0, 1]], [False, 'link']]], [['octahedron reversed', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 5, 2]], [True, 'ok']], ['open tetra cap', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1]], 1, 2]], [False, 'link']], ['two triangles shared edge', [[[[0, 1, 2], [2, 1, 3]], 1, 2]], [False, 'boundary']], ['two triangles rim edge', [[[[0, 1, 2], [2, 1, 3]], 0, 1]], [True, 'ok']], ['torus edge', [[[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]], 0, 1]], [False, 'link']], ['cylinder rung', [[[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]], 0, 5]], [False, 'boundary']], ['strip over-constrained', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 4]], 1, 3]], [False, 'link']]], [['open tetra cap', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1]], 1, 2]], [False, 'link']], ['torus edge', [[[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]], 0, 1]], [False, 'link']], ['cylinder rung', [[[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]], 0, 5]], [False, 'boundary']], ['strip over-constrained', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 4]], 1, 3]], [False, 'link']], ['grid diagonal', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 0, 4]], [True, 'ok']], ['grid interior spoke', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 4, 5]], [True, 'ok']], ['rotated face order', [[[[2, 0, 1], [3, 0, 2]], 0, 2]], [False, 'boundary']]], [['disk spoke', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 0, 1]], [True, 'ok']], ['disk rim', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 1, 2]], [True, 'ok']], ['fan interior edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 0, 2]], [False, 'boundary']], ['open tetra cap', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1]], 1, 2]], [False, 'link']], ['torus edge', [[[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]], 0, 1]], [False, 'link']], ['grid interior spoke', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 4, 5]], [True, 'ok']], ['rotated face order', [[[[2, 0, 1], [3, 0, 2]], 0, 2]], [False, 'boundary']]]]
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)

prompt:
Collapses that would fuse two faces or pinch the surface are accepted.

Input [faces, a, b] for a triangle mesh. Collapsing edge (a,b) is checked in order: missing edge -> [false,"no-edge"]; common neighbours of a and b must equal the opposite vertices of the triangles on the edge -> else [false,"link"]; if a and b are both boundary vertices the edge itself must be a boundary edge -> else [false,"boundary"]; a closed mesh with 4 or fewer vertices -> [false,"minimal"]; otherwise [true,"ok"].

split: open-access


source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    faces,a,b=x
    adj={}
    opp=[]
    ecount={}
    for f in faces:
        for i in range(3):
            u,v=f[i],f[(i+1)%3]
            adj.setdefault(u,set()).add(v)
            adj.setdefault(v,set()).add(u)
            k=(min(u,v),max(u,v))
            ecount[k]=ecount.get(k,0)+1
        if a in f and b in f:
            opp.append([w for w in f if w!=a][0])
    k=(min(a,b),max(a,b))
    if k not in ecount: return [False,'no-edge']
    if (adj[a]&adj[b])!=set(opp): return [False,'link']
    bnd=set()
    for (u,v),c in ecount.items():
        if c==1: bnd.update((u,v))
    if a in bnd and b in bnd and ecount[k]!=1: return [False,'boundary']
    if not bnd and len(adj)<=4: return [False,'minimal']
    return [True,'ok']
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['disk spoke', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 0, 1]], [True, 'ok']], ['disk rim', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 1, 2]], [True, 'ok']], ['fan interior edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 0, 2]], [False, 'boundary']], ['fan missing edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 1, 3]], [False, 'no-edge']], ['tetrahedron edge', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], 0, 1]], [False, 'minimal']], ['octahedron edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 0, 1]], [True, 'ok']], ['octahedron reversed', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 5, 2]], [True, 'ok']]], [['disk rim', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 1, 2]], [True, 'ok']], ['fan interior edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 0, 2]], [False, 'boundary']], ['octahedron edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 0, 1]], [True, 'ok']], ['octahedron reversed', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 5, 2]], [True, 'ok']], ['open tetra cap', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1]], 1, 2]], [False, 'link']], ['two triangles shared edge', [[[[0, 1, 2], [2, 1, 3]], 1, 2]], [False, 'boundary']], ['two triangles rim edge', [[[[0, 1, 2], [2, 1, 3]], 0, 1]], [True, 'ok']]], [['fan interior edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 0, 2]], [False, 'boundary']], ['tetrahedron edge', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], 0, 1]], [False, 'minimal']], ['two triangles shared edge', [[[[0, 1, 2], [2, 1, 3]], 1, 2]], [False, 'boundary']], ['two triangles rim edge', [[[[0, 1, 2], [2, 1, 3]], 0, 1]], [True, 'ok']], ['torus edge', [[[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]], 0, 1]], [False, 'link']], ['cylinder rung', [[[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]], 0, 5]], [False, 'boundary']], ['strip over-constrained', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 4]], 1, 3]], [False, 'link']]], [['tetrahedron edge', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], 0, 1]], [False, 'minimal']], ['octahedron edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 0, 1]], [True, 'ok']], ['cylinder rung', [[[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]], 0, 5]], [False, 'boundary']], ['strip over-constrained', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 4]], 1, 3]], [False, 'link']], ['grid diagonal', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 0, 4]], [True, 'ok']], ['grid interior spoke', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 4, 5]], [True, 'ok']], ['rotated face order', [[[[2, 0, 1], [3, 0, 2]], 0, 2]], [False, 'boundary']]], [['disk spoke', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 0, 1]], [True, 'ok']], ['disk rim', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 1, 2]], [True, 'ok']], ['fan interior edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 0, 2]], [False, 'boundary']], ['octahedron edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 0, 1]], [True, 'ok']], ['octahedron reversed', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 5, 2]], [True, 'ok']], ['grid interior spoke', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 4, 5]], [True, 'ok']], ['rotated face order', [[[[2, 0, 1], [3, 0, 2]], 0, 2]], [False, 'boundary']]]]
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)

prompt:
When the edge is not stored in the first two corners the link check compares against a or b.

Input [faces, a, b] for a triangle mesh. Collapsing edge (a,b) is checked in order: missing edge -> [false,"no-edge"]; common neighbours of a and b must equal the opposite vertices of the triangles on the edge -> else [false,"link"]; if a and b are both boundary vertices the edge itself must be a boundary edge -> else [false,"boundary"]; a closed mesh with 4 or fewer vertices -> [false,"minimal"]; otherwise [true,"ok"].

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    faces,a,b=x
    adj={}
    opp=[]
    ecount={}
    for f in faces:
        for i in range(3):
            u,v=f[i],f[(i+1)%3]
            adj.setdefault(u,set()).add(v)
            adj.setdefault(v,set()).add(u)
            k=(min(u,v),max(u,v))
            ecount[k]=ecount.get(k,0)+1
        if a in f and b in f:
            opp.append([w for w in f if w!=a and w!=b][0])
    k=(min(a,b),max(a,b))
    if k not in ecount: return [False,'no-edge']
    if (adj[a]&adj[b])!=set(opp): return [False,'link']
    bnd=set()
    for (u,v),c in ecount.items():
        if c==1: bnd.update((u,v))
    if a in bnd and b in bnd and ecount[k]==1: return [False,'boundary']
    if not bnd and len(adj)<=4: return [False,'minimal']
    return [True,'ok']
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['disk spoke', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 0, 1]], [True, 'ok']], ['disk rim', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 1, 2]], [True, 'ok']], ['fan interior edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 0, 2]], [False, 'boundary']], ['fan missing edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 1, 3]], [False, 'no-edge']], ['tetrahedron edge', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], 0, 1]], [False, 'minimal']], ['octahedron edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 0, 1]], [True, 'ok']], ['grid diagonal', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 0, 4]], [True, 'ok']]], [['fan interior edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 0, 2]], [False, 'boundary']], ['tetrahedron edge', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], 0, 1]], [False, 'minimal']], ['octahedron edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 0, 1]], [True, 'ok']], ['octahedron reversed', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 5, 2]], [True, 'ok']], ['open tetra cap', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1]], 1, 2]], [False, 'link']], ['two triangles shared edge', [[[[0, 1, 2], [2, 1, 3]], 1, 2]], [False, 'boundary']], ['grid diagonal', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 0, 4]], [True, 'ok']]], [['octahedron reversed', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 5, 2]], [True, 'ok']], ['open tetra cap', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1]], 1, 2]], [False, 'link']], ['two triangles shared edge', [[[[0, 1, 2], [2, 1, 3]], 1, 2]], [False, 'boundary']], ['two triangles rim edge', [[[[0, 1, 2], [2, 1, 3]], 0, 1]], [True, 'ok']], ['torus edge', [[[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]], 0, 1]], [False, 'link']], ['cylinder rung', [[[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]], 0, 5]], [False, 'boundary']], ['grid diagonal', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 0, 4]], [True, 'ok']]], [['two triangles rim edge', [[[[0, 1, 2], [2, 1, 3]], 0, 1]], [True, 'ok']], ['torus edge', [[[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]], 0, 1]], [False, 'link']], ['cylinder rung', [[[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]], 0, 5]], [False, 'boundary']], ['strip over-constrained', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 4]], 1, 3]], [False, 'link']], ['grid diagonal', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 0, 4]], [True, 'ok']], ['grid interior spoke', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 4, 5]], [True, 'ok']], ['rotated face order', [[[[2, 0, 1], [3, 0, 2]], 0, 2]], [False, 'boundary']]], [['disk spoke', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 0, 1]], [True, 'ok']], ['disk rim', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 1, 2]], [True, 'ok']], ['fan interior edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 0, 2]], [False, 'boundary']], ['cylinder rung', [[[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]], 0, 5]], [False, 'boundary']], ['grid diagonal', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 0, 4]], [True, 'ok']], ['grid interior spoke', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 4, 5]], [True, 'ok']], ['rotated face order', [[[[2, 0, 1], [3, 0, 2]], 0, 2]], [False, 'boundary']]]]
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)

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    faces,a,b=x
    adj={}
    opp=[]
    ecount={}
    for f in faces:
        for i in range(3):
            u,v=f[i],f[(i+1)%3]
            adj.setdefault(u,set()).add(v)
            adj.setdefault(v,set()).add(u)
            k=(min(u,v),max(u,v))
            ecount[k]=ecount.get(k,0)+1
        if a in f and b in f:
            opp.append([w for w in f if w!=a and w!=b][0])
    k=(min(a,b),max(a,b))
    if k not in ecount: return [False,'no-edge']
    if (adj[a]&adj[b])!=set(opp): return [False,'link']
    bnd=set()
    for (u,v),c in ecount.items():
        if c==1: bnd.update((u,v))
    if a in bnd and ecount[k]!=1: return [False,'boundary']
    if not bnd and len(adj)<=4: return [False,'minimal']
    return [True,'ok']
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['disk spoke', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 0, 1]], [True, 'ok']], ['disk rim', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 1, 2]], [True, 'ok']], ['fan interior edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 0, 2]], [False, 'boundary']], ['fan missing edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 1, 3]], [False, 'no-edge']], ['tetrahedron edge', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], 0, 1]], [False, 'minimal']], ['octahedron edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 0, 1]], [True, 'ok']], ['grid diagonal', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 0, 4]], [True, 'ok']]], [['fan interior edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 0, 2]], [False, 'boundary']], ['tetrahedron edge', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], 0, 1]], [False, 'minimal']], ['octahedron edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 0, 1]], [True, 'ok']], ['octahedron reversed', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 5, 2]], [True, 'ok']], ['open tetra cap', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1]], 1, 2]], [False, 'link']], ['two triangles shared edge', [[[[0, 1, 2], [2, 1, 3]], 1, 2]], [False, 'boundary']], ['grid diagonal', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 0, 4]], [True, 'ok']]], [['octahedron reversed', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 5, 2]], [True, 'ok']], ['open tetra cap', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1]], 1, 2]], [False, 'link']], ['two triangles shared edge', [[[[0, 1, 2], [2, 1, 3]], 1, 2]], [False, 'boundary']], ['two triangles rim edge', [[[[0, 1, 2], [2, 1, 3]], 0, 1]], [True, 'ok']], ['torus edge', [[[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]], 0, 1]], [False, 'link']], ['cylinder rung', [[[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]], 0, 5]], [False, 'boundary']], ['grid diagonal', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 0, 4]], [True, 'ok']]], [['two triangles rim edge', [[[[0, 1, 2], [2, 1, 3]], 0, 1]], [True, 'ok']], ['torus edge', [[[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]], 0, 1]], [False, 'link']], ['cylinder rung', [[[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]], 0, 5]], [False, 'boundary']], ['strip over-constrained', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 4]], 1, 3]], [False, 'link']], ['grid diagonal', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 0, 4]], [True, 'ok']], ['grid interior spoke', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 4, 5]], [True, 'ok']], ['rotated face order', [[[[2, 0, 1], [3, 0, 2]], 0, 2]], [False, 'boundary']]], [['disk spoke', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 0, 1]], [True, 'ok']], ['disk rim', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 1, 2]], [True, 'ok']], ['fan interior edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 0, 2]], [False, 'boundary']], ['cylinder rung', [[[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]], 0, 5]], [False, 'boundary']], ['grid diagonal', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 0, 4]], [True, 'ok']], ['grid interior spoke', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 4, 5]], [True, 'ok']], ['rotated face order', [[[[2, 0, 1], [3, 0, 2]], 0, 2]], [False, 'boundary']]]]
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)

prompt:
Collapsing a rim edge is refused while collapsing an interior edge between two rim vertices is allowed.

Input [faces, a, b] for a triangle mesh. Collapsing edge (a,b) is checked in order: missing edge -> [false,"no-edge"]; common neighbours of a and b must equal the opposite vertices of the triangles on the edge -> else [false,"link"]; if a and b are both boundary vertices the edge itself must be a boundary edge -> else [false,"boundary"]; a closed mesh with 4 or fewer vertices -> [false,"minimal"]; otherwise [true,"ok"].

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    faces,a,b=x
    adj={}
    opp=[]
    ecount={}
    for f in faces:
        for i in range(3):
            u,v=f[i],f[(i+1)%3]
            adj.setdefault(u,set()).add(v)
            adj.setdefault(v,set()).add(u)
            k=(min(u,v),max(u,v))
            ecount[k]=ecount.get(k,0)+1
        if a in f and b in f:
            opp.append([w for w in f if w!=a and w!=b][0])
    k=(min(a,b),max(a,b))
    if k not in ecount: return [False,'no-edge']
    if (adj[a]&adj[b])!=set(opp): return [False,'link']
    bnd=set()
    for (u,v),c in ecount.items():
        if c==1: bnd.update((u,v))
    if a in bnd and b in bnd and ecount[k]!=1: return [False,'boundary']
    if not bnd and len(adj)<4: return [False,'minimal']
    return [True,'ok']
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['disk spoke', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 0, 1]], [True, 'ok']], ['disk rim', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 1, 2]], [True, 'ok']], ['fan interior edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 0, 2]], [False, 'boundary']], ['fan missing edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 1, 3]], [False, 'no-edge']], ['tetrahedron edge', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], 0, 1]], [False, 'minimal']], ['octahedron edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 0, 1]], [True, 'ok']], ['two triangles rim edge', [[[[0, 1, 2], [2, 1, 3]], 0, 1]], [True, 'ok']]], [['fan missing edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 1, 3]], [False, 'no-edge']], ['tetrahedron edge', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], 0, 1]], [False, 'minimal']], ['octahedron edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 0, 1]], [True, 'ok']], ['octahedron reversed', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 5, 2]], [True, 'ok']], ['open tetra cap', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1]], 1, 2]], [False, 'link']], ['two triangles shared edge', [[[[0, 1, 2], [2, 1, 3]], 1, 2]], [False, 'boundary']], ['two triangles rim edge', [[[[0, 1, 2], [2, 1, 3]], 0, 1]], [True, 'ok']]], [['tetrahedron edge', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], 0, 1]], [False, 'minimal']], ['open tetra cap', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1]], 1, 2]], [False, 'link']], ['two triangles shared edge', [[[[0, 1, 2], [2, 1, 3]], 1, 2]], [False, 'boundary']], ['two triangles rim edge', [[[[0, 1, 2], [2, 1, 3]], 0, 1]], [True, 'ok']], ['torus edge', [[[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]], 0, 1]], [False, 'link']], ['cylinder rung', [[[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]], 0, 5]], [False, 'boundary']], ['strip over-constrained', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 4]], 1, 3]], [False, 'link']]], [['tetrahedron edge', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], 0, 1]], [False, 'minimal']], ['two triangles rim edge', [[[[0, 1, 2], [2, 1, 3]], 0, 1]], [True, 'ok']], ['cylinder rung', [[[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]], 0, 5]], [False, 'boundary']], ['strip over-constrained', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 4]], 1, 3]], [False, 'link']], ['grid diagonal', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 0, 4]], [True, 'ok']], ['grid interior spoke', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 4, 5]], [True, 'ok']], ['rotated face order', [[[[2, 0, 1], [3, 0, 2]], 0, 2]], [False, 'boundary']]], [['disk spoke', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 0, 1]], [True, 'ok']], ['disk rim', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 1, 2]], [True, 'ok']], ['fan interior edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 0, 2]], [False, 'boundary']], ['tetrahedron edge', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], 0, 1]], [False, 'minimal']], ['two triangles rim edge', [[[[0, 1, 2], [2, 1, 3]], 0, 1]], [True, 'ok']], ['grid interior spoke', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 4, 5]], [True, 'ok']], ['rotated face order', [[[[2, 0, 1], [3, 0, 2]], 0, 2]], [False, 'boundary']]]]
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)

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    faces,a,b=x
    adj={}
    opp=[]
    ecount={}
    for f in faces:
        for i in range(3):
            u,v=f[i],f[(i+1)%3]
            adj.setdefault(u,set()).add(v)
            adj.setdefault(v,set()).add(u)
            k=(min(u,v),max(u,v))
            ecount[k]=ecount.get(k,0)+1
        if a in f and b in f:
            opp.append([w for w in f if w!=a and w!=b][0])
    k=(min(a,b),max(a,b))
    if k not in ecount: return [False,'no-edge']
    if (adj[a]&adj[b])!=set(opp): return [False,'link']
    bnd=set()
    for (u,v),c in ecount.items():
        if c==1: bnd.update((u,v))
    if a in bnd and b in bnd and ecount[k]!=1: return [False,'boundary']
    if len(adj)<=4: return [False,'minimal']
    return [True,'ok']
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['disk spoke', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 0, 1]], [True, 'ok']], ['disk rim', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 1, 2]], [True, 'ok']], ['fan interior edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 0, 2]], [False, 'boundary']], ['fan missing edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 1, 3]], [False, 'no-edge']], ['tetrahedron edge', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], 0, 1]], [False, 'minimal']], ['octahedron edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 0, 1]], [True, 'ok']], ['two triangles rim edge', [[[[0, 1, 2], [2, 1, 3]], 0, 1]], [True, 'ok']]], [['fan missing edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 1, 3]], [False, 'no-edge']], ['tetrahedron edge', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], 0, 1]], [False, 'minimal']], ['octahedron edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 0, 1]], [True, 'ok']], ['octahedron reversed', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 5, 2]], [True, 'ok']], ['open tetra cap', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1]], 1, 2]], [False, 'link']], ['two triangles shared edge', [[[[0, 1, 2], [2, 1, 3]], 1, 2]], [False, 'boundary']], ['two triangles rim edge', [[[[0, 1, 2], [2, 1, 3]], 0, 1]], [True, 'ok']]], [['tetrahedron edge', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], 0, 1]], [False, 'minimal']], ['open tetra cap', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1]], 1, 2]], [False, 'link']], ['two triangles shared edge', [[[[0, 1, 2], [2, 1, 3]], 1, 2]], [False, 'boundary']], ['two triangles rim edge', [[[[0, 1, 2], [2, 1, 3]], 0, 1]], [True, 'ok']], ['torus edge', [[[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]], 0, 1]], [False, 'link']], ['cylinder rung', [[[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]], 0, 5]], [False, 'boundary']], ['strip over-constrained', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 4]], 1, 3]], [False, 'link']]], [['tetrahedron edge', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], 0, 1]], [False, 'minimal']], ['two triangles rim edge', [[[[0, 1, 2], [2, 1, 3]], 0, 1]], [True, 'ok']], ['cylinder rung', [[[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]], 0, 5]], [False, 'boundary']], ['strip over-constrained', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 4]], 1, 3]], [False, 'link']], ['grid diagonal', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 0, 4]], [True, 'ok']], ['grid interior spoke', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 4, 5]], [True, 'ok']], ['rotated face order', [[[[2, 0, 1], [3, 0, 2]], 0, 2]], [False, 'boundary']]], [['disk spoke', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 0, 1]], [True, 'ok']], ['disk rim', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 1, 2]], [True, 'ok']], ['fan interior edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 0, 2]], [False, 'boundary']], ['tetrahedron edge', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], 0, 1]], [False, 'minimal']], ['two triangles rim edge', [[[[0, 1, 2], [2, 1, 3]], 0, 1]], [True, 'ok']], ['grid interior spoke', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 4, 5]], [True, 'ok']], ['rotated face order', [[[[2, 0, 1], [3, 0, 2]], 0, 2]], [False, 'boundary']]]]
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)

prompt:
Collapsing any edge of a tetrahedron is accepted and produces a degenerate surface.

Input [faces, a, b] for a triangle mesh. Collapsing edge (a,b) is checked in order: missing edge -> [false,"no-edge"]; common neighbours of a and b must equal the opposite vertices of the triangles on the edge -> else [false,"link"]; if a and b are both boundary vertices the edge itself must be a boundary edge -> else [false,"boundary"]; a closed mesh with 4 or fewer vertices -> [false,"minimal"]; otherwise [true,"ok"].

split: open-access