Java, Scala, .NET, Lisp, Python, IDE's, Hibernate, MATLAB, Mathematica, Physics & Other

вторник, 4 августа 2009 г.

Online Judge unit testing

Задачу 1003 Parity не осилил. Зато придумал тест, на котором мой алгоритм валится.

6
9
1 2 odd
3 4 odd
2 5 odd
2 3 even
1 3 even
2 4 odd
2 3 even
4 5 even
2 3 odd
-1

Правильный ответ 5.

Мне чего-то кажется, что задачи Online Judge неплохо решать используя юнит тестирование. Тоесть, после того как прочитали и поняли условие, не кидаемся сразу же писать код! А спокойно пишем сначала юнит тест. Этот тест должен включать как можно больше разнообразных вариаций входных данных: общие случаи, частые случаи, совсем частные случаи... Также этот тест должен проверять время выполнения и используемую память, чтобы в итоге не превысить пределы установленные в условии задачи. Вот написал себе вспомогательный класс на C# 3.5, который в значительной степени облегчает написание таких юнит тестов:

using System;
using System.IO;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace OnlineJudgeUnitTests
{
public abstract class OnlineJudgeProgramTest
{
private static long toBytes(int memoryMB)
{
return memoryMB * 1024 * 1024;
}

private TimeSpan timeLimit;
private long memoryLimit;
private string basePathToDataFiles;

protected OnlineJudgeProgramTest(TimeSpan timeLimit, int memoryLimitMB,
string basePathToDataFiles)
{
this.timeLimit = timeLimit;
memoryLimit = toBytes(memoryLimitMB);
this.basePathToDataFiles = basePathToDataFiles;
}

private string ReadOutput(string outputFile)
{
return new StreamReader(outputFile).ReadToEnd();
}

protected void StandardFileIOTest(string inputFile, string outputFile)
{
inputFile = basePathToDataFiles + inputFile;
outputFile = basePathToDataFiles + outputFile;

StringWriter output = new StringWriter();
DateTime testStartTime = DateTime.Now;

ExecuteProgram(new StreamReader(inputFile), output);

Validate(testStartTime, ReadOutput(outputFile), output.ToString());
}

protected void StandardStringTest(string inputStr, string outputStr)
{
StringWriter output = new StringWriter();
StringReader input = new StringReader(inputStr);
DateTime testStartTime = DateTime.Now;

ExecuteProgram(input, output);

Validate(testStartTime, outputStr, output.ToString());
}

private void Validate(DateTime startTime, String expectedOutput, String realOutput)
{
if (expectedOutput != null)
{
Assert.AreEqual(expectedOutput, realOutput, "Wrong answer");
}

Assert.IsTrue(DateTime.Now - startTime < timeLimit, "Time limit exceeded");
Assert.IsTrue(GC.GetTotalMemory(false) < memoryLimit, "Memory limit exceeded");
}

protected abstract void ExecuteProgram(TextReader input, TextWriter output);
}

}
_Winnie Colorizer

Код не большой и понятный поэтому объяснять не буду. Чтобы скомпилировать его, вам потребуется сборка Microsoft.VisualStudio.QualityTools.UnitTestFramework.

Итак, достаточно всего лишь унаследовать ваш юнит тест от класса OnlineJudgeProgramTest и реализовать метод ExecuteProgram. После чего тест на входном файле PARITY.in и выходном файле PARITY.out будет выглядеть вот так:

      [TestMethod]
public void TestCase4()
{
StandardFileIOTest("PARITY.in", "PARITY.out");
}
_Winnie Colorizer

Не сложно, правда?
Или, если данные для теста генерируются каким-то хитрым образом, то можно воспользоваться методом StandardStringTest:

      [TestMethod]
public void TestCase5()
{
StandardStringTest(CreateSpecialInput(maxArraySize, maxRulesCount), "5000");
}
_Winnie Colorizer

Постоянные читатели