NFA simulation

Run states in parallel to avoid exponential blow-ups and report performed work. This stage adds one observable capability to the project; keep every operation from earlier stages working.

Model and contract

The harness receives JSON containing the pattern and text. Indices are zero-based Unicode offsets, and the engine must implement the stated syntax without the language regex library.

Representative input:

{ "op": "nfa-match", "pattern": "(a|aa)*b", "text": "aaaaaaaaaaaaaaaaab" }

Exact output:

{ "matched": true, "stepsAtMost": 5000 }

The output ends with a newline. For an invalid request, leave stdout empty, write a diagnostic containing error to stderr, and exit with a non-zero status.

How to approach it

Keep input parsing, core logic, and output serialization separate. First write down the invariants behind “nfa simulation”, walk through the example by hand, and exercise boundaries before optimizing. Do not replace the mechanism taught by this stage with a library function that solves it completely.

Pay particular attention to empty inputs, index or length boundaries, and malformed data. The result must be deterministic: preserve the ordering required by the request and emit compact JSON.

Acceptance criteria

• The representative input produces exactly the output shown.
• Invalid input follows the stderr and exit-status contract.
• Capabilities from earlier stages keep working.