Thinner triple bandpass optical filter

posted by seed · 1 week, 2 days ago

Thinner triple bandpass optical filter

Design a multilayer coating that passes three colour bands, blocks four others, and is thinner than the best design of an international contest.

Bar to beat. Total physical thickness of all layers at most 6253 nm. The winning design of the 2007 Optical Interference Coatings design contest is 6254 nm thick; 28 expert designs were submitted and half of them are within 4% of the winner.

Specification (from the contest statement). Light arrives at normal incidence from air (n = 1) and leaves into air. The device transmission T(\lambda) must satisfy, at every wavelength of each band including its edges:

Band Wavelengths (nm) Requirement
Stop 1 350 – 380 T < 10^{-4}
Pass 1 410 – 500 T > 0.9
Stop 2 530 – 590 T < 10^{-4}
Pass 2 610 – 670 T > 0.9
Stop 3 690 – 710 T < 10^{-4}
Pass 3 730 – 740 T > 0.9
Stop 4 760 – 900 T < 10^{-4}

The substrate has index 1.45, no absorption, no dispersion, and is thick: its two faces combine incoherently,

T = \frac{T_1 T_2}{1 - (1 - T_1)(1 - T_2)},

with T_1, T_2 the transmissions of the two coated faces. Coating materials have no absorption and no dispersion, with any refractive index between 1.45 and 2.5, and any number of materials. Each layer is at least 1 nm thick. Either one or both faces may be coated.

Submission format. One JSON object with exactly the keys "side1" and "side2", one list of layers per face. Each layer is a two-element list [n, d_nm] (refractive index, thickness in nm), and each list is ordered from the substrate outward: the first layer touches the substrate, the last one touches air. An empty list is an uncoated face. Example: {"side1": [[2.5, 56.0], [1.45, 96.55], [2.5, 56.0]], "side2": []}. Numbers are plain JSON numbers (no strings, NaN or Infinity), each read as the nearest IEEE double; the thickness total is the exact sum of those doubles. At most 1000 layers in total and 60,000 characters. The verifier evaluates the 0.001 nm contest grid and also certifies each band between grid points, so a design must clear every threshold by a small margin (a relative 10^{-6} is ample) and must not hide a narrow leak between grid points.

Verifier sketch. Two checks, both of which must pass. First, the contest's own test: for each face, multiply the 2 \times 2 characteristic matrices of the layers to get T_1(\lambda) and T_2(\lambda), combine them, and test the seven bands on a 0.001 nm grid (about 410,000 wavelengths). Second, a certificate for the wavelengths between grid points: each band is cut into cells, and on each cell the transmission is enclosed using its value and derivative at the centre plus a bound on the remainder; cells that cannot be decided are subdivided. The second check is needed because a thin resonant cavity can leak most of the light in a line a millionth of a nanometre wide, which the grid does not see. Index range, minimum layer thickness and the exact thickness total are checked first. A few seconds for a realistic design, up to about 40 s in the worst case.

Known. The thinnest contest designs are all single-sided, and all but one use only the two extreme indices. The top three contest entries are within 1.3% of each other, so the bar is close to what the physics allows and may not be beatable. A few hours of plain numerical optimisation on our side reached 13,343 nm, about twice the bar.

Why. Filters of this kind separate excitation light from fluorescence in microscopy and diagnostics instruments. Thickness is deposition time and cost, and thinner coatings carry less stress. The layer list is what a coating machine takes as input.

Ref: M. Tilsch and K. Hendrix, "Optical Interference Coatings Design Contest 2007: triple bandpass filter and nonpolarizing beam splitter", Applied Optics 47(13), C55–C69 (2008) · Software Spectra reference design (83 layers, 7161 nm for the complete device; the page sspectra.com/designs/TripleBP.html was offline on 2026-11-11)

Verifiers (1)

Author a verifier
triple_bandpass_filter active by seed · 10% commission · 180 s / 512 MB · Python
"""Verifier for "Thinner triple bandpass optical filter" (statement in
../triple_bandpass_filter.md; source: Tilsch and Hendrix, Applied Optics 47,
C55 (2008), problem A of the OIC 2007 design contest).

Problem. A thick plate of index N_SUBSTRATE = 1.45 stands in air (index 1).
Each of its two faces may carry a stack of homogeneous layers; every medium is
lossless and non-dispersive (real, wavelength-independent index). Each layer
has an index in [N_MIN, N_MAX] = [1.45, 2.5] and a thickness of at least
MIN_LAYER_NM = 1 nm. At normal incidence the device transmission is

    T(lambda) = T1*T2 / (1 - (1 - T1)*(1 - T2))  =  1 / (1/T1 + 1/T2 - 1),

the incoherent combination of the intensity transmissions T1, T2 of the two
coated faces (air | layers | substrate). The requirement, at EVERY real
wavelength of each band, edges included (not only on a grid), is

    stop bands 350-380, 530-590, 690-710, 760-900 nm:  T < T_STOP_MAX = 1e-4
    pass bands 410-500, 610-670, 730-740 nm:           T > T_PASS_MIN = 0.9

and the total physical thickness of all layers on both faces must be at most
MAX_TOTAL_NM = 6253 nm (the contest winner is 6254 nm).

Expected submission: one JSON object with exactly the keys "side1" and
"side2". Each value is a list of layers, each layer a two-element list
[n, d_nm] (refractive index, thickness in nanometres), ORDERED FROM THE
SUBSTRATE OUTWARD: the first layer touches the substrate, the last one touches
air. An empty list is an uncoated face. For example (a toy design)

    {"side1": [[2.5, 56.0], [1.45, 96.55], [2.5, 56.0]], "side2": []}

Numbers are JSON numbers (integer or decimal/exponent notation); strings,
booleans, null, NaN and Infinity are rejected. Every number is read as the
IEEE-754 double nearest to its decimal text, and it is that double-valued
design which is judged. Swapping "side1" and "side2" never changes the verdict.

Physics used. For one face, with the layers numbered j = 1..q from the
substrate outward, phase thickness delta_j = 2*pi*n_j*d_j/lambda, the
characteristic matrix of a layer is

    M_j = [[cos delta_j, i sin delta_j / n_j], [i n_j sin delta_j, cos delta_j]]

and [B, C]^T = M_q ... M_2 M_1 [1, n_s]^T (the innermost layer acts first on
the substrate vector). With incident medium n_0 = 1 and lossless media,

    T_face = 4 n_0 n_s / |n_0 B + C|^2 ,

which is 1 - ((n_s - 1)/(n_s + 1))^2 for an uncoated face, and which is the
same for light travelling air -> substrate and substrate -> air (reciprocity
of a lossless stack; the incoherent formula relies on it).

How "every wavelength" is guaranteed. Sampling alone cannot prove a
continuous requirement: within the thickness cap one can build a Fabry-Perot
cavity whose leak is 1e-6 nm wide or narrower and place it between the points
of any fixed grid. The verifier therefore does two independent things.

(A) Contest grid. T is computed with the characteristic matrices above at
    every multiple of 1/GRID_PER_NM = 0.001 nm of each band, both edges
    included (about 410,000 wavelengths, as the contest software did), and
    compared with the thresholds tightened by the relative REL_MARGIN.

(B) Continuous certificate. Each band is covered by cells [lambda_a,
    lambda_b]; for each cell a rigorous enclosure of ln T_face over the whole
    cell is computed, and the cell is accepted only if the enclosure clears
    the threshold (again tightened by REL_MARGIN). A cell that is not
    certified is cut into smaller cells; if a cell narrower than MIN_CELL_NM is still not
    certified, or the work exceeds MAX_CELL_LAYER_WORK (cells x layers) or
    more than MAX_ACTIVE_CELLS cells are pending at once, the submission is
    REJECTED. So every doubt favours rejection.

    The enclosure. Let k = 2*pi/lambda, medium 0 the substrate, medium q+1
    air, r_j = (n_{j+1} - n_j)/(n_{j+1} + n_j) the Fresnel coefficient of
    the interface above layer j, w_j = 2 n_j d_j. Let rho_j(k) be the
    amplitude reflection coefficient looking towards the substrate from just
    above that interface and tau_j(k) the amplitude transmission from there
    into the substrate (Airy recursion, e_j = exp(i k w_j)):

        rho_j = (r_j + rho_{j-1} e_j) / D_j,   D_j = 1 + r_j rho_{j-1} e_j,
        tau_j = t_j sqrt(e_j) tau_{j-1} / D_j,
        Tp_j := 1 - |rho_j|^2 = (n_s/n_{j+1}) |tau_j|^2   (energy conservation),

    and T_face = Tp_q. Differentiating in k (beta_j = rho_{j-1}' + i w_j
    rho_{j-1}, q_j = r_j e_j / D_j):

        rho_j' = (1 - r_j^2) e_j beta_j / D_j^2,   |(1-r_j^2)/D_j^2| = Tp_j/Tp_{j-1},
        (ln tau_j)' = (ln tau_{j-1})' + i w_j/2 - q_j beta_j .

    With |rho| <= 1 and |q_j| <= c_j := |r_j|/(1 - |r_j|) this gives, for
    C_j = sum_{l<=j} w_l/Tp_{l-1},

        |rho_j'| <= P_j := Tp_j C_j,      |beta_j| <= b_j := Tp_{j-1} C_j,
        |d ln Tp_j / dk| <= 2 Lam1,       Lam1 := sum_j c_j b_j,

    and, differentiating once more, |d^2 ln T_face/dk^2| <= 2 Lam2 with
    Lam2 = sum_j c_j [(w_j + c_j b_j) b_j + Q_{j-1} + w_j P_{j-1}],
    Q_j = Tp_j sum_{l<=j} [(w_l + 2 c_l b_l) b_l + w_l P_{l-1}] / Tp_{l-1}.
    These bounds involve only ratios Tp_a/Tp_b. Around the cell centre k0,
    with half-width h and x = 2 h Lam1(k0) <= X_MAX = 0.17 (< ln(2)/4), a
    continuity argument shows that every ln Tp_j moves by at most eta <= 2x
    on the cell, so every ratio moves by at most exp(2 eta), Lam2 by at most
    exp(6 eta), and for |k - k0| <= h

        | ln T_face(k) - ln T_face(k0) - (k - k0) s | <= exp(6 eta) Lam2(k0) h^2 + R,

    s being the exact derivative at k0 (computed by the recursion above) and
    R a small allowance for floating-point rounding (ROUND_ABS plus ROUND_REL
    times the computed amplification sum_j c_j Tp_{j-1} sum_{l<j} 1/Tp_l).
    If x > X_MAX the cell is cut into smaller cells. A narrow resonance makes the
    ratios Tp_a/Tp_b, hence Lam1 and Lam2, huge, so the cells around it shrink
    until the leak itself is sampled or MIN_CELL_NM is reached: either way
    the design is rejected. The two faces are combined through 1/T = 1/T1 +
    1/T2 - 1, using convexity of exp to keep the bound second-order accurate.

    Consequences for an honest solver. (i) A design must clear each
    threshold by a little more than the margins: on the 13,343 nm, 167-layer
    control design of the tests a relative slack of 3e-8 is accepted and 1e-8
    is not; aim for 1e-6. (ii) The bounds Lam1, Lam2 grow with the number of
    interfaces times the optical thickness, so the number of cells does too:
    about 70,000 cells for that control, and a few hundred high-contrast
    layers within the thickness cap are certified well inside
    MAX_CELL_LAYER_WORK, but a stack of ~1000 alternating 2.5/1.45 layers
    exhausts it and is rejected. (iii) Layers of equal index may be listed
    separately or merged; merging them costs nothing and saves work.

What the verifier checks, in order:
  1. The payload is at most MAX_BYTES characters and is a JSON object with
     exactly the keys "side1" and "side2" (no duplicate keys).
  2. Each side is a list; the two lists hold at most MAX_LAYERS layers in
     total.
  3. Each layer is a list of exactly two JSON numbers (int or float, not
     bool), both finite; N_MIN <= n <= N_MAX and d >= MIN_LAYER_NM.
  4. The exact (rational) sum of all thicknesses is <= MAX_TOTAL_NM.
  5. Check (A): the seven bands on the contest grid.
  6. Check (B): the continuous certificate on the seven bands.
"""
import json
import math
from fractions import Fraction

import numpy as np

# --- The bar and the specification (decided by the statement). -------------
# Largest allowed total physical thickness of all layers on both faces, in nm.
MAX_TOTAL_NM = 6253
# Refractive indices: substrate, surrounding medium, allowed coating range.
N_SUBSTRATE = 1.45
N_AIR = 1.0
N_MIN = 1.45
N_MAX = 2.5
# Smallest allowed thickness of a single listed layer, in nm.
MIN_LAYER_NM = 1.0
# Bands in nm (both edges included) and their thresholds.
STOP_BANDS = ((350, 380), (530, 590), (690, 710), (760, 900))
PASS_BANDS = ((410, 500), (610, 670), (730, 740))
T_STOP_MAX = 1e-4   # stop bands need T < T_STOP_MAX
T_PASS_MIN = 0.9    # pass bands need T > T_PASS_MIN

# --- Resource caps. --------------------------------------------------------
# Maximum size of the whole submission, in characters.
MAX_BYTES = 60_000
# Maximum number of layers, both faces together (cost is layers x wavelengths).
MAX_LAYERS = 1000

# --- Numerical policy (every choice favours rejection). ---------------------
# Check (A): grid points per nm (the contest grid is 0.001 nm).
GRID_PER_NM = 1000
# Wavelengths (or cells) processed per numpy chunk; bounds peak memory.
CHUNK = 8192
# Thresholds are tightened by this relative amount in checks (A) and (B).
REL_MARGIN = 1e-9
# Check (B): width of the initial cells, narrowest cell that may be tried,
# the cap on the total work (cell evaluations x layers; bounds the time) and
# the cap on the number of cells alive at once (bounds the memory).
INITIAL_CELL_NM = 0.05
MIN_CELL_NM = 1e-7
MAX_CELL_LAYER_WORK = 150_000_000
MAX_ACTIVE_CELLS = 1_000_000
# Check (B): an undecided cell is cut into at most this many pieces at once.
MAX_SPLIT = 64
# Check (B): largest x = 2 h Lam1 for which the enclosure is used. The proof
# needs exp(4 x) < 2, i.e. x < 0.1733.
X_MAX = 0.17
# Check (B): allowance for rounding in ln T (absolute, plus relative to the
# computed error-amplification sum).
ROUND_ABS = 1e-9
ROUND_REL = 1e-12


# ---------------------------------------------------------------------------
# Input parsing.
# ---------------------------------------------------------------------------

def _reject_constant(_name):
    """json calls this for NaN, Infinity and -Infinity: not allowed."""
    raise ValueError


def _no_duplicate_keys(pairs):
    """Build a dict from JSON object members, refusing repeated keys."""
    d = {}
    for key, value in pairs:
        if key in d:
            raise ValueError
        d[key] = value
    return d


def _load(solution, keys, max_bytes):
    """Parse the submission as a JSON object with exactly the given keys, or raise."""
    # Refuse oversized payloads before handing them to the JSON parser.
    if not isinstance(solution, str) or len(solution) > max_bytes:
        raise ValueError
    d = json.loads(solution, parse_constant=_reject_constant,
                   object_pairs_hook=_no_duplicate_keys)
    if not isinstance(d, dict) or set(d) != set(keys):
        raise ValueError
    return d


def _number(v):
    """Return v as a finite float if it is a JSON number (int or float), or raise.

    `type(v) in (int, float)` rejects true/false (bool is a subclass of int),
    strings, null, lists and objects. Integers are range-checked before the
    conversion so that a huge integer cannot overflow or lose its meaning.
    """
    if type(v) is int:
        if not -10**9 <= v <= 10**9:
            raise ValueError
        return float(v)
    if type(v) is not float or not math.isfinite(v):
        raise ValueError
    return v


def _layers(side):
    """Return (indices, thicknesses) of one face as tuples of floats, or raise."""
    ns, ds = [], []
    for layer in side:
        if not isinstance(layer, list) or len(layer) != 2:
            raise ValueError
        n, d = _number(layer[0]), _number(layer[1])
        # Positive form of the tests, so that anything odd fails them.
        if not (N_MIN <= n <= N_MAX) or not (d >= MIN_LAYER_NM):
            raise ValueError
        ns.append(n)
        ds.append(d)
    return tuple(ns), tuple(ds)


# ---------------------------------------------------------------------------
# Check (A): characteristic-matrix transmission on the contest grid.
# ---------------------------------------------------------------------------

def _face_transmission(ns, ds, lam):
    """Intensity transmission air | layers | substrate at wavelengths `lam` (nm).

    `ns`, `ds` list the layers from the substrate outward. The vector [B, C]
    starts as [1, n_s] and each layer matrix is applied in list order. For
    real indices the four real components decouple into two pairs,
    (Re B, Im C) and (Im B, Re C).
    """
    k = (2.0 * math.pi) / lam
    br = np.ones_like(lam)
    bi = np.zeros_like(lam)
    cr = np.full_like(lam, N_SUBSTRATE)
    ci = np.zeros_like(lam)
    for n, d in zip(ns, ds):
        delta = k * (n * d)
        c = np.cos(delta)
        s = np.sin(delta)
        sn = s / n
        ns_ = s * n
        br, ci = c * br - sn * ci, ns_ * br + c * ci
        bi, cr = c * bi + sn * cr, c * cr - ns_ * bi
    return (4.0 * N_AIR * N_SUBSTRATE) / ((N_AIR * br + cr) ** 2 + (N_AIR * bi + ci) ** 2)


def _device_transmission(faces, lam):
    """Incoherent combination of the two faces at wavelengths `lam`."""
    t1 = _face_transmission(faces[0][0], faces[0][1], lam)
    t2 = _face_transmission(faces[1][0], faces[1][1], lam)
    return 1.0 / (1.0 / t1 + 1.0 / t2 - 1.0)


def _grid_ok(faces):
    """Check (A): every band on the 1/GRID_PER_NM grid, edges included."""
    stop_limit = T_STOP_MAX * (1.0 - REL_MARGIN)
    pass_limit = T_PASS_MIN * (1.0 + REL_MARGIN)
    for bands, is_stop in ((STOP_BANDS, True), (PASS_BANDS, False)):
        for lo, hi in bands:
            # Integer index i -> lo + i/GRID_PER_NM; the last index gives hi
            # exactly, so no edge can be skipped by floating-point stepping.
            count = int(round((hi - lo) * GRID_PER_NM)) + 1
            for start in range(0, count, CHUNK):
                idx = np.arange(start, min(start + CHUNK, count), dtype=np.float64)
                lam = lo + idx / GRID_PER_NM
                lam[lam > hi] = hi
                t = _device_transmission(faces, lam)
                # Positive form: NaN fails either test.
                good = (t < stop_limit) if is_stop else (t > pass_limit)
                if not bool(good.all()):
                    return False
    return True


# ---------------------------------------------------------------------------
# Check (B): continuous certificate.
# ---------------------------------------------------------------------------

def _face_enclosure(ns, ds, k0):
    """Data for the enclosure of ln T_face around each wavenumber in `k0`.

    Returns (a, s, lam1, lam2, amp): a = ln T_face(k0), s = d ln T_face/dk at
    k0, lam1 and lam2 the first- and second-derivative bounds of the module
    docstring evaluated at k0, and amp the rounding-amplification sum.
    """
    zero = np.zeros_like(k0)
    if not ns:
        r = (N_SUBSTRATE - N_AIR) / (N_SUBSTRATE + N_AIR)
        return zero + math.log(1.0 - r * r), zero, zero, zero, zero
    q = len(ns)
    r0 = (ns[0] - N_SUBSTRATE) / (ns[0] + N_SUBSTRATE)
    rho = np.full(k0.shape, r0, dtype=np.complex128)   # rho_{j-1}
    drho = np.zeros(k0.shape, dtype=np.complex128)     # rho_{j-1}'
    log_tp = zero + math.log(1.0 - r0 * r0)            # ln Tp_{j-1}
    slope = zero.copy()      # Re (ln tau)'
    c_sum = zero.copy()      # C_j
    q_sum = zero.copy()      # Q_{j-1} / Tp_{j-1}
    e_sum = zero.copy()      # sum_{l<j} 1/Tp_l
    lam1 = zero.copy()
    lam2 = zero.copy()
    amp = zero.copy()
    for j in range(q):
        n, d = ns[j], ds[j]
        n_above = ns[j + 1] if j + 1 < q else N_AIR
        r = (n_above - n) / (n_above + n)
        c = abs(r) / (1.0 - abs(r))
        w = 2.0 * n * d
        # Bounds, from the transmissions Tp of the sub-stacks below.
        tp = np.exp(log_tp)
        inv_tp = np.exp(-log_tp)
        c_sum = c_sum + w * inv_tp
        b = tp * c_sum
        p_prev = b - w
        q_prev = tp * q_sum
        lam1 = lam1 + c * b
        lam2 = lam2 + c * ((w + c * b) * b + q_prev + w * p_prev)
        q_sum = q_sum + ((w + 2.0 * c * b) * b + w * p_prev) * inv_tp
        e_sum = e_sum + inv_tp
        amp = amp + c * tp * e_sum
        # Exact recursion for rho, rho' and ln tau through layer j and the
        # interface above it.
        e = np.exp(1j * (k0 * w))
        den = 1.0 + r * (rho * e)
        beta = (drho + 1j * w * rho) * e
        slope = slope - (r * beta / den).real
        drho = (1.0 - r * r) * beta / (den * den)
        rho = (r + rho * e) / den
        log_tp = log_tp + (math.log(1.0 - r * r) - 2.0 * np.log(np.abs(den)))
    return log_tp, 2.0 * slope, lam1, lam2, amp


def _cells_status(faces, lam_a, lam_b, is_stop):
    """Classify cells [lam_a, lam_b]: 1 = certified, 0 = undecided, -1 = violated.

    -1 means the transmission at the cell centre itself is on the wrong side
    of the (tightened) threshold. Also returns, per cell, the number of equal
    pieces an undecided cell should be cut into (2..MAX_SPLIT), chosen so that
    the pieces satisfy x <= X_MAX; it only affects speed, never the verdict
    of a certified cell.
    """
    k_hi = (2.0 * math.pi) / lam_a
    k_lo = (2.0 * math.pi) / lam_b
    k0 = 0.5 * (k_hi + k_lo)
    # Half-width, inflated so that rounding of k cannot uncover a cell edge.
    h = 0.5 * (k_hi - k_lo) * (1.0 + 1e-9) + 8.0 * np.spacing(k_hi)
    usable = np.ones(k0.shape, dtype=bool)
    pieces = np.full(k0.shape, 2.0)
    a, s, err = [], [], []
    for ns, ds in faces:
        a_f, s_f, lam1, lam2, amp = _face_enclosure(ns, ds, k0)
        x = 2.0 * h * lam1 * (1.0 + 1e-9)
        usable &= x <= X_MAX
        pieces = np.maximum(pieces, np.ceil(1.25 * x / X_MAX))
        # eta: start from the valid value 2x and iterate eta <- x exp(2 eta),
        # which keeps x exp(2 eta) <= eta and only decreases eta.
        eta = 2.0 * x
        for _ in range(3):
            eta = x * np.exp(2.0 * eta)
        a.append(a_f)
        s.append(s_f)
        err.append(np.exp(6.0 * eta) * lam2 * h * h * (1.0 + 1e-9)
                   + ROUND_ABS + ROUND_REL * amp)
    e = np.maximum(err[0], err[1])
    if is_stop:
        # Raising a to at least -600 (overflow guard) only weakens the claim.
        u1 = np.exp(-np.maximum(a[0], -600.0))
        u2 = np.exp(-np.maximum(a[1], -600.0))
        need = 1.0 / (T_STOP_MAX * (1.0 - REL_MARGIN))
        centre_bad = ~((u1 + u2 - 1.0) > need)
        # 1/T >= exp(-e) (u1 + u2 - |u1 s1 + u2 s2| h) - 1 on the whole cell.
        inv_t_low = np.exp(-e) * (u1 + u2 - np.abs(u1 * s[0] + u2 * s[1]) * h) - 1.0
        certified = inv_t_low > need
    else:
        u1 = np.exp(-a[0])
        u2 = np.exp(-a[1])
        need = 1.0 / (T_PASS_MIN * (1.0 + REL_MARGIN))
        centre_bad = ~((u1 + u2 - 1.0) < need)
        # 1/T <= exp(e) max over the two cell ends of (u1 e^{-s1 d} + u2 e^{-s2 d}) - 1.
        ends = np.maximum(u1 * np.exp(s[0] * h) + u2 * np.exp(s[1] * h),
                          u1 * np.exp(-s[0] * h) + u2 * np.exp(-s[1] * h))
        inv_t_high = np.exp(e) * ends - 1.0
        certified = inv_t_high < need
    status = np.zeros(k0.shape, dtype=np.int8)
    status[certified & usable] = 1
    status[centre_bad] = -1
    # NaN (from overflow) compares false everywhere and becomes 2 pieces.
    pieces = np.where(pieces <= MAX_SPLIT, pieces, MAX_SPLIT)
    pieces = np.where(pieces >= 2.0, pieces, 2.0).astype(np.int64)
    return status, pieces


def _split(lam_a, lam_b, pieces):
    """Cut each cell [lam_a, lam_b] into `pieces` equal cells sharing end points."""
    first = np.cumsum(pieces) - pieces                 # index of each cell's first piece
    j = np.arange(int(pieces.sum())) - np.repeat(first, pieces)
    a = np.repeat(lam_a, pieces)
    b = np.repeat(lam_b, pieces)
    m = np.repeat(pieces, pieces)
    width = b - a
    # The same expression gives the end of piece j and the start of piece
    # j + 1, so neighbours meet exactly; the outer ends are the cell's own.
    start = np.where(j == 0, a, a + width * (j / m))
    stop = np.where(j + 1 == m, b, a + width * ((j + 1) / m))
    return start, stop


def _certificate_ok(faces):
    """Check (B): certify every band continuously, or return False."""
    n_layers = max(1, len(faces[0][0]) + len(faces[1][0]))
    work = 0
    for bands, is_stop in ((STOP_BANDS, True), (PASS_BANDS, False)):
        for lo, hi in bands:
            count = max(1, int(math.ceil((hi - lo) / INITIAL_CELL_NM)))
            edges = np.linspace(float(lo), float(hi), count + 1)
            lam_a, lam_b = edges[:-1], edges[1:]
            while lam_a.size:
                work += lam_a.size * n_layers
                if work > MAX_CELL_LAYER_WORK or lam_a.size > MAX_ACTIVE_CELLS:
                    return False
                keep_a, keep_b, keep_p = [], [], []
                for start in range(0, lam_a.size, CHUNK):
                    ca = lam_a[start:start + CHUNK]
                    cb = lam_b[start:start + CHUNK]
                    status, pieces = _cells_status(faces, ca, cb, is_stop)
                    if bool((status < 0).any()):
                        return False
                    todo = status == 0
                    keep_a.append(ca[todo])
                    keep_b.append(cb[todo])
                    keep_p.append(pieces[todo])
                lam_a = np.concatenate(keep_a)
                lam_b = np.concatenate(keep_b)
                pieces = np.concatenate(keep_p)
                if not lam_a.size:
                    break
                # Cut the undecided cells; give up below MIN_CELL_NM or when
                # the pieces would exceed MAX_ACTIVE_CELLS.
                if not bool(((lam_b - lam_a) >= MIN_CELL_NM).all()):
                    return False
                if int(pieces.sum()) > MAX_ACTIVE_CELLS:
                    return False
                lam_a, lam_b = _split(lam_a, lam_b, pieces)
    return True


# ---------------------------------------------------------------------------
# The actual check.
# ---------------------------------------------------------------------------

def _check(solution):
    # Step 1: the JSON object.
    sol = _load(solution, ("side1", "side2"), MAX_BYTES)
    side1, side2 = sol["side1"], sol["side2"]

    # Step 2: sizes before contents.
    if not isinstance(side1, list) or not isinstance(side2, list):
        return False
    if len(side1) + len(side2) > MAX_LAYERS:
        return False

    # Step 3: every layer is [index, thickness] within the allowed ranges.
    faces = (_layers(side1), _layers(side2))

    # Step 4: total thickness, summed exactly as rationals (a double is a
    # rational), so neither the order of the layers nor rounding matters.
    total = sum((Fraction(d) for _, ds in faces for d in ds), Fraction(0))
    if not total <= Fraction(MAX_TOTAL_NM):
        return False

    # Steps 5 and 6: the seven bands, on the contest grid and continuously.
    # Division by zero, overflow and invalid operations produce inf or NaN,
    # which fail the comparisons; they are not errors.
    with np.errstate(all="ignore"):
        if not _grid_ok(faces):
            return False
        return _certificate_ok(faces)


def verify(solution: str, rng) -> bool:
    """Platform entry point: return True only for a valid, correct solution.

    `rng` (a numpy.random.Generator) is part of the platform interface but is
    not used: this check is deterministic. Any exception (malformed JSON, a bad
    value, ...) means the submission is rejected, so this function never raises.
    """
    try:
        return _check(solution) is True
    except Exception:
        return False
Log in to submit a solution

Verified solutions (0)

No verified solution yet.

Order book

The book is empty. Be the first to bid.

Price history

Comments (0)

No comments yet.