Saturday, December 27, 2008

บอร์ดรับสมัครงานจากกูเกิล



** คำเตือน : บล็อกตอนนี้ Geek มาก

เมื่อ 2 เดือนก่อน ตอนที่กำลังนั่งเรียนปรับพื้นฐานป.โท ที่จุฬาอยู่ อาจารย์กำลังสอนวิชา Human Resource ซึ่งพูดถึงเรื่องการจัดการบุคคลของแต่ละบริษัท ซักพักอาจารย์ก็ถามขึ้นว่า

"รู้ไหม ว่าบริษัทไหนที่เค้าจัดอันดับให้เป็นบริษัทที่มีนวัตกรรม มากที่สุดในโลกตอนนี้ ?"

ผมพึ่งอ่านนิยสาร Time มาหยกๆ ก็ตอบขึ้นมาเลยว่า "แอปเปิลครับ !!"
อาจารย์ทำคิ้วขมวด ท่าทางนั่นจะยังไม่ใช่คำตอบที่อยากได้ .. "แล้วบริษัทไหนอีก ?"

"กูเกิลครับ !!" ผมตอบอีกรอบ .. อาจารย์ยิ้มแล้วชี้มาบอกว่า "ใช่เลยค่ะ กูเกิล"

อาจารย์ เล่าให้ฟังถึงเรื่องเกี่ยวกับกูเกิล สวัสดิการณ์และการทำงาน ซึ่งผมอ่านเรื่องนี้มาเป็นรอบที่ร้อยได้แล้วมั้ง .. แต่ไปสะดุดใจกับรูปนึงที่อาจารย์เอามาให้ดู




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

ภายในป้ายโฆษณานี้ ไม่มีโลโก้ของบริษัทหรืออะไรที่บอกเลยว่าเป็นของใคร มีเพียงกรอบคำพูดที่อ่านแล้วงงโคตรๆ แล้วตามด้วย " .com"

ส่วน ตัวผมเป็นคนชอบดูโฆษณามาก อาจจะติดนิสัยมาจากที่อ่าน a day พอดูแล้วก็พอจะเข้าใจว่า ป้ายนี้ต้องการให้เราเข้าไปที่เว็บอะไรซักเว็บนึง คือตั้งใจให้สงสัย และลองค้นหาดูว่าเว็บนี้มันคือเว็บอะไร ก็เหมือนแคมเป็ญโฆษณาสมัยใหม่ทั่วไป แต่ที่ไม่ธรรมดาคือการจะหา url นี้ มันต้องแก้โจทย์คณิตศาสตร์ !!

"อาจารย์ก็ไม่รู้เหมือนกันว่ามันคือเว็บอะไร รู้แต่ว่าพอเราหาคำตอบออกมาได้แล้ว เราจะได้เข้าหน้าเว็บพิเศษสำหรับสมัครงานกับกูเกิล"

ฟัง แล้วน่าสนใจไหมล่ะ ... ผมจะโจทย์เอาไว้่ในกระดาษ พอกลับมาถึงห้องที่คอนโด ก็รีบเปิดคอมฯ เพื่อหาคำตอบของโจทย์ปริศนาข้อนี้ทันที .. น่าสนุกทีเดียว

{ first 10-digit prime found in consecutive digits of e }.com

ผมนั่งงงกับโจทย์นี้อยู่หลายรอบ .. คำถามสำคัญก็คือ "มันแปลว่าอะไรวะ !!??"

หลังจากเปิด dict ดูอีกรอบสองรอบ ก็เลยถึงบางอ้อว่า .. จริงๆแล้วถ้าแปลโจทย์นี้เป็นภาษาไทยก็คือ ..

"{ จำนวนเฉพาะ 10 ตัวแรกที่พบในค่า e } .com"

ถ้า มันทำให้ยิ่งงง นั่นก็ไม่ใช่เรื่องแปลก แต่ถ้าอ่านดูดีๆ แล้วจะรู้ได้เลยว่ามันก็ไม่มีอะไรมาก .. ก่อนอื่นเราต้องรู้จักค่า e ก่อน จริงๆแล้ว e เป็นค่าคงที่ทางคณิตศาสตร์ ที่เราทุกคนเคยเรียนมาแล้วตอนม.ปลาย แต่เชื่อได้ว่าส่วนใหญ่ลืมกันไปหมดแล้ว

e คือค่าคงที่ หรือที่เรียกกันว่า exponential ใช้กันมากในการคำนวณในวิชาฟิสิกส์ ... คล้ายๆกับค่าพาย π ที่มีค่าเท่ากับ 22 / 7

แล้ว e มีค่าเท่ากับเท่าไหร่ ? หาค่านี้ยังไง ?

อันนี้จำไม่ได้จริงๆ ก็ต้องพึ่ง wikipedia ล่ะครับ (วิธีทำการบ้านยุค 2.0) ก็ได้ความว่า ค่า e หาได้จากสมการที่ไม่ซับซ้อนอะไรมากประมาณนี้ :



ก็จะได้ว่า e มีค่าประมาณ 2.7182818284 59045 23536 …. ยาวออกไปเรื่อยๆ ไม่มีวันจบ คล้ายๆกับค่าพายเหมือนกัน

กลับ มาที่โจทย์อีกครั้ง .. "จำนวนเฉพาะ 10 ตัวแรกที่พบในค่า e" .. ขยายความได้ว่า ให้เอาเลขทศนิยมของเจ้าค่า e เนี่ย ออกมาดูทีละ 10 ตัว แล้วดูว่ามันใช่จำนวนเฉพาะรึเปล่า ถ้าไม่ใช่ก็ให้ดูตัวต่อไปเรื่อยๆ จนกว่าจะเจอ .. ตัวแรกที่เจอ ให้เอาค่านั้น ตามด้วย .com ก็จะเจอเว็บปริศนา

วาดเป็นรูปออกมาให้เข้าใจง่ายๆ ประมาณนี้ :



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

1. เริ่มแรกคือต้องหาค่า e ก่อน .. จริงๆ java มีค่า e มาให้อยู่แล้วที่ Math.E เพียงแต่ว่ามันดันมีทศนิยมมาให้แค่ 19 หลัก ซึ่งไม่น่าจะพอ เพราะเราก็ไม่รู้ว่าจะต้อง shift right ไำปหาทศนิยมจนถึงหลักที่เท่าไหร่กันแน่ เพราะงั้นก็ต้องเขียน function ขึ้นมาหาค่า e โดยเฉพาะ

2. จากสูตรข้างบน จะเห็นว่าเราจะต้องมี function ช่วยอีกตัวนึง คือหาค่า factorial โดยเขียนเป็น recursive เพื่อให้ได้ผลคูรออกมา เช่น ถ้าให้หา 3! ก็จะต้องได้ค่า 6 กลับมา ( 3! = 3 x 2 x 1 = 6 )

ก็ได้ออกมาประมาณนี้


สาเหตุที่ต้องใช้ BigDecimal เพราะลองใช้ double แล้วไม่เวิร์ค มันจะได้ค่า infinity ออกมา ถ้าเราลองทำซัก 1,000 ตัว

3. หาค่า e โดยการวนลูป แล้วบวกค่าไปเรื่อยๆ ในรูปนี้คือทำทั้งหมด 1,000 รอบ และใช้วิธีการหารให้ได้ทศนิยม 1,000 ตำแหน่ง



4. เสร็จแล้วก็ทดสอบดูว่าได้ค่า e ออกมาเหมือนชาวบ้านชาวเมืองเค้ารึเปล่า จากนั้นก็เขียน function ทดสอบว่าค่านี้เป็นจำนวนเฉพาะรึเปล่า (จำนวนเฉพาะคือเชขที่ไม่มีเลขใดๆ หารมันลงตัว ยกเว้น 1 กับตัวมันเอง เช่น 2 , 3 , 5 , 7 , 11 , 13 )



ที แรกใช้วิธีไล่หารมันทีละตัวเลย เริ่มตั้งแต่ 2 ไปจนถึงจำนวนของมันเอง ซึ่งก็พอจะใช้งานได้ แต่พอเจอกับตัวเลขมากๆ ถึง 10 หลักเนี่ย ก็รอเป็นชาติเลยกว่าจะได้ผลลัพท์ออกมา เพราะมันต้องวนลูปทั้งหมด n ครั้ง คือ O(n) อย่างดีที่สุดคือวนครั้งเดียว แต่อย่างแย่ก็คือต้องวน 999,999,999 ครั้ง

ก็เลยต้องพยายามให้ Big O ลดลงมาให้ได้มากที่สุด จริงๆปัญหาจำนวนเฉพาะนี้เคยเจอมาหลายรอบตอนแข่ง Google Code Jam ก็พอจะมีเทคนิคอยู่บ้าง

อย่างแรกคือ ถ้าตัวเลขเป็นเลขคู่ มันไม่ใช่จำนวนเฉพาะแน่นอน เช่น ลงท้ายด้วย 2 , 4 , 6 , 8
สองคือการหาตัวเลขมากที่สุดที่จะเอามาหาร ถ้าสังเหตุดีๆ เลขที่ไม่ใช่จำนวนเฉพาะ เช่น
6 = 3 x 2
21 = 7 x 3
121 = 11 x 11
231 = 11 x 7 x 3

ตัว เลขในกลุ่มที่หารมันได้ลงตัว จะมีค่าไม่เกิน square root ของตัวมันเอง .. เช่น sqr ( 231 ) = 15.19 ดังนั้นเราตั้งหารไปเรื่อยๆ จนถึงแค่เลข 15 ก็พอแล้ว

เท่านี้ก็ลด Big O ไปได้หลายเท่าตัว แล้วก็ได้ function หาจำนวนเฉพาะประมาณนี้




5. สุดท้ายก็เขียนตัวทำงานหลัก ก็ไม่มีอะไรมาก เริ่มจากหาค่า e จากนั้นก็ดึงตัวเลขหลังทศนิยมออกมาทีละ 10 ตัว มาเช็คว่าเป็นจำนวนเฉพาะรึเปล่า ถ้าไม่ใช่ก็ให้เลื่อนไปอีกหนึ่งตัวหาค่าต่อไป




สั่งทำลานโลด ว่าแล้วก็ได้ออกมาแล้ว ... { first 10-digit prime found in consecutive digits of e } มันก็คือ ...



7427466391 !!!

เขียนไปค่อนวัน กว่าจะได้เลขนี้ออกมา ว่าแล้วก็เปิดเข้าไปดูที่ 7427466391.com มันมี !! แล้วปรากฏว่า ..




อ๊ากก ก .. จะบ้าตาย .. มันหาเว็บไม่เจอ .. เอ๊ะ รึว่าเราคำนวณผิด ? ลองกลับไปดูใหม่อีกรอบ มันก็น่าจะถูกแล้ว ว่าแล้วก็เลยลอง search google ด้วยคำๆ นี้ โอ้ .. ทางกูเกิลบอกว่าปิดเว็บนี้ไปนานแล้ว เวรกรรม T__T

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

ปิดไฟ นอน .. หลับฝันดีอีกคืน



Link - Official Google Blog: Warning: we brake for number theory