Рубрика «алгоритм A*»

В ставших уже традиционными ежемесячных конкурсах по функциональному программированию всем желающим предлагается поразмять свои мозги и представить на суд общественности своё решение конкурсной задачи на каком-либо языке программирования (кстати, совсем не обязательно функциональном — многие конкурсанты используют и такие экзотические языки, как Java и даже Python). В апрельском конкурсе в качестве задачи была предложена задача по поиску цепочки трансмутаций между словами в заданном словаре. Конечно, это есть задача по поиску [кратчайшего] пути в графе, рёбра которого представляют возможность перехода от слова к слову по заданному правилу (должна быть изменена и только изменена одна и только одна буква), однако задача заинтересовала участников, и в качестве результатов было представлено 22 решения на 9 различных языках (C++, Clojure, D2, Erlang, F#, Go, Haskell, Mathematica и Perl).

Словарь, по которому осуществлялся поиск, можно получить здесь. Впрочем, можно воспользоваться услугами сайта «Слова из букв», с которого, собственно, и получен словарь. Конечно, многие слова там очень странные, однако какая нам разница, на каком словаре строить граф для конкурса? Пусть это будут просто формальные цепочки символом. А по результатам конкурса вообще появлялись такие предложения от участников: «Надо написать новое определение слова «АХЧЕ» — это слово, которое используется в конкурсах по программированию, для порождения самых длинных метаграмм».

Ну а поскольку конкурс был назван «Кельтская алхимия», занимались мы трансмутациями следующих пар слов (метаграмм):

1. МУХА — СЛОН
2. ДЕНЬ — НОЧЬ
3. СНЕГ — ВОДА
4. ОТЕЦ — МАТЬ
5. РУКА — НОГА
6. ЗИМА — ЛЕТО
7. СВЕТ — ТЬМА
8. ЛИПА — КЛЁН

Как видно, здесь имеет место попытка подобрать слова, часто противоположные по смыслу. Это придало конкурсу некоторую изюминку, хотя, конечно, все участники подошли к этому вопросу абсолютно по программистски — все разработали алгоритмы поиска путей в графе. А кое-кто даже граф визуализировал:

Итак, если вам интересна задача, и вы хотите узнать, как организовывался конкурс и как можно решить поставленную задачу, то милости прошу Читать полностью »