Трансмутации слов друг в друга: решение на языке Haskell
Хабы: Haskell
В ставших уже традиционными ежемесячных конкурсах по функциональному программированию всем желающим предлагается поразмять свои мозги и представить на суд общественности своё решение конкурсной задачи на каком-либо языке программирования (кстати, совсем не обязательно функциональном — многие конкурсанты используют и такие экзотические языки, как Java и даже Python). В апрельском конкурсе в качестве задачи была предложена задача по поиску цепочки трансмутаций между словами в заданном словаре. Конечно, это есть задача по поиску [кратчайшего] пути в графе, рёбра которого представляют возможность перехода от слова к слову по заданному правилу (должна быть изменена и только изменена одна и только одна буква), однако задача заинтересовала участников, и в качестве результатов было представлено 22 решения на 9 различных языках (C++, Clojure, D2, Erlang, F#, Go, Haskell, Mathematica и Perl).Словарь, по которому осуществлялся поиск, можно получить здесь. Впрочем, можно воспользоваться услугами сайта «Слова из букв», с которого, собственно, и получен словарь. Конечно, многие слова там очень странные, однако какая нам разница, на каком словаре строить граф для конкурса? Пусть это будут просто формальные цепочки символом. А по результатам конкурса вообще появлялись такие предложения от участников: «Надо написать новое определение слова «АХЧЕ» — это слово, которое используется в конкурсах по программированию, для порождения самых длинных метаграмм».
Ну а поскольку конкурс был назван «Кельтская алхимия», занимались мы трансмутациями следующих пар слов (метаграмм):
- МУХА — СЛОН
- ДЕНЬ — НОЧЬ
- СНЕГ — ВОДА
- ОТЕЦ — МАТЬ
- РУКА — НОГА
- ЗИМА — ЛЕТО
- СВЕТ — ТЬМА
- ЛИПА — КЛЁН
Как видно, здесь имеет место попытка подобрать слова, часто противоположные по смыслу. Это придало конкурсу некоторую изюминку, хотя, конечно, все участники подошли к этому вопросу абсолютно по программистски — все разработали алгоритмы поиска путей в графе. А кое-кто даже граф визуализировал:
Итак, если вам интересна задача, и вы хотите узнать, как организовывался конкурс и как можно решить поставленную задачу, то милости прошу дальше...
