FSharp · Script
[<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