Code that belongs in a problem

8.12.2017

If you want proof, Harry, that you belong in Gryffindor, I suggest you look more closely at this.

Harry Potter and the Chamber of Secrets, by J.K. Rowling

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

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

Например, задача «Отрезок»: на клетчатой плоскости заданы две точки (x1, y1) и (x2, y2), надо посчитать, сколько клеток пересекает отрезок, соединяющий эти две точки. В этой задаче на алгопроге указана тема — НОД, — и поэтому школьники, начиная решать эту задачу, сразу начинают вычислять НОД каких-нибудь величин. Но, например, вычисление НОД(x1, y1) — это очевидно неверное действие. Ни в каком правильном решении вам не может понадобиться НОД(x1, y1). Поэтому, если я вижу в решении вычисление этого НОДа, я даже не буду искать контр-тест — сразу понятно, что решение неверно. Более того, этому решению даже контр-тесты не особо помогут, его бессмысленно отлаживать на каких-то тестах — в нем принципиальная ошибка сразу в начале решения.

С другой стороны, в этой задаче надо в первую очередь вычислить x1-x2 и y1-y2 (а еще лучше сразу взять по модулю), т.к. ответ зависит только от этих величин. Вычисление этих разностей должно быть в любом правильном решении, поэтому, если в решении этого нет, то тоже сразу понятно, что решение неправильное и смотреть его дальше не имеет смысла.

Или еще задача (простая): на шахматной доске даны две клетки, надо проверить, бьет ли вторую клетку слон, стоящий в первой клетке. Я видел в этой задаче решения, которые зачем-то считают остатки от деления на 2 каких-то чисел. Это явно неправильно, тут никакой периодичности с периодом 2 нет, и потому совершенно непонятно, зачем в этой задаче брать остаток от деления на 2. (Вот если бы стоял вопрос «может ли слон добраться с одной клетки до другой за несколько ходов», то да, остаток от деления на 2 был бы очень в тему — если кто и не знает, что слоны бывают белопольными и чернопольными, то достаточно нарисовать картинку на бумажке и вы сразу увидите, что доступные и недоступные клетки чередуются.)

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


…В английском языке есть прекрасное выражение «belong in». Merriam-Webster дает ему следующее определение: «to be suitable, appropriate, or advantageous; to be in a proper situation». Я не знаю адекватного перевода этой фразы на русский, но примерный смысл — быть на своем месте. «A dictionary belongs in every home» (примеры из той же статьи) — это значит даже не то, что в каждом доме есть словарь, или что словарь обычно находится дома, а то, что словарю самое место в каждом доме. Или «a man of his ability belongs in teaching» — человек может и не быть учителем вообще, но тем не менее по его способностям он очень подходит для учительствования.

В цитате в эпиграфе к этому посту Дамблдор говорит вовсе не про то, что Гарри уже гриффиндорец, а про то, что Гарри в Гриффиндоре самое место, что Гарри — настоящий гриффиндорец, не по ошибке, а по глубоким причинам.

Так же и код. Есть код, который belong in решение задачи, а есть код, который does not belong in. И если вы пишете в задаче код, который не belong in, то неудивительно, что ваше решение не работает, и сколько if’ов не добавляйте, ваше решение не заработает.


Мой курс по алгоритмическому программированию (и подготовке к олимпиадам) для школьников, студентов и всех желающих — algoprog.ru