Spaces:
Running
Running
| """Parse, evaluate and check an arithmetic answer. | |
| An answer is an ordinary expression over the card values with + - * / and parentheses, | |
| for example ``(13 - 12 + 11 - 10 + 7) * 9 * 5 * 5``. Every card is used exactly once. | |
| Division is exact (rational), so intermediate fractions are allowed, as in the 24 game. | |
| Unary minus, powers, decimals and joining digits ("1" and "3" into "13") are not allowed. | |
| Expressions are trees: an ``int`` leaf or a ``(op, left, right)`` tuple. | |
| """ | |
| from __future__ import annotations | |
| import ast | |
| import re | |
| from collections import Counter | |
| from dataclasses import dataclass, field | |
| from fractions import Fraction | |
| from typing import Union | |
| Tree = Union[int, tuple] | |
| OPS = ("+", "-", "*", "/") | |
| _PRECEDENCE = {"+": 1, "-": 1, "*": 2, "/": 2} | |
| _AST_OPS = {ast.Add: "+", ast.Sub: "-", ast.Mult: "*", ast.Div: "/"} | |
| _LETTERS = {"A": "1", "J": "11", "Q": "12", "K": "13"} | |
| MAX_LENGTH = 400 | |
| # What people and models type for the four operators. | |
| _SYMBOLS = str.maketrans( | |
| { | |
| "×": "*", | |
| "x": "*", | |
| "X": "*", | |
| "·": "*", | |
| "∙": "*", | |
| "÷": "/", | |
| "−": "-", | |
| "–": "-", | |
| "—": "-", | |
| "[": "(", | |
| "]": ")", | |
| "{": "(", | |
| "}": ")", | |
| } | |
| ) | |
| class ExpressionError(ValueError): | |
| pass | |
| def apply(op: str, a: Fraction, b: Fraction) -> Fraction: | |
| if op == "+": | |
| return a + b | |
| if op == "-": | |
| return a - b | |
| if op == "*": | |
| return a * b | |
| if b == 0: | |
| raise ZeroDivisionError | |
| return a / b | |
| def evaluate(tree: Tree) -> Fraction: | |
| if isinstance(tree, int): | |
| return Fraction(tree) | |
| op, left, right = tree | |
| return apply(op, evaluate(left), evaluate(right)) | |
| def leaves(tree: Tree) -> list[int]: | |
| if isinstance(tree, int): | |
| return [tree] | |
| return leaves(tree[1]) + leaves(tree[2]) | |
| def to_text(tree: Tree, pretty: bool = False) -> str: | |
| """Write a tree with the fewest parentheses; pretty=True uses × ÷ − like a person would.""" | |
| symbols = {"+": "+", "-": "−", "*": "×", "/": "÷"} if pretty else {o: o for o in OPS} | |
| def walk(node: Tree) -> tuple[str, int]: | |
| if isinstance(node, int): | |
| return str(node), 3 | |
| op, left, right = node | |
| prec = _PRECEDENCE[op] | |
| ltext, lprec = walk(left) | |
| rtext, rprec = walk(right) | |
| if lprec < prec: | |
| ltext = f"({ltext})" | |
| if rprec < prec or (rprec == prec and op in "-/"): | |
| rtext = f"({rtext})" | |
| return f"{ltext} {symbols[op]} {rtext}", prec | |
| return walk(tree)[0] | |
| def steps(tree: Tree) -> list[str]: | |
| """The solution as spoken, one combination per line: "13 − 12 = 1", "1 + 1 = 2", ...""" | |
| lines: list[str] = [] | |
| def walk(node: Tree) -> Fraction: | |
| if isinstance(node, int): | |
| return Fraction(node) | |
| op, left, right = node | |
| a, b = walk(left), walk(right) | |
| value = apply(op, a, b) | |
| sym = {"+": "+", "-": "−", "*": "×", "/": "÷"}[op] | |
| lines.append(f"{fmt(a)} {sym} {fmt(b)} = {fmt(value)}") | |
| return value | |
| walk(tree) | |
| return lines | |
| def fmt(value: Fraction) -> str: | |
| return str(value.numerator) if value.denominator == 1 else f"{value.numerator}/{value.denominator}" | |
| def normalize(text: str) -> str: | |
| text = text.strip().translate(_SYMBOLS).replace("**", "^") | |
| # "... = 2025": judge the left-hand side; the value is checked against the target anyway. | |
| if "=" in text: | |
| text = text.split("=", 1)[0] | |
| # Card letters as values: A, J, Q, K (only as whole tokens). | |
| text = re.sub(r"\b([AJQK])\b", lambda m: _LETTERS[m.group(1)], text) | |
| return text.strip() | |
| def parse(text: str) -> Tree: | |
| """Parse an answer into a tree, rejecting anything but integers, + - * / and parentheses.""" | |
| if not isinstance(text, str) or not text.strip(): | |
| raise ExpressionError("empty expression") | |
| if len(text) > MAX_LENGTH: | |
| raise ExpressionError(f"expression longer than {MAX_LENGTH} characters") | |
| source = normalize(text) | |
| if "^" in source: | |
| raise ExpressionError("powers are not allowed") | |
| try: | |
| node = ast.parse(source, mode="eval").body | |
| except SyntaxError as exc: | |
| raise ExpressionError(f"not an arithmetic expression: {source!r}") from exc | |
| def build(n: ast.AST) -> Tree: | |
| if isinstance(n, ast.Constant) and type(n.value) is int and n.value >= 0: | |
| return n.value | |
| if isinstance(n, ast.BinOp) and type(n.op) in _AST_OPS: | |
| return (_AST_OPS[type(n.op)], build(n.left), build(n.right)) | |
| if isinstance(n, ast.UnaryOp): | |
| raise ExpressionError("unary minus or plus is not allowed; every card must be combined with a binary operator") | |
| if isinstance(n, ast.Constant): | |
| raise ExpressionError(f"only whole card values are allowed, not {n.value!r}") | |
| raise ExpressionError(f"only + - * / and parentheses are allowed (found {type(n).__name__})") | |
| return build(node) | |
| class Check: | |
| """Everything the grader knows about one answer.""" | |
| expression: str | |
| parsed: bool = False | |
| uses_all_cards: bool = False | |
| value: Fraction | None = None | |
| exact: bool = False | |
| error: str | None = None | |
| missing: list[int] = field(default_factory=list) | |
| extra: list[int] = field(default_factory=list) | |
| canonical: str | None = None | |
| def to_dict(self) -> dict: | |
| return { | |
| "expression": self.expression, | |
| "parsed": self.parsed, | |
| "uses_all_cards": self.uses_all_cards, | |
| "value": None if self.value is None else fmt(self.value), | |
| "exact": self.exact, | |
| "error": self.error, | |
| "missing": self.missing, | |
| "extra": self.extra, | |
| "canonical": self.canonical, | |
| } | |
| def check(expression: str, card_values: list[int], target: int) -> Check: | |
| result = Check(expression=expression) | |
| try: | |
| tree = parse(expression) | |
| except ExpressionError as exc: | |
| result.error = str(exc) | |
| return result | |
| result.parsed = True | |
| result.canonical = to_text(tree) | |
| used, have = Counter(leaves(tree)), Counter(card_values) | |
| result.missing = sorted((have - used).elements()) | |
| result.extra = sorted((used - have).elements()) | |
| result.uses_all_cards = not result.missing and not result.extra | |
| try: | |
| result.value = evaluate(tree) | |
| except ZeroDivisionError: | |
| result.error = "division by zero" | |
| return result | |
| if not result.uses_all_cards: | |
| parts = [] | |
| if result.missing: | |
| parts.append("unused cards " + ", ".join(map(str, result.missing))) | |
| if result.extra: | |
| parts.append("numbers that are not cards on the table " + ", ".join(map(str, result.extra))) | |
| result.error = "; ".join(parts) | |
| return result | |
| result.exact = result.value == target | |
| return result | |