Turingarena IOspec

一种指定输入/输出格式的语言，以及自动化 I/O 验证、解析器生成等工具。

注意：Turingarena IOspec 正在开发中。待实现的功能在此 README 中用 "TODO" 标记。

什么是 Turingarena IOspec？

当基于类似文件的输入和输出定义编程问题时，需要与问题解决者定义一个合同，其中指定以下内容

• 输入格式，
• 关于输入的假设，这些假设将得到保证，
• 输出格式，
• 关于输出的假设，输出必须满足这些假设才能被接受。

Turingarena IOspec 允许正式指定输入和输出的格式，以及它们的一些假设（只要遵循一些常规，这在 IOI-like 问题中非常常见）。

一旦指定了格式，以下任务可以自动化

• 生成
  • 在许多不同的编程语言中（TODO：目前仅支持 C++），
    • 框架 代码，该代码解析输入并格式化输出，提供对 I/O 的抽象（例如，在 CMS 问题中以意大利格式扮演“评分员”的角色），
    • 模板 代码，包含问题解决者需要实现的功能，一旦由问题解决者填写，无需管理 I/O，与框架结合后即可得到一个有效解决方案（TODO），
  • 输入/输出格式及其假设的易读描述，以多种输出格式（TODO），
• 验证（TODO）
  • 输入文件，
  • 输出文件，给定它们各自的输入
  • 动态交互式问题中的输入和输出流
• 规范化（待办事项）
  • 输入文件或流，以便输入生成器无需关注正确格式（例如，空格）
  • 输出文件或流，以便输出检查器可以假设输出格式正确（例如，空格）
• 转换输入/输出文件
  • 从文本到二进制以及反之（待办事项）
  • 从普通（文本或二进制）到结构化（例如，JSON）以及反之（待办事项）

规范语言

在IOspec中，格式使用一种类似于编程语言的语肓来描述，它从问题解决者的视角定义

• 输入应该如何解析
• 解决方案代码何时以及如何执行以计算输出
• 输出应该如何格式化
• 何时以及如何检查假设（待办事项）

举例胜于千言。以下是在边列表编码的图查找循环问题的I/O规范。

read N: n32, M: n32;

assume 2 <= N && N <= 100_000;
assume 1 <= M && M <= 1_000_000;

for i upto M {
    read A[i]: n32, B[i]: n32;

    assume 0 <= A[i] && A[i] < B[i] && B[i] < N;
}

call find_cycle(N, M, A, B) -> L: n32; // length of the cycle
assert 2 <= L && L <= N;

write L;

for i upto L {
    call get_cycle_node(i) -> u: n32;
    assert 0 <= u && u < N;

    write u;
}

该语言支持许多编程语言常见的特性，但它也有很多限制，这使其可用于自动化某些任务（否则会更难或不可能），同时使其更加紧凑。

特性

• 标量类型
  • 布尔值：bool（真或假，分别表示为1或0）
  • 自然数：n8、n16、n32、n64（自然数是非负整数，可以适应给定位大小的有符号整数，例如，n32可以包含从0到2^31 - 1的任何数字）
  • 整数：i8、i16、i32、i64（适应给定位大小的有符号整数，可以是正数或负数，但不包括最小负值，例如，i32可以包含从-2^31 + 1到2^31 - 1的任何数字）
• 聚合类型
  • 数组，在for循环中初始化
  • 可选（待办事项）
• 静态类型变量
• I/O指令（read和write）
• 调用问题解决者实现的函数（call）
  • 具有标量或聚合参数
  • 可选返回标量
• 基于范围的循环（for）
• 泛型循环（loop、break、continue）（待办事项）
• 条件语句和值匹配（if、switch）（待办事项）
• 算术和布尔表达式（待办事项）
• 使用单赋值变量重用表达式（let）（待办事项）
• 检查输入和输出假设（assume和assert）（待办事项）

    turingarena-iospec lint
        [--spec-file <spec-file>]

    turingarena-iospec code
        [--spec-file <spec-file>]
        [--target <file>]
        [--kind skeleton|template]
        [--language <lang>]

    turingarena-iospec run
        [--spec-file <spec-file>]
        [--input-source <input-file-or-pipe>]
        [--output-source <output-file-or-pipe>]
        [--input-target <input-file-or-pipe>]
        [--output-target <output-file-or-pipe>]
        [--ignore-assumptions]
        [--ignore-assertions]

read N: n32; // number of nodes

for u upto N {
    read D[u]: n32; // degree of u
    for i upto D[u] {
        read A[u][i]: n32; // adjacency list
    }
}

call find_cycle(N, D, A) -> L: n32; // length of cycle

write L;

for i upto L {
    call get_cycle_node(i) -> u: n32; // i-th node in the cycle
    write u;
}

#include <cstdio>
#include <cstdint>

int32_t find_cycle(int32_t N, int32_t* D, int32_t** A);

int32_t get_cycle_node(int32_t i);

int main() {
    int32_t N;
    scanf("%d", &N);

    int32_t* D = new int32_t[N];
    int32_t** A = new int32_t*[N];
    for(int32_t u = 0; u < N; u++) {
        scanf("%d", &D[u]);

        A[u] = new int32_t[D[u]];
        for(int i = 0; i < D[u]; i++) {
            scanf("%d", &A[u][i]);
        }
    }

    int32_t L = find_cycle(N, D, A);

    printf("%d\n", L);

    for(int32_t i = 0; i < L; i++) {
        int32_t u = get_cycle_node(i);

        printf("%d\n", u);
    }
}