V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
爱意满满的作品展示区。
azh7138m
V2EX  ›  分享创造

随机数据产生姬 - OJ 测试数据生成轮子

  •  3
     
  •   azh7138m ·
    muzea · 2019-01-29 22:56:57 +08:00 · 2774 次点击
    这是一个创建于 2136 天前的主题,其中的信息可能已经有所发展或是发生改变。

    随机数据产生姬

    这是一个字符串拼接工具,可以用于 OJ 的测试数据生成, 点我在线体验

    语法

    假装自己有个 CFG

    template      = *[statement 1*breakLine]
    breakLine     = "\n"
    statement     = constraint | repeat
    constraint    = intConstraint | setConstraint
    intConstraint = "constraint" " " varName " " "int" " " number " " number
    setConstraint = "constraint" " " varName " " "set" " " setValues
    setValues     = stringValue [ " " setValues ]
    repeat        = repeatLine | repeatGroup
    repeatLine    = "repeat" " " varName|number " " repeatContent
    repeatGroup   = "repeat group" " " varName|number breakLine *[ repeatLine breakLine ] "end group"
    repeatContent = (utf8char - "$") | ( "${" varName "}" ) *repeatContent
    varName       = stringValue
    number        = 1*digit
    digit         = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
    stringValue   = 1*utf8char
    

    现在只支持两种语句

    constraint 约束 限制变量取值

    repeat 重复 会输出内容

    重要 每一个变量都需要有约束

    constraint 的语法

    int 类型

    constraint 变量名 int 最小值 最大值
    

    比如

    constraint n int 1 233
    

    变量名 最好都是字母(汉字也行)

    最小值和最大值可以是别的变量名

    区间是左闭右开

    set 类型

    constraint 变量名 set value1 value2 value3
    

    比如

    constraint 数字 set 一 二 三 四
    

    value 之间使用空格分隔

    repeat 的语法

    line 类型

    repeat 重复次数 重复的内容

    重复次数 可以是一个数字,也可以是一个变量

    从紧跟 重复次数 的空格后面开始,到这一行结束都会被视为一个模板,我们使用 ${变量名} 来引用一个变量

    比如

    repeat 1 ${n}
    

    亦或者

    repeat 1 prefix string ${n}
    

    都是被允许的

    group 类型

    repeat group 重复次数
    repeat line
    repeat line
    repeat line
    end group
    

    重复次数 可以是一个数字,也可以是一个变量

    案例

    普通案例

    举个例子,假如我们的数据是

    第一行输入一个 n,代表接下来有 n 行数据,每行数据有三个数 a b c

    那么就是

    repeat 1 ${n}
    repeat n ${a} ${b} ${c}
    

    然后补充一下约束就好了

    再举一个例子

    假如我们的数据是这个样子的

    第一行是 n,代表接下来有 n 组数据

    每组数据的第一行有三个数 row min max,代表接下来有 row 个数字,每个数字的取值是 [min, max)

    那我们可以这样写

    constraint n int 5 10
    constraint row int 10 20
    constraint min int 150 200
    constraint max int 500 1000
    constraint num int min max
    repeat 1 ${n}
    repeat group n
    repeat 1 ${row} ${min} ${max}
    repeat row ${num}
    end group
    

    来一个 set 的例子

    constraint 姓 set 赵 钱 孙 李
    constraint 名 set 一 二 三 四
    repeat 10 ${姓}${名}
    

    当然,本质是个字符串拼接,也可以写别的东西

    sql 测试数据

    constraint 姓 set 赵 钱 孙 李
    constraint 名 set 一 二 三 四
    constraint value int 10 1000
    constraint status int 0 2
    repeat 10 INSERT INTO list (name, value, status) VALUES ("${姓}${名}", ${value}, ${status});
    

    程序没有检查输入是否合法,所以需要你自己注意一下 :)

    更新计划

    不存在的

    13 条回复    2019-02-03 22:34:32 +08:00
    DaCong
        1
    DaCong  
       2019-01-30 15:49:07 +08:00
    能智能生成树和图吗?
    azh7138m
        2
    azh7138m  
    OP
       2019-01-30 16:44:22 +08:00
    @DaCong 给个 oj 题目看看,我考虑支持下
    DaCong
        3
    DaCong  
       2019-01-30 16:56:55 +08:00
    @azh7138m 其实我只是想知道和我现在在用的 https://github.com/luogu-dev/cyaron 比怎么样而已……所以就问了一下是否有相关功能……
    题目的话,随便找了一道图论的,涉及到生成一张图: https://www.luogu.org/problemnew/show/P1345。
    讲道理,OJ 题目里不是有很多有关树和图的吗?
    azh7138m
        4
    azh7138m  
    OP
       2019-01-30 16:59:30 +08:00
    @DaCong 写代码比较简单,我是想要一个足够简单(对使用者而言)的 DSL 来描述这个问题.......
    我考虑下图怎么实现
    azh7138m
        5
    azh7138m  
    OP
       2019-01-30 17:00:47 +08:00
    @DaCong 对我而言,当然是 luogu 的好点(
    轮子设计初衷是避免写代码 :)
    DaCong
        6
    DaCong  
       2019-01-30 17:02:12 +08:00
    @azh7138m 是的,我也是觉得用 Cyaron 写脚本有点烦,所以在找一个不用写太多东西的方法。
    azh7138m
        7
    azh7138m  
    OP
       2019-01-31 02:29:35 +08:00
    @DaCong https://www.luogu.org/problemnew/show/P1345
    增加新的类型的话,大概就是
    constraint 变量名 graph 点的数量 边的数量 是否有向(或者有向无向分开实现)
    然后需要修改下 constraint 的定义,增加一个,值在每个都取一次之前不会重复的限制符( c1 c2 不是一个数字),
    如果要考虑边权的话,还要增加限制符语法的话,就得分开实现四种图(边有无权 有无向),
    不过这样搞,图类型最后的输出格式就会是固定的,点 点 [权],看上去是可以做的
    azh7138m
        8
    azh7138m  
    OP
       2019-01-31 14:02:38 +08:00
    @DaCong
    语法会类似
    constraint N int 10 15
    constraint M int 5 8
    constraint c1 int 1 N
    constraint c2 int 1 N
    constraint g graph N M
    repeat 1 ${N} ${M} ${c1} ${c2}
    repeat 1 ${g}

    一个 mvp https://random-data-tpxdwsyajl.now.sh
    DaCong
        9
    DaCong  
       2019-01-31 14:14:11 +08:00
    @azh7138m 看上去不错!数据范围能定义吗?比如出极端数据。
    azh7138m
        10
    azh7138m  
    OP
       2019-01-31 14:18:56 +08:00
    @DaCong 极端数据的情况很难定义哎,对于图我只能想到全联通,这种是可以的,需要等我设计下限制符语法;当然啦,如果有明确的'极端'的定义,是可以做的。
    azh7138m
        11
    azh7138m  
    OP
       2019-01-31 14:20:45 +08:00
    @DaCong 数据范围可以是变量的
    constraint g graph N M
    边的数量是 N,这个是引用另一个变量的,后面的边也是变量 :)
    DaCong
        12
    DaCong  
       2019-01-31 15:33:01 +08:00
    @azh7138m 极端数据需要根据题目的要求改变,不是一个固定的概念,一般看出题人怎么想,一般来说,有数据范围控制,就够了。
    azh7138m
        13
    azh7138m  
    OP
       2019-02-03 22:34:32 +08:00
    @DaCong 胡乱写了一个版本,语法变更了一下
    https://random-data-mbkleb9xg.now.sh/
    https://github.com/muzea-demo/random-data/blob/feature/graph/sample/graph.txt

    constraint n int lower higher | flags
    flags 目前只有 shuffle 一个实现了,用来保证 c1 c2 取值是不同的
    constraint n graph 1 nodeNumber edgeNumber
    第一个 1 代表这个图里面有几个联通图,目前只实现了 1 的时候的逻辑,于是这个示例为了能跑起来,还增加了变量的计算(
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1057 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 19:22 · PVG 03:22 · LAX 11:22 · JFK 14:22
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.