open System
open System.Collections.Generic
///Чашка с обхемом и количеством налитой воды
type Cap = {x: int; v: int;}
            override x.ToString() = x.ToString("емкость")
            member x.ToString(capName) = String.Format("{0} объемом {1}л",capName,x.v)
            member x.ToFullString() = String.Format("{0}л в емкости объемом {1}л", x.x,x.v)
///Сотояние двух чашем в месте с cool story о том, как они дошли до такого
type CapsState = {caps: Cap * Cap; history: string list}

///Освободить чашку!!!
let emptyChanger {caps=(cap1,cap2);history=h} =
    let empty c = {c with x=0}
    {caps=empty cap1, cap2; history=String.Format("Опустошить {0}",cap1)::h}
///Наполчнить чарку!!!
let fillChanger {caps=(cap1,cap2);history=h} =
    let fill c = {c with x=c.v}
    {caps=fill cap1, cap2; history= String.Format("Заполнить {0}",cap1)::h}
///Переливаем из стакана в стакан трезвыми руками так, что ни капли не проливается
let strainChanger {caps=(cap1,cap2);history=h} =
    let strain = function
    | c1, c2 when c1.x+c2.x<=c2.v -> {c1 with x=0}, {c2 with x=c1.x+c2.x}
    | c1, c2                      -> {c1 with x=c1.x-c2.v+c2.x}, {c2 with x=c2.v}
    {caps=strain(cap1,cap2); history=String.Format("Из {0} перелить воду в {1}",
                                                   cap1.ToString("емкости"),cap2)::h}
///Списко действий, которые можно осуществлять над сосудами
let changers = [fillChanger; strainChanger; emptyChanger]

///Это всмопогательные активные патерны, должны быть с станадратной либе,
///но авторы F# считают, что flip или там матчить сиквенсы нинужно
let (|SeqEmpty|SeqCons|) (xs: 'a seq) =
    if Seq.isEmpty xs then SeqEmpty
    else SeqCons(Seq.head xs, Seq.skip 1 xs)

let find v1 v2 tv =
    ///Расстояние до нужного нам объема
    let distatnce {caps=c1,c2} =  min (abs (c1.x-tv)) (abs (c2.x-tv))
    ///Запоминаем состояние, в котором побывали
    let setVisited visiteds {caps=caps} = Set.add caps visiteds
    ///Проверяем посящили ли мы состоянние, не забывая, что от перемены мест блабла
    let isVisited visiteds {caps=c1,c2} = Set.contains (c1,c2) visiteds ||
                                          Set.contains (c2,c1) visiteds
    ///Добавляем новые состояния в списоск неповященным
    let addUnvisiteds unvisiteds states =
        Seq.fold(fun u s -> Set.add s u) unvisiteds states
    ///Получаем следующее состояние, которое надо посетить
    ///Для этого группируем состояния по расстоянию до "цели"
    ///Выбираем наименьшее, потом выбираем состояние с самой короткой историей
    let getUnvisited unvisiteds =
        let unv = unvisiteds |> Seq.groupBy(distatnce) |> Seq.head |> snd
                             |> Seq.sortBy(fun s ->List.length s.history)
                             |> Seq.head
        unv, Set.remove unv unvisiteds
    ///генерируем состояния, в которые можно перейти из текущего
    ///исклюяаем дубликаты и уже посещенные, сортируем по расстоянию
    let getChanges visiteds state =
        let {caps=cap1,cap2} = state
        let revState = {state with caps = cap2,cap1}
        seq{ for s in List.map(fun f -> f state) changers -> s;
             for s in List.map(fun f -> f revState) changers -> s}
        |> Seq.distinctBy(fun s->s.caps)
        |> Seq.filter(isVisited visiteds>>not)
        |> Seq.sortBy(distatnce)
    ///ДАЙ НАЙДЕТ ИЩУЩИЙ!
    let rec find' state visiteds unvisiteds =
        let {caps=c1,c2} = state
        let visiteds = (setVisited visiteds state)
        match distatnce state, (addUnvisiteds unvisiteds (getChanges visiteds state))  with
        | 0, _             -> Some(state) //нашли - ну ок
        | n, SeqEmpty      -> None        //не нашли - ну ок, чо
        | n, unvisiteds    -> let s, u = getUnvisited unvisiteds in find' s visiteds u //ищем дальше
    find' {caps={x=0;v=v1},{x=0;v=v2};history =[]} Set.empty Set.empty

match find 5 8 2 with
| None         -> Console.WriteLine("Поиск не дал результатов")
| Some(result) -> result.history |> List.rev |> List.iter (printfn "%s")
                  Console.WriteLine("Найдено состояние \n{0}\n{1}",
                                    (fst result.caps).ToFullString(),
                                    (snd result.caps).ToFullString())
                  Console.WriteLine("Profit!!!")