Проблема «Fizz Buzz»

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

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

Разумеется, были среди них и приверженцы опен сорса, такие как я, например. Были даже линуксоиды, точнее был — из пишущих под линукс — всего один; студент из ДВГУ. Долго ли коротко ли, завязалось знакомство. Несколько интересных вечеров в чате, а затем пришел твиттер.

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

Первым «кластером» (говоря по-русски — сильно связным графом) образовавшихся соц.сетевых связей оказалась, как ни странно, группа студентов ДВГУ. Думаю это говорит о большой ошибке, допущеной мной после выпуска из школы: я поступил в отстойный Уссурийский ВУЗ, в котором вообще не было правильных людей (впрочем, я исправил эту ошибку благополучно из него вылетев :).

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

Тогда, сейчас — нет ничего такого что я мог бы написать в своем резюме. Я отправил пустое. Через неделю мне пришло письмо с десятком заданий. Бóльшая их часть была посвящена проблемам типа рефакторинга странного процедурного PHP-кода, рефакторинга С++-кода с использованием паттернов объектно-ориентированого программирования (о богомерзкие ООП-паттерны!) и пара простых алгоритмических вопросов среди которых был знаменитый «Fizz Buzz». С заданиями я по всей видимости не справился; или мои ответы были неожиданной форме — кто знает? В общем, это был провал.

Казалось бы — причем здесь моя жизнь? История о том как примитивная задача для программистов встретилась на моем пути — ну и…?

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

Говорят, в хорошо поставленном вопросе содержится половина ответа. Вопрос «Fizz Buzz» поставлен настолько хорошо, что он по сути и является ответом для самого себя:

Write a program that prints the numbers from 1 to 100. But for multiples of three print «Fizz» instead of the number and for the multiples of five print «Buzz». For numbers which are multiples of both three and five print «FizzBuzz».

Продемонстрировать последнее утверждение поможет решение задачи Ъ-лисперским способом — с помощью правильной расстановки скобочек прямо в определении задачи:

Write a program that (prints the numbers) (from 1 to 100). But (for (multiples of three) (print «Fizz»)) instead of the number and (for the (multiples of five) (print «Buzz»)). (For numbers which are (multiples of both three and five) (print «FizzBuzz»)).

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

(from 1 to 100)
(print numbers)
(for (multiples of three) (print "Fizz"))
(for (multiples of five) (print "Buzz"))
(for (multiples of three and five) (print "FizzBuzz"))

Это очень декларативный код. В самом деле, лисп не сильно отличается от пролога, но декларативный стиль не уместен для решения явно итеративной задачи, тем более что для реализации получившегося кода идеально подходит средство Iterate из мира Common Lisp'а. Осталось лишь перетосовать условия, добавить пару императивных фишек — и решение готово.

(iterate
 (for number from 1 to 100)
 (for (multiples-of 3 5 number) do (print "FizzBuzz") (continue))
 (for (multiples-of 3 number) do (print "Fizz") (continue))
 (for (multiples-of 5 number) do (print "Buzz") (continue))
 (print number))

Если есть желание, можете привести реализацию функции multiples-of и драйвера for do.