Just algorithm!

Triangle Trilemma



ข้อต่อมา 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.[2with
    | -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)

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



จบ




 

Create Date : 01 มิถุนายน 2557    
Last Update : 1 มิถุนายน 2557 11:16:30 น.
Counter : 693 Pageviews.  

Shopping Plan



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

สถานที่มี 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 00, 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, 0false)
sprintf "%.7f" minCost

จบ




 

Create Date : 31 พฤษภาคม 2557    
Last Update : 31 พฤษภาคม 2557 0:31:47 น.
Counter : 532 Pageviews.  

Egg Drop



ข้อถัดมา 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 มีค่ามากกว่าเท่ากับ 232

ให้ return -1



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

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



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

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



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

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

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

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



และถ้า d = b

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

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

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



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

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


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

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

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

แต่เนื่องจากโจทย์บอกว่า ถ้า result เกิน 232 ให้ 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 จะมีค่ามากกว่า 232 เสมอ



คราวนี้เราเริ่มหาค่า 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)

จบ





 

Create Date : 25 พฤษภาคม 2557    
Last Update : 27 พฤษภาคม 2557 12:09:14 น.
Counter : 730 Pageviews.  

Always Turn Left



ข้อถัดมา 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 = [(-10), 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 แต่ละแถวมาเชื่อมกัน

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



จบ




 

Create Date : 18 พฤษภาคม 2557    
Last Update : 6 กรกฎาคม 2557 22:05:35 น.
Counter : 592 Pageviews.  

Alien Numbers



ไม่ได้เขียน 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



จบ





 

Create Date : 03 พฤษภาคม 2557    
Last Update : 27 พฤษภาคม 2557 12:08:33 น.
Counter : 569 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.