from __future__ import annotations

import math
import re
from collections import Counter
from typing import Dict, List, Optional, Tuple

from models import SolverResult


# ============================================================
# basic parsing helpers
# ============================================================

def _clean(text: str) -> str:
    return (text or "").strip()


def _lower(text: str) -> str:
    return _clean(text).lower()


def _nums(text: str) -> List[int]:
    return [int(x) for x in re.findall(r"-?\d+", text)]


def _positive_ints(text: str) -> List[int]:
    return [n for n in _nums(text) if n > 0]


def _safe_int(value: str) -> Optional[int]:
    try:
        return int(value)
    except Exception:
        return None


def _has_any(text: str, phrases: List[str]) -> bool:
    return any(p in text for p in phrases)


def _normalize_math_words(text: str) -> str:
    t = _lower(text)
    replacements = {
        "greatest common factor": "gcf",
        "greatest common divisor": "gcd",
        "highest common factor": "gcf",
        "least common multiple": "lcm",
        "lowest common multiple": "lcm",
        "smallest common multiple": "lcm",
        "divides evenly": "divisible",
        "is a divisor of": "factor of",
        "is a factor of": "factor of",
        "odd integer": "odd",
        "even integer": "even",
        "composite number": "composite",
        "prime number": "prime",
        "perfect square": "square",
        "perfect cube": "cube",
    }
    for old, new in replacements.items():
        t = t.replace(old, new)
    return t


# ============================================================
# number theory core helpers
# ============================================================

def _is_prime(n: int) -> bool:
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    limit = int(math.isqrt(n))
    for d in range(3, limit + 1, 2):
        if n % d == 0:
            return False
    return True


def _prime_factorization(n: int) -> Dict[int, int]:
    n = abs(n)
    factors: Dict[int, int] = {}
    if n < 2:
        return factors

    while n % 2 == 0:
        factors[2] = factors.get(2, 0) + 1
        n //= 2

    d = 3
    while d * d <= n:
        while n % d == 0:
            factors[d] = factors.get(d, 0) + 1
            n //= d
        d += 2

    if n > 1:
        factors[n] = factors.get(n, 0) + 1

    return factors


def _factorization_string(factors: Dict[int, int]) -> str:
    if not factors:
        return ""
    parts = []
    for p in sorted(factors):
        exp = factors[p]
        parts.append(f"{p}^{exp}" if exp > 1 else str(p))
    return " * ".join(parts)


def _num_divisors_from_factors(factors: Dict[int, int]) -> int:
    total = 1
    for exp in factors.values():
        total *= (exp + 1)
    return total


def _sum_divisors_from_factors(factors: Dict[int, int]) -> int:
    total = 1
    for p, exp in factors.items():
        total *= (p ** (exp + 1) - 1) // (p - 1)
    return total


def _proper_divisors(n: int) -> List[int]:
    n = abs(n)
    if n <= 1:
        return []
    divisors = {1}
    root = int(math.isqrt(n))
    for d in range(2, root + 1):
        if n % d == 0:
            divisors.add(d)
            divisors.add(n // d)
    return sorted(divisors)


def _is_perfect_number(n: int) -> bool:
    if n <= 1:
        return False
    return sum(_proper_divisors(n)) == n


def _is_perfect_square(n: int) -> bool:
    if n < 0:
        return False
    r = int(math.isqrt(n))
    return r * r == n


def _is_perfect_cube(n: int) -> bool:
    if n == 0:
        return True
    sign = -1 if n < 0 else 1
    m = abs(n)
    r = round(m ** (1 / 3))
    return (r ** 3 == m) and sign in (-1, 1)


def _gcd_list(values: List[int]) -> int:
    g = 0
    for v in values:
        g = math.gcd(g, v)
    return abs(g)


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


def _lcm_list(values: List[int]) -> int:
    result = 1
    for v in values:
        result = _lcm(result, v)
    return result


def _digit_sum(n: int) -> int:
    return sum(int(ch) for ch in str(abs(n)))


def _alternating_digit_sum_for_11(n: int) -> int:
    digits = [int(ch) for ch in str(abs(n))]
    s1 = sum(digits[::2])
    s2 = sum(digits[1::2])
    return s1 - s2


def _divisibility_rule_result(n: int, d: int) -> Optional[bool]:
    if d == 2:
        return abs(n) % 2 == 0
    if d == 3:
        return _digit_sum(n) % 3 == 0
    if d == 4:
        return abs(n) % 100 % 4 == 0
    if d == 5:
        return str(abs(n))[-1] in {"0", "5"}
    if d == 6:
        return (abs(n) % 2 == 0) and (_digit_sum(n) % 3 == 0)
    if d == 8:
        return abs(n) % 1000 % 8 == 0
    if d == 9:
        return _digit_sum(n) % 9 == 0
    if d == 10:
        return str(abs(n))[-1] == "0"
    if d == 11:
        return _alternating_digit_sum_for_11(n) % 11 == 0
    if d == 12:
        return (_digit_sum(n) % 3 == 0) and (abs(n) % 100 % 4 == 0)
    if d == 25:
        return abs(n) % 100 in {0, 25, 50, 75}
    return None


def _remainder(a: int, b: int) -> Optional[int]:
    if b == 0:
        return None
    return a % b


def _consecutive_terms_from_text(text: str) -> Optional[int]:
    patterns = [
        r"(\d+)\s+consecutive",
        r"consecutive\s+(\d+)\s+(?:integers|numbers|terms)",
        r"sum of the first\s+(\d+)",
        r"product of\s+(\d+)\s+consecutive",
    ]
    for pat in patterns:
        m = re.search(pat, text)
        if m:
            return int(m.group(1))
    return None


# ============================================================
# explanation builders
# ============================================================

def _sr(
    solved: bool,
    internal_answer: Optional[str],
    steps: List[str],
    answer_value: Optional[str] = None,
) -> SolverResult:
    return SolverResult(
        domain="quant",
        solved=solved,
        topic="number_properties",
        answer_value=answer_value,
        internal_answer=internal_answer,
        steps=steps,
    )


def _generic_number_theory_steps() -> List[str]:
    return [
        "Identify the number property being tested: divisibility, factors, primes, GCD/LCM, parity, remainder, or square structure.",
        "Rewrite the number using prime factors or modular relationships if that makes the pattern easier to see.",
        "Use the relevant rule, then check whether the condition is satisfied.",
    ]


# ============================================================
# recognizers / solver blocks
# ============================================================

def _solve_prime_or_composite(text: str, nums: List[int]) -> Optional[SolverResult]:
    if not nums:
        return None

    if not _has_any(text, ["prime", "composite", "primality"]):
        return None

    n = nums[0]
    prime = _is_prime(n)
    result = "prime" if prime else "composite" if n > 1 else "not prime"

    return _sr(
        solved=True,
        internal_answer=result,
        answer_value=None,
        steps=[
            "This is a primality check.",
            "Test divisibility only up to the square root of the number.",
            "If no smaller factor pair exists, the number is prime; otherwise it is composite.",
        ],
    )


def _solve_prime_factorization(text: str, nums: List[int]) -> Optional[SolverResult]:
    if not nums:
        return None

    triggers = [
        "prime factorization",
        "prime factors",
        "factorize",
        "factorise",
        "written as a product of primes",
    ]
    if not _has_any(text, triggers):
        return None

    n = nums[0]
    if abs(n) < 2:
        return _sr(
            solved=False,
            internal_answer=None,
            answer_value=None,
            steps=[
                "Prime factorization is only useful for integers with absolute value greater than 1.",
                "Send the full integer to factor.",
            ],
        )

    fac = _prime_factorization(n)
    fac_str = _factorization_string(fac)

    return _sr(
        solved=True,
        internal_answer=fac_str,
        answer_value=None,
        steps=[
            "Break the number into smaller factor pairs.",
            "Continue until every remaining factor is prime.",
            "Group repeated primes using exponents.",
        ],
    )


def _solve_factor_count(text: str, nums: List[int]) -> Optional[SolverResult]:
    if not nums:
        return None

    triggers = [
        "number of factors",
        "how many factors",
        "count factors",
        "total factors",
        "number of divisors",
        "how many divisors",
    ]
    if not _has_any(text, triggers):
        return None

    n = nums[0]
    if abs(n) < 1:
        return None

    fac = _prime_factorization(n)
    total = _num_divisors_from_factors(fac)

    return _sr(
        solved=True,
        internal_answer=str(total),
        answer_value=None,
        steps=[
            "Start with the prime factorization.",
            "If n = p^a * q^b * ..., then the number of positive factors is (a+1)(b+1)...",
            "Each exponent contributes one more choice than its power because you can use 0 through that power.",
        ],
    )


def _solve_sum_of_factors(text: str, nums: List[int]) -> Optional[SolverResult]:
    if not nums:
        return None

    triggers = [
        "sum of factors",
        "sum of divisors",
        "sum of all factors",
        "sum of all divisors",
    ]
    if not _has_any(text, triggers):
        return None

    n = nums[0]
    if abs(n) < 1:
        return None

    fac = _prime_factorization(n)
    total = _sum_divisors_from_factors(fac)

    return _sr(
        solved=True,
        internal_answer=str(total),
        answer_value=None,
        steps=[
            "Write the prime factorization first.",
            "Use the geometric-series factor formula for each prime power.",
            "Multiply the separate prime-power sums together.",
        ],
    )


def _solve_factor_or_multiple_or_divisible(text: str, nums: List[int]) -> Optional[SolverResult]:
    if len(nums) < 2:
        return None

    a, b = nums[0], nums[1]

    if "factor of" in text or _has_any(text, ["is factor", "a factor of", "factor?"]):
        if a == 0:
            return None
        ok = (b % a == 0)
        return _sr(
            solved=True,
            internal_answer=str(ok),
            answer_value=None,
            steps=[
                "A is a factor of B exactly when B divided by A leaves remainder 0.",
                "So the job is to test clean divisibility, not estimate size.",
            ],
        )

    if _has_any(text, ["multiple of", "is a multiple", "multiple?"]):
        if b == 0:
            return None
        ok = (a % b == 0)
        return _sr(
            solved=True,
            internal_answer=str(ok),
            answer_value=None,
            steps=[
                "A is a multiple of B when A = Bk for some integer k.",
                "Equivalent test: A divided by B leaves remainder 0.",
            ],
        )

    if _has_any(text, ["divisible by", "divisible", "evenly divisible"]):
        if b == 0:
            return None
        ok = (a % b == 0)
        return _sr(
            solved=True,
            internal_answer=str(ok),
            answer_value=None,
            steps=[
                "Divisibility means there is no remainder.",
                "Translate the question into a remainder test.",
            ],
        )

    return None


def _solve_divisibility_rules(text: str, nums: List[int]) -> Optional[SolverResult]:
    if len(nums) < 2:
        return None

    if not _has_any(text, ["divisible by", "divisibility rule", "is divisible"]):
        return None

    n, d = nums[0], nums[1]
    rule_result = _divisibility_rule_result(n, d)
    if rule_result is None:
        return None

    rule_steps_map = {
        2: "Check whether the last digit is even.",
        3: "Add the digits and test whether that sum is divisible by 3.",
        4: "Check whether the last two digits form a multiple of 4.",
        5: "Check whether the last digit is 0 or 5.",
        6: "A number must be divisible by both 2 and 3.",
        8: "Check whether the last three digits form a multiple of 8.",
        9: "Add the digits and test whether that sum is divisible by 9.",
        10: "Check whether the number ends in 0.",
        11: "Take the alternating digit sum and test divisibility by 11.",
        12: "A number must be divisible by both 3 and 4.",
        25: "Check whether the last two digits are 00, 25, 50, or 75.",
    }

    return _sr(
        solved=True,
        internal_answer=str(rule_result),
        answer_value=None,
        steps=[
            "This is a divisibility-rule question.",
            rule_steps_map[d],
            "Use the shortcut rule instead of doing full division.",
        ],
    )


def _solve_gcd_lcm(text: str, nums: List[int]) -> Optional[SolverResult]:
    if len(nums) < 2:
        return None

    relevant = _has_any(text, ["gcd", "gcf", "lcm"])
    if not relevant:
        return None

    values = nums[:]
    if "gcd" in text or "gcf" in text:
        result = _gcd_list(values)
        return _sr(
            solved=True,
            internal_answer=str(result),
            answer_value=None,
            steps=[
                "Find the common prime factors shared by all numbers.",
                "For GCD/GCF, keep the smallest exponent of each shared prime.",
                "Multiply those shared prime parts together.",
            ],
        )

    if "lcm" in text:
        result = _lcm_list(values)
        return _sr(
            solved=True,
            internal_answer=str(result),
            answer_value=None,
            steps=[
                "Find the prime factorization of each number.",
                "For LCM, keep every prime that appears, using the largest exponent needed.",
                "Multiply those required prime powers together.",
            ],
        )

    return None


def _solve_gcd_lcm_product_relation(text: str, nums: List[int]) -> Optional[SolverResult]:
    if len(nums) < 3:
        return None

    triggers = [
        "ab = gcd*lcm",
        "product of two numbers equals gcd times lcm",
        "gcd and lcm",
        "gcf and lcm",
    ]
    if not _has_any(text, triggers):
        return None

    # Heuristic:
    # if 3 numbers and asking for a missing one, often the known values are a, gcd, lcm
    a, b, c = nums[0], nums[1], nums[2]
    candidates = [
        ("x_from_a_gcd_lcm", (b * c) // a if a != 0 and (b * c) % a == 0 else None),
        ("x_from_gcd_lcm_a", (a * c) // b if b != 0 and (a * c) % b == 0 else None),
        ("x_from_gcd_lcm_a_alt", (a * b) // c if c != 0 and (a * b) % c == 0 else None),
    ]
    vals = [v for _, v in candidates if v is not None]
    if not vals:
        return None

    return _sr(
        solved=True,
        internal_answer=str(vals[0]),
        answer_value=None,
        steps=[
            "Use the identity: product of two integers = GCD × LCM.",
            "Substitute the known values and isolate the missing quantity.",
            "Then check that the result is consistent with integer conditions.",
        ],
    )


def _solve_even_odd(text: str, nums: List[int]) -> Optional[SolverResult]:
    if not nums:
        return None

    n = nums[0]

    if "even" in text and not _has_any(text, ["odd", "evenly spaced", "evenly"]):
        return _sr(
            solved=True,
            internal_answer=str(n % 2 == 0),
            answer_value=None,
            steps=[
                "An integer is even when it is divisible by 2.",
                "Equivalently, it leaves remainder 0 when divided by 2.",
            ],
        )

    if "odd" in text:
        return _sr(
            solved=True,
            internal_answer=str(n % 2 != 0),
            answer_value=None,
            steps=[
                "An integer is odd when it leaves remainder 1 when divided by 2.",
                "Equivalently, it is not divisible by 2.",
            ],
        )

    parity_triggers = [
        "even + even", "even + odd", "odd + odd",
        "even - even", "even - odd", "odd - odd",
        "even * even", "even * odd", "odd * odd",
        "parity"
    ]
    if _has_any(text, parity_triggers):
        return _sr(
            solved=False,
            internal_answer=None,
            answer_value=None,
            steps=[
                "Translate each term into parity form: even = 2k, odd = 2k+1.",
                "Then simplify the expression.",
                "Use parity rules: even±even=even, even±odd=odd, odd±odd=even, and any product with an even factor is even.",
            ],
        )

    return None


def _solve_remainder(text: str, nums: List[int]) -> Optional[SolverResult]:
    if len(nums) < 2:
        return None

    triggers = [
        "remainder",
        "mod",
        "modulo",
        "when divided by",
        "leaves remainder",
    ]
    if not _has_any(text, triggers):
        return None

    # direct form: "remainder when a is divided by b"
    a, b = nums[0], nums[1]
    r = _remainder(a, b)
    if r is None:
        return None

    return _sr(
        solved=True,
        internal_answer=str(r),
        answer_value=None,
        steps=[
            "Use the division algorithm: dividend = divisor × quotient + remainder.",
            "The remainder must be at least 0 and smaller than the divisor.",
            "Compute the leftover after dividing by the given base.",
        ],
    )


def _solve_square_cube(text: str, nums: List[int]) -> Optional[SolverResult]:
    if not nums:
        return None

    n = nums[0]

    if _has_any(text, ["perfect square", "is square", "square?"]):
        return _sr(
            solved=True,
            internal_answer=str(_is_perfect_square(n)),
            answer_value=None,
            steps=[
                "A perfect square has even exponents in its prime factorization.",
                "You can also compare the number to the square of its integer root.",
            ],
        )

    if _has_any(text, ["perfect cube", "is cube", "cube?"]):
        fac = _prime_factorization(n)
        ok = all(exp % 3 == 0 for exp in fac.values()) if fac else _is_perfect_cube(n)
        return _sr(
            solved=True,
            internal_answer=str(ok),
            answer_value=None,
            steps=[
                "A perfect cube has prime-factor exponents that are multiples of 3.",
                "Alternatively, compare the number with the cube of its nearest integer root.",
            ],
        )

    if _has_any(text, ["least number to multiply", "smallest number to multiply", "make it a square"]):
        fac = _prime_factorization(n)
        needed = 1
        for p, exp in fac.items():
            if exp % 2 == 1:
                needed *= p
        return _sr(
            solved=True,
            internal_answer=str(needed),
            answer_value=None,
            steps=[
                "Write the prime factorization.",
                "For a perfect square, every prime exponent must be even.",
                "Multiply by exactly the primes whose exponents are currently odd.",
            ],
        )

    if _has_any(text, ["least number to divide", "smallest number to divide", "divide to make it a square"]):
        fac = _prime_factorization(n)
        needed = 1
        for p, exp in fac.items():
            if exp % 2 == 1:
                needed *= p
        return _sr(
            solved=True,
            internal_answer=str(needed),
            answer_value=None,
            steps=[
                "Write the prime factorization.",
                "To become a perfect square after division, remove primes with odd exponents.",
                "So divide by the product of the odd-exponent prime parts.",
            ],
        )

    return None


def _solve_consecutive_integers(text: str, nums: List[int]) -> Optional[SolverResult]:
    if not _has_any(text, ["consecutive", "consecutive integers", "consecutive numbers"]):
        return None

    k = _consecutive_terms_from_text(text)

    if _has_any(text, ["sum of", "sum is divisible", "sum divisible"]) and k is not None:
        divisible = (k % 2 == 1)
        return _sr(
            solved=True,
            internal_answer=str(divisible),
            answer_value=None,
            steps=[
                "For a set of consecutive integers, the sum equals average × number of terms.",
                "When the number of terms is odd, the average is an integer middle term, so the sum is divisible by the number of terms.",
                "When the number of terms is even, the average falls halfway between two integers, so that divisibility fails.",
            ],
        )

    if _has_any(text, ["product of", "product divisible"]) and k is not None:
        factorial_val = math.factorial(k)
        return _sr(
            solved=True,
            internal_answer=str(factorial_val),
            answer_value=None,
            steps=[
                "The product of k consecutive integers is always divisible by k!.",
                "Think of those consecutive terms as containing one complete set of factors needed for 1 through k.",
            ],
        )

    return _sr(
        solved=False,
        internal_answer=None,
        answer_value=None,
        steps=[
            "For consecutive integers, define them with a central variable or starting variable.",
            "Use symmetry: average = (first + last) / 2.",
            "Then rewrite the sum or divisibility condition in that form.",
        ],
    )


def _solve_positive_negative_sign(text: str, nums: List[int]) -> Optional[SolverResult]:
    if not _has_any(text, ["positive", "negative", "sign"]):
        return None

    if len(nums) < 2:
        return _sr(
            solved=False,
            internal_answer=None,
            answer_value=None,
            steps=[
                "Track the sign separately from the magnitude.",
                "A product or quotient is negative when there are an odd number of negative factors.",
                "It is positive when there are an even number of negative factors.",
            ],
        )

    return None


def _solve_units_digit_or_last_digit(text: str, nums: List[int]) -> Optional[SolverResult]:
    triggers = ["last digit", "units digit", "unit digit"]
    if not _has_any(text, triggers):
        return None

    if len(nums) == 1:
        n = nums[0]
        return _sr(
            solved=True,
            internal_answer=str(abs(n) % 10),
            answer_value=None,
            steps=[
                "The last digit of an integer is its remainder when divided by 10.",
                "Only the final digit matters for units-digit questions.",
            ],
        )

    # simple product form: use all listed integers
    product_last = 1
    for n in nums:
        product_last = (product_last * (abs(n) % 10)) % 10

    return _sr(
        solved=True,
        internal_answer=str(product_last),
        answer_value=None,
        steps=[
            "For last-digit products, only the last digit of each factor matters.",
            "Reduce each factor to its units digit, then multiply cyclically mod 10.",
            "You never need the full product.",
        ],
    )


def _solve_integer_or_real_type(text: str, nums: List[int]) -> Optional[SolverResult]:
    if _has_any(text, ["integer", "integers"]) and "consecutive" not in text:
        return _sr(
            solved=False,
            internal_answer=None,
            answer_value=None,
            steps=[
                "An integer is a whole number: ..., -2, -1, 0, 1, 2, ...",
                "Fractions and decimals are not integers unless they simplify to a whole number.",
                "Check whether the expression must evaluate to a whole-number value.",
            ],
        )

    if _has_any(text, ["rational", "irrational", "real number", "terminating decimal", "repeating decimal"]):
        return _sr(
            solved=False,
            internal_answer=None,
            answer_value=None,
            steps=[
                "Rational numbers can be written as a fraction of integers.",
                "Terminating and repeating decimals are rational; non-terminating non-repeating decimals are irrational.",
                "Use the decimal pattern or fraction form to classify the number.",
            ],
        )

    return None


# ============================================================
# master solver
# ============================================================

def solve_number_properties(text: str) -> Optional[SolverResult]:
    raw = _clean(text)
    if not raw:
        return None

    lower = _normalize_math_words(raw)
    nums = _nums(lower)

    broad_triggers = [
        "divisible", "multiple", "factor", "prime", "composite",
        "gcd", "gcf", "lcm", "even", "odd", "remainder", "mod",
        "square", "cube", "consecutive", "integer", "positive", "negative",
        "last digit", "units digit", "divisor", "number of factors",
        "sum of factors", "prime factorization"
    ]
    if not _has_any(lower, broad_triggers):
        return None

    # ordered from most specific to more general
    blocks = [
        _solve_prime_factorization,
        _solve_factor_count,
        _solve_sum_of_factors,
        _solve_gcd_lcm_product_relation,
        _solve_gcd_lcm,
        _solve_divisibility_rules,
        _solve_factor_or_multiple_or_divisible,
        _solve_prime_or_composite,
        _solve_square_cube,
        _solve_remainder,
        _solve_consecutive_integers,
        _solve_units_digit_or_last_digit,
        _solve_even_odd,
        _solve_positive_negative_sign,
        _solve_integer_or_real_type,
    ]

    for block in blocks:
        try:
            result = block(lower, nums)
            if result is not None:
                return result
        except Exception:
            continue

    return _sr(
        solved=False,
        internal_answer=None,
        answer_value=None,
        steps=_generic_number_theory_steps(),
    )