let's code: แก้โจทย์คณิตศาสตร์กับ Project Euler

Project Euler คือสถานที่ฝึกปรือฝีมือการแก้โจทย์ปัญหาอีกที่หนึ่ง โดยโจทย์ส่วนใหญ่จะเป็นโจทย์ทางคณิตศาสตร์-คอมพิวเตอร์ ทำให้งานนี้เขียนโปรแกรมเป็นอย่างเดียวไม่พอ ยังต้องงัดสารพัดเทคนิคทางคณิตศาสตร์ออกมาเพื่อให้แก้ปัญหาได้อย่างสวยงามอีกด้วย

ถึงแม้จะไม่มีข้อกำหนดที่ชัดเจนว่าควรใช้ภาษาอะไร/เวลาประมวลผลเท่าไหร่ แต่ทางเว็บก็ได้ออกแบบโจทย์ทุกข้อไว้ให้สามารถแก้ได้ภายในเวลาที่น้อยกว่า 1 นาที (ด้วย algorithm ที่ optimize มาอย่างถูกต้อง) นอกจากนี้ผู้เล่นก็ควรจะซื่อสัตย์ต่อตัวเองด้วย เพราะโจทย์ทุกข้อจะใช้ test case เดิมไปตลอดครับ

ภาษาที่ใช้ได้
ภาษาใดก็ได้ หรือจะทดคำตอบในกระดาษก็ยังไหว

รูปแบบการตรวจคำตอบ
รับ test case จากหน้าเว็บมาประมวลผล แล้วส่งเฉพาะคำตอบ

ตัวอย่างโจทย์

• 1: หาผลรวมของเลขจำนวนเต็มบวกทุกตัวที่ต่ำกว่า 1000 ซึ่งเลขแต่ละตัวเป็นผลคูณของ 3 หรือ 5
• 25: จงหาลำดับของเลขฟีโบนักชีตัวแรก ที่เมื่อเขียนเป็นเลขฐานสิบแล้ว มีตัวเลขถึง 1000 หลัก
• 80: สังเกตว่า √2 สามารถเขียนเป็นทศนิยมไม่รู้จบได้คือ 1.41421356237309504880... จงหาผลรวมของผลรวมของตัวเลข 100 หลักแรกในทศนิยมไม่รู้จบนี้ สำหรับรากที่สองของจำนวนเต็มบวกที่น้อยกว่า 100 ที่เป็นทศนิยมไม่รู้จบ
• 206: จงหาจำนวนเต็มบวกเพียงหนึ่งเดียว ที่กำลังสองของมันสามารถเขียนให้อยู่ในรูป 1_2_3_4_5_6_7_8_9_0 เมื่อ _ แทนตัวเลขอะไรก็ได้ 1 หลัก

let's code: ย่อโปรแกรมให้สั้นที่ 140byt.es

140byt.es เป็นเว็บที่เกิดจากกลุ่มผู้ใช้งานทวิตเตอร์ เล่นสนุกกันโดยการเขียน code สั้นๆ แล้วทวีต (เพราะทวิตเตอร์อนุญาตให้ใช้ได้แค่ 140 ตัวอักษรต่อทวีต) ดังนั้นหลายๆ อันก็ต้องลงมือเขียนแบบ obfuscate กันเลยทีเดียว นับได้ว่าเป็นการฝึกพลังลมปราณอย่างหนึ่งนะครับ ;D

ความแตกต่างที่น่าสนใจจากที่อื่นๆ คือ ไม่มีโจทย์ตายตัวว่าจะต้องเขียนโปรแกรมอะไร ย่อให้ได้สั้นเท่าไหร่ แต่ขึ้นอยู่กับเราเลยว่าคิดอะไรออก แล้วก็ย่อให้อยู่ในขนาด 140 ตัวอักษรก็พอ (เกินก็ได้ - แล้วค่อยๆ แก้กันไปเรื่อยๆ) หรือว่าถ้ายังไม่แก่กล้าพอก็ไปศึกษา/ให้ความเห็น code ของคนอื่นๆ ก่อนก็ได้ ด้านประเภทของโปรแกรมก็มีอยู่หลากหลายมาก ตั้งแต่คำนวณทางคณิตศาสตร์ธรรมดาๆ ไปจนกระทั่งเขียนเกมกันเลยทีเดียว

ภาษาที่ใช้ได้
JavaScript

รูปแบบการตรวจคำตอบ
ส่ง source code ให้ชุมชนช่วยกันตรวจสอบ

ตัวอย่างโปรแกรม

• Fibonacci (41b): มือใหม่เริ่มที่ตรงนี้เลยครับ กับการหาเลขฟีโบนัชชีแบบง่ายๆ โดยการ recursive
• RGB to HEX (68b): แปลงค่าสีจากตัวเลขของ RGB ไปเป็น code สีตัวอักษร เทคนิคคือ shift bit
• Konami Code (105b): ปลดล็อกสูตร 30 ตัว จากการตวจสอบ regular expression
• Minesweeper (125b): เกมกู้ระเบิดนั่นเองครับ (เริ่มแกะ code ไม่รู้เรื่องแล้ว 555+)
• Vigenère Cypher (138b): รหัสลับวิจเญอแนร์ (เลื่อนอักษรตามขนาดอักษรแต่ละตัวในกุญแจ)
• Sudoku (141b): แก้ซูโดกุ เกินมาแค่ตัวเดียวเองนะ :'D (ใครสนใจไปช่วยลดขนาดมันบ้าง)

let's code: แก้โจทย์ Google Code Jam

Google Code Jam เป็นงานแข่งขันแก้โจทย์โปรแกรมมิ่งที่ Google จัดขึ้นปีละครั้งในช่วงปิดเทอม ของรางวัลนอกเหนือไปเงินเป็นหมื่นเหรียญสำหรับผู้ชนะเลิศแล้ว สิ่งที่ล่อตาล่อใจเหล่า geek ทั้งหลาย คงหนีไม่พ้นเสื้อยืดกูเกิลสำหรับยอดฝีมือ 1000 คนแรกเท่านั้น เรียกได้ว่า ใส่แล้วหล่อราศีจับกันเลยทีเดียว

และถึงแม้ว่างานจะมีจัดแค่ปีละหนึ่งครั้ง แต่ตัวเว็บก็สามารถเข้าไปแก้โจทย์เล่นได้ตลอดเวลาครับ ซึ่งก็พอมีโจทย์ที่ไม่ยากเท่าไหร่โผล่มาบ้าง (หาดูได้ในรอบคัดตัว) แต่โจทย์ส่วนใหญ่ก็ไม่ใช่สนามเด็กเล่นสำหรับมือใหม่แน่ๆ ข้อดีอีกอย่างที่น่าสนใจคือการที่สามารถใช้ได้หลากหลายภาษา จึงเหมาะอย่างยิ่งสำหรับผู้ที่เป็นภาษาใดภาษาหนึ่งอยู่แล้ว และต้องการฝึกฝนภาษาใหม่ๆ เพิ่มเติมครับ

ภาษาที่ใช้ได้
ภาษาใดก็ได้ที่มี compiler ฟรีให้ใช้งาน
(ตัวอย่างภาษาที่ไม่ผ่านเกณฑ์เช่น Maple, Mathematica)

รูปแบบการตรวจคำตอบ
ดาว์นโหลด test case มาประมวลผลเอง แล้วส่งคำตอบ (พร้อม source code) ให้ server

ตัวอย่างโจทย์

• Reverse Words: ให้ประโยคในภาษาอังกฤษมาประโยคหนึ่ง จงเรียงลำดับของคำแต่ละคำใหม่ โดยกลับให้ตำแหน่งของคำที่อยู่ด้านท้ายมาอยู่ด้านหน้า ด้านหน้าลงไปอยู่ด้านท้าย
• Center of Mass: ให้ตำแหน่งและความเร็วของหิ่งห้อยกลุ่มหนึ่งมา จงหาว่าที่เวลาเท่าใด จุดศูนย์กลางมวลของกลุ่มหิ่งห้อยกลุ่มนั้น จะเข้าไปใกล้กับจุด origin มากที่สุด และจุดนั้นอยู่ห่างจากจุด origin เป็นระยะทางเท่าใด สมมติว่านี่เป็นหิ่งห้อยในอุดมคติ (มวลเท่ากัน, ขนาดเป็นศูนย์)
• Watersheds: ให้แผนที่ระดับความสูงของป่าแห่งหนึ่งมา สมมติว่าเกิดฝนตกทั่วป่า จงแบ่งโซนพื้นที่ป่าแห่งนั้น โดยมีกฎว่าน้ำฝนที่ตกลงมาสู่พื้นนั้น จะไหลจากที่สูงลงไปยังที่ต่ำที่สุดเสมอ

let's code: แก้โจทย์ Interviewstreet

Interviewstreet เป็นเว็บหางานสำหรับโปรแกรมเมอร์แนวใหม่ ที่ตัดสินคัดเลือกคนขั้นต้นด้วยการจัดให้เขียนโปรแกรมแข่งกันซะเลย (แล้วค่อยไปยื่น resume + สัมภาษณ์ทีหลัง) เพียงแค่ทำโจทย์ผ่าน 7 ข้อ ก็มีสิทธิยื่นใบสมัครกับบริษัทเช่น Facebook, Microsoft, Amazon.com, Dropbox ฯลฯ เรียกได้ว่า นอกจากจะได้ฝึกสมองแก้โจทย์แล้ว ยังมีโอกาสลุ้นไปทำงานกับบริษัทเหล่านี้อีกด้วย

แม้ว่าตอนนี้เว็บจะมีโจทย์ให้ไปเล่นไม่มากเท่าไหร่ แต่ความยากนั้นรับรองว่าไม่ธรรมดาแน่นอน (โจทย์ค่อนข้างง่ายแต่ test case โหดมาก) นอกจากที่จะต้องใช้ algorithm ที่มีประสิทธิภาพควบคู่ไปกับ data structure ที่เหมาะสมแล้ว ยังต้องแม่นในการพิสูจน์ทางคณิตศาสตร์เพื่อนำมาลดขนาดของ big-O ด้วยครับ

ภาษาที่ใช้ได้
C/C++, C#, Java,
Haskell, Clojure, Scala,
PHP, Ruby, Python, Perl

ปล. ไม่ต้องกังวลจนเกินไปว่า เขียนภาษาในกลุ่ม script แล้วจะเสียเปรียบกลุ่ม native/managed นะครับ เพราะทางเว็บได้ชดเชยเวลาให้ตามสัดส่วนครับ

รูปแบบการตรวจคำตอบ
ส่ง source code ให้ server ประมวลผลกับ test case

ตัวอย่างโจทย์

• Meeting Point: หมู่บ้านแห่งหนึ่ง บ้านแต่ละหลังจะสามารถสร้างอยู่บนจุดตัดของกริดได้เท่านั้น จากบ้านหลังหนึ่งถ้าเดินทางตรงๆ ไปจุดถัดไปในทิศทั้ง 4 จะใช้เวลา 1 หน่วย แต่ถ้าเดินทางทะแยงในทิศทั้ง 4 ก็จะใช้เวลา 1 หน่วยเช่นกัน ถ้าให้พิกัดของบ้านทุกหลังในหมู่บ้านแห่งหนึ่งมา จงหาบ้านหลังที่ถ้าทุกคนในหมู่บ้านเดินทางมาประชุมที่บ้านหลังนั้น เวลารวมของการเดินทางของทุกคนจะมีค่าน้อยที่สุด
• String Reduction: ในระบบภาษาระบบหนึ่ง มีตัวอักษรแค่ 3 ตัวคือ abc เท่านั้น ถ้าต้องการย่อคำในภาษานั้น โดยกฎการย่อคือ จะย่อตัวอักษรไม่เหมือนกัน 2 ตัวที่อยู่ติดกันให้กลายเป็นตัวอักษรตัวที่ 3 ถ้าให้คำๆ หนึ่งมา ให้บอกว่าคำนั้นสามารถย่อให้สั้นที่สุดเหลือกี่ตัวอักษร
• Changing Bit: ให้บิตของตัวเลขขนาดใหญ่มาก (ใหญ่ได้ถึง 100,000 บิต) มา 2 ชุด ถ้าให้การคิวรี่อีกจำนวนหนึ่งมา ซึ่งสามารถ 1. ทำการเปลี่ยนข้อมูลบิตใดบิตหนึ่งในเลขทั้งสอง และ 2. นำเลขทั้งสองมาบวกกัน แล้วพิมพ์ค่าของบิตในตำแหน่งที่ร้องขอ จงสร้างระบบสำหรับตัวเลขและการคิวรีนี้

let's code: แก้โจทย์ ACM-ICPC

ACM-ICPC หรือเรามักที่เรียกย่อๆ กันว่า ACM คืองานแข่งขันโปรแกรมมิ่งในระดับอุดมศึกษาทั่วโลก นศ.ที่เรียนทางด้านวิศวกรรม-วิทยาการคอมพิวเตอร์ ก็คงหนีไม่พ้นที่จะโดนอาจารย์ชักชวนให้ลงแข่งเป็นแน่แท้

และด้วยความที่มันเป็นการแข่งที่แพร่หลายมาก ก็ทำให้มี mirror site เกิดขึ้นมากมาย เช่น Online Judge, Zhejiang University หรือจะลองไปถามๆ อาจารย์ที่ภาควิชาคอมพิวเตอร์ดูก็ได้นะ :D

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

ภาษาที่ใช้ได้
C/C++, Java, Pascal

รูปแบบการตรวจคำตอบ
ส่ง source code ให้ server ประมวลผลกับ test case

ตัวอย่างโจทย์

• 2088 - Entropy: สมมติให้คำในภาษาอังกฤษมาคือ "AAAAABCD" ถ้าย่อตัวอักษรแต่ละตัวด้วยบิตดังนี้ {"A": "0", "B": "10", "C": "110", "D": "111"} จะได้ว่าคำนี้สามารถเขียนด้วยบิตได้สั้นที่สุด (entropy encoding) ถ้าให้คำใดๆ มา จงบอกว่าคำนั้นสามารถย่อได้เหลือกี่บิต
• 2145 - Lost in Space: ให้ความยาวด้านทั้งสามของสามเหลี่ยมต้นแบบมา และให้เซ็ตของพิกัด xyz ของจุดมาอีกจำนวนหนึ่ง จงหาจุด 3 จุดจากเซ็ตนั้น ที่จะสร้างสามเหลี่ยมคล้ายกับสามเหลี่ยมต้นแบบ (มีสัดส่วนด้านทั้งสามคงเดิม) และมี error น้อยกว่า 0.01%
• 2334 - Gridland: สมมติประเทศ ซึ่งเมืองแต่ละเมืองอยู่บนกริดขนาด N x M แต่ละเมืองสามารถเดินทางไปยังเมืองอื่นๆ ที่อยู่ติดกันได้ 8 ทิศ คนขายของต้องเดินทางสั้นที่สุดเป็นระยะทางเท่าไหร่ ถึงจะผ่านเมืองครบทุกเมือง