Как обычно с опозданием в месяц или даже полтора я публикую отчёт о проведённом в начале августа конкурсе по функциональному программированию под эгидой Фонда Поддержки Функционального Программирования ФП(ФП). Задачей конкурса было разработать программное решение для игры Wordament, которая заключается в поиске на квадратном поле 4х4 из букв запрятанных в нём слов. Слова могут быть в любой форме, каждая буква может быть использована в слове только один раз. Переходить от буквы к букве можно по горизонтали, вертикали или диагонали, поэтому иногда слова запрятаны в поле очень мудрёным способом.
Задача осложнялась тем, что один раунд игры длится ровно две минуты, а потому необходимо было реализовать очень быстрое решение — загрузка словаря в память, ввод исходных данных, поиск слов и вывод найденных слов на экран в порядке, отсортированном по возрастанию стоимости слов — всё это надо было сделать очень быстро, чтобы у игрока оставалось время на ввод слов в игру для получения большого количества очков. Скажем, что на экране слова должны были появиться не позднее, чем через 15 секунд после ввода исходных данных.
В конкурсе приняли участие четыре человека, которые написали свои решения на следующих языках программирования: Clojure, Nemerle, Python и Haskell. На основе последнего решения и написана данная краткая заметка.
Так что ежели кто интересуется алгоритмом поиска слов в поле, то добро пожаловать под кат.
