ข้อถัดมา
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
จบ
ขอให้มีความสุขนะคะ ขอบคุณค่ะที่เอา code มาแบ่งปัน