Source code for onlinejudge_template.analyzer.constants

"""
the module to list constants used in given problems (e.g. 1000000007)

この module は問題中で使われている定数を列挙します。
この機能の実装は `kyuridenamida/atcoder-tools <https://github.com/kyuridenamida/atcoder-tools>`_ を参考にしています。

たとえば `Educational Codeforces Round 83: D. Count the Arrays <https://codeforces.com/contest/1312/problem/D>`_ に対しては
::

    {
        "MOD": 998244353,
    }

に相当する結果を返します。

MOD の値や YES / NO の文字列は間違えやすいため、この機能は便利です。
1000000007 でなく 10000000009 が使われていることに気付かず WA を出す、``Impossible`` と出力すべきところを ``impossible`` と出力してしまい WA になる、などの事態を防げます。
"""

import re
from logging import getLogger
from typing import *

from onlinejudge_template.types import *

logger = getLogger(__name__)


[docs]def list_constants_from_html(html: bytes) -> Dict[VarName, ConstantDecl]: replace = [ ("\\", ""), ("{", ""), ("}", ""), (",", ""), ("'", ""), (" ^ ", "^"), (" + ", "+"), ("10^9+7", "1000000007"), ("10^9+9", "1000000009"), ] normalized = html.decode() for a, b in replace: normalized = normalized.replace(a, b) mod: Set[int] = set() for value in (10**9 + 7, 10**9 + 9, 998244353): if re.search(r'\b' + re.escape(str(value)) + r'\b', normalized): mod.add(value) constants: Dict[VarName, ConstantDecl] = {} if len(mod) == 1: constants[VarName('MOD')] = ConstantDecl(name=VarName('MOD'), type=VarType.ValueInt, value=Expr(str(mod.pop()))) elif len(mod) >= 2: logger.error('too many MOD-like integers found: %s', mod) return constants
[docs]def list_constants_from_sample_cases(sample_cases: List[SampleCase]) -> Dict[VarName, ConstantDecl]: yes: Set[str] = set() no: Set[str] = set() first: Set[str] = set() second: Set[str] = set() for case in sample_cases: for token in case.output.decode().split(): if token.lower() in ("yes", "possible"): yes.add(token) if token.lower() in ("no", "impossible"): no.add(token) if token.lower() in ("first", "alice"): first.add(token) if token.lower() in ("second", "bob"): second.add(token) logger.debug('YES-like strings: %s', yes) logger.debug('NO-like strings: %s', no) logger.debug('Alice-like strings: %s', first) logger.debug('Bob-like strings: %s', second) constants: Dict[VarName, ConstantDecl] = {} if len(yes) == 1: constants[VarName('YES')] = ConstantDecl(name=VarName('YES'), type=VarType.String, value=yes.pop()) if len(no) == 1: constants[VarName('NO')] = ConstantDecl(name=VarName('NO'), type=VarType.String, value=no.pop()) if len(first) == 1: constants[VarName('FIRST')] = ConstantDecl(name=VarName('FIRST'), type=VarType.String, value=first.pop()) if len(second) == 1: constants[VarName('SECOND')] = ConstantDecl(name=VarName('SECOND'), type=VarType.String, value=second.pop()) return constants
[docs]def list_constants(*, html: Optional[bytes], sample_cases: Optional[List[SampleCase]]) -> Dict[VarName, ConstantDecl]: constants = {} if html is not None: constants.update(list_constants_from_html(html)) if sample_cases is not None: constants.update(list_constants_from_sample_cases(sample_cases)) return constants