import re
from typing import Optional


BOTANICAL_VEGETABLES = {
    "asparagus",
    "beet",
    "beets",
    "broccoli",
    "cabbage",
    "carrot",
    "carrots",
    "cauliflower",
    "celery",
    "fresh basil",
    "lettuce",
    "onion",
    "onions",
    "potato",
    "potatoes",
    "spinach",
    "sweet potato",
    "sweet potatoes",
}


def _normalized(text: str) -> str:
    return re.sub(r"\s+", " ", text or "").strip()


def _solve_reversed_instruction(question: str) -> Optional[str]:
    reversed_question = question[::-1].lower()
    if "opposite of the word" in reversed_question and "left" in reversed_question:
        return "Right"
    return None


def _parse_markdown_table(question: str) -> tuple[list[str], list[list[str]]]:
    rows = []
    for raw_line in question.splitlines():
        line = raw_line.strip()
        if not line.startswith("|") or not line.endswith("|"):
            continue
        cells = [cell.strip() for cell in line.strip("|").split("|")]
        if all(set(cell) <= {"-"} for cell in cells if cell):
            continue
        rows.append(cells)

    if len(rows) < 2:
        return [], []

    headers = rows[0][1:]
    body = rows[1:]
    return headers, body


def _solve_noncommutative_elements(question: str) -> Optional[str]:
    q = question.lower()
    if "commutative" not in q or "|" not in question:
        return None

    headers, body = _parse_markdown_table(question)
    if not headers or not body:
        return None

    table = {}
    for row in body:
        if len(row) < len(headers) + 1:
            continue
        row_key = row[0]
        table[row_key] = dict(zip(headers, row[1: len(headers) + 1]))

    involved = set()
    for left in headers:
        for right in headers:
            left_result = table.get(left, {}).get(right)
            right_result = table.get(right, {}).get(left)
            if left_result is not None and right_result is not None and left_result != right_result:
                involved.add(left)
                involved.add(right)

    if not involved:
        return None

    return ", ".join(sorted(involved))


def _solve_botanical_vegetables(question: str) -> Optional[str]:
    q = question.lower()
    if "vegetable" not in q or "alphabetize" not in q:
        return None

    candidates = []
    after_colon = question.split(":")[-1]
    for item in re.split(r",|\n|;", after_colon):
        item = item.strip().strip(".").lower()
        if item in BOTANICAL_VEGETABLES:
            candidates.append(item)

    if not candidates:
        return None

    return ", ".join(sorted(dict.fromkeys(candidates)))


def try_programmatic_answer(question: str) -> Optional[str]:
    question = question or ""

    for solver in (
        _solve_reversed_instruction,
        _solve_noncommutative_elements,
        _solve_botanical_vegetables,
    ):
        answer = solver(question)
        if answer is not None:
            return answer

    return None