вторник, 20 декабря 2011 г.

Задача о движущихся точках и её решение на языке Haskell

В блогах на сайте free-lance.ru не так давно один человек разместил задачу, условие которой в чуть облагороженном (мной :) виде звучит следующим образом:
===
Имеется N вершин, между ними есть ребра (длину ребер мы задаем сами целым числом). По ребрам ездят точки, которые могут ехать в обе стороны. При нахождении двух точек в одной вершине происходит столкновение. Соответственно, если точки едут по одному ребру навстречу друг другу, тоже произойдет столкновение. Движение точек задано списком вершин, через которые они проходят. Скорости точек равны единице. При
достижении конечной вершины точка исчезает. По заданной конфигурации сети и точек
определить, будет ли столкновение.

===
Попробуем написать решение этой задачи на Haskell.