py-14-regex-engine

# Backtracking regex matcher

Implement a file **`solution.py`** containing a function `fullmatch` that decides
whether a regular expression matches a string. You must implement the matching
yourself with a **backtracking** algorithm — **do not** call Python's `re` module.

```python
def fullmatch(pattern: str, text: str) -> bool:
    """Return True iff `pattern` matches the ENTIRE `text`."""
```

`fullmatch` is **anchored**: the pattern must consume the entire `text`, as if it
were wrapped in an implicit `^...$`. Matching only a prefix of `text` is **not**
a match.

## Supported syntax

An *element* is the smallest matchable unit. It is one of:

- A **literal character** — matches exactly itself (e.g. `a` matches `"a"`).
- `.` — matches **any single character**.
- An **escaped character** `\x` — the backslash strips any special meaning from
  the next character, which then matches **literally**. So `\.` matches a literal
  `.`, `\*` a literal `*`, `\\` a literal backslash, `\[` a literal `[`. Escaping
  an ordinary character (e.g. `\a`) just matches that character.
- A **character class** `[...]`:
  - `[abc]` matches any **one** of the listed characters.
  - `[^abc]` matches any one character **not** listed (a *negated* class). The `^`
    is special only as the **first** character inside the brackets.
  - **Ranges** like `[a-z]`, `[0-9]`, `[A-Za-z0-9]` match any character whose code
    point falls in the (inclusive) range.
  - A `-` that appears **first or last** inside the class (right after `[` or
    `[^`, or right before `]`) is a **literal** `-`, not a range.
  - A class always matches **exactly one** character of `text` (so a class can
    never match against the empty string at a position).

## Quantifiers

A quantifier applies to the **single preceding element**:

- `*` — **zero or more** of the preceding element.
- `+` — **one or more** of the preceding element.
- `?` — **zero or one** of the preceding element.

Quantifiers are **greedy**: they consume as many repetitions as possible, but they
**must backtrack** — giving repetitions back one at a time — so that the rest of
the pattern can still match and the **whole** text can be consumed.

A quantifier always binds to the whole element immediately to its left, where an
element is a literal char, an escaped char `\x`, `.`, or an entire `[...]` class.
For example, in `a[0-9]*b` the `*` applies to the class `[0-9]`, and in `\.*` the
`*` applies to the escaped literal dot.

## Not supported

There are **no** groups `(...)` and **no** alternation `|`. You do not need to
handle them.

## Semantics / edge cases

- The **empty pattern** matches **only** the empty string.
- `a*` matches `""` (zero repetitions). `a+` does **not** match `""`.
- Greedy backtracking: `a*a` matches `"aaa"` — the `*` first grabs all three
  `a`s, then gives one back so the trailing `a` can match.
- `.*` matches **anything** (including `""`); `.+` matches any non-empty string.
- Anchoring: `a` does **not** match `"ab"` (trailing `b` unconsumed), and `b` does
  not match `"ab"` (leading `a` unconsumed).

## Worked example

```python
assert fullmatch("a*a", "aaa") is True      # '*' backtracks, gives back one 'a'
assert fullmatch("a+", "") is False         # '+' needs at least one
assert fullmatch("a?b", "b") is True        # '?' matches zero
assert fullmatch("[a-z]+[0-9]*", "abc12") is True
assert fullmatch("[^0-9]+", "abc") is True  # negated class
assert fullmatch("h\\.t", "h.t") is True    # escaped dot is literal
assert fullmatch("h.t", "hat") is True      # '.' matches any char
assert fullmatch("a.c", "ac") is False      # '.' needs one char
assert fullmatch("colou?r", "color") is True
assert fullmatch("", "") is True
assert fullmatch("", "x") is False
```

from solution import fullmatch


def test_empty_pattern_matches_only_empty():
    assert fullmatch("", "") is True
    assert fullmatch("", "x") is False
    assert fullmatch("", "abc") is False


def test_plain_literals():
    assert fullmatch("abc", "abc") is True
    assert fullmatch("abc", "abd") is False
    assert fullmatch("a", "a") is True
    assert fullmatch("a", "") is False


def test_anchoring_requires_full_consume():
    # leading and trailing extra chars must cause failure
    assert fullmatch("a", "ab") is False
    assert fullmatch("b", "ab") is False
    assert fullmatch("ab", "abc") is False
    assert fullmatch("bc", "abc") is False
    assert fullmatch("abc", "ab") is False


def test_dot_matches_any_single_char():
    assert fullmatch("h.t", "hat") is True
    assert fullmatch("h.t", "h9t") is True
    assert fullmatch(".", "x") is True
    assert fullmatch(".", "") is False     # needs exactly one char
    assert fullmatch("a.c", "ac") is False  # dot must consume one
    assert fullmatch("...", "abc") is True
    assert fullmatch("...", "ab") is False


def test_star_zero_or_more():
    assert fullmatch("a*", "") is True
    assert fullmatch("a*", "a") is True
    assert fullmatch("a*", "aaaa") is True
    assert fullmatch("a*", "aaab") is False
    assert fullmatch("ba*", "b") is True
    assert fullmatch("ba*c", "bc") is True
    assert fullmatch("ba*c", "baaac") is True


def test_plus_one_or_more():
    assert fullmatch("a+", "") is False
    assert fullmatch("a+", "a") is True
    assert fullmatch("a+", "aaa") is True
    assert fullmatch("a+", "aaab") is False
    assert fullmatch("ba+c", "bac") is True
    assert fullmatch("ba+c", "bc") is False


def test_question_zero_or_one():
    assert fullmatch("a?", "") is True
    assert fullmatch("a?", "a") is True
    assert fullmatch("a?", "aa") is False
    assert fullmatch("colou?r", "color") is True
    assert fullmatch("colou?r", "colour") is True
    assert fullmatch("colou?r", "colouur") is False
    assert fullmatch("a?b", "b") is True
    assert fullmatch("a?b", "ab") is True


def test_greedy_backtracking_star():
    # '*' must give characters back so the trailing 'a' can match
    assert fullmatch("a*a", "aaa") is True
    assert fullmatch("a*a", "a") is True
    assert fullmatch("a*a", "") is False     # need at least one 'a'
    assert fullmatch("a*ab", "aaab") is True
    assert fullmatch("a*ab", "ab") is True


def test_dotstar_matches_anything():
    assert fullmatch(".*", "") is True
    assert fullmatch(".*", "anything at all 123 !@#") is True
    assert fullmatch(".+", "") is False
    assert fullmatch(".+", "x") is True
    # backtracking through dot-star
    assert fullmatch(".*b", "aaabxb") is True
    assert fullmatch(".*b", "aaabx") is False


def test_dotstar_backtracking_with_suffix():
    assert fullmatch("a.*z", "az") is True
    assert fullmatch("a.*z", "abcz") is True
    assert fullmatch("a.*z", "abc") is False
    assert fullmatch("x.*y.*z", "xyz") is True
    assert fullmatch("x.*y.*z", "x111y222z") is True


def test_char_class_basic():
    assert fullmatch("[abc]", "a") is True
    assert fullmatch("[abc]", "b") is True
    assert fullmatch("[abc]", "c") is True
    assert fullmatch("[abc]", "d") is False
    assert fullmatch("[abc]", "") is False
    assert fullmatch("[abc]", "ab") is False  # class matches exactly one


def test_char_class_ranges():
    assert fullmatch("[a-z]", "m") is True
    assert fullmatch("[a-z]", "M") is False
    assert fullmatch("[0-9]", "7") is True
    assert fullmatch("[0-9]", "a") is False
    assert fullmatch("[A-Za-z0-9]", "Q") is True
    assert fullmatch("[A-Za-z0-9]", "q") is True
    assert fullmatch("[A-Za-z0-9]", "5") is True
    assert fullmatch("[A-Za-z0-9]", "_") is False


def test_char_class_with_quantifiers():
    assert fullmatch("[a-z]+", "hello") is True
    assert fullmatch("[a-z]+", "Hello") is False
    assert fullmatch("[a-z]+[0-9]*", "abc12") is True
    assert fullmatch("[a-z]+[0-9]*", "abc") is True
    assert fullmatch("[a-z]+[0-9]*", "123") is False
    assert fullmatch("[0-9]*", "") is True


def test_negated_char_class():
    assert fullmatch("[^0-9]", "a") is True
    assert fullmatch("[^0-9]", "5") is False
    assert fullmatch("[^0-9]+", "abc") is True
    assert fullmatch("[^0-9]+", "ab3c") is False
    assert fullmatch("[^abc]", "d") is True
    assert fullmatch("[^abc]", "a") is False


def test_literal_dash_in_class():
    # '-' first or last in the class is a literal dash
    assert fullmatch("[-a]", "-") is True
    assert fullmatch("[-a]", "a") is True
    assert fullmatch("[a-]", "-") is True
    assert fullmatch("[a-]", "a") is True
    assert fullmatch("[a-]", "b") is False
    # literal dash in a negated class
    assert fullmatch("[^-]", "-") is False
    assert fullmatch("[^-]", "x") is True


def test_escaped_metacharacters():
    assert fullmatch("h\\.t", "h.t") is True
    assert fullmatch("h\\.t", "hat") is False   # escaped dot is literal
    assert fullmatch("a\\*b", "a*b") is True
    assert fullmatch("a\\*b", "aab") is False
    assert fullmatch("a\\\\b", "a\\b") is True   # \\ -> literal backslash
    assert fullmatch("\\[x\\]", "[x]") is True
    assert fullmatch("a\\+", "a+") is True
    assert fullmatch("a\\?", "a?") is True


def test_escaped_element_with_quantifier():
    # quantifier applies to the escaped element
    assert fullmatch("\\.*", "") is True
    assert fullmatch("\\.*", "...") is True
    assert fullmatch("\\.*", ".a.") is False
    assert fullmatch("\\*+", "***") is True
    assert fullmatch("\\*+", "") is False


def test_combined_realistic_patterns():
    # identifier-ish: letter then letters/digits/underscore-via-class
    assert fullmatch("[a-z][a-z0-9]*", "x") is True
    assert fullmatch("[a-z][a-z0-9]*", "var123") is True
    assert fullmatch("[a-z][a-z0-9]*", "1var") is False
    # crude decimal: digits . digits
    assert fullmatch("[0-9]+\\.[0-9]+", "3.14") is True
    assert fullmatch("[0-9]+\\.[0-9]+", "3.") is False
    assert fullmatch("[0-9]+\\.[0-9]+", ".14") is False
    assert fullmatch("[0-9]+\\.[0-9]+", "10.005") is True


def test_clear_non_matches():
    assert fullmatch("abc", "") is False
    assert fullmatch("a+b+", "aaa") is False
    assert fullmatch("[xyz]+", "xya") is False
    assert fullmatch("a.c.e", "abcd") is False
    assert fullmatch("a*b*c*", "cba") is False

You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.

```python
def fullmatch(pattern: str, text: str) -> bool:
    """Return True iff `pattern` matches the ENTIRE `text`."""
    
    # --- Helper: Parse the pattern into a list of tokens ---
    # Tokens are tuples: (type, value)
    # Types: 'LIT', 'DOT', 'CLASS', 'STAR', 'PLUS', 'QUEST'
    tokens = []
    i = 0
    n = len(pattern)
    
    while i < n:
        char = pattern[i]
        
        if char == '\\':
            # Escaped character
            if i + 1 < n:
                tokens.append(('LIT', pattern[i+1]))
                i += 2
            else:
                # Trailing backslash, treat as literal backslash
                tokens.append(('LIT', '\\'))
                i += 1
        elif char == '.':
            tokens.append(('DOT', None))
            i += 1
        elif char == '[':
            # Character class
            i += 1
            if i >= n:
                # Malformed, treat as literal [
                tokens.append(('LIT', '['))
                break
            
            is_negated = False
            if pattern[i] == '^':
                is_negated = True
                i += 1
            
            # Parse class contents
            class_content = []
            while i < n and pattern[i] != ']':
                if i + 1 < n and pattern[i] == '-':
                    # Check if '-' is a literal hyphen (first or last)
                    # We are at '-', check previous char or next char
                    prev_is_first = (len(class_content) == 0)
                    next_is_last = (i + 2 >= n or pattern[i+2] == ']')
                    
                    if prev_is_first or next_is_last:
                        class_content.append('-')
                        i += 1
                    else:
                        # Range start
                        start = pattern[i]
                        i += 1
                        if i >= n or pattern[i] == ']':
                            # Incomplete range, treat as literal -
                            class_content.append('-')
                            break
                        end = pattern[i]
                        i += 1
                        class_content.append((start, end))
                else:
                    class_content.append(pattern[i])
                    i += 1
            
            if i < n and pattern[i] == ']':
                i += 1
            
            tokens.append(('CLASS', (is_negated, class_content)))
            
        elif char in '*+?':
            # Quantifier
            tokens.append((char, None))
            i += 1
        else:
            # Literal character
            tokens.append(('LIT', char))
            i += 1

    # --- Backtracking Matcher ---
    
    def match(token_idx: int, text_idx: int) -> bool:
        # Base case: if we consumed all tokens, we must have consumed all text
        if token_idx == len(tokens):
            return text_idx == len(text)
        
        token_type, token_val = tokens[token_idx]
        
        if token_type == 'LIT':
            if text_idx < len(text) and text[text_idx] == token_val:
                return match(token_idx + 1, text_idx + 1)
            return False
            
        elif token_type == 'DOT':
            if text_idx < len(text):
                return match(token_idx + 1, text_idx + 1)
            return False
            
        elif token_type == 'CLASS':
            is_negated, class_content = token_val
            if text_idx >= len(text):
                return False
            
            char = text[text_idx]
            in_class = False
            
            for item in class_content:
                if isinstance(item, str):
                    if char == item:
                        in_class = True
                        break
                else:
                    start, end = item
                    if start <= char <= end:
                        in_class = True
                        break
            
            if is_negated:
                in_class = not in_class
            
            if in_class:
                return match(token_idx + 1, text_idx + 1)
            return False
            
        elif token_type == 'STAR':
            # Zero or more repetitions
            # Greedy: try to match as many as possible first
            # Backtrack: if we fail later, try matching fewer
            
            # 1. Try to match zero characters (immediate success)
            if match(token_idx + 1, text_idx):
                return True
            
            # 2. Try to match one or more characters
            # We consume one char and try to match the rest of the pattern
            # If that fails, we consume another char and try again
            while text_idx < len(text):
                # Consume one character
                text_idx += 1
                # Check if the rest of the pattern matches from this new position
                if match(token_idx + 1, text_idx):
                    return True
            
            return False
            
        elif token_type == 'PLUS':
            # One or more repetitions
            # Must match at least one character
            
            # Try to match one character first
            if text_idx < len(text):
                # Consume one char
                text_idx += 1
                # Now try to match zero or more of the same token
                # (STAR allows backtracking)
                if match(token_idx + 1, text_idx):
                    return True
            
            return False
            
        elif token_type == 'QUEST':
            # Zero or one repetitions
            # Try zero first (greedy)
            if match(token_idx + 1, text_idx):
                return True
            
            # Try one
            if text_idx < len(text):
                text_idx += 1
                if match(token_idx + 1, text_idx):
                    return True
            
            return False
            
        return False

    return match(0, 0)
```

[
  {
    "total": 19,
    "answer": "```python\ndef fullmatch(pattern: str, text: str) -> bool:\n    \"\"\"Return True iff `pattern` matches the ENTIRE `text`.\"\"\"\n    \n    # --- Helper: Parse the pattern into a list of tokens ---\n    # Tokens are tuples: (type, value)\n    # Types: 'LIT', 'DOT', 'CLASS', 'STAR', 'PLUS', 'QUEST'\n    tokens = []\n    i = 0\n    n = len(pattern)\n    \n    while i < n:\n        char = pattern[i]\n        \n        if char == '\\\\':\n            # Escaped character\n            if i + 1 < n:\n                tokens.append(('LIT', pattern[i+1]))\n                i += 2\n            else:\n                # Trailing backslash, treat as literal backslash\n                tokens.append(('LIT', '\\\\'))\n                i += 1\n        elif char == '.':\n            tokens.append(('DOT', None))\n            i += 1\n        elif char == '[':\n            # Character class\n            i += 1\n            if i >= n:\n                # Malformed, treat as literal [\n                tokens.append(('LIT', '['))\n                break\n            \n            is_negated = False\n            if pattern[i] == '^':\n                is_negated = True\n                i += 1\n            \n            # Parse class contents\n            class_content = []\n            while i < n and pattern[i] != ']':\n                if i + 1 < n and pattern[i] == '-':\n                    # Check if '-' is a literal hyphen (first or last)\n                    # We are at '-', check previous char or next char\n                    prev_is_first = (len(class_content) == 0)\n                    next_is_last = (i + 2 >= n or pattern[i+2] == ']')\n                    \n                    if prev_is_first or next_is_last:\n                        class_content.append('-')\n                        i += 1\n                    else:\n                        # Range start\n                        start = pattern[i]\n                        i += 1\n                        if i >= n or pattern[i] == ']':\n                            # Incomplete range, treat as literal -\n                            class_content.append('-')\n                            break\n                        end = pattern[i]\n                        i += 1\n                        class_content.append((start, end))\n                else:\n                    class_content.append(pattern[i])\n                    i += 1\n            \n            if i < n and pattern[i] == ']':\n                i += 1\n            \n            tokens.append(('CLASS', (is_negated, class_content)))\n            \n        elif char in '*+?':\n            # Quantifier\n            tokens.append((char, None))\n            i += 1\n        else:\n            # Literal character\n            tokens.append(('LIT', char))\n            i += 1\n\n    # --- Backtracking Matcher ---\n    \n    def match(token_idx: int, text_idx: int) -> bool:\n        # Base case: if we consumed all tokens, we must have consumed all text\n        if token_idx == len(tokens):\n            return text_idx == len(text)\n        \n        token_type, token_val = tokens[token_idx]\n        \n        if token_type == 'LIT':\n            if text_idx < len(text) and text[text_idx] == token_val:\n                return match(token_idx + 1, text_idx + 1)\n            return False\n            \n        elif token_type == 'DOT':\n            if text_idx < len(text):\n                return match(token_idx + 1, text_idx + 1)\n            return False\n            \n        elif token_type == 'CLASS':\n            is_negated, class_content = token_val\n            if text_idx >= len(text):\n                return False\n            \n            char = text[text_idx]\n            in_class = False\n            \n            for item in class_content:\n                if isinstance(item, str):\n                    if char == item:\n                        in_class = True\n                        break\n                else:\n                    start, end = item\n                    if start <= char <= end:\n                        in_class = True\n                        break\n            \n            if is_negated:\n                in_class = not in_class\n            \n            if in_class:\n                return match(token_idx + 1, text_idx + 1)\n            return False\n            \n        elif token_type == 'STAR':\n            # Zero or more repetitions\n            # Greedy: try to match as many as possible first\n            # Backtrack: if we fail later, try matching fewer\n            \n            # 1. Try to match zero characters (immediate success)\n            if match(token_idx + 1, text_idx):\n                return True\n            \n            # 2. Try to match one or more characters\n            # We consume one char and try to match the rest of the pattern\n            # If that fails, we consume another char and try again\n            while text_idx < len(text):\n                # Consume one character\n                text_idx += 1\n                # Check if the rest of the pattern matches from this new position\n                if match(token_idx + 1, text_idx):\n                    return True\n            \n            return False\n            \n        elif token_type == 'PLUS':\n            # One or more repetitions\n            # Must match at least one character\n            \n            # Try to match one character first\n            if text_idx < len(text):\n                # Consume one char\n                text_idx += 1\n                # Now try to match zero or more of the same token\n                # (STAR allows backtracking)\n                if match(token_idx + 1, text_idx):\n                    return True\n            \n            return False\n            \n        elif token_type == 'QUEST':\n            # Zero or one repetitions\n            # Try zero first (greedy)\n            if match(token_idx + 1, text_idx):\n                return True\n            \n            # Try one\n            if text_idx < len(text):\n                text_idx += 1\n                if match(token_idx + 1, text_idx):\n                    return True\n            \n            return False\n            \n        return False\n\n    return match(0, 0)\n```",
    "passed": 8,
    "test_error": "ullmatch('[a-z]', 'm')\n\ntest_regex_engine.py:103: AssertionError\n_______________________ test_char_class_with_quantifiers _______________________\n\n    def test_char_class_with_quantifiers():\n>       assert fullmatch(\"[a-z]+\", \"hello\") is True\nE       AssertionError: assert False is True\nE        +  where False = fullmatch('[a-z]+', 'hello')\n\ntest_regex_engine.py:114: AssertionError\n___________________________ test_negated_char_class ____________________________\n\n    def test_negated_char_class():\n        assert fullmatch(\"[^0-9]\", \"a\") is True\n>       assert fullmatch(\"[^0-9]\", \"5\") is False\nE       AssertionError: assert True is False\nE        +  where True = fullmatch('[^0-9]', '5')\n\ntest_regex_engine.py:124: AssertionError\n_____________________ test_escaped_element_with_quantifier _____________________\n\n    def test_escaped_element_with_quantifier():\n        # quantifier applies to the escaped element\n>       assert fullmatch(\"\\\\.*\", \"\") is True\nE       AssertionError: assert False is True\nE        +  where False = fullmatch('\\\\.*', '')\n\ntest_regex_engine.py:156: AssertionError\n_______________________ test_combined_realistic_patterns _______________________\n\n    def test_combined_realistic_patterns():\n        # identifier-ish: letter then letters/digits/underscore-via-class\n>       assert fullmatch(\"[a-z][a-z0-9]*\", \"x\") is True\nE       AssertionError: assert False is True\nE        +  where False = fullmatch('[a-z][a-z0-9]*', 'x')\n\ntest_regex_engine.py:165: AssertionError\n=========================== short test summary info ============================\nFAILED test_regex_engine.py::test_star_zero_or_more - AssertionError: assert ...\nFAILED test_regex_engine.py::test_plus_one_or_more - AssertionError: assert F...\nFAILED test_regex_engine.py::test_question_zero_or_one - AssertionError: asse...\nFAILED test_regex_engine.py::test_greedy_backtracking_star - AssertionError: ...\nFAILED test_regex_engine.py::test_dotstar_matches_anything - AssertionError: ...\nFAILED test_regex_engine.py::test_dotstar_backtracking_with_suffix - Assertio...\nFAILED test_regex_engine.py::test_char_class_ranges - AssertionError: assert ...\nFAILED test_regex_engine.py::test_char_class_with_quantifiers - AssertionErro...\nFAILED test_regex_engine.py::test_negated_char_class - AssertionError: assert...\nFAILED test_regex_engine.py::test_escaped_element_with_quantifier - Assertion...\nFAILED test_regex_engine.py::test_combined_realistic_patterns - AssertionErro...\n11 failed, 8 passed in 0.06s"
  },
  {
    "total": 19,
    "answer": "```python\ndef fullmatch(pattern: str, text: str) -> bool:\n    \"\"\"Return True iff `pattern` matches the ENTIRE `text`.\"\"\"\n    \n    # --- Helper: Parse the pattern into a list of tokens ---\n    # Tokens are tuples: (type, value)\n    # Types: 'LIT', 'DOT', 'CLASS', 'STAR', 'PLUS', 'QUEST'\n    tokens = []\n    i = 0\n    n = len(pattern)\n    \n    while i < n:\n        char = pattern[i]\n        \n        if char == '\\\\':\n            # Escaped character\n            if i + 1 < n:\n                tokens.append(('LIT', pattern[i+1]))\n                i += 2\n            else:\n                # Trailing backslash, treat as literal backslash\n                tokens.append(('LIT', '\\\\'))\n                i += 1\n        elif char == '.':\n            tokens.append(('DOT', None))\n            i += 1\n        elif char == '[':\n            # Character class\n            i += 1\n            if i >= n:\n                # Malformed, treat as literal [\n                tokens.append(('LIT', '['))\n                break\n            \n            is_negated = False\n            if pattern[i] == '^':\n                is_negated = True\n                i += 1\n            \n            # Parse class contents\n            class_content = []\n            while i < n and pattern[i] != ']':\n                if i + 1 < n and pattern[i] == '-':\n                    # Check if '-' is a literal hyphen (first or last)\n                    # We are at '-', check previous char or next char\n                    prev_is_first = (len(class_content) == 0)\n                    next_is_last = (i + 2 >= n or pattern[i+2] == ']')\n                    \n                    if prev_is_first or next_is_last:\n                        class_content.append('-')\n                        i += 1\n                    else:\n                        # Range start\n                        start = pattern[i]\n                        i += 1\n                        if i >= n or pattern[i] == ']':\n                            # Incomplete range, treat as literal -\n                            class_content.append('-')\n                            break\n                        end = pattern[i]\n                        i += 1\n                        class_content.append((start, end))\n                else:\n                    class_content.append(pattern[i])\n                    i += 1\n            \n            if i < n and pattern[i] == ']':\n                i += 1\n            \n            tokens.append(('CLASS', (is_negated, class_content)))\n            \n        elif char in '*+?':\n            # Quantifier\n            tokens.append((char, None))\n            i += 1\n        else:\n            # Literal character\n            tokens.append(('LIT', char))\n            i += 1\n\n    # --- Backtracking Matcher ---\n    \n    def match(token_idx: int, text_idx: int) -> bool:\n        # Base case: if we consumed all tokens, we must have consumed all text\n        if token_idx == len(tokens):\n            return text_idx == len(text)\n        \n        token_type, token_val = tokens[token_idx]\n        \n        if token_type == 'LIT':\n            if text_idx < len(text) and text[text_idx] == token_val:\n                return match(token_idx + 1, text_idx + 1)\n            return False\n            \n        elif token_type == 'DOT':\n            if text_idx < len(text):\n                return match(token_idx + 1, text_idx + 1)\n            return False\n            \n        elif token_type == 'CLASS':\n            is_negated, class_content = token_val\n            if text_idx >= len(text):\n                return False\n            \n            char = text[text_idx]\n            in_class = False\n            \n            for item in class_content:\n                if isinstance(item, str):\n                    if char == item:\n                        in_class = True\n                        break\n                else:\n                    start, end = item\n                    if start <= char <= end:\n                        in_class = True\n                        break\n            \n            if is_negated:\n                in_class = not in_class\n            \n            if in_class:\n                return match(token_idx + 1, text_idx + 1)\n            return False\n            \n        elif token_type == 'STAR':\n            # Zero or more repetitions\n            # Greedy: try to match as many as possible first\n            # Backtrack: if we fail later, try matching fewer\n            \n            # 1. Try to match zero characters (immediate success)\n            if match(token_idx + 1, text_idx):\n                return True\n            \n            # 2. Try to match one or more characters\n            # We consume one char and try to match the rest of the pattern\n            # If that fails, we consume another char and try again\n            while text_idx < len(text):\n                # Consume one character\n                text_idx += 1\n                # Check if the rest of the pattern matches from this new position\n                if match(token_idx + 1, text_idx):\n                    return True\n            \n            return False\n            \n        elif token_type == 'PLUS':\n            # One or more repetitions\n            # Must match at least one character\n            \n            # Try to match one character first\n            if text_idx < len(text):\n                # Consume one char\n                text_idx += 1\n                # Now try to match zero or more of the same token\n                # (STAR allows backtracking)\n                if match(token_idx + 1, text_idx):\n                    return True\n            \n            return False\n            \n        elif token_type == 'QUEST':\n            # Zero or one repetitions\n            # Try zero first (greedy)\n            if match(token_idx + 1, text_idx):\n                return True\n            \n            # Try one\n            if text_idx < len(text):\n                text_idx += 1\n                if match(token_idx + 1, text_idx):\n                    return True\n            \n            return False\n            \n        return False\n\n    return match(0, 0)\n```",
    "passed": 8,
    "test_error": "ullmatch('[a-z]', 'm')\n\ntest_regex_engine.py:103: AssertionError\n_______________________ test_char_class_with_quantifiers _______________________\n\n    def test_char_class_with_quantifiers():\n>       assert fullmatch(\"[a-z]+\", \"hello\") is True\nE       AssertionError: assert False is True\nE        +  where False = fullmatch('[a-z]+', 'hello')\n\ntest_regex_engine.py:114: AssertionError\n___________________________ test_negated_char_class ____________________________\n\n    def test_negated_char_class():\n        assert fullmatch(\"[^0-9]\", \"a\") is True\n>       assert fullmatch(\"[^0-9]\", \"5\") is False\nE       AssertionError: assert True is False\nE        +  where True = fullmatch('[^0-9]', '5')\n\ntest_regex_engine.py:124: AssertionError\n_____________________ test_escaped_element_with_quantifier _____________________\n\n    def test_escaped_element_with_quantifier():\n        # quantifier applies to the escaped element\n>       assert fullmatch(\"\\\\.*\", \"\") is True\nE       AssertionError: assert False is True\nE        +  where False = fullmatch('\\\\.*', '')\n\ntest_regex_engine.py:156: AssertionError\n_______________________ test_combined_realistic_patterns _______________________\n\n    def test_combined_realistic_patterns():\n        # identifier-ish: letter then letters/digits/underscore-via-class\n>       assert fullmatch(\"[a-z][a-z0-9]*\", \"x\") is True\nE       AssertionError: assert False is True\nE        +  where False = fullmatch('[a-z][a-z0-9]*', 'x')\n\ntest_regex_engine.py:165: AssertionError\n=========================== short test summary info ============================\nFAILED test_regex_engine.py::test_star_zero_or_more - AssertionError: assert ...\nFAILED test_regex_engine.py::test_plus_one_or_more - AssertionError: assert F...\nFAILED test_regex_engine.py::test_question_zero_or_one - AssertionError: asse...\nFAILED test_regex_engine.py::test_greedy_backtracking_star - AssertionError: ...\nFAILED test_regex_engine.py::test_dotstar_matches_anything - AssertionError: ...\nFAILED test_regex_engine.py::test_dotstar_backtracking_with_suffix - Assertio...\nFAILED test_regex_engine.py::test_char_class_ranges - AssertionError: assert ...\nFAILED test_regex_engine.py::test_char_class_with_quantifiers - AssertionErro...\nFAILED test_regex_engine.py::test_negated_char_class - AssertionError: assert...\nFAILED test_regex_engine.py::test_escaped_element_with_quantifier - Assertion...\nFAILED test_regex_engine.py::test_combined_realistic_patterns - AssertionErro...\n11 failed, 8 passed in 0.06s"
  },
  {
    "total": 19,
    "answer": "```python\ndef fullmatch(pattern: str, text: str) -> bool:\n    \"\"\"Return True iff `pattern` matches the ENTIRE `text`.\"\"\"\n    \n    # --- Helper: Parse the pattern into a list of tokens ---\n    # Tokens are tuples: (type, value)\n    # Types: 'LIT', 'DOT', 'CLASS', 'STAR', 'PLUS', 'QUEST'\n    tokens = []\n    i = 0\n    n = len(pattern)\n    \n    while i < n:\n        char = pattern[i]\n        \n        if char == '\\\\':\n            # Escaped character\n            if i + 1 < n:\n                tokens.append(('LIT', pattern[i+1]))\n                i += 2\n            else:\n                # Trailing backslash, treat as literal backslash\n                tokens.append(('LIT', '\\\\'))\n                i += 1\n        elif char == '.':\n            tokens.append(('DOT', None))\n            i += 1\n        elif char == '[':\n            # Character class\n            i += 1\n            if i >= n:\n                # Malformed, treat as literal [\n                tokens.append(('LIT', '['))\n                break\n            \n            is_negated = False\n            if pattern[i] == '^':\n                is_negated = True\n                i += 1\n            \n            # Parse class contents\n            class_content = []\n            while i < n and pattern[i] != ']':\n                if i + 1 < n and pattern[i] == '-':\n                    # Check if '-' is a literal hyphen (first or last)\n                    # We are at '-', check previous char or next char\n                    prev_is_first = (len(class_content) == 0)\n                    next_is_last = (i + 2 >= n or pattern[i+2] == ']')\n                    \n                    if prev_is_first or next_is_last:\n                        class_content.append('-')\n                        i += 1\n                    else:\n                        # Range start\n                        start = pattern[i]\n                        i += 1\n                        if i >= n or pattern[i] == ']':\n                            # Incomplete range, treat as literal -\n                            class_content.append('-')\n                            break\n                        end = pattern[i]\n                        i += 1\n                        class_content.append((start, end))\n                else:\n                    class_content.append(pattern[i])\n                    i += 1\n            \n            if i < n and pattern[i] == ']':\n                i += 1\n            \n            tokens.append(('CLASS', (is_negated, class_content)))\n            \n        elif char in '*+?':\n            # Quantifier\n            tokens.append((char, None))\n            i += 1\n        else:\n            # Literal character\n            tokens.append(('LIT', char))\n            i += 1\n\n    # --- Backtracking Matcher ---\n    \n    def match(token_idx: int, text_idx: int) -> bool:\n        # Base case: if we consumed all tokens, we must have consumed all text\n        if token_idx == len(tokens):\n            return text_idx == len(text)\n        \n        token_type, token_val = tokens[token_idx]\n        \n        if token_type == 'LIT':\n            if text_idx < len(text) and text[text_idx] == token_val:\n                return match(token_idx + 1, text_idx + 1)\n            return False\n            \n        elif token_type == 'DOT':\n            if text_idx < len(text):\n                return match(token_idx + 1, text_idx + 1)\n            return False\n            \n        elif token_type == 'CLASS':\n            is_negated, class_content = token_val\n            if text_idx >= len(text):\n                return False\n            \n            char = text[text_idx]\n            in_class = False\n            \n            for item in class_content:\n                if isinstance(item, str):\n                    if char == item:\n                        in_class = True\n                        break\n                else:\n                    start, end = item\n                    if start <= char <= end:\n                        in_class = True\n                        break\n            \n            if is_negated:\n                in_class = not in_class\n            \n            if in_class:\n                return match(token_idx + 1, text_idx + 1)\n            return False\n            \n        elif token_type == 'STAR':\n            # Zero or more repetitions\n            # Greedy: try to match as many as possible first\n            # Backtrack: if we fail later, try matching fewer\n            \n            # 1. Try to match zero characters (immediate success)\n            if match(token_idx + 1, text_idx):\n                return True\n            \n            # 2. Try to match one or more characters\n            # We consume one char and try to match the rest of the pattern\n            # If that fails, we consume another char and try again\n            while text_idx < len(text):\n                # Consume one character\n                text_idx += 1\n                # Check if the rest of the pattern matches from this new position\n                if match(token_idx + 1, text_idx):\n                    return True\n            \n            return False\n            \n        elif token_type == 'PLUS':\n            # One or more repetitions\n            # Must match at least one character\n            \n            # Try to match one character first\n            if text_idx < len(text):\n                # Consume one char\n                text_idx += 1\n                # Now try to match zero or more of the same token\n                # (STAR allows backtracking)\n                if match(token_idx + 1, text_idx):\n                    return True\n            \n            return False\n            \n        elif token_type == 'QUEST':\n            # Zero or one repetitions\n            # Try zero first (greedy)\n            if match(token_idx + 1, text_idx):\n                return True\n            \n            # Try one\n            if text_idx < len(text):\n                text_idx += 1\n                if match(token_idx + 1, text_idx):\n                    return True\n            \n            return False\n            \n        return False\n\n    return match(0, 0)\n```",
    "passed": 8,
    "test_error": ""
  }
]