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

จบ