from __future__ import annotations

import ast
import math
import re
from typing import Optional, List, Tuple

from models import SolverResult


# ----------------------------
# Helpers
# ----------------------------

def _clean(text: str) -> str:
    t = text or ""
    t = t.replace("−", "-").replace("–", "-").replace("—", "-")
    t = t.replace("×", "*").replace("·", "*")
    t = t.replace("÷", "/")
    t = t.replace("^", "**")
    t = t.replace("≡", " congruent ")
    t = t.replace("modulo", "mod")
    t = t.replace("modulus", "mod")
    t = re.sub(r"\s+", " ", t)
    return t.strip()


def _gcd(a: int, b: int) -> int:
    return math.gcd(a, b)


def _lcm(a: int, b: int) -> int:
    return abs(a * b) // math.gcd(a, b) if a and b else 0


def _normalize_remainder(r: int, m: int) -> int:
    return r % m


def _safe_int_eval(expr: str) -> Optional[int]:
    """
    Safely evaluate simple integer arithmetic expressions.
    Supports: +, -, *, //, / (only if exact), %, **, parentheses, unary +/-.
    """
    if not expr:
        return None

    expr = expr.strip()
    expr = expr.replace("^", "**")

    if re.search(r"[^0-9\+\-\*\/%\(\)\s]", expr):
        return None

    try:
        node = ast.parse(expr, mode="eval")
    except Exception:
        return None

    def _eval(n):
        if isinstance(n, ast.Expression):
            return _eval(n.body)

        if isinstance(n, ast.Constant):
            if isinstance(n.value, int):
                return n.value
            return None

        if isinstance(n, ast.UnaryOp) and isinstance(n.op, (ast.UAdd, ast.USub)):
            v = _eval(n.operand)
            if v is None:
                return None
            return +v if isinstance(n.op, ast.UAdd) else -v

        if isinstance(n, ast.BinOp):
            left = _eval(n.left)
            right = _eval(n.right)
            if left is None or right is None:
                return None

            if isinstance(n.op, ast.Add):
                return left + right
            if isinstance(n.op, ast.Sub):
                return left - right
            if isinstance(n.op, ast.Mult):
                return left * right
            if isinstance(n.op, ast.Mod):
                if right == 0:
                    return None
                return left % right
            if isinstance(n.op, ast.Pow):
                if right < 0 or right > 10000:
                    return None
                return left ** right
            if isinstance(n.op, ast.FloorDiv):
                if right == 0:
                    return None
                return left // right
            if isinstance(n.op, ast.Div):
                if right == 0:
                    return None
                if left % right != 0:
                    return None
                return left // right

        return None

    try:
        val = _eval(node)
        if isinstance(val, int):
            return val
    except Exception:
        return None
    return None


def _pow_mod(base: int, exp: int, mod: int) -> Optional[int]:
    if mod == 0 or exp < 0:
        return None
    return pow(base, exp, mod)


def _extract_choices(text: str) -> List[int]:
    """
    Pull numeric answer choices if they exist.
    """
    nums = re.findall(r"(?:^|[\s\(])(-?\d+)(?:[\s\),\.]|$)", text)
    out = []
    for n in nums:
        try:
            out.append(int(n))
        except Exception:
            pass
    return out


def _first_crt_solution(r1: int, m1: int, r2: int, m2: int) -> Optional[int]:
    """
    Find the smallest nonnegative x satisfying:
      x ≡ r1 (mod m1)
      x ≡ r2 (mod m2)
    Return None if inconsistent.
    """
    if m1 <= 0 or m2 <= 0:
        return None

    r1 %= m1
    r2 %= m2

    g = math.gcd(m1, m2)
    if (r1 - r2) % g != 0:
        return None

    step = m1
    limit_mod = _lcm(m1, m2)
    x = r1
    for _ in range(limit_mod // step + 2):
        if x % m2 == r2:
            return x
        x += step
    return None


def _make_result(
    internal_answer: str,
    steps: List[str],
    topic: str = "remainder",
    solved: bool = True,
    answer_value: Optional[str] = None,
    answer_letter: Optional[str] = None,
) -> SolverResult:
    # keep the true answer internal; downstream formatter should avoid printing it directly
    return SolverResult(
        domain="quant",
        solved=solved,
        topic=topic,
        answer_value=answer_value if answer_value is not None else internal_answer,
        answer_letter=answer_letter,
        internal_answer=internal_answer,
        steps=steps,
    )


def _mentions_remainders(lower: str) -> bool:
    triggers = [
        "remainder",
        "mod ",
        " mod",
        "divisible",
        "divided by",
        "leaves",
        "left over",
        "last digit",
        "units digit",
        "tens digit",
        "ones digit",
    ]
    return any(t in lower for t in triggers)


# ----------------------------
# Core patterns
# ----------------------------

def _solve_direct_numeric_remainder(text: str) -> Optional[SolverResult]:
    lower = text.lower()

    # "remainder when 17 is divided by 5"
    m = re.search(
        r"remainder.*?when\s+(.+?)\s+(?:is\s+)?divided\s+by\s+(-?\d+)",
        lower,
    )
    if m:
        expr = m.group(1).strip()
        mod = int(m.group(2))
        val = _safe_int_eval(expr)
        if val is not None and mod != 0:
            result = val % mod
            return _make_result(
                internal_answer=str(result),
                steps=[
                    "Write the dividend in quotient–remainder form: dividend = divisor × quotient + remainder.",
                    "Reduce the computed value modulo the divisor.",
                    "Keep the remainder nonnegative and smaller than the divisor.",
                ],
            )

    # "123 mod 10" or "123 % 10"
    m = re.search(r"(-?\d+(?:\s*[\+\-\*\/%]\s*-?\d+|\s*\*\*\s*-?\d+)*)\s*(?:mod|%)\s*(-?\d+)", lower)
    if m:
        expr = m.group(1).strip()
        mod = int(m.group(2))
        val = _safe_int_eval(expr)
        if val is not None and mod != 0:
            result = val % mod
            return _make_result(
                internal_answer=str(result),
                steps=[
                    "Interpret the expression as a modulo calculation.",
                    "Evaluate the expression carefully, then reduce modulo the divisor.",
                    "Adjust to the standard remainder range from 0 up to divisor - 1.",
                ],
            )

    return None


def _solve_last_digit_patterns(text: str) -> Optional[SolverResult]:
    lower = text.lower()

    # "last digit of 12345" / "ones digit of 12345"
    m = re.search(r"(?:last|ones|units)\s+digit\s+of\s+(.+)", lower)
    if m:
        expr = m.group(1).strip(" ?.")
        val = _safe_int_eval(expr)
        if val is not None:
            result = val % 10
            return _make_result(
                internal_answer=str(result),
                steps=[
                    "The last digit is the remainder upon division by 10.",
                    "So reduce the number modulo 10 rather than working with the entire value.",
                    "That gives the required digit.",
                ],
                topic="remainder",
            )

    # "tens digit of x" given remainder 30 when divided by 100 is harder DS style;
    # here support simple explicit numeric prompts only.
    m = re.search(r"remainder.*?divided by 100.*?is\s+(\d+)", lower)
    if m and ("tens digit" in lower):
        rem = int(m.group(1))
        tens = (rem // 10) % 10
        return _make_result(
            internal_answer=str(tens),
            steps=[
                "A remainder upon division by 100 preserves the last two digits.",
                "The tens digit is therefore the tens digit of that two-digit remainder.",
                "Read the target digit directly from the remainder.",
            ],
            topic="remainder",
        )

    return None


def _solve_known_remainder_linear_transform(text: str) -> Optional[SolverResult]:
    lower = text.lower()

    # n divided by m leaves remainder r; what remainder when k*n is divided by m?
    m = re.search(
        r"remainder\s+(?:is|of)\s+(\d+)\s+when\s+\w+\s+is\s+divided\s+by\s+(\d+).*?"
        r"what\s+is\s+the\s+remainder\s+when\s+(\d+)\s*\*?\s*\w+\s+is\s+divided\s+by\s+(\d+)",
        lower,
    )
    if m:
        r = int(m.group(1))
        old_mod = int(m.group(2))
        mult = int(m.group(3))
        new_mod = int(m.group(4))
        # only safe when divisor is same or the old divisor term remains divisible by new divisor
        if old_mod % new_mod == 0:
            result = (mult * r) % new_mod
            return _make_result(
                internal_answer=str(result),
                steps=[
                    "Replace the variable by divisor × quotient + known remainder.",
                    "Multiply through, then ignore the term guaranteed to stay divisible by the new divisor.",
                    "Reduce the remaining expression modulo the requested divisor.",
                ],
            )

    # n leaves remainder r on division by m. what is remainder when (a*n + b) is divided by m?
    m = re.search(
        r"(?:(?:when|if)\s+)?(?:positive\s+integer\s+)?([a-z])\s+(?:is\s+)?divided\s+by\s+(\d+)\s+"
        r"(?:has|leaves|gives)\s+(?:a\s+)?remainder\s+(?:of\s+)?(\d+).*?"
        r"what\s+is\s+the\s+remainder\s+when\s+([\-]?\d*)\s*\*?\s*\1\s*([+\-]\s*\d+)?\s+is\s+divided\s+by\s+(\d+)",
        lower,
    )
    if m:
        mod1 = int(m.group(2))
        r = int(m.group(3))
        a_txt = m.group(4).strip()
        b_txt = (m.group(5) or "").replace(" ", "")
        mod2 = int(m.group(6))

        if a_txt in ("", "+"):
            a = 1
        elif a_txt == "-":
            a = -1
        else:
            a = int(a_txt)

        b = int(b_txt) if b_txt else 0

        if mod1 == mod2:
            result = (a * r + b) % mod2
            return _make_result(
                internal_answer=str(result),
                steps=[
                    "Substitute the variable with its remainder class modulo the divisor.",
                    "Apply the linear transformation to the remainder instead of to the full number.",
                    "Reduce once more to keep the answer in the standard remainder range.",
                ],
            )

    # book-style: remainder 7 when n divided by 18; find remainder when n divided by 6
    m = re.search(
        r"remainder\s+(?:is|of)\s+(\d+)\s+when\s+([a-z])\s+is\s+divided\s+by\s+(\d+).*?"
        r"what\s+is\s+the\s+remainder\s+when\s+\2\s+is\s+divided\s+by\s+(\d+)",
        lower,
    )
    if m:
        r = int(m.group(1))
        big_mod = int(m.group(3))
        small_mod = int(m.group(4))
        if big_mod % small_mod == 0:
            result = r % small_mod
            return _make_result(
                internal_answer=str(result),
                steps=[
                    "Write the number as big divisor × quotient + known remainder.",
                    "If the big divisor is a multiple of the smaller divisor, that first term contributes no new remainder.",
                    "So reduce the known remainder by the smaller divisor.",
                ],
            )

    return None


def _solve_power_remainder(text: str) -> Optional[SolverResult]:
    lower = text.lower()

    # "when 51^25 is divided by 13"
    m = re.search(
        r"when\s+(-?\d+)\s*\*\*\s*(\d+)\s+is\s+divided\s+by\s+(\d+)", lower
    )
    if not m:
        m = re.search(
            r"when\s+(-?\d+)\s*\^\s*(\d+)\s+is\s+divided\s+by\s+(\d+)", text.lower()
        )
    if not m:
        m = re.search(
            r"remainder.*?when\s+(-?\d+)\s*(?:\^|\*\*)\s*(\d+)\s+(?:is\s+)?divided\s+by\s+(\d+)",
            lower,
        )

    if m:
        base = int(m.group(1))
        exp = int(m.group(2))
        mod = int(m.group(3))
        if mod != 0:
            result = pow(base, exp, mod)
            return _make_result(
                internal_answer=str(result),
                steps=[
                    "Reduce the base modulo the divisor first.",
                    "Then use modular exponentiation or a repeating cycle pattern.",
                    "Only the remainder class matters, not the full power.",
                ],
            )

    # special pattern: prime > 3, remainder when n^2 is divided by 12
    if "prime number greater than 3" in lower and ("n^2" in text.lower() or "n**2" in lower) and "divided by 12" in lower:
        result = 1
        return _make_result(
            internal_answer=str(result),
            steps=[
                "A prime greater than 3 is not divisible by 2 or 3.",
                "So it must be congruent to 1, 5, 7, or 11 modulo 12.",
                "Squaring any of those residue classes gives the same remainder modulo 12.",
            ],
        )

    return None


def _solve_two_congruences_same_variable(text: str) -> Optional[SolverResult]:
    lower = text.lower()

    # Example:
    # n leaves remainder 4 when divided by 6 and remainder 3 when divided by 5
    matches = re.findall(
        r"([a-z])\s+(?:is\s+)?(?:greater\s+than\s+\d+\s+and\s+)?(?:leaves|has|gives)\s+(?:a\s+)?remainder\s+(\d+)\s+"
        r"(?:after\s+division\s+by|when\s+divided\s+by)\s+(\d+)",
        lower,
    )

    if len(matches) >= 2:
        v1, r1, m1 = matches[0]
        v2, r2, m2 = matches[1]
        if v1 == v2:
            r1, m1, r2, m2 = int(r1), int(m1), int(r2), int(m2)
            first = _first_crt_solution(r1, m1, r2, m2)
            if first is not None:
                l = _lcm(m1, m2)

                # ask for remainder when same variable divided by lcm or another modulus
                q = re.search(
                    rf"what\s+is\s+the\s+remainder.*?{v1}.*?divided\s+by\s+(\d+)",
                    lower,
                )
                if q:
                    target_mod = int(q.group(1))
                    result = first % target_mod
                    return _make_result(
                        internal_answer=str(result),
                        steps=[
                            "Translate each condition into a congruence.",
                            "Find the first common value that satisfies both patterns, then express all solutions using the least common multiple of the divisors.",
                            "Reduce that shared residue class by the requested divisor.",
                        ],
                    )

                # if question explicitly asks remainder on division by lcm
                result = first % l
                return _make_result(
                    internal_answer=str(result),
                    steps=[
                        "Find the overlap of the two arithmetic patterns.",
                        "That overlap becomes the residue class modulo the least common multiple of the divisors.",
                        "The remainder on division by that common modulus is the first shared residue.",
                    ],
                )

    return None


def _solve_difference_same_remainders(text: str) -> Optional[SolverResult]:
    lower = text.lower()

    # x and y have same remainder mod 5 and mod 7; factor of x-y?
    m1 = re.search(
        r"when\s+positive\s+integer\s+x\s+is\s+divided\s+by\s+(\d+),\s+the\s+remainder\s+is\s+(\d+).*?"
        r"when\s+x\s+is\s+divided\s+by\s+(\d+),\s+the\s+remainder\s+is\s+(\d+)",
        lower,
        re.DOTALL,
    )
    m2 = re.search(
        r"when\s+positive\s+integer\s+y\s+is\s+divided\s+by\s+(\d+),\s+the\s+remainder\s+is\s+(\d+).*?"
        r"when\s+y\s+is\s+divided\s+by\s+(\d+),\s+the\s+remainder\s+is\s+(\d+)",
        lower,
        re.DOTALL,
    )

    if m1 and m2:
        ax1, ar1, ax2, ar2 = map(int, m1.groups())
        ay1, br1, ay2, br2 = map(int, m2.groups())

        if ax1 == ay1 and ax2 == ay2 and ar1 == br1 and ar2 == br2:
            must_factor = _lcm(ax1, ax2)
            return _make_result(
                internal_answer=str(must_factor),
                steps=[
                    "If two numbers leave the same remainder upon division by a modulus, their difference is divisible by that modulus.",
                    "Apply that idea to each divisor separately.",
                    "So the difference must be divisible by the least common multiple of those divisors.",
                ],
            )

    return None


def _solve_decimal_quotient_remainder(text: str) -> Optional[SolverResult]:
    lower = text.lower()

    # s/t = 64.12 ; what could be the remainder when s is divided by t?
    m = re.search(
        r"([a-z])\s*/\s*([a-z])\s*=\s*(\d+)\.(\d+).*?remainder\s+when\s+\1\s+is\s+divided\s+by\s+\2",
        lower,
    )
    if m:
        # If s/t = q + frac, then remainder / t = frac.
        # For 64.12 = 64 + 12/100 = 64 + 3/25, so remainder must be a multiple of 3.
        frac_num = int(m.group(4))
        frac_den = 10 ** len(m.group(4))
        g = _gcd(frac_num, frac_den)
        num = frac_num // g
        # remainder = num * k, t = den * k
        return _make_result(
            internal_answer=str(num),
            steps=[
                "Use dividend = divisor × quotient + remainder, then divide both sides by the divisor.",
                "The decimal part of the quotient equals remainder/divisor.",
                "Reduce the fractional part to lowest terms; the numerator controls the remainder pattern.",
            ],
        )

    return None


def _solve_divisibility_from_remainder_expression(text: str) -> Optional[SolverResult]:
    lower = text.lower()

    # Is n divisible by d? / what is remainder when expression divided by d?
    # x^3 - x pattern
    if ("x^3 - x" in text.lower() or "x**3 - x" in lower or "x^3-x" in text.lower()) and "divisible by 8" in lower:
        return _make_result(
            internal_answer="yes",
            steps=[
                "Factor the expression into consecutive integers.",
                "Among consecutive integers, use parity structure to identify enough factors of 2.",
                "That guarantees divisibility by the target power of 2.",
            ],
            topic="remainder",
            answer_value="yes",
        )

    return None


def _solve_smaller_dividend_than_divisor(text: str) -> Optional[SolverResult]:
    lower = text.lower()

    m = re.search(
        r"remainder.*?when\s+(\d+)\s+(?:is\s+)?divided\s+by\s+(\d+)",
        lower,
    )
    if m:
        a = int(m.group(1))
        b = int(m.group(2))
        if 0 <= a < b:
            return _make_result(
                internal_answer=str(a),
                steps=[
                    "If the dividend is smaller than the divisor, the quotient is 0.",
                    "So the entire dividend becomes the remainder.",
                    "No further reduction is needed.",
                ],
            )

    return None


# ----------------------------
# Fallback pattern helpers
# ----------------------------

def _solve_generic_known_remainder_question(text: str) -> Optional[SolverResult]:
    lower = text.lower()

    # Parse statements like:
    # "n divided by 5 has remainder 2"
    known = re.findall(
        r"([a-z])\s+(?:is\s+)?divided\s+by\s+(\d+)\s+(?:has|gives|leaves)\s+(?:a\s+)?remainder\s+(?:of\s+)?(\d+)",
        lower,
    )
    if not known:
        known = re.findall(
            r"remainder\s+(?:is|of)\s+(\d+)\s+when\s+([a-z])\s+is\s+divided\s+by\s+(\d+)",
            lower,
        )
        known = [(v, m, r) for (r, v, m) in known]

    if not known:
        return None

    var, mod, rem = known[0]
    mod = int(mod)
    rem = int(rem)

    # ask for variable itself divided by another modulus
    q = re.search(rf"what\s+is\s+the\s+remainder\s+when\s+{var}\s+is\s+divided\s+by\s+(\d+)", lower)
    if q:
        target = int(q.group(1))
        if mod % target == 0:
            result = rem % target
            return _make_result(
                internal_answer=str(result),
                steps=[
                    "Rewrite the number as divisor × quotient + remainder.",
                    "Check whether the known divisor is a multiple of the target divisor.",
                    "Then reduce the known remainder by the target divisor.",
                ],
            )

    return None


# ----------------------------
# Main entry
# ----------------------------

def solve_remainder(text: str) -> Optional[SolverResult]:
    raw = text or ""
    cleaned = _clean(raw)
    lower = cleaned.lower()

    if not _mentions_remainders(lower):
        return None

    solvers = [
        _solve_direct_numeric_remainder,
        _solve_smaller_dividend_than_divisor,
        _solve_last_digit_patterns,
        _solve_known_remainder_linear_transform,
        _solve_power_remainder,
        _solve_two_congruences_same_variable,
        _solve_difference_same_remainders,
        _solve_decimal_quotient_remainder,
        _solve_divisibility_from_remainder_expression,
        _solve_generic_known_remainder_question,
    ]

    for fn in solvers:
        try:
            out = fn(cleaned)
            if out is not None:
                return out
        except Exception:
            continue

    return None