Just algorithm!

Square Fields



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

เราต้องวางสี่เหลี่ยมจตุรัสจำนวน 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-1do
               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

จบ






 

Create Date : 06 กรกฎาคม 2557    
Last Update : 6 กรกฎาคม 2557 22:37:33 น.
Counter : 124 Pageviews.  

Old Magician



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

มีลูกแก้วสีขาวอยู่ 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"

จบ




 

Create Date : 06 กรกฎาคม 2557    
Last Update : 6 กรกฎาคม 2557 12:58:11 น.
Counter : 458 Pageviews.  

Hexagon Game




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

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

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


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

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

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


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

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

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







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

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

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

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

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 ให้มันหาคะแนนที่น้อยที่สุดออกมา



จบ





 

Create Date : 29 มิถุนายน 2557    
Last Update : 29 มิถุนายน 2557 9:37:00 น.
Counter : 498 Pageviews.  

Random Route



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



จบ




 

Create Date : 07 มิถุนายน 2557    
Last Update : 7 มิถุนายน 2557 9:20:06 น.
Counter : 497 Pageviews.  

Price is Wrong



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

จบ




 

Create Date : 04 มิถุนายน 2557    
Last Update : 4 มิถุนายน 2557 20:45:31 น.
Counter : 541 Pageviews.  

1  2  3  4  

chaowman
Location :
กรุงเทพฯ Thailand

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 8 คน [?]









New Comments
Group Blog
 
All Blogs
 
Friends' blogs
[Add chaowman's blog to your web]
Links
 

 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.