Bloggang.com : chaowman

ข้อต่อมา TriangleTrilema

ข้อนี้จะให้จุดมา 3 จุด แล้วให้เราบอกว่านี่เป็นสามเหลี่ยมประเภทไหน

โดยต้องบอกว่าเป็นสามเหลี่ยมด้านเท่า (Equilateral) สามเหลี่ยมหน้าจั่ว (Isosceles) หรือสามเหลี่ยมด้านไม่เท่า (Scalene)

และต้องบอกอีกว่า เป็นสามเหลี่ยมมุมป้าน (Obtuse) มุมฉาก (Right) หรือมุมแหลม (Acute)

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

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

เริ่มจากการหา ประเภทด้านของสามเหลี่ยม อันนี้เราอาจจะแค่วัดความยาวของแต่ละด้าน

แต่ตรงนี้มีกับดักนิดนึง ถ้าวัดความยาวตัวเลขอาจเป็น float เวลาเปรียบเทียบค่าอาจจะคลาดเคลื่อน

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

สูตรการหาพื้นที่คือ

let area (x1, y1) (x2, y2) =
    let deltaX = x1 - x2
    let deltaY = y1 - y2
    (deltaX * deltaX) + (deltaY * deltaY)

ถัดมา มาหาประเภทด้านของสามเหลี่ยม

let typeSide areas =
    let count = areas |> Seq.distinct
                      |> Seq.length
    match count with
    | 1 -> "equilateral"
    | 2 -> "isosceles"
    | 3 -> "scalene"

เราก็วัดขนาดพื้นที่ ถ้าเท่ากันหมด ก็ equilateral

ถ้าเท่ากัน 2 ด้านก็ isosceles

ถ้าไม่เท่ากันเลยก็ scalene

คราวนี้เรามาวัดมุม

let typeAngle areas =
    let sorted = Array.sort areas
    match compare (sorted.[0] + sorted.[1]) sorted.[2] with
    | -1 -> "obtuse"
    | 0  -> "right"
    | 1  -> "acute"

ถ้าเป็นมุมฉากก็ง่ายมาก เรารู้ว่าพื้นที่ด้าน A + B = C เสมอ (right)

จริงๆ คิดต่อก็ไม่ยาก ถ้า A + B > C แปลว่า C มีพื้นที่แคบ จึงเป็นสามเหลี่ยมมุมแหลม (acute)

ถ้า A + B < C แปลว่า C มีพื้นที่กว้าง จึงเป็นสามเหลี่ยมมุมป้าน (obtuse)

ถัดมา เรามาหาว่าถ้าสามเหลี่ยมอยู่ระนาบเดียวกันหมด ก็ไม่ใช่สามเหลี่ยม

let (|Collinear|Triangle|) ((x1, y1), (x2, y2), (x3, y3)) =
    if (x1 - x2) * (y1 - y3) = (x1 - x3) * (y1 - y2) 
    then Collinear
    else Triangle

ด้านบนเป็น feature ของ f# ชื่อว่า Active Patterns

วิธีการหาก็ใช้สูตรหาความชัน ถ้าความชันเท่ากันก็ถือว่าเป็นระนาบเดียวกัน

ที่จริงสูตรหาความชันต้องเป็นหาร (x1 - x2) / (x1 - x3) = (y1 - y2) / (y1 - y3)

แต่เพียงแค่เอามาคูณสลับ เพื่อไม่อยากให้ type เป็น float

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

let solve p1 p2 p3 =
    match p1, p2, p3 with
    | Collinear -> "not a triangle"
    | Triangle  -> let areas = [| area p1 p2; area p2 p3; area p3 p1 |]
                   sprintf "%s %s triangle" (typeSide areas) (typeAngle areas)

โดย p1 = (x1, y1), p2 = (x2, y2), p3 = (x3, y3)

เข้าสูตรต่างๆ ด้านบนก็ได้ผลลัพธ์ออกมา

จบ

ข้อถัดมา Shopping Plan

ข้อนี้เค้าจะให้ตำแหน่งร้านต่างๆ มา

ซึ่งแต่ละร้านจะขายของราคาต่างๆ กัน

การไปร้านต่างๆ ก็ต้องจ่ายค่าเดินทาง

และของบางอย่างเป็นของสดมาก

ซื้อเสร็จต้องรีบเอากลับบ้าน ห้ามแวะที่อื่น

โจทย์ให้หาราคาที่ถูกที่สุดที่สามารถซื้อของทุกอย่างได้

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

*** คำเตือน: บทนี้อาจจะเข้าใจยากหน่อย แต่ถ้าลองทำไปด้วย น่าจะเข้าใจมากขึ้น ***

ข้อนี้ก็ยังเป็นแบบ Dynamic Programming สูตรคือ

findMinCost(ของที่ยังไม่รู้ราคา, สถานที่) = min { ค่าของ + ค่าเดินทาง + findMinCost(ของที่ยังไม่รู้ราคา - ของที่ซื้อไป, ร้านที่ซื้อ) }

วิธีคิด ให้คิดถอยหลัง

เริ่มจากเราอยู่ที่บ้าน และมีของครบทุกอย่าง (แต่ไม่รู้ราคาสักชิ้น)

ทีนี้ตัวเลือกเราจะมีเพียบ คือ ก่อนเราอยู่บ้าน เราไปร้านไหนมาก็ไม่รู้ และซื้อของอะไรมาก็ไม่รู้

สมมติ ร้านมี Top, BigC, Lotus และของมี Lay, Pocky, Pepsi

เนื่องจากเราไม่รู้อะไรเลย เราจึงต้องลองทุกๆ แบบ เช่น เราอาจจะมาจาก Top และซื้อ Lay

พอเราย้อนไปที่ Top เราก็จะรู้ราคาของ Lay รู้ค่าเดินทาง และจาก Top เราก็ findMinCost อีกครั้ง

โดยคราวนี้ของที่ยังไม่รู้ราคามีแค่ Pocky และ Pepsi พอเรา findMinCost ย้อนไปเรื่อยๆ จนรู้ราคาของจนหมด

เราก็กลับมาลองแบบอื่น เช่น ไป BigC และซื้อ Lay แทน

พอเราย้อนไปย้อนมาจนครบทุกรูปแบบ เราก็จะรู้ว่าแบบไหนถูกที่สุด

เริ่มแรกมารู้จัก class ของร้านขายของก่อน

type Store = { id:int; position:float*float; items:Map<int,float>; costToHome:float }
let homeStore = { id=0; position=0.0,0.0; items=Map.empty; costToHome=0.0 }

แบบนี้ f# เค้าเรียกว่า record

บรรทัดถัดมา homeStore คือบ้านเราเอง

id คือ id ของร้าน เลข 0 คือบ้านเรา ร้านต่างๆ จะเริ่มที่ 1,2,3,... ไปเรื่อยๆ

position คือ ตำแหน่ง บ้านเราจะเป็นตำแหน่ง 0,0

items คือ ของต่างๆ ที่ขาย เป็น map (คล้ายๆ dictionary) บ้านเราจะไม่มีของขาย (Map.empty)

key ของ map คือ itemId ซึ่งเป็น flag ซึ่ง itemId จะเริ่มที่ 1,2,4,8,... ไปเรื่อยๆ ทีละ 2 เท่า

ส่วน value ของ map คือ ราคาของ

สุดท้าย costToHome ค่าเดินทางกลับมาบ้าน

ถัดมามารู้จัก function หาระยะทาง

let (<->) (x1, y1) (x2, y2) =
    let deltaX = x1 - x2
    let deltaY = y1 - y2
    sqrt (deltaX*deltaX + deltaY*deltaY)

การประกาศแบบนี้เรียกว่า operator overload

วิธีใช้ เช่น store1.position <-> store2.position

ซึ่งบางครั้งการใช้ operator อ่านง่ายกว่า การใช้ function

วิธีการหาตำแหน่ง ก็ใช้ ทฤษฎีบทพีทาโกรัส

เรามาเริ่มคำนวนกันเลย!

let solve gas allItems freshMask stores =

gas คือ ค่า gas

allItems เป็น sequence เก็บ itemId ของสินค้าทุกตัว เช่น [1;2;4;8;16;32;...] (อย่าลืมว่า itemId เป็น flag ต้องเพิ่มทีละ 2 เท่า)

freshMask คือ mask ของสินค้าที่เป็นของสด เช่น itemId 2,4,16 เป็นของสด freshMask จะได้ 22 (ง่ายๆ ก็เอา id มาบวกกัน)

ส่วน stores เป็น array ที่เก็บ type Store ที่ประกาศไว้ด้านบน โดย array ที่ 0 คือบ้านเราเอง array ที่ 1 คือ ร้าน id=1 ไปเรื่อยๆ

วิธีการ build input ผมว่าไม่ยากมาก ลองหัดทำเองแล้วส่งค่าเข้ามานะครับ

ก่อนจะเริ่มทำ อาจต้องคำนวน search space ก่อน

ร้านมีได้ 50 ร้าน และของมีได้ 15 ชนิด

หมายความว่า ต่อ 1 รอบ เราต้องหาค่า min ของ 750 ทางเลือก (50 x 15)

แล้วจำนวนครั้งที่เรา call findMinCost คือ จำนวนรูปแบบของ ของที่ยังไม่รู้ราคา และจำนวนร้าน

ของที่ยังไม่รู้ราคามี 2 สถานะ รู้แล้ว และยังไม่รู้ ของมี 15 ชนิด ดังนั้นมี input 32,768 แบบ (2¹⁵)

สถานที่มี 50 แห่ง รวมบ้านของเราเป็นจุดเริ่มต้นอีก เป็น 51 แห่ง

เอาตัวเลขทุกตัวมาคูณกันได้กว่า 1 พันล้านแบบ (750 x 32,768 x 51)

นี่ยังไม่รวมที่ต้องจัดการกับของสดอีก

วิธีการลดจำนวนการคำนวนที่ดีคือ การลดตัวเลือก

1. เนื่องจากบางร้านขายของราคาแพงมาก เราสามารถตัดของชิ้นนั้นออกจากตัวเลือกได้เลย

2. ถ้าเราอยู่ร้าน A ซึ่งขายของชิ้นนึง 20 บาท เราสามารถตัดตัวเลือกที่จะซื้อของชิ้นเดียวกัน แต่แพงกว่า 20 บาทได้เลย

3. ถ้าอยู่บ้าน แปลว่าจะต้องซื้อของสดแล้วกลับเข้ามาเสมอ

4. ถ้าอยู่ร้าน แล้วไม่ได้กลับบ้านแปลว่าซื้อของแห้งเสมอ

เริ่มข้อ 1 ตัดของราคาแพงออกไป

let storeMap =
    let storeMapX itemId =
        let itemPrices =
            seq {
                for store in stores do
                let item = store.items.TryFind(itemId)
                if item.IsSome then
                yield store,item.Value
            } |> Seq.cache

storeMap มี input คือ itemId เพื่อต้องการหาว่า itemId นี้ มีร้านไหนขายบ้าง (และต้องขายไม่แพง)

itemPrices ก็แค่ loop ทุกร้าน เพื่อหาว่าร้านไหนขาย itemId นี้บ้าง และราคาเท่าไหร่

function ไม่จบ มีต่อ


        let filterFn (store1,price1) =
            let forallFn =
                if itemId &&& freshMask > 0 then
                    fun (store2,price2) -> price1 <= price2 + (store1.position <-> store2.position)*gas 
                                                            + store2.costToHome 
                                                            + store1.costToHome
                else
                    fun (store2,price2) -> price1 <= price2 + (store1.position <-> store2.position)*gas*2.0
            itemPrices |> Seq.forall forallFn

สมมติอยู่ร้านแรก เพื่อเปรียบเทียบราคา เราต้องเดินทางไปร้าน 2 เพื่อซื้อของ และกลับมาร้านแรกใหม่

ถ้าค่าใช้จ่ายทั้งหมด ยังถูกกว่าการซื้อของที่ร้านแรก

แปลว่าของร้านแรกแพงมากถึงขนาดเดินไปซื้อที่ร้าน 2 แล้วยังคุ้มกว่า เราสามารถตัดของชิ้นนั้นออกจากร้านแรกได้เลย

function ไม่จบ มาต่อส่วนสุดท้าย

        itemPrices |> Seq.filter filterFn
                   |> Seq.map (fun (store,price) -> store.id,(store,price))
                   |> Map.ofSeq
    memoize storeMapX

เมื่อเอา itemPrices ผ่าน filterFn จะเหลือแค่ของที่ไม่แพงมากเท่านั้น

บรรทัดสุดท้ายมีการเรียก memoize (ดูวิธีการประกาศบทที่แล้ว) เพื่อเมื่อเรียกซ้ำจะได้ไม่ต้องคำนวนใหม่

ถัดมาข้อ 2 หาร้านที่จะซื้อของชิ้นถัดไป โดยร้านที่จะซื้อต้องขายของถูกว่าร้านที่เรายืนอยู่

let rec findStores =
    let findStoresX (storeId, itemId) =
        seq {
            let store1 = Array.get stores storeId
            let map = storeMap itemId
            let item1 = Map.tryFind storeId map
            for kvp in map do
            let store2,price2 = kvp.Value
            if storeId = store2.id || item1.IsNone || snd item1.Value > price2 then
            let travel = (store1.position <-> store2.position)*gas
            yield store2.id, itemId, price2 + travel
        } |> Seq.cache
    let cached = memoize findStoresX
    fun storeId itemId -> cached (storeId, itemId)

findStores มี input 2 ตัว คือ storeId และ itemId

storeId คือ ปัจจุบันเราอยู่ที่ร้านไหน

itemId คือ ปัจจุบันเราอยากรู้ราคาของของชิ้นไหน

เป้าหมายของ findStores คือ บอกว่าเราควรไปซื้อ itemId นี้ที่ร้านไหนบ้าง

ใน code จะมี for in อยู่ คือเราก็ไปทุกๆ ร้าน (ที่ขายของไม่แพงมากจาก function storeMap ด้านบน)

และก็มีการเช็คนิดหน่อยว่า ถ้าร้านที่เรายืนอยู่ขายของชิ้นเดียวกันถูกกว่า เราจะไม่ไปร้านอื่น

แล้วก็คืนค่า storeId ร้านใหม่ (store2.id), itemId, และราคาของบวกค่าเดินทาง

function นี้ก็มีการเรียก memoize เพราะ function นี้มีการเรียก input เดิมๆ ซ้ำหลายครั้ง

ถัดมาข้อ 3 และข้อ 4 เรามีการแยกของแห้งและของสด

ถ้าอยู่บ้าน เราก็เลือกที่จะซื้อของสด และกลับบ้าน

ถ้าอยู่ร้าน ยังไงก็ต้องซื้อของแห้ง

let isFresh itemId = itemId &&& freshMask > 0
let dryItems = allItems |> Seq.filter (not << isFresh)
                        |> Seq.cache
let freshItems = allItems |> Seq.filter isFresh
                          |> Seq.cache

ไม่มีอะไรมาก dryItems คือ รายการของแห้ง freshItems คือ รายการของสด

และ function สุดท้าย ยาวนิดนึงแต่เป็น logic ทั้งหมดของ program

let rec findMinCost =
    let findMinCostX (mask, id, home) =
        let filterFn itemId = mask &&& itemId > 0
        let validFreshItems = Seq.filter filterFn freshItems
        let validDryItems = Seq.filter filterFn dryItems
 
        let mapFn (storeId, itemId, itemCost) =
            let newHome = id = 0 || (home && id = storeId)
            itemCost + findMinCost (mask ^^^ itemId, storeId, newHome)

findMinCost เป็น logic ในการหาราคาที่ถูกที่สุด

ถ้ายังจำได้ findMinCost ผมได้ define procedure คร่าวๆ ไว้ว่า

findMinCost(ของที่ยังไม่รู้ราคา, สถานที่) = min { ค่าของ + ค่าเดินทาง + findMinCost(ของที่ยังไม่รู้ราคา - ของที่ซื้อไป, ร้านที่ซื้อ) }

ดังนั้น mask คือ ของที่ยังไม่รู้ราคา เป็น flag

id คือ storeId สถานที่ๆ เรายืนอยู่

parameter อีกตัวคือ home คือบอกว่าเราจะกลับไปบ้านหรือเปล่า (ถ้าใช่จะได้ซื้อของสดติดมือกลับไปได้)

validFreshItems กับ validDryItems ก็คือ freshItems กับ dryItems ที่เรายังไม่รู้ราคา

mapFn คือ ค่าของ + ค่าเดินทาง + ผลลัพธ์จาก findMinCost ที่เป็น subproblem เพื่อเอามาหา mininum cost

function ไม่จบ มีต่อ


        match mask, id, home with
        | 0, id, _ -> stores.[id].costToHome
        | mask, 0, _ ->
            let items = if mask &&& freshMask > 0 
                        then validFreshItems |> Seq.truncate 1
                        else validDryItems
            items |> Seq.collect (findStores id)
                  |> Seq.map mapFn
                  |> Seq.min

เริ่มทำการ match

แบบแรกคือ mask=0 ซึ่งหมายความว่า เรารู้ราคาของครบแล้ว

ซึ่งค่าใช้จ่ายมีแค่ค่าเดินทางจากบ้าน มาร้านที่เราอยู่เท่านั้น

แบบถัดมาคือ id=0 หมายความว่าเราอยู่บ้าน ถ้าเราอยู่บ้าน

และมีของสดที่ยังไม่รู้ราคา เราก็สนใจแค่ของสดเท่านั้น

ของสดต่างจากของแห้ง ตรงที่เราไม่สนใจลำดับการซื้อก่อนหลัง

เพราะยังไงซื้อเสร็จ ต้องกลับบ้านอยู่ดี

ดังนั้น validFreshItems อาจจะมีหลายชิ้น แต่เราสนใจแค่อันแรกเท่านั้น (Seq.truncate 1)


        | mask, id, home -> 
            let freshItemStores =
                seq {
                    if mask &&& freshMask > 0 then
                    let costToHome = stores.[id].costToHome
                    yield 0, 0, costToHome
                    if home then
                    for itemId in validFreshItems do
                    let result = Map.tryFind id (storeMap itemId)
                    if result.IsSome then
                    yield id, itemId, snd result.Value
                }
            validDryItems |> Seq.collect (findStores id)
                          |> Seq.append freshItemStores
                          |> Seq.map mapFn
                          |> Seq.min
    memoize findMinCostX

แบบสุดท้าย คืออยู่ที่ร้าน

ถ้ามีของสดที่ยังไม่รู้ราคา เราอาจจะต้องกลับไปเริ่มที่บ้าน

หรือซื้อของสดในร้านเดียวกัน

มิเช่นนั้น เราจะซื้อแต่ของแห้งเท่านั้น

และเราก็ทำการ memoize อีกครั้ง

วิธีการหาคือสั่งอย่างนี้ครับ

let minCost = findMinCost (Seq.sum allItems, 0, false)
sprintf "%.7f" minCost

จบ

ข้อถัดมา Egg Drop

โจทย์เกี่ยวกับการทดลองโยนไข่จากตึก เพื่อหาว่าไข่จะแตกจากชั้นที่เท่าไหร่

โดย input จะมี

จำนวนชั้นของตึก (F)

จำนวนไข่ (D)

จำนวนไข่ที่แตกได้ (B)

ข้อนี้ข้อเดียวให้หาถึง 3 คำตอบ

จำนวนชั้นของตึกที่มากที่สุด (FMax)

จำนวนไข่ที่น้อยที่สุด (DMin)

จำนวนไข่ที่แตกได้น้อยที่สุด (BMin)

ลองไปอ่านเพิ่มเติม ที่นี่

เริ่มจาก FMax

ข้อนี้สามารถ Solve ได้โดยง่ายด้วย Dynamic Programming

คือ แทนที่จะคิดว่าจะหาสูตรอะไรเพื่อคำนวนได้ FMax

เราก็แตก FMax เป็น subproblem แทน ได้มาเป็นสูตรนี้

FMax(d, b) = 1 + FMax(d-1,b) + FMax(d-1,b-1)

1 ตัวแรกคือ เมื่อโยนไข่ 1 ที เราก็รู้ว่าชั้นที่โยนแตกหรือไม่แตก

FMax(d-1,b) คือ ถ้าโยนแล้วไม่แตก เราก็ขึ้นไปชั้นบนเพื่อโยนต่อไป

d-1 คือ จำนวนไข่จะลดลง 1 และ b คือ จำนวนไข่ที่แตกยังเท่าเดิม เพราะโยนแล้วไม่แตก

FMax(d-1,b-1) คือ ถ้าโยนแล้วแตก เราจะลงชั้นล่าง เพื่อโยนต่อไป

คราวนี้จะเห็นว่าเป็น b-1 คือ จำนวนไข่ที่แตกลดลงไป 1

โดยมาก Dynamic Programming จะมาคู่กับ Memoization

เพราะเราอาจจะเรียก input แบบเดิมซ้ำแล้วซ้ำอีก

เราควรจะบันทึกคำตอบ ดีกว่าจะคำนวนใหม่อีกครั้ง

นี้เป็นคำสั่ง Memoize

let memoize f =
    let dict = Dictionary<_,_>()
    fun n ->
        match dict.TryGetValue(n) with
        | true, v -> v
        | _       -> let v = f(n)
                     dict.Add(n, v)
                     v

หลักๆ คือใช้ dict ถ้าเคยเห็น input (n) แบบนี้แล้ว ก็ return value (v) ทันที

แต่ถ้าไม่เคย ก็คำนวน (f) แล้วเอาค่ามาเก็บใน dict

คราวนี้มาต่อกับ FMax

let rec maxF = 
    let maxFx (d, b) =
        let result = 1L + maxF (d - 1, b) + maxF (d - 1, b - 1)
        if result >= 4294967296L
        then -1L
        else result
    let cache = memoize maxFx
    function
    | d, 1 -> int64 d
    | d, b when d = b -> (1L <<< b) - 1L
    | d, b -> cache (d, b)

วิธีการหา result อธิบายไปแล้วด้านบน

มีเพิ่มจากที่อธิบายไปก่อนหน้านิดนึง

โจทย์สั่งว่าถ้า result มีค่ามากกว่าเท่ากับ 2³²

ให้ return -1

และถัดมา cache คือ การสั่ง memoize เพื่อจำคำตอบ

อะไรที่เรียกจาก cache จะมีการคำนวนเพียงครั้งเดียวเท่านั้น

ถัดมา คือการคืนค่าโดยไม่ต้องผ่าน cache

ซึ่งค่าบางอย่าง เราสามารถคำนวนสดได้เลย ไม่ต้องผ่าน dynamic programming

เริ่มจาก
ถ้า b = 1 คือ ไข่แตกได้แค่ฟองเดียว

ถ้ามีไข่อยู่ 10 ฟอง แต่แตกได้แค่ฟองเดียว

เราก็โยนจากชั้นล่างขึ้นไปเรื่อยๆ จำนวนชั้นที่มากที่สุดคือ 10 ชั้น

ดังนั้น ถ้า b = 1 และ d = 10 คือตอบคือ 10

และถ้า d = b

มันจะกลายเป็น binary search ทันที

จำนวน search space มากที่สุด สำหรับการค้นหา b ครั้งคือ 2^b - 1

ซึ่งสามารถแปลงเป็น (1L <<< b) - 1L

แต่ function maxF ยังมีจุดอ่อนคือ

ถ้าจำนวนไข่ (d) มากกว่าจำนวนไข่ที่แตกได้ (b) มากๆ

เช่น จำนวนไข่มี 2 พันล้าน แต่ไข่ที่แตกได้มีแค่ 2

ทำให้เกิดการ recursion เกือบ 2 พันล้านครั้ง แน่นอนว่าจะเกิด stack overflow

และต่อให้ไม่เกิด stack overflow ก็ใช้เวลา search นานอยู่ดี

แต่เนื่องจากโจทย์บอกว่า ถ้า result เกิน 2³² ให้ return -1 เสมอ

อีกสูตรที่เราควรหาคือ หาว่า input ของ function maxF จะเป็น overflow หรือไม่

วิธีหาก็ brute force เลยครับ

let isOverflow = 
    let maxD b =
        let rec brute d =
            match maxF (d, b) with
            | -1L -> d - 1
            | _   -> brute (d + 1)
        brute (b + 1)
    let cache = memoize maxD
    function
    | d, 1 -> false
    | d, b when b > 32 -> true
    | d, b -> d > cache b

จากด้านบน คำสั่ง maxD เราก็แค่เพิ่ม d ไปเรื่อยๆ จนเจอ -1 เราก็หยุด

และก็มี function จัดการนิดหน่อยเพื่อไม่ต้องเรียกจาก cache

เช่น ถ้า b = 1 แล้ว d จะมีค่าเท่ากับ f เสมอ ตามที่อธิบายด้านบน ดังนั้นจึงไม่มีทาง overflow

และถ้า b > 32 และ d จะมีค่าน้อยที่สุดคือ เท่ากับ b

และเมื่อเข้าสูตร binary search แล้ว f จะมีค่ามากกว่า 2³² เสมอ

คราวนี้เราเริ่มหาค่า FMax ได้ด้วย function นี้ครับ

let rec solveF d b =
    if d < b                then solveF d d
    elif isOverflow (d, b)  then -1L
    else maxF (d, b)

ถ้าจำนวนไข่ (d) น้อยกว่าจำนวนไข่ที่แตกได้ (b)

เช่น มีไข่อยู่ 8 ใบ แต่สามารถแตกได้ 10 ใบ

เมื่อไข่แตกไปแล้ว 8 ใบ จำนวนไข่ก็หมดไม่สามารถแตกได้อีกต่อไป

ดังนั้น กรณีนี้ จำนวนไข่ที่แตกได้ จะไม่มีวันมากกว่าจำนวนไข่เสมอ

ถัดมา หาค่า DMin

ถ้าจำนวนชั้น (f) มีค่า 2 พันล้านชั้น

และไข่ที่แตกได้ (b) มีแค่ใบเดียว

จำนวนไข่ทั้งหมดที่ต้องมีคือ 2 พันล้านใบ

search space ขนาดนี้ binary search สามารถเอาอยู่

let solveD f b =
    let rec binarySearch low hi =
        if low = hi 
        then low
        else let mid = (low + hi) / 2
             let maxF = solveF mid b
             if maxF = -1L || maxF >= int64 f
             then binarySearch low mid
             else binarySearch (mid + 1) hi
    binarySearch 1 f

ถัดมา หาค่า BMin

อันนี้เรารู้จากด้านบนแล้วว่า ถ้า b มีค่าเกิน 32 จะ overflow

ดังนั้นค่า b จะมีค่าแค่ 1-32 เท่านั้น ใช้ brute force ไปเลยสะดวกที่สุด

let solveB f d =
    let rec brute b =
        let maxF = solveF d b
        if maxF = -1L || maxF >= int64 f 
        then b
        else brute (b + 1)
    brute 1

สุดท้าย พิมพ์คำตอบ

let solve f d b = 
    sprintf "%i %i %i" (solveF d b) (solveD f b) (solveB f d)

จบ

ข้อถัดมา Always Turn Left

คือ สมมติว่าคุณมีหุ่นยนต์ตัวนึงเพื่อสำรวจเขาวงกต

หลักการของหุ่นยนต์ตัวนี้ง่ายมาก ถ้าเจอทางแยกจะเลี้ยวซ้ายเสมอ

โจทย์ต้องการให้คุณวาดแผนที่ออกมา

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

โจทย์ข้อนี้หลักการคิดคือ

ระหว่างที่หุ่นยนต์ตัวนี้เดินไป เราก็แค่เก็บตำแหน่งและทิศทางของแต่ละจุด

แล้วก็เอามา plot เป็นแผนที่

ก่อนอื่นเรามารู้จัก type ชื่อ direction กันก่อน

[<Flags>]
type Direction =
    | None = 0
    | North = 1
    | South = 2
    | West = 4
    | East = 8

ด้านบนเป็นวิธีการเขียน enum ของ f#

แล้วก็ functions ต่างๆ ที่เกี่ยวกับทิศทาง

let turnLeft = function
    | Direction.North -> Direction.West
    | Direction.South -> Direction.East
    | Direction.West  -> Direction.South
    | Direction.East  -> Direction.North
 
let opposite = function
    | Direction.North -> Direction.South
    | Direction.South -> Direction.North
    | Direction.West  -> Direction.East 
    | Direction.East  -> Direction.West 
 
let turnRight = turnLeft >> opposite

หันซ้าย และ ย้อนกลับ ค่อนข้างตรงตัว

ส่วนหันขวาคือการเอาหันซ้ายและย้อนกลับมาผสมกัน

และ function เกี่ยวกับการเดินทาง

let move (r, c) dir = 
    match dir with
    | Direction.North -> r - 1, c
    | Direction.South -> r + 1, c
    | Direction.West  -> r, c - 1
    | Direction.East  -> r, c + 1

อันนี้เป็นคำสั่งเลื่อน 1 ตำแหน่ง r และ c คือ ตำแหน่ง (rows และ columns)

อีกคำสั่งยากหน่อยแต่ควรทำความเข้าใจ

let rec replay cmd states dir = 
    match cmd with
    | [] -> states, dir
    | 'L'::cmd -> replay cmd states (turnLeft dir)
    | 'R'::cmd -> replay cmd states (turnRight dir)
    | 'W'::cmd ->
        let newList = 
            let (point, wall)::tail = states
            let newPoint = move point dir
            let newState = newPoint, opposite dir
            if wall = Direction.None then
                newState::tail
            else
                let head = (point, wall ||| dir)
                newState::head::tail
        replay cmd newList dir

คือ คำสั่ง replay บันทึกการเดินทาง

cmd เป็น list เก็บบันทึกการเดินทาง

states เป็น list เก็บตำแหน่ง และลักษณะของห้อง

dir เป็น direction เก็บทิศทางล่าสุด

ถ้าดูจาก function ถ้า replay หมดทุกคำสั่ง [] ก็จะ return state กับ dir ออกไป

ถ้าสั่ง L หรือ R ก็แค่หันซ้ายและขวา แล้วทำคำสั่งถัดไป

ทีนี้ที่เยอะคือสั่ง W หลักๆ เช่น เรากำลังหันไปทางทิศเหนือ

เราก็กำหนดให้ ตำแหน่งที่เราอยู่ มีทางเดินไปทางทิศเหนือได้

และตำแหน่งถัดไป มีทางเดินมาจากทางทิศใต้ได้

คราวนี้มาเริ่มกันเลย เริ่มจาก function หลัก

let solve forward backward =

forward คือ บันทึกการเดินทางขาไป

backward คือ บันทึกการเดินทางขากลับ

เริ่มจากสั่ง replay เดินไปกลับ

let startPoint = [(-1, 0), Direction.None]
let (point, _)::tail, dir = replay (List.ofSeq forward) startPoint Direction.South
 
let returnPoint = (point, Direction.None)::tail
let _::tail2, _ = replay (List.ofSeq backward) returnPoint (opposite dir)

จุดเริ่มต้น startPoint คือ แถว -1 และเดินเข้าเขาวงกตจากทิศใต้เสมอ (โจทย์กำหนด)

แล้วก็เอาผลลัพธ์ของการ replay ครั้งแรกไปใส่ returnPoint เพื่อจะได้ทำการ replay ขากลับ

ได้ผลลัพธ์ tail2 คือ บันทึกตำแหน่งและลักษณะห้องในเขาวงกตทั้งหมด

สุดท้ายคือการเอา บันทึกตำแหน่งมา plot เป็นแผนที่เขาวงกต

let mergeWalls (key, list) = 
    key, list |> Seq.map snd
              |> Seq.fold (|||) Direction.None
let hex = sprintf "%x"
let createRows (key, list) = list |> Seq.sortBy fst
                                  |> Seq.map (snd >> int >> hex)
                                  |> String.Concat
                                  |> (+) "\r\n"
tail2 |> Seq.groupBy fst
      |> Seq.map mergeWalls
      |> Seq.groupBy (fst >> fst)
      |> Seq.sortBy fst
      |> Seq.map createRows
      |> String.Concat

tail2 เป็น list เก็บตำแหน่งและลักษณะของห้องทั้งหมด

Seq.groupBy fst คือ การ group ตามตำแหน่ง

Seq.map mergeWalls คือ การเอาลักษณะของห้องมารวมกัน

ห้องๆ นึงเราอาจเดินผ่านหลายรอบ เช่นครั้งแรกเดินเข้ามาทางทิศตะวันตก แล้วไปทิศเหนือ

ผ่านมาอีกครั้งอาจจะมาจากทางทิศเหนือ ไปทางทิศตะวันออก

เมื่อเราเอาข้อมูลมารวมกัน ก็จะรู้ว่าห้องนี้ มีทางเดินทางทิศตะวันตก ทิศเหนือ และทิศตะวันออก

Seq.groupBy (fst >> fst) คือ จัดกลุ่มตาม row

Seq.sortBy fst คือเรียงตาม row คือ row แรกให้อยู่ด้านบน

คราวนี้คือ Seq.map createRows คือ การพิมพ์ห้องต่างๆ ในแต่ละ row

createRows คือ คำสั่งแปลงลักษณะห้องต่างๆ เป็น hex (โจทย์กำหนด)

แล้วเอา hex ของทั้งแถวมาเชื่อมกัน

สุดท้าย String.Concat คือการเอา hex แต่ละแถวมาเชื่อมกัน

จะได้ออกมาเป็นแผนที่เขาวงกต

จบ

ไม่ได้เขียน blog มานานมาก

แต่ว่าตอนนี้มีองค์ประกอบดีๆ 3 อย่างคือ

1. เพิ่งพลาดไม่ได้ join codejam เลยต้องฝึกฝีมือเผื่อปีหน้า

2. กำลังหัดเขียน f#

3. ช่วงนี้งานค่อนข้างโอเค ไม่ยุ่งมาก

เลยตั้งเป้าว่า solve codejam ไปเรื่อย ๆ ด้วย f# และเขียน blog ไปด้วย

เริ่มที่ข้อแรก Alien Numbers

โจทย์คือ จะมีตัวเลขภาษาต่างดาวมา 2 ชุด ให้แปลจากตัวเลขภาษานึงไปอีกภาษานึง

สมมติมนุษย์ใช้เลขอารบิก 0123456789 มนุษย์ต่างดาวใช้เลข hex 0123456789abcdef

ดังนั้นเลข 10 จะเท่ากับ a

มนุษย์ต่างดาวไม่ได้ใช้ภาษาเหมือนเรา 0-9 ของเขาอาจจะเป็น )!@#$%^&*(

แต่หลักการนับเหมือนเลขของมนุษย์ทุกอย่าง

อ่านรายละเอียดเพิ่ม ที่นี่ครับ

โจทย์ข้อนี้ถือว่าง่ายมาก ถ้ารู้จักเลขฐานก็สบายเลย

วิธีคิดคือให้แปลจากภาษาแรกเป็น int ก่อน แล้วจาก int ค่อยแปลเป็นภาษาที่สอง

เริ่มจาก function หลัก

let solve value txt1 txt2 =

function ชื่อ solve

value คือ เลขที่ต้องแปล เช่น foo

txt1 คือ ชุดตัวเลขของเลขที่ต้องแปล เช่น of8

txt2 คือ ชุดตัวเลขอีกภาษานึง ที่เราต้องการแปลเป็นภาษานี้ เช่น 0123456789

value type เป็น string ส่วน txt1 กับ txt2 เป็น char[]

function การแปลจาก txt1 เป็น int คือ

let txtToNum txt v =
    let baseN = Array.length txt
    let foldFn a b = a * baseN + Array.IndexOf(txt, b)
    Seq.fold foldFn 0 v

baseN คือ จำนวนเลขฐาน เช่น of8 เป็นเลขฐาน 3

foldFn คือ สูตรการคำนวนเลขฐานอื่นๆ เป็น int

โดยเอาเลขก่อนหน้า (a) x เลขฐาน (baseN) + ค่าของตัวอักษรนั้น

เช่นเลข foo จาก of8

โดยถ้านับตามตำแหน่ง f เท่ากับ 1 ส่วน o เท่ากับ 0

f = 1

fo = 1 * 3 + 0 = 3

foo = 3 * 3 + 0 = 9

ดังนั้น foo = 9

function การแปลจาก int เป็น txt2 คือ

let numToTxt txt v =
    let baseN = Array.length txt
    let unfoldFn = function
        | -1 -> None
        | n  -> match Math.DivRem(n, baseN) with
                | 0, r -> Some(r, -1)
                | d, r -> Some(r, d)
    v |> Seq.unfold unfoldFn
      |> Enumerable.Reverse
      |> Seq.map (Array.get txt)
      |> Seq.map string
      |> String.Concat

unfoldFn คือ function แปลเลข int เป็นเลขฐานใด ๆ

สมมติเป็นเลข 454 และต้องการแปลเป็นเลขฐาน 6

454 / 6 ได้ 75 เศษ 4

75 / 6 ได้ 12 เศษ 3

12 / 6 ได้ 2 เศษ 0

2 / 6 ได้ 0 เศษ 2

เราจะได้ 4,3,0,2 ผลลัพธ์ที่ได้ต้องอ่านย้อนหลัง

เราเลยต้อง call Enumerable.Reverse เป็น 2,0,3,4

Seq.map (Array.get txt) คือการ map กับอีกชุดอักษร

เช่น 2,0,3,4 map กับ A?JM!. ก็จะกลายเป็น J,A,M,!

แล้ว Seq.map string กับ String.Concat คือ แปลงเป็น string

จาก J,A,M,! เป็น JAM!

เวลาเรียก function ก็ง่าย

value |> txtToNum txt1
      |> numToTxt txt2

โยน value เข้าไป txtToNum และเอาผลลัพธ์ไป numToTxt

จบ