php - 我对这个编程挑战的解决方案是错误的，因为它为 10/11 测试用例输出了错误的答案。那些测试用例是什么？

Question

我正在做这个编程挑战，可以在 www.interviewstreet.com 上找到(这是第一个挑战，值(value) 30 分)。

当我提交解决方案时，返回结果说答案是错误的，因为它只通过了 1/11 的测试用例。但是，我觉得已经测试了各种情况并且不明白我做错了什么。了解这些测试用例可能会很有帮助，以便我可以测试我的程序。

这里是问题(在下面的灰线之间):

---

象限查询(30 分)

平面上有N个点。第 i 个点的坐标为 (xi, yi)。执行以下查询:

1) 反射(reflect)点 i 和 j 之间的所有点，包括沿 X 轴的点。此查询表示为“X i j”
2) 反射(reflect)点 i 和 j 之间的所有点，包括沿 Y 轴的点。此查询表示为“Y i j”
3) 计算 4 个象限中每个象限中 i 和 j 点之间的点数。该查询表示为“C i j”

输入:
第一行包含 N，点数。接下来是 N 行。
第 i 行包含由空格分隔的 xi 和 yi。
下一行包含 Q 查询的数量。接下来的 Q 行每行包含一个上述形式之一的查询。
所有索引都是 1 索引。

输出:
为“C i j”类型的每个查询输出一行。对应行包含4个整数；分别在第 1、2、3、4 象限中索引在 [i..j] 范围内的点数。

限制条件:
1 <= N <= 100000
1 <= Q <= 100000
您可能会假设 X 轴或 Y 轴上没有任何点。
所有 (xi,yi) 都将放入一个 32 位有符号整数
在所有查询中，1 <=i <=j <=N

示例输入:
4
1 1
-1 1
-1 -1
1 -1
5
C 1 4
X 2 4
C 3 4
是 1 2
C 1 3
示例输出:
1 1 1 1
1 1 0 0
0 2 0 1

解释:
当查询说“X i j”时，这意味着获取索引 i 和 j 之间的所有点，包括并反射(reflect) X 轴上的那些点。这里的 i 和 j 与点的坐标无关。它们是指数。 i指的是点i，j指的是点j

“C 1 4”要求您“考虑在 {1,2,3,4} 中具有索引的点集。在这些点中，分别有多少点位于第 1、2、3 和 4 个四边形？ 答案显然是 1 1 1 1。

接下来我们反射(reflect)沿 X 轴的索引“2 4”之间的点。所以新的坐标是:
1 1
-1 -1
-1 1
1 1

现在 'C 3 4' 是 '考虑索引在 {3,4} 中的点集。在这些点中，分别有多少点位于第 1、2、3 和 4 个四边形？点 3 位于象限 2，点 4 位于象限 1。 所以答案是 1 1 0 0

---

我用 PHP 编写代码，测试方法是使用 STDIN 和 STDOUT。

关于用于测试我的代码的困难测试用例有什么想法吗？我不明白为什么我有 10/11 个测试用例都失败了。

此外，如果您有兴趣，这是我的代码:

// The global variable that will be changed
$points = array();

/******** Functions ********/
// This function returns the number of points in each quadrant. 
function C($beg, $end) {
    // $quad_count is a local array and not global as this gets reset for every C operation
    $quad_count = array("I" => 0, "II" => 0, "III" => 0, "IV" => 0);

    for($i=$beg; $i<$end+1; $i++) {
        $quad = checkquad($i);
        $quad_count[$quad]++;
    }

    return $quad_count["I"]." ".$quad_count["II"]." ".$quad_count["III"]." ".$quad_count["IV"];        
}

// Reflecting over the x-axis means taking the negative value of y for all given points
function X($beg, $end) {
    global $points;

    for($i=$beg; $i<$end+1; $i++) {
        $points[$i]["y"] = -1*($points[$i]["y"]);
    }
}

// Reflecting over the y-axis means taking the negative value of x for all given points    
function Y($beg, $end) {
    global $points;

    for($i=$beg; $i<$end+1; $i++) {
        $points[$i]["x"] = -1*($points[$i]["x"]);
    }
}

// Determines which quadrant a given point is in
function checkquad($i) {
    global $points;

    $x = $points[$i]["x"];
    $y = $points[$i]["y"];

    if ($x > 0) {
        if ($y > 0) {
            return "I";
        } else {
            return "IV";
        }
    } else {
        if ($y > 0) {
            return "II";
        } else {
            return "III";
        }
    }
}


// First, retrieve the number of points that will be provided. Make sure to check constraints.
$no_points = intval(fgets(STDIN));    
if ($no_points > 100000) {
    fwrite(STDOUT, "The number of points cannot be greater than 100,000!\n");
    exit;
}

// Remember the points are 1 indexed so begin key from 1. Store all provided points in array format. 
for($i=1; $i<$no_points+1; $i++) {
    global $points;

    list($x, $y) = explode(" ",fgets(STDIN)); // Get the string returned from the command line and convert to an array
    $points[$i]["x"] = intval($x);
    $points[$i]["y"] = intval($y);
}

// Retrieve the number of operations that will be provied. Make sure to check constraints. 
$no_operations = intval(fgets(STDIN));    
if($no_operations > 100000) {
    fwrite(STDOUT, "The number of operations cannot be greater than 100,000!\n");
    exit;
}

// Retrieve the operations, determine the type and send to the appropriate functions. Make sure i <= j.  
for($i=0; $i<$no_operations; $i++) {
    $operation = explode(" ",fgets(STDIN));
    $type = $operation[0];

    if($operation[1] > $operation[2]) {
        fwrite(STDOUT, "Point j must be further in the sequence than point i!\n");
        exit;
    }

    switch ($type) {
        case "C":
            $output[$i] = C($operation[1], $operation[2]);
            break;
        case "X":
            X($operation[1], $operation[2]);
            break;
        case "Y":
            Y($operation[1], $operation[2]);
            break;
        default:
            $output[$i] = "Sorry, but we do not recognize this operation. Please try again!";
    }
}

// Print the output as a string
foreach($output as $line) {
    fwrite(STDOUT, $line."\n");
}

<强>更新: 我终于找到了一个我的程序失败的测试用例。现在我正在尝试确定原因。这是关于大量测试的很好的一课。

10
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
12
C 1 10
X 1 3
C 5 5
是 2 10
C 10 10
C 1 10
X 1 3
C 5 5
是 2 10
C 10 10
X 3 7
C 9 9
我将通过初始化错误数组并确定导致问题的操作来正确测试它。

Answer 1

我发现了一个失败的测试用例并理解了原因。我在这里发布这个答案，所以每个人都清楚。

我给程序加了一个约束，j必须大于i，否则会报错。我注意到以下测试用例存在错误:

10
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1
C 2 10

操作 C 返回的错误。基本上程序认为“2”大于“10”。我发现的原因如下:

当使用 fgets() 时，返回一个字符串。如果您在该行执行诸如 explode() 或 substr() 之类的字符串操作，您将再次将该初始字符串中的数字转换为字符串。所以这意味着 10 变为“10”，然后在字符串操作后变为“0”。

对此的一种解决方案是使用 sscanf() 函数并基本上告诉程序需要一个数字。示例:对于“C 2 10”，您可以使用:
$operation_string = fgets(STDIN);
列表($type, $begpoint, $endpoint) = sscanf($operation_string, "%s %d %d");

我使用 sscanf() 提交了新的解决方案，现在有 3/11 的测试用例通过了。它没有检查更多的测试用例，因为超过了 CPU 时间限制。所以，现在我必须回去优化我的算法。

恢复工作! :)