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 : 352 Pageviews.   0 comment Share Tweet

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.0, 0.0), false          else (1.0, 0.5), true     elif b > Rin then         if a > Rin         then (1.0, 1.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.0, 0.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.0, 1.0             else conquer center (R,R) sprintf "%.6f" pop จบ   Create Date : 15 พฤศจิกายน 2557     Last Update : 15 พฤศจิกายน 2557 10:42:31 น. Counter : 580 Pageviews.   0 comment Share Tweet

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 : 485 Pageviews.   0 comment Share Tweet

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 : 605 Pageviews.   0 comment Share Tweet

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-1) do                     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 % 9901) 1 {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 : 787 Pageviews.   1 comment Share Tweet

• F# CodeJam
• C# & Algorithms
• Review
• KM

• ศล
• owjung
• Webmaster - BlogGang

• My Blog
• My Network
• My Albums
• BlogGang.com