Stress testing

Допустим вы написали решение к какой-то олимпиадной задаче, отправили его на проверку, получили "wrong answer", прочитали код и не нашли баг. Что делать дальше?

Хороший следующий шаг — написать стресс-тест. Нужно написать максимально простое решение задачи, но которое работает только на маленьких тестах, и генератор маленьких тестов. А потом в цикле генерировать тест, запускать два решения, сранивать ответы и остановиться, когда они не совпадут. Как лучше (по скромному мнению авторого этого поста, которое может не совпадать с вашим) всего все это запускать?

Тут довольно хорошо описан типичный "плохой" и "хороший" способы. Постараюсь объяснить почему на самом деле все наоборот. В посте предлагается делать три отдельных программы — генератор, решение и медленное решение. И еще дополнительно написать скрипт, который все запускает.

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

Типичный способ решить эту проблему — генерировать сразу несколько тестов в одном файле, но тогда нужно тратить время, чтобы понять, какой именно из тестов не работает.

Я обычно пишу все четыре части в одном месте, код получается примерно такой:

fn gen(rng: &mut Random, max_n: usize) -> Input { ... }
fn solve(input: &Input) -> Output { ... }
fn solve_slow(input: &Input) -> Output { ... }

fn main() {
    const MAX_N: usize = 10;
    for seed in 1.. {
        dbg!(seed);
        let mut rng = Random::seed_from_u64(seed);
        let input = gen(&mut rng, MAX_N);
        let output = solve(&input);
        let slow_output = solve_slow(&input);
        assert_eq!(output, slow_output);
    }
}

В данном случае Input это тип, который хранит все входные данные задачи в формате, удобном для запуска решения.

После того как плохой тест найден, можно попробовать уменьшить MAX_N и найти минимальный тест.

Допустим решение упало на 100500-м тесте и мы хотим его подебажить. Можно просто заменить строку for seed in 1.. на for seed in 100500.. и тогда этот тест сгенерируется первым.

Сразу отвечу на потенциальные вопросы:

1. Обычно решение написано таким образом, что оно читает тест из stdin, а тут тест передается как уже готовая структура данных. Придется переписать эту часть solve?
Полезно сразу писать решение в формате, когда чтение инпута и решение это отдельные части, тогда такой проблемы нет.

2. Решение может использовать какие-то глобальные переменные, тогда так писать стресс нельзя.
Не используйте глобальные переменные.