คราวนี้สมมติว่าเราเป็นผู้จัดการร้านนมปั่น

ซึ่งร้านเราจะขายหลายรสชาติ และแต่ละรสก็แบ่งเป็น 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 เราจะเอาแค่คำตอบแรกเท่านั้น



จบ