Стресс-тестер для соревнований по программированию +8


AliExpress RU&CIS



Во-первых, не бойтесь названия «стресс-тестер». Это просто модный термин для написанного мной служебного инструмента для соревнований по программированию. Вместо того чтобы просто дать вам код, я расскажу о стратегии и плане, которые у меня были, когда я писал этот инструмент.



Введение


Мы много раз сталкивались с трудностями в соревнованиях, особенно когда чувствовали, что наша логика безошибочна, но оказывалось, что код терпит неудачу в каком-то крутом тестовом примере. При этом не всегда есть резервная копия, когда в голову приходит спасительное решение с помощью грубой силы.

Да, метод грубой силы дает верное решение. Тогда в чем проблема? Вы угадали: этот метод медленный. Строго говоря, с точки зрения соревновательного программирования, он не оптимален, и в некоторых задачах код может выйти за рамки временных ограничений некоторых небольших подзадач. Мы могли бы воспользоваться тем фактом, что наше решение методом грубой силы правильное, и протестировать оптимальное решение вместе с ним.

Мне пришла в голову идея: что, если мы возьмем тестовый пример, скормим его брут-форсу и оптимальному решению и проверим, где решение терпит неудачу. Но где взять столько тестовых случаев? Здесь в игру вступает случайность.



Стратегия


  • Сгенерировать случайные тестовые наборы.
  • Скормить их программам.
  • Вооружиться исполняемыми файлами брут-форса и оптимального решения.
  • Поместить их результаты в разные файлы и проверить разницу.

И еще одно: может потребоваться выполнить эту задачу тысячу раз.

Выбор технологий


Я мог бы реализовать эту стратегию с помощью Python и нескольких его модулей, таких как subprocess для запуска команд терминала, difflib для проверки разницы вывода, random для генерации случайных тест-кейсов и операций ввода-вывода файлов, но подход может стать лихорадочным, потому что включает в себя много операций в терминале, то есть мы можем столкнуться с проблемами. Поэтому я выбрал идеальное сочетание bash и python.



Причина выбора bash — легкость, с которой скрипт bash может выполнять большинство вышеперечисленных действий, а для генерации тестовых данных я буду использовать Python.



Структура каталога:

  • brute.cpp и optimal.cpp содержат соответствующий названиям код.
  • testcase.py генерирует тестовые данные.
  • brute_out.txt и optimal_out.txt, (которые будет созданы во время выполнения), будут содержать соответствующие выходные названиям данные.
  • difference_file.txt, где мы можем посмотреть на разницу.



1. Генерация тестовых файлов


Я выбрал в качестве примера вопрос на codechef. Прежде всего нужно понимать, что один тестовый файл — это точные значения входного формата. Уточню: один тестовый файл (не то же самое, что тест-кейс) из этого вопроса содержит все, что описывается на изображении:



Ниже тестовый файл. Пожалуйста, посмотрите на входной формат выше.



Мы будем генерировать n таких тестовых файлов. Код для создания тестового файла зависит от входного формата. Посмотрите на приведенный ниже код для создания подходящего входному формату тестового файла.



Я написал несколько классов, чтобы проще генерировать тест-кейсы и облегчить некоторые общие операции, скажем, генерацию массива из n целых чисел и другие действия. Вот код:

import sys
import random

sys.stdout = open("testcase.txt", "w")


class RandomGenerator():
  def __init__(self):
    pass

  def integer(self, lower_bound, upper_bound):
    ret = random.randint(lower_bound, upper_bound)
    return ret

  def array(self, array_size, lower_bound, upper_bound):
    l = [0]*array_size
    for index, element in enumerate(l):
      l[index] = self.integer(lower_bound, upper_bound)
    return l


class ListOperation():
  def __init__(self):
    pass

  def print_space(self, l):
    for element in l:
      print(element, end=" ")
    print()

  def print_csv(self, l):
    for element in l:
      print(element, end=", ")
    print()


class Print():
  def __init__(self):
    pass

  def inline_print(self, n):
    """
    print n elements in a line and then print an endline
    """
    for i in range(n):
      print()


if __name__ == "__main__":
  rand = RandomGenerator()
  lops = ListOperation()
  t = 10
  for __ in range(t):
    print(rand.integer(1, 1000))

testcase.py

2. Bash


  1. Генерирует исполняемые файлы брут-форса и оптимального решения.
  2. Принимает аргумент командной строки — количество исполняемых файлов — для запуска
  3. Для каждого сгенерированного тестового файла сопоставляет выходные данные и проверяет разницу

В коде всё объясняется:

# 1. creating the executables
g++ brute.cpp -o brute_executable
g++ optimal.cpp -o optimal_executable

# 2. getting the number of times to run the script from command line args
n=$1

# --------------------- 3 -------------------------- #
# running loop for n times (N files)
for (( i=1; i<=n; ++i ))
do
  # generate and map testcases to testcase.txt
  python testcase.py 

  # generate and map respective outputs
  ./brute_executable < testcase.txt > brute_out.txt
  ./optimal_executable < testcase.txt > optimal_out.txt

# Bash Magic : If the difference command produces any output
  if [[ $(diff brute_out.txt optimal_out.txt) ]]
  then
    # map the output of diff command to difference_file
    echo "$(diff -Z brute_out.txt optimal_out.txt)" > difference_file.txt

    echo "Difference reported in file difference_file.txt"
    echo "-----------------------------------------------"
    echo "You Can find the testcase where your optimal solution failed in testcase.txt"
    echo "and their respective outputs in brute_out.txt and optimal_out.txt"
    
    # Once the difference is found and we've reported it 
    # then no need to generate extra testcases we can break right here
    break
  else
    echo "AC on super-test $i"
  fi
done

# When the program passes all the test files
echo "--------------Testing done-----------"

mapper.sh

Описание некоторых важных частей скрипта

Важно: цикл прерывается, когда обнаруживается разница и мы смотрим на тест-кейс, на котором программа терпит неудачу. Программа записывает тест-кейс в файл testcase.txt.

Команда diff:

diff <file_1> <file_2> возвращает разницу между двумя файлами. Флаг -Z используется, чтобы diff пропускала начальные пробелы и новые строки.

Получение результата выполнения команды внутри скрипта bash:



$(command) дает нам вывод command. Воспользуемся этим фактом и проверим, есть ли какая-то разница, потому что если команда diff ничего не возвращает, то это означает, что файлы одинаковы.

Перенаправление ввода-вывода:



  • command > "filename" перенаправит вывод команды на «filename».
  • command < "filename" передает содержимое файла в command в качестве входных данных.

Применение стресс-тестера:

  1. Скопируйте ваш код в brute.cpp и optimal.cpp.
  2. Измените testcase.py так, чтобы он подходил выходному формату.
  3. Переключитесь на терминал и перейдите в каталог проекта.
  4. Выполните mapper.sh, передав аргумент командной строки (количества тестовых файлов) и наслаждайтесь магией.
  5. Посмотрите в файл difference_file.txt, чтобы увидеть разницу выводов.

Мне потребовалось некоторое время, чтобы привыкнуть к использованию этого инструмента. Но когда я почувствовал помощь в работе со сложными «Answer is correct», прилив адреналина был потрясающим. И это еще не все: можно использовать стресс-тестер для тестирования ожидаемого решения, которое проходит придуманные нами тест-кейсы.



Посмотрите: я запустил инструмент на 20 тестовых файлах, но разница замечена в самом первом из них.



И после проверки файла с разницей я обнаружил несколько крайних случаев, когда моя программа каждый раз выводила 1. После изменения optimal.cpp и обработки крайнего случая я запустил код снова. На этот раз я убедился, что учитываю каждый тестовый случай, и запустил инструмент на 100 тестовых файлах. Вы можете посмотреть процесс выполнения в видео ниже. Поверьте, мне без этого инструмента я бы не получил «Answer is Correct». Инструмент стоит того, чтобы поделиться им. Github

Осваивать новую сферу или повышать квалификацию куда проще с промокодом HABR, который даст вам дополнительные 10% к скидке указанной на баннере.

image



Рекомендуемые статьи





Комментарии (2):

  1. maxzhurkin
    /#22247892

    def array(self, array_size, lower_bound, upper_bound):
        l = [0]*array_size
        for index, element in enumerate(l):
          l[index] = self.integer(lower_bound, upper_bound)
        return l
    Зачем такой запутанный код?
    Почему нельзя было, например, просто
    def array(self, array_size, lower_bound, upper_bound):
        return [self.integer(lower_bound, upper_bound) for _ in range(array_size)]

  2. /#22253484

    Под Windows для аналогичной задачи использовал примерно такой bat-файл:

    :again
      random_testgen.exe > input.txt
      solution_bruteforce.exe < input.txt > output1.txt
      solution_wrong_answer.exe < input.txt > output2.txt
      fc /W output1.txt output2.txt 
      if ERRORLEVEL 1 goto end
      goto again
    :end