Just algorithm!

Minimum Scalar Product



ข้อนี้โจทย์ให้จับคู่ vector

แล้วให้เอาแต่ละจุดของ vector มาคูณกัน

โดยต้องได้ผลรวมที่น้อยที่สุด

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



วิธีคิดก็ง่ายมาก ก็ให้ vector นึงเรียงจากน้อยไปมาก

อีก vector ก็เรียงมากไปน้อยแล้วคูณกันก็จบ
let solve seq1 seq2 =
    let seq1 = seq1 |> Seq.sort
    let seq2 = seq2 |> Seq.sortBy (~-)    // Unary minus
    Seq.zip seq1 seq2 |> Seq.map (fun (a, b) -> int64 a * int64 b)
                      |> Seq.sum
                      |> string

ใน f# การประกาศทับตัวแปรเดิมเค้าเรียกว่า shadowing

เช่น let seq1 = seq1 |> Seq.sort

จริงๆ ก็เหมือน imparative แต่ shadowing จะพิเศษกว่าตรงที่ ตัวแปลแรกกับตัวแปรหลังไม่เกี่ยวข้องกันเลย

เช่น เราสามารถเปลี่ยน type ของตัวแปรก็ได้



และใน f# เราไม่มี sort descending เลยต้อง sortBy negative แทน

อีกอย่างคือ operator ของ f# จะไม่ซ้ำกันเลย ดังนั้น minus กับ unary minus มี symbol ต่างกัน



ส่วน zip คือ จับคู่ item ใน list

แล้วเราก็เอามาคูณกัน แล้วก็หาผลรวม



จบ




 

Create Date : 15 พฤศจิกายน 2557    
Last Update : 15 พฤศจิกายน 2557 11:10:02 น.
Counter : 116 Pageviews.  

Fly Swatter



ข้อนี้สนุกมาก



สมมติว่าเราเป็นนักเทนนิส ซึ่งจะใช้ไม้เทนนิสของเราตบแมลงวัน

โจทย์จะให้ขนาดของแมลงวัน (f)

ขนาดของไม้ (R)

ความหนาของไม้ (t)

ความหนาของเส้นเอ็น (r)

และความห่างของเส้นเอ็น (g)







โจทย์ให้หาว่า โอกาสที่ไม้เทนนิสจะตบโดนแมลงวันเป็นเท่าไหร่?

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



โจทย์ข้อนี้ ใครมานั่งหาสูตรคำนวนพื้นที่ก็อ้วกครับ มานั่งคำนวนเส้นตัดวงกลมทีละช่อง โหดแท้

เนื่องจากโจทย์ไม่ได้ให้คำนวนละเอียดมาก ทศนิยมหกหลัก เราสามารถใช้วิธี divide and conquer ได้

หลักการคือ แบ่งไม้เป็นสี่ส่วน แล้วก็พิจารณาดูว่าในส่วนนึง มีทั้งเส้นเอ็นและขอบเทนนิสหรือเปล่า

ถ้ามี เราก็แบ่งเป็นสี่ส่วนอีก แบ่งเฉพาะช่องที่มีขอบเทนนิสไปเรื่อยๆ จนทศนิยมไม่เกินหกหลักเราก็หยุด



เริ่มเลยละกัน
let solve f R t r g =
    let Rin = R - t - f
    let start = -(r + f)
    let r = (r + f)*2.0
    let g = g - f*2.0
    let rg = r + g

วิธีที่จะทำให้คิดง่ายขึ้นคือ เอาขนาดของแมลงวันมาขยายขนาดไม้ แล้วแมลงวันจะเหลือแค่จุดเดียว



Rin คือขนาดไม้ด้านใน (หักขนาดของแมลงวันแล้ว)

start สมมติว่า 0 คือกลางไม้ start คือจุดซ้ายล่างของเส้นเอ็นกลางไม้

r คือ ขนาดของเส้นเอ็น (รวมขนาดของแมลงวันแล้ว)

g คือ ช่องว่างระหว่างเส้นเอ็น (หักขนาดของแมลงวันแล้ว)

rg คือ ความห่างระหว่างจุดศูนย์กลางของเส้นเอ็น
let calculateGap p len =
    //calculate head
    let num = floor ((p - start) / rg)
    let headBlock = start + rg*num
    let headTouch = if p - headBlock > r
                    then 0.0
                    else min (headBlock + r - p) len
    let head = min (headBlock + rg - p) len

    //calculate body & tail
    let body = len - head
    let bodySize = floor (body / rg)
    let tail = body - rg*bodySize

    //calculate gap & return
    let headGap = head - headTouch
    let bodyGap = g * bodySize
    let tailGap = max 0.0 (tail-r)
    headGap + bodyGap + tailGap

อันนี้คือสูตรหาความยาวของช่องว่าง

p คือจุดเริ่มต้น


len คือความยาวของเส้น

concept ในการหาจะมี head, body, tail

head คือ gap ระหว่างขอบจุดเริ่มต้น ไปแต่ขอบเอ็นเส้นแรก

body คือ ขนาดของ gap ระหว่างเส้นเอ็น ภายในเส้นตรง

tail คือ gap ระหว่างขอบเอ็นเส้นสุดท้าย กับจุดสิ้นสุดของเส้นตรง
let touchString (x1,y1) (x2,y2) =
    let len = x2 - x1
    let gapH = calculateGap x1 len
    let gapV = calculateGap y1 len
    let untouch = (gapH * gapV) / (len * len)
    1.0 - untouch

function นี้ใช้คู่กับ function calculateGap

คือหาพื้นที่ของ gap หารด้วยพื้นที่ของสี่เหลี่ยม

ผลลัพธ์คือ โอกาสที่แมลงวันจะหลุดไปใน gap
let rinMixRate = (r / rg) * 0.5 + 0.5
let getHitRate p1 p2 =
    let a = center <-> p1
    let b = center <-> p2
    if b > R then
        if a > R 
        then (0.00.0), false 
        else (1.00.5), true
    elif b > Rin then
        if a > Rin
        then (1.01.0), false
        else (rinMixRate, 1.0), true
    else
        (touchString p1 p2, 1.0), false

ถัดมาคือการคำนวน ที่รวมขอบไม้

rinMixRate คือ โอกาสคร่าวๆ ที่แมลงวันจะรอดระหว่างขอบไม้กับเส้นเอ็นได้

p1 p2 คือจุดของสี่เหลี่ยม โดย p1 คือจุดซ้ายล่าง p2 คือ ขวาบน

a กับ b คือ ระยะระหว่าง จุดศูนย์กลางถึง p1 และ p2

operator (<->) คือการหาระยะ อ่านของเก่าดูครับ



function นี้ return โอกาสที่ตีโดนแมลงวัน โอกาสที่อยู่ในไม้ และ สามารถแบ่งออกได้อีกหรือไม่

logic คือ ถ้าทั้ง p1 และ p2 อยู่นอกขอบไม้ โอกาสตีโดนคือ 0 โอกาสอยู่ในไม้คือ 0 และไม่ต้องแบ่งอีกแล้ว

ถ้า p2 อยู่นอกไม้ แต่ p1 อยู่ในไม้ โอกาสตีโดนคือ 1 โอกาสอยู่ในไม้คือ 0.5 และสามารถแบ่งเพื่อคำนวนให้ละเอียดขึ้นได้

ถ้าใน p1 และ p2 อยู่ระหว่างขอบไม้ด้านในกับด้านนอก ก็คือตีโดนแน่นอน

แต่ถ้า p2 อยู่ระหว่างขอบไม้ แต่ p1 อยู่ในวงกลม โอกาสคือ rinMixRate แต่สามารถแบ่งเพื่อคำนวนละเอียดขึ้นได้

สุดท้ายถ้า p1 และ p2 อยู่ในวงกลม ก็ใช้สูตรคำนวน touchString
let epsilon = 0.00000025 * R

let rec divide (x1,y1) (x2,y2) =
    let xHalf = (x1 + x2) / 2.0
    let yHalf = (y1 + y2) / 2.0
    let pos1,area1 = conquer (x1,y1) (xHalf,yHalf)
    let pos2,area2 = conquer (x1,yHalf) (xHalf,y2)
    let pos3,area3 = conquer (xHalf,y1) (x2,yHalf)
    let pos4,area4 = conquer (xHalf,yHalf) (x2,y2)
    let area = area1 + area2 + area3 + area4
    if area = 0.0
    then 0.00.0
    else let pos = pos1*area1 + pos2*area2 + pos3*area3 + pos4*area4
         pos/area, area/4.0

and conquer (x1,y1) (x2,y2) =
    let hitRate,mix = getHitRate (x1,y1) (x2,y2)
    if mix && x2-x1 > epsilon
    then divide (x1,y1) (x2,y2)
    else hitRate

function สุดท้ายละ

epsilon คือ ขนาดที่เล็กที่สุดที่เราจะไม่คำนวนต่อ

divide คือ แบ่งสี่เหลี่ยมเป็นพื้นที่สี่ส่วนย่อย แล้วก็ conquer

ส่วน conquer คือ คำนวนหา hitRate ถ้าสามารถคำนวนละเอียดขึ้นได้ ก็ divide ไปเรื่อยๆ



ด้านบนมีใช้ keyword "and" ใน f# คือ mutually recursive function ครับ



แล้วก็ print ผลลัพธ์
let pop,_ = if g <= 0.0
            then 1.01.0
            else conquer center (R,R)
sprintf "%.6f" pop

จบ




 

Create Date : 15 พฤศจิกายน 2557    
Last Update : 15 พฤศจิกายน 2557 10:42:31 น.
Counter : 170 Pageviews.  

Train Timetable



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

ซึ่งมีแค่ 2 สถานี คือ A กับ B

A กับ B มีตารางออกจากสถานีแน่นอน มีระยะเวลาเดินทางแน่นอน และมีระยะเวลาพักรถแน่นอน

เราต้องหาว่า เราต้องหารถมาวางไว้ที่สถานี A กี่คัน และสถานี B กี่คัน

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



วิธีคิดก็เอาตารางเวลามาเรียงกันทั้งหมด เราหยิบเที่ยวที่ออกเช้าสุดออกมา

เมื่อเดินไปถึงอีกสถานีนึง เราก็มาดูว่าตารางเวลาถัดไปของอีกสถานีนึงคืออะไร แล้วก็ตัดไปเรื่อยๆ



เริ่มกันเลย
let solve t set =

t คือระยะเวลาพักรถ

set คือ Set ของตารางเวลาซึ่งเป็น tuple ซึ่งเรียงดังนี้ เวลาออก เวลาถึง สถานี id

สถานีผมใช้เป็น boolean ถ้าเป็น true คือ สถานี A ถ้า false คือ สถานี B
let rec runTrip startTime station set =
    let findFn (dep,_,i,_) = dep >= startTime && i = station
    match Seq.tryFind findFn set with
    | None     -> set
    | Some(it) -> let _,arr,_,_ = it
                  runTrip (arr+t) (not station) (Set.remove it set)

ถัดมาคือ function เดินรถ เช่น เดินรถจาก A ไป B ถึง B กี่โมง สามารถออกจาก B ไป A ได้อีกหรือไม่

ถ้าได้ (Some(it)) ก็ตัดออกจาก set ไปเรื่อยๆ


แต่ถ้าไม่ได้ (None) ก็คืนค่า set ที่ถูกตัดออกไป
let rec startTrip a b set =
    if set = Set.empty
    then a, b
    else let startTime,_,station,_ = set.MinimumElement
         let newSet = runTrip startTime station set
         if station
         then startTrip (a+1) b newSet
         else startTrip a (b+1) newSet

และถัดมาคือ function ดูว่าต้องมีรถที่ A และ B อย่างละเท่าไหร่

หลักการคือ เอารถเที่ยวแรกออกมา แล้วโยนเข้าไปใน runTrip ก็จะได้ set ใหม่ที่หักตารางของรถคันนี้ออกไป

วนไปเรื่อยๆ จนไม่มี item ใน set (Set.empty) จะได้คำตอบออกมา



สุดท้ายคืนค่า
let a, b = startTrip 0 0 set
sprintf "%A %A" a b

จบ




 

Create Date : 15 พฤศจิกายน 2557    
Last Update : 15 พฤศจิกายน 2557 9:40:52 น.
Counter : 131 Pageviews.  

Saving the Universe



เรื่องมีอยู่ว่า โลกของเรามี Search Engine อยู่หลายเจ้า

แต่รู้ไหมครับว่า เราไม่สามารถใส่ keyword ตรงกับ ชื่อของ Search Engine

เช่น ถ้าคุณ search "Google" บน Google จักรวาลจะระเบิดทันที !!!



หน้าที่คุณคือปกป้องจักรวาลแห่งนี้

ระบบจะป้อนชื่อของ Search Engine ต่างๆ และรายการ keyword ต่างๆ

ระบบคุณจะต้องบอกได้ว่า ระบบคุณจะสลับ Search Engine อย่างน้อยกี่ครั้ง

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



วิธีคิดก็ง่ายมาก แต่ต้องรู้จัก Set ใน F#

โครงสร้างของ Set จะเป็น binary tree ซึ่งสมาชิกจะไม่ซ้ำกัน

ทีนี้เราก็สร้าง set มา set นึง

แล้วป้อน keyword ไปเรื่อยๆ ซึ่ง Search Engine ที่จะมา search set นี้

คือ Search Engine สุดท้ายที่กำลังใส่ใน set นี้

แต่ก่อนใส่ เราก็สลับ set ใหม่เข้ามา ทีนี้เราก็ปกป้องจักรวาลได้แล้ว



ใน F# เราสามารถสรุป logic ด้านบนใน function เดียว

let solve s list =
    let rec run list set times = 
        match list with
        | []         -> times
        | head::tail -> 
            let newSet = Set.add head set
            if Set.count newSet = s
            then run tail (Set.singleton head) (times+1)
            else run tail newSet times

    run list Set.empty 0 |> string

s คือ จำนวนของ Search Engine

list คือ รายการของ keyword



function run เป็น recursive ที่จะ return ค่าว่าต้องสลับ set กี่ครั้ง

โดยที่ ถ้ารายการ keyword หมด ([]) เราก็ return จำนวนครั้ง

แต่ถ้ามี keyword เหลืออยู่ (head::tail) เราก็เอา head ใส่ set

หลังจากนั้นก็ count สมาชิกใน set ถ้าครบตามจำนวน Search Engine ก็เริ่ม set ใหม่ และเพิ่มจำนวนครั้งเข้าไป



จบ






 

Create Date : 15 พฤศจิกายน 2557    
Last Update : 15 พฤศจิกายน 2557 9:01:37 น.
Counter : 357 Pageviews.  

Circle




โจทย์ข้อนี้ให้หาจำนวนรูปแบบของวงกลม Hamiltonion Cycle

สมมติ วงกลมเรียงตามจุดหมายเลข 1-2-3-4-5 (และต่อจาก 5 คือ 1 ใหม่)

กับวงกลมตามหมายเลข 2-3-4-5-1 เป็นวงกลมชุดเดียวกัน เพราะเรียงเหมือนวงกลมแรก แค่เริ่มจาก 2 เท่านั้นเอง

และวงกลม 5-4-3-2-1 ก็ถือเป็นวงกลมชุดเดียวกัน เพราะไม่ว่าจะเรียงจากหน้าไปหลัง หรือหลังไปหน้า ก็เรียงเหมือนกัน

แต่กับวงกลม 1-3-2-4-5 ถือเป็นวงกลมคนละชุด เพราะเรียงไม่เหมือนกัน



ยังไม่จบ โจทย์มีข้อห้ามให้บางจุด ไม่สามารถเชื่อมกัน

เช่น ห้าม 3-5

เราไม่สามารถสร้างรูปแบบ 1-2-3-5-4 ได้

โจทย์จะให้จำนวนของจุด และจุดที่ห้ามเชื่อมกัน แล้วให้หาจำนวนชุดของวงกลมทั้งหมด

โดยคำตอบต้อง modulo กับ 99010

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



เนื่องจากเรามี constraint ที่ห้ามบางจุดเชื่อมกัน เราจึงไม่สามารถใช้ factorial คำนวนได้

แต่ถ้าเรา loop ทดลองทีละวิธี วิธีนี้อาจจะมีความซับซ้อนถึง O(n!) (n สามารถมีค่าถึง 300)

แต่โจทย์บอกว่า จุดที่ห้ามเชื่อมกันจะมีไม่เกิน 15 ชุด

ดังนั้น เราอาจใช้ factorial หาจำนวนวิธีการเรียงของวงกลม ทำให้ได้จำนวนรูปแบบของวงกลมทั้งหมด

แล้วค่อยหาจำนวนรูปแบบที่มีจุดที่ห้ามเชื่อมกัน แล้วเอามาลบกัน



เริ่มจาก class ช่วยก่อน
type EdgeString = { terminal:string Set; connections:string Set }
module Edge =
    let TryJoin b a =
        let conn = Set.intersect a.terminal b.terminal
        if conn = Set.empty
        then None
        else Some({ terminal = a.terminal + b.terminal - conn; 
connections = a.connections + b.connections + conn })

เหตุผลที่มี class นี้เพราะ เราจะเอาไว้หาจุดเชื่อม

เช่น EdgeString 1-2-3 terminal คือปลายของเส้น คือ 1;3 ส่วน connections คือจุดกลางของเส้น คือ 2

คำสั่ง TryJoin คือลองเชื่อม EdgeString 2 เส้นดู เช่น 1-2-3 เชื่อมกับ 3-4-5 จะกลายเป็น 1-2-3-4-5



ถัดมา อีกคำสั่งที่จำเป็นเลย คือ factorial
let rec fac n =
    if n <= 1 
    then 1
    else n * fac (n-1% 99010

เราสามารถ % 99010 ได้เลย เพราะโจทย์กำหนด มิเช่นนั้นอาจจะ overflow



เริ่ม solve กันเลย
let solve len set =

len คือ จำนวนจุด

set คือ set ของจุดที่ห้ามเชื่อมกัน



ถัดมาคือ หาวิธีเรียงทั้งหมด
let allCount = fac (len-1/ 2

สมมติ จำนวนจุดทั้งหมดคือ 5

วิธีการเรียงทั้งหมดคือ (n-1)!/2

n-1 เพราะตามหลักด้านบน 1-2-3-4-5 และ 2-3-4-5-1 คือวงกลมเดียวกัน

และ /2 เพราะตามหลักด้านบนเช่นเดียวกัน 1-2-3-4-5 และ 5-4-3-2-1 คือวงกลมเดียวกัน

ดังนั้น รูปแบบวงกลมทั้งหมดมี


(5-1)!/2 = 12 รูปแบบ



ถัดมาเป็นคำสั่งยาวหน่อย
let rec combin id = function
    | 0   -> Seq.singleton List.empty
    | cnt -> let collectFn i =
                let edge = Array.get set i
                let Validate it =
                    Set.intersect it.connections edge.terminal = Set.empty &&
                    (Set.count it.connections = len-2 || it.terminal <> edge.terminal)
                seq {
                    for edges in combin (i+1) (cnt-1do
                    if Seq.forall Validate edges then
                    let foldFn (edge,list) it =
                        match Edge.TryJoin edge it with
                        | None          -> edge,it::list
                        | Some(newEdge) -> newEdge,list
                    let newEdge,list = Seq.fold foldFn (edge,List.empty) edges
                    yield newEdge::list
                }
             let finish = Array.length set - cnt
             Seq.collect collectFn {id..finish}

คำสั่งยาว แต่ไม่มีอะไรมาก มันคือคำสั่งลองเชื่อมจุดแบบต่างๆ ดู

เช่น ถ้ามี 1-2, 2-3, และ 3-4

มันก็จะได้ [1-2-3] [1-2;3-4] [2-3-4]



ถัดมา อันนี้ซับซ้อนนิดนึง
let forbidCount = 
    let sumFn i =
        let sign = if i % 2 = 0 then -1 else 1
        let allCount = fac (len-i-1% 9901
        let sumFnX edges =
            let len = List.length edges
            Seq.fold (fun last i -> last * 2 % 99011 {2..len} % 9901
        let combCount = combin 0 i |> Seq.sumBy sumFnX
        sign * allCount * combCount % 9901
    let maxCombo = min (Array.length set) len
    Seq.sumBy sumFn {1..maxCombo} % 9901

คำสั่งชุดนี้ ไว้หาว่า รูปแบบวงกลมที่มีจุดที่ห้ามเชื่อมกัน มีกี่รูปแบบ

คำสั่งนี้ ใช้หลักการ Inclusion-Exclusion Principle

เช่น ถ้าห้าม 1-2, 2-3 และ 3-4

จะมี set ทั้งหมด 7 set คือ [1-2] [2-3] [3-4] [1-2-3] [1-2;3-4] [2-3-4] [1-2-3-4]

ถ้าเข้าตามสูตรด้านบนจะได้ดังนี้



จำนวน Union Setจำนวนรูปแบบทั้งหมด
1[1-2]6
[2-3]6
[3-4]6
2[1-2-3]-2
[1-2;3-4]-4
[2-3-4]-2
3[1-2-3-4]1



รวมกัน แบบที่มีจุดที่ห้ามเชื่อมกันทั้งหมด คือ 11 รูปแบบ

สุดท้ายเอามาหักลบกัน
let count = allCount - forbidCount
string ((count+9901% 9901)

เช่น จากด้านบน ถ้าจำนวนจุดคือ 5 และห้าม 1-2, 2-3, และ 3-4

allCount คือ 12

forbitCount คือ 11

คำตอบคือ 1 (เส้น 1-3-5-2-4)



จบ




 

Create Date : 11 กรกฎาคม 2557    
Last Update : 11 กรกฎาคม 2557 12:21:39 น.
Counter : 515 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.