CatsAndMouse.fs

FSharp · Script

/Program.fs


[<EntryPoint>]
let main argv =
    // Пока что не нашёл ничего умнее, чем просто пройтись по графу с "улучшением" результата
    // Применил несколько допущений:
    // - вероятность в районе 100, т.е. не может быть такого, что вероятность выживания 140%, тем самым избегаем зацикливаний
    // - граф связный, иначе пляшем от 1го и куда максимум уйдём
    // - бегать по улицам можно в обе стороны. Допущение легко убирается - выкидывается из кода момент где направления дублируют в обратную сторону
    // - я плохо знаком с ФП, поэтому как вышло так вышло

    let extract (paths:Map<int, (int*float)>) =
        let finish = paths |> Map.toSeq |> Seq.map fst |> Seq.max
        let rec follow x = seq {
            yield x
            match x with
            | 1 -> yield! Seq.empty
            | _ ->
                let prev, _ = paths.[x]
                yield! follow prev
        }
        let rev xs = Seq.fold (fun acc x -> x::acc) [] xs
        (snd paths.[finish], follow finish |> rev)
        
    let rec run directionsToInvestigate (roadmap: Map<int, seq<int*float>>) (investigatedMap:Map<int,(int * float)>) =
        let newPlaces = 
            directionsToInvestigate 
            |> Seq.map (fun x -> 
                let _, (pX: float) = investigatedMap.[x]
                roadmap.[x] |> Seq.map (fun (where, p) -> (where, p*pX, x))
            ) 
            |> Seq.concat
            |> Seq.groupBy (fun (x, p, from) -> x)
            |> Seq.map (fun (x, s) -> 
                let (p, from) = 
                    s 
                    |> Seq.fold (fun (maxP, maxPFrom) (x, p, from) ->
                        match p with
                        | p when p > maxPFrom -> (from, p)
                        | _ -> (maxP, maxPFrom)
                    ) (-1, -1.)
                (x, from, p)
            )
            |> Seq.filter (fun (x, p, from) -> 
                match x with
                | x when Map.containsKey x investigatedMap ->
                    let oldFrom, oldP = investigatedMap.[x]
                    oldP < p
                | _ -> true
            )
        
        let (justInvestigatedMap, newPlaces) = 
            newPlaces
            |> Seq.fold ( fun ( (investigatedMap: Map<int, int*float>), newPlaces) (x, p, from)  ->
                let updated = seq {
                    yield! newPlaces
                    yield x
                }
                ( investigatedMap.Add(x, (from, p)), updated)
            ) (investigatedMap, Seq.empty)
        match justInvestigatedMap with
        | justInvestigatedMap when (justInvestigatedMap=investigatedMap) -> investigatedMap
        | _ -> run newPlaces roadmap justInvestigatedMap

    //
    //    Основная функция. 
    //

    let solution input =
        let roadmap = 
            input 
            |> Seq.map (fun (a,b,p) -> (a,b,(float(p)/100.))) 
            |> Seq.map (fun (a,b,p) -> seq {
                yield (a,b,p)
                yield (b,a,p)
            })
            |> Seq.concat 
            |> Seq.groupBy (fun (a,b,p) -> a) 
            |> Seq.map (fun (key,s) -> (key, s |> Seq.map (fun (a,b,p)->(b,p))))
            |> Map.ofSeq

        let investigatedMap = seq { yield (1, (1, 1.))} |> Map.ofSeq
        let paths = run (seq{ yield 1}) roadmap investigatedMap
        extract paths

    let display (p, path) = 
        printfn "propability: %f\npath: %s\n" p (path |> Seq.map string |> String.concat " -> ")

    let inputs = seq {
        yield [ (1, 2, 98); (3, 1, 50); (1, 4, 20); (2, 4, 99); (3, 4, 70) ] 
        yield [ (1, 2, 95); (3, 1, 99); (1, 4, 20); (2, 5, 94); (3, 5, 70); (4, 5, 99); (3, 2, 70; (3, 4, 99)) ] 
        yield [ (1, 2, 99); (3, 1, 99); (1, 4, 20); (2, 5, 94); (3, 5, 70); (4, 5, 99); (3, 2, 70; (3, 4, 99)) ] 
        yield [ (1, 2, 98); (3, 1, 98); (1, 4, 99); (2, 5, 98); (3, 5, 99); (4, 5, 95); (3, 2, 70; (3, 4, 99)) ] 
        yield [ (1, 2, 98); (3, 1, 98); (1, 4, 99); (2, 5, 98); (3, 5, 99); (4, 5, 95); (3, 2, 70; (3, 4, 99)); (1, 5, 98) ] 
    }

    inputs 
    |> Seq.iter (fun x ->
        let res = solution (x |> List.toSeq)
        display res
    )
    |> ignore
    0
;