ข้อถัดมา Random Route

ข้อนี้จะให้รายการถนนมา และเวลาในการผ่านถนนเส้นนี้

โดยคุณก็ไม่รู้จุดหมาย คุณเลยสุ่มเลือกให้ทุกจุดหมายมีโอกาสเท่ากัน

และคุณก็ไม่รู้จะใช้ถนนเส้นไหน คุณก็สุ่มเลือกถนนที่สั้นที่สุด ถ้ามีหลายเส้น ทุกเส้นมีโอกาสเท่ากัน

อ่านเพิ่มเติมได้ ที่นี่



ข้อนี้อาจจะต้องใช้ทักษะในการใช้ Sequence ของ F# อยู่สักหน่อย



เริ่มจาก type ของถนน

type Road = { id:int; origin:string; dest:string; distant:int }

id คือหมายเลขถนน

origin กับ dest คือ ชื่อเมืองต้นทาง ปลายทาง

และ distant คือ ระยะทาง



เริ่มกันเลย

let solve start roads =

start ชื่อชื่อเมืองเริ่มต้น

roads ชื่อ sequence ของถนน (Road)

let rec explore ways =
    let newWays = 
        seq {
            for way in ways do
            for road in roads do
            let head::tails = way
            if road.origin = head.dest then
            if Seq.forall (fun it -> it.origin <> road.dest) way then
            yield road::way
        } |> Seq.cache
    if Seq.isEmpty newWays
    then ways
    else explore newWays |> Seq.append ways 
                         |> Seq.cache

คำสั่ง explore คำสั่งนี้จะต่อถนนไปเรื่อยๆ เช่น

เริ่มแรกอาจเป็น { กรุงเทพฯ-สมุทรสาคร }

พอ explore ครั้งนึงก็จะเป็น { กรุงเทพฯ-สมุทรสาคร; กรุงเทพฯ-สมุทรสาคร-เพชรบุรี }

คือ มันจะเติมเส้นทางไปเรื่อยๆ จนไม่เจอทางใหม่ๆ ถึงจะหยุด

let destinations = roads |> Seq.filter (fun it -> it.origin = start)
                         |> Seq.map (List.replicate 1)
                         |> explore
                         |> Seq.groupBy (fun (head::tails) -> head.dest)

ถัดมาก็จัดกลุ่มตามจุดหมาย

let destScore = 1.0 / float (Seq.length destinations)

และเนื่องจากเราจะสุ่มให้ทุกจุดหมายมีโอกาสเท่ากัน

เราก็แค่หารตามจำนวนจุดหมาย

let collectFn ways =
    let shortestWays = ways |> Seq.groupBy (List.sumBy (fun it -> it.distant))
                            |> Seq.minBy fst
                            |> snd
                            |> Seq.cache
    let wayScore = 1.0 / float (Seq.length shortestWays)
    shortestWays |> Seq.collect id
                 |> Seq.map (fun it -> it.id, destScore * wayScore)

ถัดมาเป็นคำสั่งหาโอกาสของถนนต่างๆ

เริ่มจากหาถนนที่สั้นที่สุด

และถ้าเส้นทางที่สั้นที่สุดมีหลายเส้น เราให้โอกาสเท่าๆ กัน

เราเลยหาโอกาสการใช้ถนน ด้วยการหารด้วยจำนวนเส้นทางที่สั้นที่สุด

เสร็จแล้วก็เอาโอกาสของจุดหมาย คูณกันโอกาสของเส้นทาง กลายเป็นโอกาสการใช้ถนน

let probs = query {
                for _, ways in destinations do
                for id, score in collectFn ways do
                groupValBy score id into g
                select (g.Key, g.Sum())
            } |> Map.ofSeq

สุดท้ายแล้วกันการหาโอกาสของการใช้ถนนแต่ละเส้น

เราเอาเส้นทางต่างๆ ของแต่ละจุดหมายไปโยนใส่ collectFn ด้านบน

แล้วจัดกลุ่มตามเลขถนน และรวมโอกาสเข้าด้วยกัน

ด้านบนใช้ feature ของ F# เรียกว่า query expression

ซึ่งทำอะไรได้มากกว่า linq มาก



สุดท้าย คืนค่า

let ans = roads |> Seq.map (fun road -> probs.TryFind(road.id))
                |> Seq.map (fun prob -> if prob.IsNone then 0.0 else prob.Value)
                |> Seq.map (fun prob -> sprintf "%.7f" prob)
String.Join(" ", ans)

โดยการ loop ทุกๆ ถนน แล้วไปหาใน probs ด้านบน

หากไม่เจอก็เป็น 0



จบ