Bloggang.com : chaowman

สมมติมีจุดหลายๆ จุดอยู่บนพื้นที่

เราต้องวางสี่เหลี่ยมจตุรัสจำนวน k อัน

เพื่อครอบคลุมจุดทั้งหมด โดยต้องวางขนานกับแกน x y

คำถามคือ ต้องใช้สี่เหลี่ยมขนาดเล็กที่สุดขนาดเท่าไหร่ถึงจะครอบคลุมจุดทั้งหมด

อ่านเพิ่มเติม ที่นี่

เนื่องจากโจทย์กำหนดว่า ขนาดของพื้นที่ที่ใหญ่ที่สุดคือ 64,000

ดังนั้น วิธีการแก้ปัญหาคือ Binary Search

เราแค่ต้องหาว่า สี่เหลี่ยมขนาด x จำนวน k อัน จะครอบคลุมจุดทั้งหมดได้หรือไม่

เริ่มจาก ประกาศ function

let solve sets sqrs =

sets คือจุดต่างๆ

sqrs คือจำนวนสี่เหลี่ยมจตุรัส

ถัดมาคือ function เพื่อหาว่าสี่เหลี่ยมจตุรัสจะสามารถครอบคลุมจุดทั้งหมดได้หรือไม่

let matchSqr size =
    let rec matchSqrX sets sqrs =
        if Set.count sets <= sqrs then
            Seq.singleton size
        elif sqrs = 0 then
            Seq.empty

function ชื่อ matchSqr

size คือขนาดของสี่เหลี่ยมจตุรัส

เราสร้างอีก function (matchSqrX) เพื่อทำ recursive

ถ้า จำนวนจุดที่เหลือ (sets) <= จำนวนสี่เหลี่ยม (sqrs)

หมายความว่าเราสามารถใช้สี่เหลี่ยมหนึ่งอัน ต่อหนึ่งจุด และได้คำตอบทันที

แต่ถ้า จำนวนสี่เหลี่ยม (sqrs) เหลือ 0 แปลว่าไม่มีคำตอบ

function ยังไม่จบ มีต่อ


        else 
            let x,y = Set.minElement sets
            let ys1 = sets |> Seq.filter (fun (x2,y2) -> x2 > x && x2 <= x+size &&
                                                         y2 >= y-size && y2 <= y)
                           |> Seq.map snd
                           |> Set.ofSeq
            let ys2 = sets |> Seq.filter (fun (x2,y2) -> x2 > x && x2 <= x+size &&
                                                         y2 >= y && y2 <= y+size)
                           |> Seq.map snd
                           |> Seq.map (fun y2 -> y2 - size)
                           |> Set.ofSeq
            let ys = ys1 + ys2 + Set.singleton y
            seq {
               for y in ys do
               let coveredSet = sets |> Seq.filter (fun (x2,y2) -> x2 >= x && x2 <= x+size &&
                                                                   y2 >= y && y2 <= y+size)
                                     |> Set.ofSeq
               for i in matchSqrX (sets-coveredSet) (sqrs-1) do
               yield i
            }
    matchSqrX sets sqrs

ตอนแรก เราดีงเฉพาะจุดที่น้อยที่สุด (x,y) ออกมาจาก sets

เนื่องจาก x น้อยที่สุด เราแน่ใจได้เลยว่ามันจะเป็นจุดที่อยู่ซ้ายที่สุด

เราสามารถวางสี่เหลี่ยมชนจุดทางด้านซ้ายได้เลย

ต่อมาเราก็เลื่อนสี่เหลี่ยมไปบนสุด คือด้านล่างของสี่เหลี่ยมชนจุด y

แล้วเราก็ list จุด y ต่างๆ ที่เจอออกมา (ys1)

เช่นเดียวกัน ทีนี้ลองเลื่อนสี่เหลี่ยมไปล่างสุด ด้านบนของสี่เหลี่ยมชนจุด y

แล้วเราก็ list จุด y ต่างๆ ออกมา (ys2)

ys ก็คือจุด y ทั้งหมดที่สี่เหลี่ยมจะเลื่อนขึ้นและลงได้

ทีนี้ก็ loop เลยครับ ลองทุกวิธี

coveredSet คือ จุดที่โดนครอบโดยสี่เหลี่ยม

แล้วเราก็ recursive เพื่อลองต่อไป

สุดท้าย ก็หาขนาดที่เล็กที่สุดด้วย binary search

let rec binarySearch min max =
    if min = max then
        max
    else 
        let mid = (min + max) / 2
        let result = matchSqr mid
        if Seq.isEmpty result then
            binarySearch (mid+1) max
        else
            binarySearch min mid
binarySearch 1 64000 |> string

จบ

สมมติมีลูกแก้วอยู่ในถุง

มีลูกแก้วสีขาวอยู่ W ลูก และสีดำ B ลูก

และเราสุ่มหยิบลูกแก้ว ถ้าได้สีเหมือนกัน เราจะใส่สีขาวเพิ่มลงไป

แต่ถ้าสีต่างกัน เราจะใส่สีดำเพิ่มเข้าไป

คำถามคือ ลูกแก้วลูกสุดท้ายในถุงจะเป็นสีอะไร

อ่านเพิ่ม ที่นี่

คำถามข้อนี้ง่ายมาก อยากให้คุณคิดให้ดีก่อนอ่านต่อไป

เมื่อเราหยิบลูกแก้ว จะมีผลลัพธ์อยู่ 3 แบบ

1. ได้สีขาวและสีดำ แบบนี้เราจะได้สีดำคืนมา ดังนั้น เท่ากับหักสีขาวไป 1 ลูก

2. ได้สีขาว 2 ลูก แบบนี้เราจะได้สีขาวคืนมา 1 ลูก เท่ากับหักสีขาวไป 1 ลูก

3. ได้สีดำ 2 ลูก แบบนี้เราก็ได้สีขาวคืนมา 1 ลูก เท่ากับเพิ่มสีขาว 1 ลูก แต่หักสีดำไป 2 ลูก

ดังนั้น หากเหลือสีดำลูกเดียว เราจะไม่มีวิธีกำจัดสีดำออกไปได้เลย

และในขณะเดียวกันถ้าสีดำเป็นเลขคู่ สุดท้ายสีดำจะถูกกำจัดออกไปเสมอ

ดังนั้น แค่เราดูจำนวนของสีดำ ก็ได้คำตอบแล้วครับ

let solve white black =
    if (black &&& 1) = 0
    then "WHITE"
    else "BLACK"

จบ

สมมติว่าคุณกำลังเล่นหมากกระดานอยู่

หมากกระดานนี้ไม่ใช่ตาราง 4 เหลี่ยม แต่เป็น 6 เหลี่ยม

คุณมีเบี้ยอยู่จำนวนเท่าขนาดของตาราง เบี้ยแต่ละตัววางมั่วๆ บนกระดาน

เบี้ยสามารถเดินได้เฉพาะช่องที่ติดกัน

และเมื่อไหร่ที่เบี้ยเรียงกันทุกตัวคุณชนะ

ยังไม่จบ เบี้ยแต่ละตัวมีแต้มไม่เท่ากัน

หากเดินเบี้ย 1 ครั้ง คุณจะต้องเสียแต้มตามที่กำหนดบนเบี้ย

คำถามคือ คุณจะสามารถชนะได้โดยเสียแต้มน้อยที่สุดกี่คะแนน

อ่านเพิ่มเติม ที่นี่

ข้อนี้เป็นโจทย์ประเภทกำหนดงาน

คือ ต้องหาว่าเบี้ยตัวไหนจะเดินไปที่ตำแหน่งไหน

หากไม่รู้จัก algorithm เราคงใช้วิธีการ brute force O(n!)

ทีนี้ มันมี algorithm ตัวนึง ที่เพิ่มประสิทธิภาพในการจัดสรรงาน เป็น O(n³)

algorithm ตัวนี้คือ Hungarian Algorithm

เรียนรู้จัก algorithm ตัวนี้ไว้ก็ไม่เสียหาย

เราสามารถเอา algorithm นี้ ไปแก้ปัญหาการจัดสรรทรัพยากรในธุรกิจได้

ทีนี้ตัว code ก็ไม่ต้องเขียนเอง ไป download ที่นี่

มาเริ่มกันเลย เรามาสร้างตารางกันก่อน

วิธีคิดตารางก็ต้องใช้จินตนาการนิดนึง เพราะตารางไม่ใช่สี่เหลี่ยม

สำหรับผม ผมให้ตารางมันเว้นช่องว่าง

|..|..|01|..|02|..|03|..|..|
|..|04|..|05|..|06|..|07|..|
|08|..|09|..|10|..|11|..|12|
|..|13|..|14|..|15|..|16|..|
|..|..|17|..|18|..|19|..|..|

เราไม่ต้องสร้างตารางจริงๆ

เราแค่รู้ว่าเลขต่างๆ อยู่ตำแหน่งไหนก็พอ

เช่น เลข 1 อยู่ตำแหน่งที่ (0,2)

let getBoard =
    let getBoardX size =
        seq {
            let mid = (size + 1) / 2
            let width = (size * 2) - 1
            for row = 1 to size do
            let rowPadding = abs (mid - row)
            for col in { 1+rowPadding .. 2 .. width-rowPadding } do
            yield col,row
        } |> Seq.append [0,0]
          |> Seq.toArray
 
    memoize getBoardX

คำสั่ง getBoard มีไว้หาตำแหน่งของเลขต่างๆ

ทีนี้ การวัดระยะห่างของช่องก็คำนวนง่ายนิดเดียว

let (<->) (x1,y1) (x2,y2) =
    let deltaY = abs (y1 - y2)
    let deltaX = abs (x1 - x2) - deltaY |> max 0
    deltaY + (deltaX / 2)

ถ้ามีการเลื่อนในแนวตั้ง เราสามารถเอามาลบแนวนอนได้ เพราะเวลาเลื่อนในแนวตั้ง เราเลื่อนแนวทแยง

และเวลาเลื่อนแนวนอน เวลาหาระยะห่างเราเอามาหาร 2 เพราะตารางมีการเว้นช่องว่างระหว่างเลข

ถัดมาคือหาตำแหน่งจบ

let finishPos =
    let finishPosX size =
        let board = getBoard size
        let mid = (size + 1) / 2
        let finish1 =
            let col,row = board.[1]
            [|  for i = 0 to size-1 do
                yield col+i,row+i |]
        let finish2 =
            let col,row = board.[mid]
            [|  for i = 0 to size-1 do
                yield col-i,row+i |]
        let finish3 =
            [|  for i = 0 to size-1 do
                yield 1 + (i*2),mid |]
        [| finish1; finish2; finish3 |]
    memoize finishPosX

ตำแหน่งจบมี 3 แบบเสมอ คือ

จบแบบแนวนอน

|..|..|01|..|02|..|03|..|..|
|..|04|..|05|..|06|..|07|..|
|08|..|09|..|10|..|11|..|12|
|..|13|..|14|..|15|..|16|..|
|..|..|17|..|18|..|19|..|..|

และแนวทแยง ซ้ายขวา

|..|..|01|..|02|..|03|..|..|
|..|04|..|05|..|06|..|07|..|
|08|..|09|..|10|..|11|..|12|
|..|13|..|14|..|15|..|16|..|
|..|..|17|..|18|..|19|..|..|

|..|..|01|..|02|..|03|..|..|
|..|04|..|05|..|06|..|07|..|
|08|..|09|..|10|..|11|..|12|
|..|13|..|14|..|15|..|16|..|
|..|..|17|..|18|..|19|..|..|

เริ่มเลย

let solve nums costs =

nums คือ ตำแหน่งเริ่มต้นของเบี้ยแต่ละตัว

costs คือ คะแนนของเบี้ยแต่ละตัว

let size = Array.length nums
let board = getBoard size
let start = nums |> Seq.map (Array.get board)
                 |> Seq.zip costs
                 |> Seq.cache
let finish = finishPos size

size คือขนาดของ board

start คือ คะแนน และ ตำแหน่งเริ่มต้นของเบี้ยแต่ละตัว ซึ่งตำแหน่งเปลี่ยนเป็น (x, y) แทนตัวเลข

finish คือ ตำแหน่งสิ้นสุดของเบี้ย ซึ่งมี 3 แบบ

let minCost finPos =
    let matrix = 
        array2D [|
            for cost, pos in start do
            yield Array.map (fun pos2 -> (pos <-> pos2) * cost) finPos
        |]
    let sol = HungarianAlgorithm.FindAssignments (Array2D.copy matrix)
    sol |> Seq.mapi (Array2D.get matrix)
        |> Seq.sum
 
finish |> Seq.map minCost
       |> Seq.min
       |> string

ทีนี้เวลาหาผลลัพธ์ ก็เอา finish แต่ละแบบมาดูว่าแบบไหนใช้คะแนนน้อยที่สุด

ใน minCost เรามีการสร้าง matrix โดยการใช้ความสามารถของ f# ที่เรียกว่า array comprehension

โดย matrix จะเก็บคะแนนที่ใช้ของเบี้ยแต่ละตัว และตำแหน่งสิ้นสุดแต่ละตำแหน่ง

หลังจากนั้นก็โยนใส่ hangarian algorithm ให้มันหาคะแนนที่น้อยที่สุดออกมา

จบ

ข้อถัดมา 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

จบ

ข้อถัดมา Price is wrong

จริงๆ ข้อนี้ไม่เกี่ยวอะไรกับราคา

เค้าจะให้ตัวเลขเรามาชุดนึง ซึ่งเป็นราคาสินค้า

แล้วให้ตอบว่าต้องแก้ตัวเลขอย่างน้อยกี่ตัวจึงทำให้ตัวเลขเรียงกัน

แต่แทนที่จะตอบตัวเลข เราต้องตอบชื่อสินค้าที่ราคาผิด

อ่านเพิ่มเติม ที่นี่

ข้อนี้ก็ยังเป็น Dynamic Programming

จุดสนุกของ Dynamic Programming คือ การวิเคราะห์หา subproblem

ซึ่งบางครั้ง ต้องอาศัยการคิดนอกกรอบแบบสุดๆ

วิธีคิดของข้อนี้คือ

ให้สมมติว่ามี ตัวเลขพิเศษมาประกบหัวท้าย เช่น

20 15 40 30 60

ให้เพิ่มตัวเลขน้อยสุด กับมากสุดเข้าไป เช่น เลข 0 และ 101 เป็น

0 20 15 40 30 60 101

แล้วลองหยิบตัวเลขมาตัวนึง เช่น 40

ทีนี้เราก็ได้ subproblem คือ เรียง 0 20 15 40 กับเรียง 40 30 60 100

ดังนั้น เราจะได้สูตรว่า

minGuess (min, max) = min { minGuess(min, i) + minGuess(i, max) }

แค่นี้เองครับ ง่ายบ่

ทีนี้ ตัวเลขที่เราจะเอามาเป็น node สำหรับแยก subproblem ต้องมีค่าระหว่าง min กับ max

เรามาสร้าง operator สำหรับทำ between กัน

let inline (<.) a b =
    a, b
let inline (.<) (a, b) c =
    a < b && b < c

มี 2 operators เหตุเพราะว่า f# ไม่รองรับการทำ ternary operator

ทีนี้วิธีใช้ operator นี้คือ a <. b .< c

ดูแล้วเข้าใจง่ายฝุดๆ

มาเริ่มกันเลยครับ

let solve names prices =
    let prices = Array.concat [[|0|]; prices; [|101|]]
    let priceOf = Array.get prices
    let nameOf n = Array.get names (n-1)

names คือ array ของชื่อสินค้า

prices คือ ราคาของสินค้า และทีนี้เรามีการประกบ 0 กับ 101 เข้าไปหัวท้าย

priceOf กับ nameOf คือการดึงราคาและชื่อ โดยใส่ index เข้าไป

let rec minGuess =
    let minGuessX (min, max) =
        let inside = { min+1..max-1 } |> Seq.filter (fun i -> priceOf min <. priceOf i .< priceOf max)
        if Seq.isEmpty inside then
            let newSet = { min+1..max-1 } |> Seq.map nameOf
                                          |> Set.ofSeq
            newSet.Count, newSet
        else
            seq {
                for i in inside do
                let leftCount,leftSet = minGuess (min, i)
                let rightCount,rightSet = minGuess (i, max)
                yield leftCount+rightCount, leftSet+rightSet
            } |> Seq.min
    memoize minGuessX

บรรทัด let inside คือ ดึงเฉพาะตัวเลขที่ราคาอยู่ระหว่าง min กับ max

ถ้าไม่เจอ inside หมายความว่าต้องปรับราคาทุกตัว

แต่ถ้าเจอ ก็ใช้ inside เป็น node แล้วหา minGuess ทั้งด้านซ้ายและด้านขวา

แล้ว return ผลเฉพาะค่า minimum

สุดท้ายก็ return ผล

let _,set = minGuess (0, prices.Length - 1)
String.Join(" ", set)

จบ