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]¶