使用 docker 作为 online judge(OJ) 的 sandbox (2)

This article is deprecated, please see here for more details.

使用 docker 作为 online judge(OJ) 的 sandbox (1) 中我们讨论了OJ在架构上的大概实现,现在我们继续讨论判题(以  leetcode-Longest Common Prefix 为例)。

我们首先将一个完整的题目拆分为以下几个模块:

(1)测试集

(2)用户提交代码

(3)将测试集和用户提交的代码结合在一起,并运行出测试结果的预置代码(以下简称测试代码)

测试集

测试集由两部分构成:输入和输出。考虑以下两点:

一、我们不能简单地将输入和输出理解为两个字符串:输入有可能是复杂的数据结构,而针对某个题目是否回答正确的判定标准也不仅仅是输出一项(有可能包括检查输入数据),所以输入和输出需要一个可以存储复杂数据结构的传输格式构成;

二、某一道题需要针对不同的语言提供不同的测试代码,在不同的语言当中初始化数据的方式不尽相同。

由以上两点得出:合理的方式应该是JSON存储输入和输出,并保存在DB中。

用户提交代码

用户提交的代码没有太多的规范,安全性和对现有web系统的影响已经在(1)中讨论过了。

测试代码

这里是最有意思的部分:如何通过现有的测试数据来测试用户提交的代码是正确的?

在Javascript中,我们有一个现成的方法:.apply,我们可以将测试代码传给它来达到测试的目的:

// var input = [["aa","ab","ac"]];
// var output = "a";
if(output != longestCommonPrefix.apply(this, input)) {
    // 没有通过本测试
}

同理,在其它脚本语言中,也都有类似的技巧:

PHP – call_user_func_array

Python – getattr

Javascript’s Apply in Ruby

但是在Java / C / C++ 中,是没有类似的函数或者语法糖可以直接拿来使用的,好在 Java 中有反射可以给我们使用

Object result = this.getClass().getDeclaredMethod("multiply", classes).invoke(this,ints);

Java 的反射也有其弊端:很难在运行时确定提供的参数类型,而 C / C++ 则根本没有反射,所以我们需要换一个办法来处理:将用户提交的代码和测试代码拼接到一起,并写入到独立的文件中进行测试。缺点是:每道题都需要提供一段独立的测试代码来进行拼接(而如果使用 Javascript 的 apply 方法进行测试则没有这种问题:这段测试代码可以去和任意一段用户提交的代码 + 测试数据拼接来进行测试)

下面的两个例子是Javascript和Java的,分别对应上面提到的两种情况:

// ========  用户提交代码  ========
/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if(strs.length === 0) return "";

    var shortest_string_length = strs[0].length;
    for(var i = 0; i < strs.length; i++) {
        if(strs[i].length < shortest_string_length) {
            shortest_string_length = strs[i].length;
        }
    }

    var result = "";
    loop:
    for(var j = 0; j < shortest_string_length; j++) {
        var mark = strs[0].charAt(j);
        for(var k = 0; k < strs.length; k++) {
            if(strs[k].charAt(j) != mark) {
                break loop;
            }
        }
        result = result + mark;
    }

    return result;
};
// ========  用户提交代码  ========

// ========  由DB数据生成的测试集  ========
var test_set = [
    {"input":[[]], "output":""},
    {"input":[[""]], "output":""},
    {"input":[["a"]], "output":"a"},
    {"input":[["","a"]], "output":""},
    {"input":[["a","b"]], "output":""},
    {"input":[["aa","ab","ac"]], "output":"a"},
    {"input":[["","ab","ac"]], "output":""},
    {"input":[["aaaaaaaaaaaaaaa","aaaaavvvvvv"]], "output":"aaaaa"},
    {"input":[["a","bbbbbbbbbbbbbbbbbbbbbbb"]], "output":""},
    {"input":[["","",""]], "output":""},
    {"input":[["0123456789","0111"]], "output":"01"}
];
// ========  由DB数据生成的测试集  ========

// ========  测试代码  ========
for (var i = 0; i < test_set.length; i++) {
    var input  = test_set[i]["input"];
    var output = test_set[i]["output"];
    try {
        if(output != longestCommonPrefix.apply(this, input)) {
            console.log(JSON.stringify({
                "message": "Wrong Answer",
                "code": 1,
                "data": {
                    "input": input[0],
                    "output": output,
                    "calculated": longestCommonPrefix.apply(this, input)
                }
            }));
            process.exit();
        }
    }
    catch (err) {
        console.log(JSON.stringify({
            "message": err.toString(),
            "code": 2
        }));
        process.exit();
    }
}

console.log(JSON.stringify({
    "message": "AC",
    "code": 0
}));
process.exit();
// ========  测试代码  ========
import java.util.ArrayList;

import com.fasterxml.jackson.databind.ObjectMapper;

public class Oj {
    public static void main(String[] args) {

        // ========  由DB数据生成的测试集  ========
        ArrayList<TestCase> testCases = new ArrayList<>();
        testCases.add(new TestCase(new String[]{}, ""));
        testCases.add(new TestCase(new String[]{""}, ""));
        testCases.add(new TestCase(new String[]{"a"}, "a"));
        testCases.add(new TestCase(new String[]{"", "a"}, ""));
        testCases.add(new TestCase(new String[]{"a","b"}, ""));
        testCases.add(new TestCase(new String[]{"aa","ab","ac"}, "a"));
        testCases.add(new TestCase(new String[]{"","ab","ac"}, ""));
        testCases.add(new TestCase(new String[]{"aaaaaaaaaaaaaaa","aaaaavvvvvv"}, "aaaaa"));
        testCases.add(new TestCase(new String[]{"a","bbbbbbbbbbbbbbbbbbbbbbb"}, ""));
        testCases.add(new TestCase(new String[]{"","",""}, ""));
        testCases.add(new TestCase(new String[]{"0123456789","0111"}, "01"));
        // ========  由DB数据生成的测试集  ========

        ObjectMapper objectMapper = new ObjectMapper();

        try {
            Solution s = new Solution();

            for (TestCase tc : testCases) {
                String calculatedResult = s.longestCommonPrefix(tc.getStrs());
                String result = tc.getResult();

                if(!calculatedResult.equals(result)) {
                    ErrorResponseData errorResponseData = new ErrorResponseData(tc.getStrs(), tc.getResult(), calculatedResult);
                    ErrorResponse errorResponse = new ErrorResponse("Wrong Answer", 1, errorResponseData);
                    System.out.println(objectMapper.writeValueAsString(errorResponse));
                    System.exit(0);
                }
            }

            CommonResponse commonResponse = new CommonResponse("AC", 0);
            System.out.println(objectMapper.writeValueAsString(commonResponse));
            System.exit(0);
        } catch (Exception ex) {
            ex.printStackTrace();
            System.exit(1);
        }
    }
}

class TestCase {
    private String[] strs;
    private String result;

    public TestCase(String[] strs, String result) {
        this.strs = strs;
        this.result = result;
    }

    public String[] getStrs() {
        return strs;
    }

    public void setStrs(String[] strs) {
        this.strs = strs;
    }

    public String getResult() {
        return result;
    }

    public void setResult(String result) {
        this.result = result;
    }
}

class CommonResponse {
    private String message;
    private Integer code;

    public CommonResponse(String message, Integer code) {
        this.message = message;
        this.code = code;
    }

    public String getMessage() {
        return message;
    }

    public void setMessage(String message) {
        this.message = message;
    }

    public Integer getCode() {
        return code;
    }

    public void setCode(Integer code) {
        this.code = code;
    }
}

class ErrorResponse {
    private String message;
    private Integer code;
    private ErrorResponseData errorResponseData;

    public ErrorResponse(String message, Integer code, ErrorResponseData errorResponseData) {
        this.message = message;
        this.code = code;
        this.errorResponseData = errorResponseData;
    }

    public String getMessage() {
        return message;
    }

    public void setMessage(String message) {
        this.message = message;
    }

    public Integer getCode() {
        return code;
    }

    public void setCode(Integer code) {
        this.code = code;
    }

    public ErrorResponseData getErrorResponseData() {
        return errorResponseData;
    }

    public void setErrorResponseData(ErrorResponseData errorResponseData) {
        this.errorResponseData = errorResponseData;
    }
}

class ErrorResponseData {
    private String[] input;
    private String output;
    private String calculated;

    public ErrorResponseData(String[] input, String output, String calculated) {
        this.input = input;
        this.output = output;
        this.calculated = calculated;
    }

    public String[] getInput() {
        return input;
    }

    public void setInput(String[] input) {
        this.input = input;
    }

    public String getOutput() {
        return output;
    }

    public void setOutput(String output) {
        this.output = output;
    }

    public String getCalculated() {
        return calculated;
    }

    public void setCalculated(String calculated) {
        this.calculated = calculated;
    }
}

// ========  用户提交代码  ========
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0) return "";
        if(strs.length == 1) return strs[0];

        String result = strs[0];
        int index = result.length();

        for (int i = 1; i < strs.length; i++) {
            index = index < strs[i].length() ? index : strs[i].length();
            for (int j = 0; j < index; j++) {
                if (result.charAt(j) != strs[i].charAt(j)) {
                    index = j;
                    break;
                }
            }
        }

        return result.substring(0, index);
    }
}
// ========  用户提交代码  ========

Leave a Reply

Your email address will not be published. Required fields are marked *

*