onlinejudge_template.analyzer.minimum_tree module

the module to find minimum format trees from sample strings

この module はサンプル文字列から直接 (つまり、フォーマット文字列を用いずに) フォーマット木を推測します。利用可能なサンプル文字列の個数がひとつしかない場合での利用が想定されています。 フォーマット木に対する評価関数を固定しておき、すべてのサンプル文字列とマッチするフォーマット木の中で最小のものを求めるという形で実装されています。

たとえば

3
1 2
3 4 1 2
2 4 1

および

1
2 0 8

というサンプル文字列から

sequence([
    item("N"),
    newline(),
    loop(counter="i", size="N", sequence([
        item("K_i"),
        loop(counter="j", size="K_i",
            item("A", indices=("i", "j"))
        ),
        newline(),
    ])),
])

のようなフォーマット木 (FormatNode) を作ります。 この例の場合は

sequence([
    item("N"),
    newline(),
    loop(counter="i", size="N - 1", sequence([
        item("K_i"),
        loop(counter="j", size="K_i - 1",
            item("A", indices=("i", "j"))
        ),
        item("B", indices="i"),
        newline(),
    ])),
    item("L"),
    loop(counter="i", size="L",
        item("C", indices="i")
    ),
    newline(),
])

というフォーマット木もこれらのサンプルにマッチしますが、これは木の大きさが最小ではないので作られません。

内部のデータ構造は Haskell 風に書くと以下のような感じになります。 LoopNode が持つふたつの Int は、ループの回数を表現する変数の de Bruijn index およびその変数を修正するための -1, 0, 1 のいずれかの数です。 木の一部は構築途中である場合があります。

:: haskell
data Token
= IntToken Int | StrngToken | NewlineToken
data Node m
= LoopNode Int Int (m (Node m)) (m (Node m)) | IntNode (m (Node m)) | StringNode (m (Node m)) | NewlineNode (m (Node m)) | EOFNode

match :: Node Maybe -> [Token] -> Maybe MatchState …

size :: Node Maybe -> Int size (LoopNode _ delta body next) = 1 + abs delta + size body + size next size (IntNode next) = 1 + size next size (StringNode next) = 1 + size next size (NewlineNode next) = 1 + size next size EOFNode = 1

class onlinejudge_template.analyzer.minimum_tree.EnvItem(name, is_counter)[source]

Bases: tuple

is_counter

Alias for field number 1

name

Alias for field number 0

onlinejudge_template.analyzer.minimum_tree.construct_minimum_input_format_tree(*, instances: List[str], multiple_test_cases: bool = False) → Optional[onlinejudge_template.types.FormatNode][source]
onlinejudge_template.analyzer.minimum_tree.construct_minimum_output_format_tree(*, instances: List[str]) → Optional[onlinejudge_template.types.FormatNode][source]
onlinejudge_template.analyzer.minimum_tree.construct_minimum_output_format_tree_using_input_format(*, instances: List[onlinejudge_template.types.SampleCase], input_format: onlinejudge_template.types.FormatNode, input_variables: Dict[NewType.<locals>.new_type, onlinejudge_template.types.VarDecl], multiple_test_cases: bool) → Optional[onlinejudge_template.types.FormatNode][source]
onlinejudge_template.analyzer.minimum_tree.count_placeholder(node: onlinejudge_template.analyzer.minimum_tree._Node) → int[source]
onlinejudge_template.analyzer.minimum_tree.get_replaced_first_placeholder(node: onlinejudge_template.analyzer.minimum_tree._Node, subst: onlinejudge_template.analyzer.minimum_tree._Node) → Optional[onlinejudge_template.analyzer.minimum_tree._Node][source]
onlinejudge_template.analyzer.minimum_tree.get_tree_size(node: onlinejudge_template.analyzer.minimum_tree._Node) → int[source]
onlinejudge_template.analyzer.minimum_tree.list_next_possible_node(states: List[onlinejudge_template.analyzer.minimum_tree._MatchState]) → Iterator[onlinejudge_template.analyzer.minimum_tree._Node][source]
onlinejudge_template.analyzer.minimum_tree.run_match(node: onlinejudge_template.analyzer.minimum_tree._Node, state: onlinejudge_template.analyzer.minimum_tree._MatchState) → Optional[onlinejudge_template.analyzer.minimum_tree._MatchState][source]
Raises:_MatchStop
onlinejudge_template.analyzer.minimum_tree.tokenize_content(content: str) → Iterator[onlinejudge_template.analyzer.minimum_tree._Token][source]