คราวนี้สมมติว่าเราเป็นผู้จัดการร้านนมปั่น
ซึ่งร้านเราจะขายหลายรสชาติ และแต่ละรสก็แบ่งเป็น malt กับ unmalt
และเราก็มีลูกค้าหลายคน แต่ละคนก็ชอบไม่เหมือนกัน
บางทีก็ชอบหลายรส แต่ลูกค้าจะชอบแบบ malt แค่รสเดียวเท่านั้น
โจทย์สั่งให้เราจัดเตรียมวัตถุดิบ โดยที่ให้มี malt น้อยที่สุด
โจทย์ประเภท
constraint satisfaction problem เนี่ย ไม่มีอะไรเหมาะเท่า F# อีกแล้วครับ
เวลาคิดก็เหมือนเล่น Sudoku เลือกตัวเลือกที่มีตัวเลือกน้อยที่สุดก่อน
แล้วเมื่อเลือกแล้ว ก็ตัด choice ออกไปเรื่อยๆ
ก่อนเริ่มเรามาสร้าง module กันเล่นๆ ก่อน
module Map =
let count (map:Map<_,_>) = map.Count
เดิมที f# มี module ชื่อ
Map อยู่แล้ว
ใน f# เราสามารถ เพิ่ม function เข้าไปใน module ที่มีอยู่แล้วได้
ในที่นี้ คือการเพิ่ม function count
เริ่มเลย
let solve n custs =
n คือ จำนวนรสชาติ
cust เป็น รายการ (seq) ของ map ที่บอกว่าลูกค้าแต่ละคนชอบรสอะไรบ้าง และมีค่าเป็น malt หรือ unmalt
ถัดมาคือ function หลัก
let rec logic map custs =
let custs = custs |> Seq.sortBy Map.count
|> Seq.toList
match custs with
| [] -> Seq.singleton map
| head::tail ->
seq {
let prefs = head |> Map.toSeq
|> Seq.sortBy snd
for a, b in prefs do
let newMap = Map.add a b map
let notMatch choices =
let item = Map.tryFind a choices
item.IsNone || item.Value <> b
let newCusts = tail |> Seq.where notMatch
|> Seq.map (Map.remove a)
yield! logic newMap newCusts
}
map คือ map ของรสชาติต่างๆ ที่เราจะขาย และมีค่าเป็น malt หรือ unmalt
ตอนแรกเราก็เรียง custs ก่อน ใครมี choice น้อยสุดก็เลือกก่อน
ถ้า custs หมดแล้ว ([]) ก็คือจบ เราได้คำตอบแล้ว
แต่ถ้า custs ยังไม่หมด (head::tail)
prefs คือ ตัวเลือกของลูกค้า โดยที่เราจะเรียงเอาแบบ unmalt ก่อน
แล้วทีนี้ก็ลองตัวเลือกของลูกค้าทีละอัน
newMap คือ รสชาติที่เราจะขาย โดยเพิ่มตัวเลือกของลูกค้าเข้าไป
newCusts คือ ลูกค้าที่ยังไป satisfy และเราก็ตัดตัวเลือกรสเดียวกันออกไป (เช่น ลูกค้าชอบ unmalt แต่เราจะขาย malt)
แล้วก็วนไปเรื่อยๆ
เสร็จแล้วก็คืนค่า
let result = custs |> logic Map.empty
|> Seq.truncate 1
|> Seq.toList
match result with
| [] -> "IMPOSSIBLE"
| head::_ -> let createFn i =
match Map.tryFind (i+1) head with
| None -> "0"
| Some(j) -> string (j - 1)
let strs = Seq.init n createFn
String.Join(" ", strs)
โดย result เราจะเอาแค่คำตอบแรกเท่านั้น
จบ