Just algorithm!

F# เบื้องต้น

  ผมกับเพื่อนๆ ในกลุ่ม F# สร้าง blog ใหม่สำหรับผู้เรียนภาษา F# ที่ //fsharpthai.com/ แวะไปเยี่ยมเยียน ศึกษากันดูนะครับ




 

Create Date : 01 มิถุนายน 2558    
Last Update : 1 มิถุนายน 2558 16:14:20 น.
Counter : 1709 Pageviews.  

์Number Sets



ข้อนี้จะมีจำนวนตั้งแต่ 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)/+ 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



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




 

Create Date : 15 พฤศจิกายน 2557    
Last Update : 15 พฤศจิกายน 2557 23:57:50 น.
Counter : 655 Pageviews.  

Crop Triangles



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

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

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

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

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



สูตรการหาจุดศูนย์กลางคือ (x1 + x2 + x3) / 3, (y1 + y2 + y3) /3



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

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

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



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

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



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


หมายความว่า x1 + x2 + x3 หาร 3 ลงตัว

ซึ่งก็หมายความว่า x1 mod 3 + x2 mod 3 + x3 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*+ B) % M
               let yN = (C*+ 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

จบ






 

Create Date : 15 พฤศจิกายน 2557    
Last Update : 15 พฤศจิกายน 2557 23:10:03 น.
Counter : 492 Pageviews.  

Numbers



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


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



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

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



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


ก็จะเป็น a + bx



ทีนี้ function คูณก็จะง่ายแล้ว (a1 + b1x) * (a2 + b2x) เขียนเป็น 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)2 จะได้ 14 + 6x


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

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



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

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

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




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


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

= 2a - 1



(3 - √5)n เราแปลงเป็น 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



จบ






 

Create Date : 15 พฤศจิกายน 2557    
Last Update : 15 พฤศจิกายน 2557 20:11:45 น.
Counter : 461 Pageviews.  

Milkshakes



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

ซึ่งร้านเราจะขายหลายรสชาติ และแต่ละรสก็แบ่งเป็น 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 เราจะเอาแค่คำตอบแรกเท่านั้น



จบ




 

Create Date : 15 พฤศจิกายน 2557    
Last Update : 15 พฤศจิกายน 2557 18:11:14 น.
Counter : 427 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.