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 หลัก

Python: รีดความเร็วด้วย PyPy

เนื่องจากตัว Python เป็นภาษาสคริปต์ เวลาสั่งทำงานโปรแกรมจะช้ากว่าภาษาที่ compile เตรียมไว้ก่อนอย่างไม่ต้องสงสัย

ทางออกสำหรับโปรแกรมเมอร์ Python ที่ต้องการให้โปรแกรมเร็วขึ้นก็มีหลายวิธี ตั้งแต่วิเคราะห์ algorithm เพื่อทำ optimization ย้ายไปใช้ module ที่เขียนในภาษา C ไปจนถึงใช้ Python เป็นโครงต้นแบบแล้วเขียนโปรแกรมใหม่ทั้งหมดด้วยภาษาอื่นเลย

จะเห็นว่าทุกวิธีที่ว่ามา มี cost ในการเปลี่ยนที่สูงพอควร ทั้งที่วิธีแก้ปัญหามันควรจะง่ายกว่านั้น เพี่ยงแค่ compile โปรแกรมที่เขียนด้วย Python เก็บไว้ก่อนเช่นเดียวกับภาษาอื่นๆ

ตัวโครงการหลักของ Python ยังไม่มีความสามารถนี้ แต่ไม่ต้องเสียใจไป เพราะโครงการ PyPy สามารถเร่งความเร็วให้โปรแกรมที่เขียนใน Python โดยการใช้ JIT compiler เข้าช่วย แน่นอนว่าเราแทบไม่ต้องเขียน code ใหม่หมดเพื่อความเร็วนี้เลย

สำหรับ Linux สามารถดาวน์โหลด binary package มาติดตั้งเองได้ หรือจะสั่งติดตั้งผ่าน apt-get ก็ได้เช่นกัน เพียงแค่เพิ่ม repository ก่อนดังนี้

ส่วน Windows จะได้ไฟล์ .exe มาเลย ก่อนใช้ก็อย่าลืมเพิ่ม environmental path เพื่อความสะดวกนะครับ

---

วิธีใช้งานก็เรียบง่ายตรงไปตรงมา แค่เปลี่ยนจาก

ไปเป็น

ก็เรียบร้อย โดย option ที่เพิ่มขึ้นมาจาก python ธรรมดาได้แก่

ที่จะทำการปิด JIT compiler ทิ้งไป โดย option นี้จะเหมาะกับโปรแกรมขนาดเล็กที่ไม่ได้ทำงานซ้ำๆ กันซักเท่าไหร่ครับ

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

สำหรับรายละเอียดเต็มๆ ว่าอะไรที่ใช้ได้และไม่ได้บ้าง สามารถอ่านได้จากหน้า compatibility