Запускаем апрельский конкурс по функциональному программированию, который посвящается Международному дню математика (1 апреля, если что, — это никакой не «день дурака»). Сегодня мы будем заниматься «алхимией». Будем трансмутировать вещи друг в друга. Вещами на этот раз будут слова русского языка.Помните, в детстве у нас была забава, иногда публикуемая в различных журналах в виде пары слов одинаковой длины, которые надо было преобразовать друг в друга. Например, надо было превратить муху в слона. То есть найти такую кратчайшую последовательность переходов от слова «МУХА» к слову «СЛОН», на каждом шаге которой заменялась бы ровно одна буква, при этом получающееся слово должно быть правильным словом русского языка.
То есть правила трансмутаций просты. На каждом шаге можно поменять ровно одну букву (не добавить, не убрать, а именно поменять — заменить одну букву другой) так, чтобы вновь получившееся слово входило в состав лексикона языка. Каждое вновь получаемое в цепочке трансмутаций слово должно быть в начальной форме. Если существует такая последовательность от начального слова к целевому, то трансмутация объявляется успешной, и мы получаем в свой арсенал алхимика новое заклинание. При этом, как полагается, такая цепочка должна быть кратчайшей — если на пути есть всякие циклы, то нам они не нужны.
Итак, произведите трансмутации (или докажите, что они невозможны в данном лексиконе):
1. МУХА — СЛОН.
2. ДЕНЬ — НОЧЬ.
3. СНЕГ — ВОДА.
4. ОТЕЦ — МАТЬ.
5. РУКА — НОГА.
6. ЗИМА — ЛЕТО.
7. СВЕТ — ТЬМА.
8. ЛИПА — КЛЁН.
Уровень 1: Вот здесь лежит словарь слов русского языка длиной 4 буквы.
Уровень 2: Словарь можно получить здесь. Только его надо выкачать и выделить из разметки.
Уровень 3: Сами найдите для себя словарь и используйте его. Правда, в этом случае я, скорее всего, не смогу проверить результаты, поскольку этот уровень слишком высок для меня.
Регламент конкурса обычный. Начинайте решать, конкурс продлится до понедельника 09.04.2012, где-то до 12:00 по московскому времени. Решить надо при помощи программы, реализованной на каком-нибудь языке программирования, используемом вами (не обязательно на функциональном языке). После этого будем проверять общность алгоритмов — в качестве тестовой задачи задам что-нибудь обратное. Первый и второй конкурсанты, кто даст ответы в комментариях и подтвердит общность своего алгоритма, получат материальные призы — мою книгу и журнальчик с моей статьёй соответственно. Остальные, правильно нашедшие цепочки трансмутаций (и опять же доказавшие общность своих алгоритмов), получат поощрительные призы в виде персональных электронных экземпляров моих книг. Ну и скидки на печать таких книг в издательстве «Самиздал». Вопросы по существу можно задавать в комментариях, которые я буду раскрывать, ибо все комментарии до окончания конкурса скрываются.
При публикации своего решения в комментариях давайте ссылки на свой код. Также прошу указывать примерное время разработки и язык программирования.
Дерзайте!
Дополнение 1: Комментарии раскрыты в 07:45 09.04.2012. Начинаем проверку общности. Для этого прошу конкурсантов указать мне длину самой длинной цепочки трансмутации, которая есть в этом словаре (уровень 1 или 2, там словари идентичны). Ну и саму эту цепочку тоже можно указать.
Дополнение 2: Конкурс закрыт в 23:09 09.04.2012. Начинаю подводить итоги. Кто не успел — не обессудьте.
Дополнение 3: Результаты конкурса опубликованы.
Предыдущие конкурсы:
1. Август 2011. Задача о возрастах детей математика: условие, результаты.
2. Сентябрь 2011. Кто на ком женат: условие, результаты.
3. Октябрь 2011. Задачи о переправах: условие, результаты.
4. Ноябрь 2011. Задача о надёжности кода: условие, результаты.
5. Декабрь 2011. Задача о конструировании чисел из чисел: условие, результаты.
6. Январь 2012. Расшифровка кода на языке Haskell: условие, результаты.
7. Февраль 2012. Мат в один ход: условие, результаты.
8. Март 2012. Переливание жидкости из сосуда в сосуд: условие, результаты.
Кто ещё не зарегистрировался на официальном форуме ФП(ФП), может сделать это прямо сегодня. Там можно задать вопросы как по организации конкурсов, так и вообще по функциональному программированию.
Если вы хотите дополнительно отблагодарить организатора (то есть меня), но не знаете как, то вам сюда. Собранные благодарности пойдут прямиком в ФП(ФП).