a/testing.en

   1 <p>
   2 Testing is an important step of writing programs of any kind. In algorithm contests, bugs cost time and points, so they must be avoided. There are two strategies you can use in order to avoid bugs: detecting them in an already-written program and writing programs without them.
   3
   4 <p>
   5 The most common method to finding bugs in a program is by testing it. The most common way of testing during an algorithm contest is by writing two other separate programs: one that solves the problem in a very simple way (generally a brute-force solution), and one that generates a random test. Then you can repeatedly generate a test, run the two programs on the test, and compare the outputs. If they are different, there is a bug in one of the programs.
   6
   7 <p>
   8 Since you don't have to submit these two extra programs, you have a wider choice of tools than those that are allowed for the final solutions. For example in the ACM-ICPC you may only use C, C++, Java, and in the IOI C, C++, Pascal, but all Linux computers have Perl and Python interpreters.
   9
  10 <p>
  11 We'll use <a href="http://mindcoding.ro/pb/maxsquare">MaxSquare</a> as an example problem. A possible generator is:
  12
  13 <pre>
  14 <span class="perl-hl lin">    1 </span><span class="perl-hl slc">#!/usr/bin/perl -w</span>
  15 <span class="perl-hl lin">    2 </span><span class="perl-hl kwa">use</span> v5<span class="perl-hl opt">.</span>14<span class="perl-hl opt">;</span>
  16 <span class="perl-hl lin">    3 </span>
  17 <span class="perl-hl lin">    4 </span><span class="perl-hl kwc">my</span> <span class="perl-hl kwb">$n</span> <span class="perl-hl opt">=</span> <span class="perl-hl num">1</span> <span class="perl-hl opt">+</span> <span class="perl-hl kwc">int rand</span> <span class="perl-hl num">50</span><span class="perl-hl opt">;</span>
  18 <span class="perl-hl lin">    5 </span><span class="perl-hl kwc">say</span> <span class="perl-hl kwb">$n</span><span class="perl-hl opt">;</span>
  19 <span class="perl-hl lin">    6 </span><span class="perl-hl kwa">for</span> <span class="perl-hl kwc">my</span> <span class="perl-hl kwb">$i</span> <span class="perl-hl opt">(</span><span class="perl-hl num">1</span> <span class="perl-hl opt">..</span> <span class="perl-hl kwb">$n</span><span class="perl-hl opt">) {</span>
  20 <span class="perl-hl lin">    7 </span>    <span class="perl-hl kwa">for</span> <span class="perl-hl kwc">my</span> <span class="perl-hl kwb">$j</span> <span class="perl-hl opt">(</span><span class="perl-hl num">1</span> <span class="perl-hl opt">..</span> <span class="perl-hl kwb">$n</span><span class="perl-hl opt">) {</span>
  21 <span class="perl-hl lin">    8 </span>        <span class="perl-hl kwc">print</span> <span class="perl-hl num">100</span> <span class="perl-hl opt">-</span> <span class="perl-hl kwc">int rand</span> <span class="perl-hl num">200</span><span class="perl-hl opt">,</span> <span class="perl-hl str">' '</span><span class="perl-hl opt">;</span>
  22 <span class="perl-hl lin">    9 </span>    <span class="perl-hl opt">}</span>
  23 <span class="perl-hl lin">   10 </span>    <span class="perl-hl kwc">say</span> <span class="perl-hl str">''</span><span class="perl-hl opt">;</span>
  24 <span class="perl-hl lin">   11 </span><span class="perl-hl opt">}</span>
  25 </pre>
  26
  27 We'll now need a script to run the tests. Assume that the two programs are written in C++ and named 'prog1.cpp' and 'prog2.cpp', and that the generator is named 'gen'.
  28 '
  29 <pre>
  30 <span class="perl-hl lin">    1 </span><span class="perl-hl slc">#!/usr/bin/perl -w</span>
  31 <span class="perl-hl lin">    2 </span><span class="perl-hl kwa">use</span> v5<span class="perl-hl opt">.</span>14<span class="perl-hl opt">;</span>
  32 <span class="perl-hl lin">    3 </span>
  33 <span class="perl-hl lin">    4 </span><span class="perl-hl kwc">system</span> <span class="perl-hl str">'make prog1 prog2'</span><span class="perl-hl opt">;</span>
  34 <span class="perl-hl lin">    5 </span><span class="perl-hl kwa">for</span> <span class="perl-hl opt">(</span><span class="perl-hl num">1</span> <span class="perl-hl opt">..</span> <span class="perl-hl num">1000</span><span class="perl-hl opt">) {</span>
  35 <span class="perl-hl lin">    6 </span>    <span class="perl-hl kwc">system</span> <span class="perl-hl str">'./gen &gt; input'</span><span class="perl-hl opt">;</span>
  36 <span class="perl-hl lin">    7 </span>    <span class="perl-hl kwc">system</span> <span class="perl-hl str">'./prog1 &lt; input &gt; output1'</span><span class="perl-hl opt">;</span>
  37 <span class="perl-hl lin">    8 </span>    <span class="perl-hl kwc">system</span> <span class="perl-hl str">'./prog2 &lt; input &gt; output2'</span><span class="perl-hl opt">;</span>
  38 <span class="perl-hl lin">    9 </span>    <span class="perl-hl kwc">die</span> <span class="perl-hl str">&quot;The outputs are different!</span><span class="perl-hl esc">\n</span><span class="perl-hl str">&quot;</span> <span class="perl-hl kwa">if</span> <span class="perl-hl kwc">system</span> <span class="perl-hl str">'diff -q output1 output2'</span><span class="perl-hl opt">;</span>
  39 <span class="perl-hl lin">   10 </span><span class="perl-hl opt">}</span>
  40 </pre>
  41
  42 <p>
  43 If the two programs produce different outputs for a test, the script dies with an error, allowing the user to inspect the input and outputs, find the bug, and fix it.
  44
  45 <hr>
  46 <p>
  47 You can also do this in other languages, such as C++. For example: <!-- The following program compares the programs <code>ok.cpp</code> and <code>brute.cpp</code>, using <code>gen.cpp</code> as a generator. -->
  48
  49 <p>
  50 Generator:
  51
  52 <pre>
  53 <span class="cpp-hl lin">    1 </span><span class="cpp-hl ppc">#include &lt;iostream&gt;</span>
  54 <span class="cpp-hl lin">    2 </span><span class="cpp-hl ppc">#include &lt;cstdlib&gt;</span>
  55 <span class="cpp-hl lin">    3 </span><span class="cpp-hl ppc">#include &lt;ctime&gt;</span>
  56 <span class="cpp-hl lin">    4 </span><span class="cpp-hl kwa">using namespace</span> std<span class="cpp-hl opt">;</span>
  57 <span class="cpp-hl lin">    5 </span>
  58 <span class="cpp-hl lin">    6 </span><span class="cpp-hl kwb">int</span> <span class="cpp-hl kwd">rnd</span><span class="cpp-hl opt">(</span><span class="cpp-hl kwb">int</span> a<span class="cpp-hl opt">,</span> <span class="cpp-hl kwb">int</span> b<span class="cpp-hl opt">) {</span>
  59 <span class="cpp-hl lin">    7 </span>    <span class="cpp-hl kwa">return</span> a <span class="cpp-hl opt">+</span> <span class="cpp-hl kwd">rand</span><span class="cpp-hl opt">() % (</span>b <span class="cpp-hl opt">-</span> a<span class="cpp-hl opt">);</span>
  60 <span class="cpp-hl lin">    8 </span><span class="cpp-hl opt">}</span>
  61 <span class="cpp-hl lin">    9 </span>
  62 <span class="cpp-hl lin">   10 </span><span class="cpp-hl kwb">int</span> <span class="cpp-hl kwd">main</span><span class="cpp-hl opt">() {</span>
  63 <span class="cpp-hl lin">   11 </span>    <span class="cpp-hl kwd">srand</span><span class="cpp-hl opt">(</span><span class="cpp-hl kwd">time</span><span class="cpp-hl opt">(</span>NULL<span class="cpp-hl opt">));</span>
  64 <span class="cpp-hl lin">   12 </span>    <span class="cpp-hl kwb">int</span> n <span class="cpp-hl opt">=</span> <span class="cpp-hl kwd">rnd</span><span class="cpp-hl opt">(</span><span class="cpp-hl num">1</span><span class="cpp-hl opt">,</span> <span class="cpp-hl num">100</span><span class="cpp-hl opt">);</span>
  65 <span class="cpp-hl lin">   13 </span>    cout <span class="cpp-hl opt">&lt;&lt;</span> n <span class="cpp-hl opt">&lt;&lt;</span> <span class="cpp-hl str">'</span><span class="cpp-hl esc">\n</span><span class="cpp-hl str">'</span><span class="cpp-hl opt">;</span>
  66 <span class="cpp-hl lin">   14 </span>    <span class="cpp-hl kwa">for</span><span class="cpp-hl opt">(</span><span class="cpp-hl kwb">int</span> i<span class="cpp-hl opt">=</span><span class="cpp-hl num">0</span><span class="cpp-hl opt">;</span> i<span class="cpp-hl opt">&lt;</span>n<span class="cpp-hl opt">; ++</span>i<span class="cpp-hl opt">) {</span>
  67 <span class="cpp-hl lin">   15 </span>        <span class="cpp-hl kwa">for</span><span class="cpp-hl opt">(</span><span class="cpp-hl kwb">int</span> j<span class="cpp-hl opt">=</span><span class="cpp-hl num">0</span><span class="cpp-hl opt">;</span> j<span class="cpp-hl opt">&lt;</span>n<span class="cpp-hl opt">; ++</span>j<span class="cpp-hl opt">)</span>
  68 <span class="cpp-hl lin">   16 </span>            cout <span class="cpp-hl opt">&lt;&lt;</span> <span class="cpp-hl kwd">rnd</span><span class="cpp-hl opt">(-</span><span class="cpp-hl num">100</span><span class="cpp-hl opt">,</span> <span class="cpp-hl num">100</span><span class="cpp-hl opt">) &lt;&lt;</span> <span class="cpp-hl str">' '</span><span class="cpp-hl opt">;</span>
  69 <span class="cpp-hl lin">   17 </span>        cout <span class="cpp-hl opt">&lt;&lt;</span> <span class="cpp-hl str">'</span><span class="cpp-hl esc">\n</span><span class="cpp-hl str">'</span><span class="cpp-hl opt">;</span>
  70 <span class="cpp-hl lin">   18 </span>    <span class="cpp-hl opt">}</span>
  71 <span class="cpp-hl lin">   19 </span>    <span class="cpp-hl kwa">return</span> <span class="cpp-hl num">0</span><span class="cpp-hl opt">;</span>
  72 <span class="cpp-hl lin">   20 </span><span class="cpp-hl opt">}</span>
  73 </pre>
  74
  75 Test runner:
  76
  77 <pre>
  78 <span class="cpp-hl lin">    1 </span><span class="cpp-hl ppc">#include &lt;iostream&gt;</span>
  79 <span class="cpp-hl lin">    2 </span><span class="cpp-hl ppc">#include &lt;cstdlib&gt;</span>
  80 <span class="cpp-hl lin">    3 </span><span class="cpp-hl ppc">#define TESTS 1000</span>
  81 <span class="cpp-hl lin">    4 </span><span class="cpp-hl kwa">using namespace</span> std<span class="cpp-hl opt">;</span>
  82 <span class="cpp-hl lin">    5 </span>
  83 <span class="cpp-hl lin">    6 </span><span class="cpp-hl kwb">int</span> <span class="cpp-hl kwd">main</span><span class="cpp-hl opt">() {</span>
  84 <span class="cpp-hl lin">    7 </span>    <span class="cpp-hl kwd">system</span><span class="cpp-hl opt">(</span><span class="cpp-hl str">&quot;g++ -o gen gen.cpp&quot;</span><span class="cpp-hl opt">);</span><span class="cpp-hl slc">//compile the files, the executable file will be named gen</span>
  85 <span class="cpp-hl lin">    8 </span>    <span class="cpp-hl kwd">system</span><span class="cpp-hl opt">(</span><span class="cpp-hl str">&quot;g++ -o brute brute.cpp&quot;</span><span class="cpp-hl opt">);</span>
  86 <span class="cpp-hl lin">    9 </span>    <span class="cpp-hl kwd">system</span><span class="cpp-hl opt">(</span><span class="cpp-hl str">&quot;g++ -o ok ok.cpp&quot;</span><span class="cpp-hl opt">);</span>
  87 <span class="cpp-hl lin">   10 </span>    <span class="cpp-hl kwa">for</span><span class="cpp-hl opt">(</span><span class="cpp-hl kwb">int</span> i<span class="cpp-hl opt">=</span><span class="cpp-hl num">0</span><span class="cpp-hl opt">;</span> i<span class="cpp-hl opt">&lt;</span>TESTS<span class="cpp-hl opt">; ++</span>i<span class="cpp-hl opt">) {</span>
  88 <span class="cpp-hl lin">   11 </span>        <span class="cpp-hl kwd">system</span><span class="cpp-hl opt">(</span><span class="cpp-hl str">&quot;./gen &gt; input&quot;</span><span class="cpp-hl opt">);</span><span class="cpp-hl slc">//redirects the stdout of the program gen to the file named input</span>
  89 <span class="cpp-hl lin">   12 </span>        <span class="cpp-hl kwd">system</span><span class="cpp-hl opt">(</span><span class="cpp-hl str">&quot;./brute &lt; input &gt; bout&quot;</span><span class="cpp-hl opt">);</span><span class="cpp-hl slc">//redirects the file input to stdin and stdout to bout</span>
  90 <span class="cpp-hl lin">   13 </span>        <span class="cpp-hl kwd">system</span><span class="cpp-hl opt">(</span><span class="cpp-hl str">&quot;./ok &lt;input &gt; oout&quot;</span><span class="cpp-hl opt">);</span>
  91 <span class="cpp-hl lin">   14 </span>        <span class="cpp-hl kwa">if</span><span class="cpp-hl opt">(</span><span class="cpp-hl kwd">system</span><span class="cpp-hl opt">(</span><span class="cpp-hl str">&quot;diff -q bout oout&quot;</span><span class="cpp-hl opt">)) {</span>
  92 <span class="cpp-hl lin">   15 </span>            cout<span class="cpp-hl opt">&lt;&lt;</span><span class="cpp-hl str">&quot;Outputs differ&quot;</span><span class="cpp-hl opt">;</span>
  93 <span class="cpp-hl lin">   16 </span>            <span class="cpp-hl kwa">return</span> <span class="cpp-hl num">0</span><span class="cpp-hl opt">;</span>
  94 <span class="cpp-hl lin">   17 </span>        <span class="cpp-hl opt">}</span>
  95 <span class="cpp-hl lin">   18 </span>    <span class="cpp-hl opt">}</span>
  96 <span class="cpp-hl lin">   19 </span>    <span class="cpp-hl kwa">return</span> <span class="cpp-hl num">0</span><span class="cpp-hl opt">;</span>
  97 <span class="cpp-hl lin">   20 </span><span class="cpp-hl opt">}</span>
  98 </pre>