Bloggang.com : chaowman

ข้อนี้จะมีจำนวนตั้งแต่ A ถึง B

โดยจะมีเลขจำนวนเฉพาะอย่างน้อย P

ถ้าเลขระหว่าง A ถึง B ตัวไหนหารด้วยจำนวนเฉพาะลงตัว จะถือว่าเลขเหล่านั้นอยู่กลุ่มเดียวกัน

และถ้ามีตัวเลขไหนสามารถหารด้วยจำนวนเฉพาะ 2 ตัวลงตัว

กลุ่มของจำนวนเฉพาะ 2 ตัวนั้นจะรวมกันเป็นกลุ่มเดียวกัน

อ่านต่อ ที่นี่

ข้อนี้เขียนเป็น functional ค่อนข้างลำบาก

เช่น จำนวนเฉพาะอาจจะต้องใช้ Sieve

การจัดกลุ่มต้องใช้ Disjoint Set

ซึ่ง data structure ดังกล่าวเป็นแบบ mutable

ข้อดีของ f# อีกอย่างคือ ไม่ใช่ pure functional

หากจำเป็นต้องใช้ mutable data structure ก็ไม่มีปัญหา

เริ่มจาก Prime

let prime = Prime()

อันนี้ผมใช้ prime ที่เขียนเอง อ่านเพิ่มได้ ที่นี่

เริ่มเลย

let solve A B P =
    let mutable size = int (B - A + 1L)
    let primes = prime.FromRange(P, B-A)
    let set = DisjointSet()

size เป็น การประกาศแบบ mutable ซึ่งจะแก้ค่าได้ภายหลัง

primes คือ จำนวนเฉพาะระหว่าง P ถึง B-A

set ก็คือ disjoint set เขียนเองก็ได้ครับ logic ตาม wiki

for p in primes do
    let start = ((A - 1L)/p + 1L)*p
    for n in {start+p..p..B} do
        if set.Union(start, n) then
            size <- size - 1
 
size |> string

ทีนี้ก็ loop ตาม prime แต่ละตัว

ไล่หาตัวที่หารด้วย prime ลงตัว จาก A ถึง B

แล้วเอาค่าที่ได้ union เข้า disjoint set

ถ้า union สำเร็จก็หัก size ไป 1

ทำจนจบก็ได้คำตอบครับ

หลังจากคุณดู Discovery คุณก็อยากจะสร้าง Crop Circles บ้าง

แต่ระดับคุณ คุณจะสร้าง Crop Triangles แทน

และ Triangle ของคุณต้องไม่ธรรมดา

มุมต่างๆ ของสามเหลี่ยม ต้องอยู่บนจุดตัดบน Grid

ไม่พอ จุดศูนย์กลางของสามเหลี่ยมจะต้องอยู่บนจุดตัดบน Grid ด้วย

สูตรการหาจุดศูนย์กลางคือ (x₁ + x₂ + x₃) / 3, (y₁ + y₂ + y₃) /3

โจทย์จะมีสูตรให้สร้างจุดต่างๆ บน Grid

แล้วให้หาว่าเราสามารถสร้าง Crop Triangles ได้กี่แบบ

อ่านต่อ ที่นี่

เนื่องจาก large dataset สามารถสร้างจุดได้ถึง 100,000 จุด

เราจึงไม่สามารถใช้วิธี brute force ได้ ซึ่งจะต้องหาทั้งหมด 100,000! วิธี

แต่จริงๆ พอจะมีทางลัด ถ้า (x₁ + x₂ + x₃) / 3 เป็นจุดตัดบน grid

หมายความว่า x₁ + x₂ + x₃ หาร 3 ลงตัว

ซึ่งก็หมายความว่า x₁ mod 3 + x₂ mod 3 + x₃ mod 3 หาร 3 ลงตัว

เริ่มเลย

let solve n A B C D x0 y0 M =
    let unfoldFn (n, (x, y)) = 
        match n with
        | 0 -> None
        | n -> let xN = (A*x + B) % M
               let yN = (C*y + D) % M
               Some((x, y), (n-1, (xN, yN)))
 
    let trees = Seq.unfold unfoldFn (n, (x0, y0))

n A B C D x0 y0 M เป็น input ที่โจทย์กำหนด

unfoldFn ก็เป็น function ที่โจทย์กำหนด เพื่อสร้างจุดต่างๆ

ส่วน trees คือจุดต่างๆ

let buckets = trees |> Seq.groupBy (fun (x, y) -> (int x % 3)*3 + (int y % 3))
                    |> Seq.map (fun (key, g) -> key, g.LongCount())
                    |> Seq.sortBy fst
                    |> Seq.cache

ทีนี้ก็จัดกลุ่มเป็น 9 กลุ่ม (x mod 3) ตัดกับ (y mod 3)

แล้วก็นับจำนวนในกลุ่ม

let sameBucketCount = buckets |> Seq.map (fun (key, cnt) -> cnt * (cnt-1L) * (cnt-2L) / 6L)
                              |> Seq.sum

ถ้าเป็นกลุ่มเดียวกัน ก็แปลว่าหารลงตัวแน่นอน

เรื่องการหาจำนวนในกลุ่ม ใช้สูตร combinatorics

หยิบ 3 จาก cnt ตัว

อีกแบบคือ คนละกลุ่มหมด แต่หาร 3 ลงตัว

let diffBucketCount = seq {
                        for key1,cnt1 in buckets do
                        for key2,cnt2 in buckets do
                        if key1 < key2 then
                        for key3,cnt3 in buckets do
                        if key2 < key3 then
                        if (key1+key2+key3) % 3 = 0 then
                        if (key1/3 + key2/3 + key3/3) % 3 = 0 then
                        yield cnt1 * cnt2 * cnt3
                      } |> Seq.sum

คือ ถ้ามาจากคนละกลุ่มหมดเลย

และทั้งแกน x และ y หาร 3 ลงตัว

ก็เอาจำนวนมาคูณกันได้เลย

จบแล้วครับ ได้คำตอบ

sameBucketCount + diffBucketCount |> string

จบ

ข้อนี้ให้หา 3 หลักสุดท้ายก่อนจุดทศนิยมของ (3 + √5)ⁿ

เช่น (3 + √5)⁵ = 3935.73982... ก็ให้ตอบ 935

ข้อนี้ถ้าคูณธรรมดาผิดแน่นอนครับ ใน large set ยกกำลังถึง 2,000,000,000

precision ไม่พอแน่นอน

ทีนี้ลองแทนค่า √5 ด้วย x และแทนตัวบวกตัวคูณเป็น a กับ b

ก็จะเป็น a + bx

ทีนี้ function คูณก็จะง่ายแล้ว (a₁ + b₁x) * (a₂ + b₂x) เขียนเป็น function ได้ดังนี้

let (.*.) (a1, b1) (a2, b2) =
    a1*a2 + b1*b2*5, a1*b2 + a2*b1

เรารู้อยู่แล้วว่า x^2 จะได้ 5 จึงแทนค่าด้วย 5 ได้เลย

อีก function นึงสำหรับ mod

let (.%.) (a, b) m =
    a % m, b % m

ไม่มีอะไร แค่ mod a และ b

ถัดมาเป็น function สำหรับทำ modPow

let rec modPow num = function
    | 1   -> num
    | exp -> let result = modPow (num .*. num .%. 1000) (exp >>> 1)
             if exp &&& 1 = 1
             then num .*. result .%. 1000
             else result

อันนี้ค่อนข้างตรงสูตร ลองอ่านเพิ่มเติมใน wiki ดูนะครับ

ถัดมา หลังจากได้คำตอบแล้วจะถอดออกมาอย่างไร เช่น

(3 + √5)² จะได้ 14 + 6x

ถึงตอนนี้ เราจะแทน x ด้วย √5 ตรงๆ ไม่ได้เพราะ 6 ถูก mod มาก่อนหน้าแล้ว

ซึ่งอาจจะมีค่าเป็น 1006 ก็ได้

ทีนี้ลองพิจารณา conjugate ของ 3 + √5 ซึ่งก็คือ 3 - √5

3 - √5 มีค่าเท่ากับ 0.76... ซึ่งเมื่อยกกำลังไปเรื่อยๆ ก็มีค่าไม่เกิน 0

ดังนั้นคำตอบเท่ากับ

= (3 + √5)ⁿ + (3 - √5)ⁿ - (3 - √5)ⁿ

= (a + bx) + (a - bx) - 1

= 2a - 1

(3 - √5)ⁿ เราแปลงเป็น 1 ไปเลยเพราะเราไม่สนใจเศษทศนิยม

เอา 2a - 1 มาเป็น function คำตอบ

let solve exp =
    let a, _ = modPow (3,1) exp
    (a*2 + 999) % 1000 |> sprintf "%03d"

เราเปลี่ยน -1 เป็น 999 เพราะมี mod มาเกี่ยวข้อง

ดังนั้นเมื่อ a เป็น 0 จะได้ 999 ไม่ใช่ -1

จบ

คราวนี้สมมติว่าเราเป็นผู้จัดการร้านนมปั่น

ซึ่งร้านเราจะขายหลายรสชาติ และแต่ละรสก็แบ่งเป็น malt กับ unmalt

และเราก็มีลูกค้าหลายคน แต่ละคนก็ชอบไม่เหมือนกัน

บางทีก็ชอบหลายรส แต่ลูกค้าจะชอบแบบ malt แค่รสเดียวเท่านั้น

โจทย์สั่งให้เราจัดเตรียมวัตถุดิบ โดยที่ให้มี malt น้อยที่สุด

โจทย์ประเภท constraint satisfaction problem เนี่ย ไม่มีอะไรเหมาะเท่า F# อีกแล้วครับ

เวลาคิดก็เหมือนเล่น Sudoku เลือกตัวเลือกที่มีตัวเลือกน้อยที่สุดก่อน

แล้วเมื่อเลือกแล้ว ก็ตัด choice ออกไปเรื่อยๆ

ก่อนเริ่มเรามาสร้าง module กันเล่นๆ ก่อน

module Map =
    let count (map:Map<_,_>) = map.Count

เดิมที f# มี module ชื่อ Map อยู่แล้ว

ใน f# เราสามารถ เพิ่ม function เข้าไปใน module ที่มีอยู่แล้วได้

ในที่นี้ คือการเพิ่ม function count

เริ่มเลย

let solve n custs =

n คือ จำนวนรสชาติ

cust เป็น รายการ (seq) ของ map ที่บอกว่าลูกค้าแต่ละคนชอบรสอะไรบ้าง และมีค่าเป็น malt หรือ unmalt

ถัดมาคือ function หลัก

let rec logic map custs = 
    let custs = custs |> Seq.sortBy Map.count
                      |> Seq.toList
    match custs with
    | [] -> Seq.singleton map
    | head::tail ->
        seq {
            let prefs = head |> Map.toSeq
                             |> Seq.sortBy snd
            for a, b in prefs do
            let newMap = Map.add a b map
            let notMatch choices =
                let item = Map.tryFind a choices
                item.IsNone || item.Value <> b
            let newCusts = tail |> Seq.where notMatch
                                |> Seq.map (Map.remove a)
            yield! logic newMap newCusts
        }

map คือ map ของรสชาติต่างๆ ที่เราจะขาย และมีค่าเป็น malt หรือ unmalt

ตอนแรกเราก็เรียง custs ก่อน ใครมี choice น้อยสุดก็เลือกก่อน

ถ้า custs หมดแล้ว ([]) ก็คือจบ เราได้คำตอบแล้ว

แต่ถ้า custs ยังไม่หมด (head::tail)

prefs คือ ตัวเลือกของลูกค้า โดยที่เราจะเรียงเอาแบบ unmalt ก่อน

แล้วทีนี้ก็ลองตัวเลือกของลูกค้าทีละอัน

newMap คือ รสชาติที่เราจะขาย โดยเพิ่มตัวเลือกของลูกค้าเข้าไป

newCusts คือ ลูกค้าที่ยังไป satisfy และเราก็ตัดตัวเลือกรสเดียวกันออกไป (เช่น ลูกค้าชอบ unmalt แต่เราจะขาย malt)

แล้วก็วนไปเรื่อยๆ

เสร็จแล้วก็คืนค่า

let result = custs |> logic Map.empty
                   |> Seq.truncate 1
                   |> Seq.toList
match result with
| []       -> "IMPOSSIBLE"
| head::_  -> let createFn i = 
                  match Map.tryFind (i+1) head with
                  | None    -> "0"
                  | Some(j) -> string (j - 1)
              let strs = Seq.init n createFn
              String.Join(" ", strs)

โดย result เราจะเอาแค่คำตอบแรกเท่านั้น

จบ