Корректность решения: вопросы, тесты и инварианты

1. Что значит «решение верное»

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

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

Такое описание почти никогда не бывает полным. «Найдите второй максимум», «сожмите строку», «посчитайте слова» — за каждой такой фразой прячется десяток случаев, о которых не сказано ни слова. Что делать с пустым входом? Считать ли одинаковые значения одним? Что вернуть, если ответа нет? Пока эти случаи не оговорены, у задачи не один правильный ответ, а несколько, и любая проверка превращается в спор.

Условие, которое читается двумя способами

Возьмём задачу про сжатие строки. Формулировка звучит так: «Сожмите строку, записывая подряд идущие одинаковые символы как символ и количество: aaabb → a3b2». Пример в условии есть, и кажется, что этого достаточно.

Но пример ничего не говорит про символ, который встретился один раз. Писать a1 или просто a? Обе трактовки разумны, обе дают на примере из условия один и тот же ответ, и обе дают разные ответы на строке abc:

def sjat_vsegda_s_chislom(text):
    """Пишет число всегда, даже когда символ один: abc → a1b1c1."""

def sjat_bez_edinic(text):
    """Одиночный символ пишет без числа: abc → abc."""

'aaabb'  с числом всегда: 'a3b2'     без единиц: 'a3b2'
'abc'    с числом всегда: 'a1b1c1'   без единиц: 'abc'
''       с числом всегда: ''         без единиц: ''

На aaabb версии совпали, на abc разошлись. Если такой вопрос не задать, версию выберет случайность — то, как вы прочитали условие в первый раз. Расхождение вскроется, когда результат сверят с ожиданиями заказчика.

Контракт функции

Чтобы прекратить споры, договорённости записывают. Такая запись называется контрактом.

У контракта две половины, и у них есть свои имена. Предусловие — то, что должно быть верно на входе; за это отвечает тот, кто вызывает функцию. Постусловие — то, что будет верно на выходе, если предусловие соблюдено; за это отвечает сама функция.

Работает это как договор проката: прокат обещает исправную машину (постусловие), но при условии, что у вас есть права и вы вернёте её с тем же баком (предусловие). Если условие нарушил клиент — претензий к прокату нет. Если клиент всё выполнил, а машина сломалась — виноват прокат.

В Python обе половины можно записать прямо в коде инструкцией assert. Она проверяет, что утверждение истинно, и останавливает программу с сообщением, если это не так:

def srednee(chisla):
    """Среднее арифметическое непустого списка чисел.

    Предусловие: список непустой.
    Постусловие: ответ не меньше минимума и не больше максимума списка.
    """
    assert len(chisla) > 0, 'предусловие: список не должен быть пустым'
    itog = sum(chisla) / len(chisla)
    assert min(chisla) <= itog <= max(chisla), 'постусловие: среднее вне диапазона'
    return itog

srednee([4, 6]) = 5.0
srednee([-5, 5]) = 0.0
srednee([]) — вызов с нарушенным предусловием:
Traceback (most recent call last):
  File "6_predusloviye.py", line 23, in <module>
    srednee([])
  File "6_predusloviye.py", line 14, in srednee
    assert len(chisla) > 0, 'предусловие: список не должен быть пустым'
AssertionError: предусловие: список не должен быть пустым

Строки после слова Traceback — это цепочка вызовов, которая привела к ошибке. Читают её снизу вверх: в последней строке тип ошибки и сообщение, выше — строка, где она произошла, ещё выше — откуда был сделан вызов.

Здесь важны две детали. Программа остановилась в той строке, где нарушен договор, а не через три вызова, когда None где-то сложили с числом. И сообщение после запятой попадает в текст ошибки, поэтому в нём пишут, чего ожидали.

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

2. Уточняющие вопросы к условию

Работа над задачей начинается не с кода: сначала условие дополняют вопросами. На собеседовании это прямо ожидаемая часть работы: интервьюер смотрит, заметит ли кандидат пробелы. В обычной работе то же самое происходит с задачей в трекере — только вопросы задают автору задачи, а неверно понятое условие обнаруживается через неделю на приёмке.

Вопросов к любой задаче можно придумать много, а времени мало. Поэтому нужен критерий отбора.

По этому критерию «Как назвать функцию?» отсеивается сразу: имя не меняет ни алгоритм, ни проверки. А вот «Могут ли значения повторяться?» остаётся: от ответа зависит, убирать ли дубликаты, и появляется отдельный тест.

Пять групп, о которых спрашивают

Вопросы задают группами: так их проще не забыть под давлением времени.

Первая группа — вход. Какие данные приходят, какого они типа, насколько велики, бывает ли вход пустым. Пустой вход стоит отдельного упоминания: это самый частый случай, о котором молчит условие, и самый частый повод для падения.

Вторая группа — ответ. Что именно вернуть: значение, индекс, True или False, список пар. Разница не косметическая. Для задачи «найти в списке два числа с заданной суммой» ответ True/False позволяет обойтись множеством просмотренных значений, а ответ «индексы» требует словаря «значение → индекс».

Третья группа — особые случаи. Что вернуть, когда ответа не существует? Как считать повторы? Что делать, если подходящих ответов несколько? Здесь чаще всего обнаруживается, что задач в условии две.

Четвёртая группа — ограничения. Насколько большим бывает вход, в каком диапазоне значения, сколько раз функцию вызовут. Эти ответы определяют не правильность, а выбор алгоритма: для тысячи элементов подойдёт двойной цикл, для миллиона — нет.

Пятая группа — данные. Можно ли менять то, что пришло на вход. Сортировка на месте экономит память, но вызывающий код теряет исходный порядок; если он ему нужен, придётся делать копию и платить за неё O(n) памяти.

Банк вопросов: что можно спросить дословно

Ниже вопросы в той формулировке, в которой их произносят. Их не задают все подряд — из каждой группы выбирают те, что подходят к задаче. Список есть отдельным файлом, его удобно держать перед глазами первое время: bank-voprosov.md.

Вопросы задают до кода и в том порядке, в каком они влияют на решение: сначала вход и ответ, потом особые случаи, потом ограничения. Если время кончается, первым задают тот вопрос, без ответа на который нельзя написать ни строчки.

Три кейса: вопрос, ответ, что изменилось

Ниже три условия в том виде, в каком их дают, и разбор: какие вопросы к ним задали, что ответили и чем это обернулось для кода.

Куда записать ответы

Ответ, услышанный на словах, через десять минут превращается в «кажется, договаривались, что пустой список допустим». Записывать его нужно там, где его увидит любой, кто откроет файл, — в документирующей строке функции:

def sjat(text):
    """Сжимает подряд идущие одинаковые символы: aaabb → a3b2.

    Одиночный символ пишется без числа: abc → abc.
    Пустая строка даёт пустую строку.
    Исходная строка не изменяется.
    """

Такая запись занимает минуту, а дальше служит трижды: по ней пишут тесты, по ней проверяют готовый код и по ней же объясняют своё решение тому, кто пришёл с вопросом.

3. Тестовые примеры и классы входов

Контракт — это текст, и сам по себе он ничего не проверяет. Чтобы им можно было пользоваться, его переводят в примеры.

Количество тестов при этом значения не имеет: важен порядок действий. Посмотрим на подсчёт слов. Версия ниже считает пробелы и прибавляет единицу — так пишут часто, и на первом же примере она отвечает верно:

def count_words(text):
    """Ошибочная версия: считает пробелы, а не слова."""
    probelov = 0
    for simvol in text:
        if simvol == ' ':
            probelov += 1
    return probelov + 1

'кот пёс'        ждём 2  получили 2  ок     обычный случай
'кот'            ждём 1  получили 1  ок     одно слово без разделителей
''               ждём 0  получили 1  ОШИБКА пустая строка
'  кот   пёс '   ждём 2  получили 7  ОШИБКА лишние пробелы по краям и внутри
'кот\nпёс'       ждём 2  получили 1  ОШИБКА разделитель — перевод строки

Разберём результат построчно. Первые два теста прошли — и именно поэтому они бесполезны как доказательство: функция считает разделители, а в этих строках число разделителей случайно совпало с ответом. Третий тест ловит пустую строку: разделителей ноль, функция прибавляет единицу и сообщает про одно слово, которого нет. Четвёртый показывает, что лишние пробелы считаются наравне со словами. Пятый — что перевод строки для этой версии вообще не разделитель.

Класс входов

Почему пять тестов поймали три разные ошибки, а три первых теста не поймали бы ни одной? Потому что они относятся к разным классам.

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

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

Пять классов, которые проверяют почти всегда

• Обычный случай. Один тест, чтобы проверить сам способ решения.
• Границы допустимого. Пустой вход, один элемент, наибольшее допустимое значение.
• Особые значения. Ноль, отрицательные числа, повторы, разделители подряд.
• Отказной случай. Ответа не существует: None, False или исключение — смотря что записано в контракте.
• Случай, о котором договорились отдельно. Тот самый, ради которого задавали уточняющий вопрос.

Контрпример

Отдельно стоит назвать особый вид теста.

В обратную сторону это не работает, и разница здесь принципиальная. Один контрпример доказывает, что решение неверно. Любое количество пройденных тестов не доказывает, что оно верно, — проверить все возможные входы невозможно. Поэтому дальше понадобится рассуждение об инварианте: тесты находят ошибку, а правильность объясняет оно.

4. Особые входы: где ломаются решения

Классы входов — вещь общая, но на практике падают на одних и тех же пяти. Разберём каждый: что именно в коде оказывается неверным и почему это не видно на обычных данных.

Пустой вход

Пустой список ломает две конструкции. Первая — деление на длину: sum(chisla) / len(chisla) при нулевой длине даёт ZeroDivisionError. Вторая — обращение к первому элементу: chisla[0] вызывает IndexError, потому что элемента с индексом 0 не существует. Обе строки на непустом входе работают, поэтому в обычных тестах не проявляются.

Лечится это не проверкой «на всякий случай», а решением, записанным в контракте: вернуть ноль, вернуть None или объявить пустой вход недопустимым и выбросить исключение. У каждого варианта своя цена. None легко не заметить: вызывающий код сложит его с числом и упадёт в другом месте, далеко от причины. Исключение останавливает программу там, где нарушен договор.

Отрицательные числа

Строка best = 0 в поиске максимума — не техническая деталь, а утверждение: «ответ точно не меньше нуля». Для списка [-7, -3] оно ложно, и функция возвращает 0 — число, которого во входе нет вообще.

Правильное начальное значение берут из самих данных: первый элемент списка. Тогда утверждение «best — максимум просмотренной части» истинно с самого начала. Та же ошибка в зеркальном виде встречается при поиске минимума: старт с нуля даёт неверный ответ, если все числа положительные.

Дубликаты

Когда ответ — индекс, а не значение, повторы перестают быть безразличными. Сравнение chisla[i] <= chisla[best] вместо < переносит ответ на каждое следующее равное значение, и вместо первого вхождения возвращается последнее. На списке без повторов обе версии неразличимы.

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

Последний элемент

Цикл for i in range(len(chisla) - 1) перебирает индексы от 0 до n − 2 и не доходит до последнего. Если тело цикла читает пару соседей chisla[i] и chisla[i + 1], такая граница правильная: последняя пара как раз заканчивается на n − 1. Если же тело читает только chisla[i], последний элемент остаётся непроверенным.

Граница цикла зависит не от длины списка, а от того, к каким индексам обращается тело цикла.

Большие числа

Последний случай отличается от предыдущих: здесь алгоритм верный, а ответ всё равно неверный. Если каждое слагаемое помещается в тип фиксированной разрядности, это ещё не значит, что в него поместится сумма. Знаковое 32-битное целое — это тип, под который отведено 32 двоичных разряда, причём один из них уходит на знак. Вмещает он значения до 2 147 483 647; два числа по два миллиарда по отдельности проходят, их сумма — нет.

В самом Python у целых нет предела разрядности, поэтому сумма посчитается точно. Ограничение появляется на границе: поле int32 в базе данных, формат обмена, переменная в Java или C++. Проверять нужно диапазон принимающей стороны, а границу считать по худшему случаю — длина входа, умноженная на наибольший модуль элемента.

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

пустой вход        вход []
                   ждём ошибку или None · получили ZeroDivisionError: division by zero
отрицательные      вход [-7, -3]
                   ждём -3 · получили 0
дубликаты          вход [3, 1, 1]
                   ждём 1 · получили 2
последний элемент  вход [4, 8, 0]
                   ждём True · получили False
переполнение       вход [2000000000, 2000000000]
                   ждём 4000000000 · получили не помещается в int32: 4000000000

5. Инвариант цикла

У тестов есть ограничение. Они показывают, что функция верна на тех входах, которые вы перебрали. Входов бесконечно много, перебрать их нельзя, а утверждать нужно про все. Остаётся рассуждение о том, что происходит в цикле.

Сумма покупок в корзине

Человек ходит по магазину со списком, складывает товары в корзину и держит сумму в уме. После каждого товара сумма в уме меняется, но одно остаётся верным всегда: в уме лежит стоимость того, что уже в корзине. Не всего списка, не будущих покупок — именно уже положенного.

Это утверждение и есть инвариант. Удобство его вот в чём: помнить весь путь по магазину не нужно, достаточно знать, что правило соблюдалось на каждом шаге. Тогда на кассе сумма в уме окажется стоимостью всей корзины — просто потому, что в конце «уже положенное» и есть всё, что вы взяли.

Сломать такое рассуждение легко: если на одном товаре вы забыли прибавить цену, правило нарушилось, и на кассе числа не сойдутся. В коде это выглядит так же, только «забыть прибавить» превращается в пропущенную строку или неверную ветку if.

def summa(ceny):
    itogo = 0
    for k, cena in enumerate(ceny, start=1):
        itogo += cena
        print(f'  положили {k}-й товар за {cena} | в корзине {ceny[:k]} | itogo = {itogo}')
    return itogo

Функция enumerate(ceny, start=1) выдаёт пары «номер, значение» и нумерует с единицы, поэтому k — это сколько товаров уже положили, а ceny[:k] — сама корзина на этот момент.

цены: [120, 45, 300, 60]
проход:
  положили 1-й товар за 120 | в корзине [120] | itogo = 120
  положили 2-й товар за  45 | в корзине [120, 45] | itogo = 165
  положили 3-й товар за 300 | в корзине [120, 45, 300] | itogo = 465
  положили 4-й товар за  60 | в корзине [120, 45, 300, 60] | itogo = 525
итог: 525 | проверка суммой Python: 525

Каждая строка вывода читается отдельно от остальных. В третьей itogo = 465 — это сумма трёх товаров, которые к тому моменту в корзине. Про четвёртый товар строка ничего не утверждает, потому что его ещё не клали.

Три шага объяснения

Из инварианта правильность выводят в три шага. Проверим их на той же корзине.

1. Инициализация. До цикла обработано ноль товаров, их стоимость равна нулю, и itogo = 0. Утверждение верно при k = 0.
2. Сохранение. Если до шага itogo была стоимостью первых k товаров, то после itogo += cena она станет стоимостью первых k + 1. Шаг переносит утверждение с k на k + 1.
3. Завершение. Цикл заканчивается, когда обработаны все n товаров. Подставляем k = n: itogo равна стоимости всего списка — это и есть нужный ответ.

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

Третий шаг объясняет, почему инвариант выбирают именно таким, а не любым верным. Утверждение «itogo не больше миллиона» тоже держится на каждом шаге, но при k = n из него не следует ответ, поэтому пользы от него нет.

Разбор на примере

В корзине переменная была одна, и утверждение про неё получалось само собой. Возьмём случай посложнее — поиск самой длинной серии одинаковых соседей, где переменных две: longest_run([1, 1, 2, 2, 2]) должна вернуть 3.

Тот же счёт встречается и вне кода. Человек идёт вдоль забора и считает, сколько досок подряд выкрашены в один цвет. В голове два числа: длина полосы, которая тянется прямо сейчас, и самая длинная полоса из уже пройденных. Первое сбрасывается, как только цвет сменился, второе только растёт. Это и есть две переменные из кода.

def longest_run(chisla):
    if not chisla:
        return 0
    best = tekushchaya = 1
    for i in range(1, len(chisla)):
        if chisla[i] == chisla[i - 1]:
            tekushchaya += 1
        else:
            tekushchaya = 1
        if tekushchaya > best:
            best = tekushchaya
    return best

Чтобы утверждение не осталось словами, тот же проход можно запустить с печатью состояний и проверить его глазами после каждого шага:

вход [1, 1, 2, 2, 2]
  k = 2: обработано [1, 1]  tekushchaya = 2  best = 2
  k = 3: обработано [1, 1, 2]  tekushchaya = 1  best = 2
  k = 4: обработано [1, 1, 2, 2]  tekushchaya = 2  best = 2
  k = 5: обработано [1, 1, 2, 2, 2]  tekushchaya = 3  best = 3
ответ: 3

Посмотрите на строку k = 3. Цвет сменился, tekushchaya сбросилась в единицу, и это не ошибка: новая полоса действительно состоит пока из одной доски. А best помнит полосу из двух, которую мы уже прошли. Оба утверждения на этой строке верны — значит, инвариант держится.

Как отличить рабочую формулировку от бесполезной

Своя формулировка редко получается точной с первого раза. Проверить её можно на трёх типичных промахах — все три встречаются в работах постоянно.

• «best = 3» — это состояние одного запуска на одном входе, а не утверждение про любой вход.
• «best хранит максимум» — не сказано, максимум чего. Проверить такое утверждение после шага нечем.
• «После первых k элементов best — самая длинная серия внутри них» — названы и смысл переменной, и обработанная часть. Вот это проверяется на каждом шаге и при k = n даёт ответ.

Инвариант не совпадает с условием цикла. Условие while left < right решает, будет ли следующая итерация, и после выхода из цикла оно ложно. Инвариант, наоборот, истинен и после выхода — на этом и построен третий шаг.

Для цикла while к трём шагам добавляется четвёртый вопрос: почему цикл вообще закончится. У for список конечен: шагов столько, сколько элементов. У while нужно назвать величину, которая уменьшается на каждой итерации и не может уменьшаться бесконечно. В двоичном поиске это длина отрезка: каждый шаг делит её пополам, и рано или поздно она доходит до нуля.

6. Ручной прогон

Остаётся случай, когда запустить код нельзя. На алгоритмической секции кнопку запуска обычно выключают именно для того, чтобы увидеть, умеет ли человек рассуждать о своём коде. В работе бывает похожее: ошибка воспроизводится только на данных заказчика, и разбираться приходится по листингу.

Разберём двоичный поиск с ошибкой в границе цикла. Условие записано как while left < right, хотя отрезок задан включительно с обеих сторон:

def binary_search(chisla, target):
    left, right = 0, len(chisla) - 1
    while left < right:            # ошибка: нужно left <= right
        middle = (left + right) // 2
        if chisla[middle] == target:
            return middle
        if chisla[middle] < target:
            left = middle + 1
        else:
            right = middle - 1
    return -1

Прогоним binary_search([1, 3, 5], 5). Записываем состояние на каждом шаге:

Место ошибки видно на втором шаге: в отрезке остался один элемент — тот самый, который мы ищем, — но цикл в него уже не зашёл. Инвариант двоичного поиска звучит так: «если target есть в списке, он находится внутри отрезка от left до right». Утверждение верно и на выходе, а вот использовать его нечем, потому что отрезок из одного элемента остался непроверенным.

binary_search([1, 3, 5], 5)
  left = 0, right = 2, middle = 1, chisla[middle] = 3
  выход из цикла: left = 2, right = 2 — отрезок из одного элемента не проверен
  ответ: -1

binary_search([5], 5)
  выход из цикла: left = 0, right = 0 — отрезок из одного элемента не проверен
  ответ: -1

Минимальный контрпример

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

Ищут его сужением: взяв вход, на котором функция ошибается, выбрасывают из него всё, что можно, пока ошибка не исчезнет. На коротком входе каждое изменение переменной видно целиком, и прогон занимает три строки вместо тридцати.

Что проверять в границах цикла

• range(n) перебирает индексы от 0 до n − 1: правая граница не включается.
• range(n - 1) нужен, когда тело читает пару chisla[i] и chisla[i + 1], и ошибочен, когда тело читает только chisla[i].
• while left < right оставляет непроверенным отрезок из одного элемента; while left <= right проверяет и его.
• Если тело меняет индекс само, отдельно проверяют, что величина «сколько осталось» действительно уменьшается: иначе цикл не закончится.

7. Итоги

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

Сначала условие дополняют вопросами: о входе, об ответе, об особых случаях, об ограничениях и о том, можно ли менять данные. Ответы записывают контрактом рядом с кодом. Потом контракт превращают в тестовые примеры, разложенные по классам входов: каждый тест берёт свой класс, а один контрпример уже доказывает ошибку. И наконец, правильность цикла объясняют инвариантом — утверждением про обработанную часть, которое проверяют на инициализации, на шаге и на завершении.

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