Задачка "Star delete" и мое решение

Нашел замечательный раздел на reddit, на котором публикуют задачки на программирование — dailyprogrammer. Открыл первую попавшуюся задачку и стал решать.

Задача

Полный тест задачи. Нужно написать функцию, которая берет строку, удаляет из нее все символы "*", а так же удаляет все символы слева и справа от этой звездочки.

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

"adf*lp" --> "adp"
"a*o" --> ""
"*dech*" --> "ec"
"de**po" --> "do"
"sa*n*ti" --> "si"
"abc" --> "abc"

Мое решение

Шаг 0. Написать тест.

В задаче есть примеры как функция должна рабоать, так что мне показалось что будет удобнее всего сначала написать тест, который проверят что будущая функция работает правильно. Это TDD (test driven development) в чистом виде. Я далеко не всегда пишу тесты заранее, но в этом случае я посчитал что это самый простой способ.

Скелет функции и тест на нее

Подход 1.

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

Так что первое что я написал была вот такая регулярка:

$string =~ s/(.\*.)//g;

Запускаю тесты (команда "prove -l") — оказывается что некоторые тесты проходятся, а некоторые фейлятся:

#   Failed test 'de**po'
#   at t/simple.t line 17.
#          got: 'dpo'
#     expected: 'do'

#   Failed test '*dech*'
#   at t/simple.t line 17.
#          got: '*dech*'
#     expected: 'ec'

#   Failed test 'sa*n*ti'
#   at t/simple.t line 17.
#          got: 's*ti'
#     expected: 'si'
# Looks like you failed 3 tests of 7.

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

Подход 2.

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

$string =~ s/(.?\*.?)//g;

После такого дополенния падает только один тест:

#   Failed test 'de**po'
#   at t/simple.t line 17.
#          got: 'dpo'
#     expected: 'do'
# Looks like you failed 1 test of 7.

Подход 3.

Тест показал что мое решене неправильно работает в том случае если несколько звездочек находится подряд. Вношу исправление:

$string =~ s/(.?\*+.?)//g;

Теперь все тесты проходятся.

Считаю что задача решена.

Я засекал время сколько мне понадобилось для решения этой задачи — 12 минут.

Размышления

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

После того как я решил задачку я прочитал комментарии и другие решения этой же задачи (ссылка).

Как результат решения и чтения коментов я вынес для себя несколько мыслей.

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

Во-вторых. Задачка совершенно элементарная, но я умудрился решить ее только с третьего подхода. Благодаря тому что были тесты переходы между подходами были очень простые и плавным, но тем не менее у меня было 2 решения, которые оказались неправильными. И тут я задаю себе вопрос на который у меня нет ответа: правильно ли что я решал задачу таким способом — взял попробовал, получил ошибку, переделал. Не является ли более правильным подход - чуть-чуть больше подумал в начале, но решил задачу сразу правильно.

В-третьих. У меня нет полной, 100% уверенности в том что я решил задачу правильно. Я не знаю как доказать корректность решения.

В-четвертых. Мой окончательный вариант — это регулярка:

$string =~ s/(.?\*+.?)//g;

В комментариях я увидел другую регулярка:

$string =~ s/([^*]?\*+[^*]?)//g;

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

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

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

Иван Бессарабов
ivan@bessarabov.ru

12 июня 2014

Edit this post on GitHub