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

** คำเตือน : บล็อกตอนนี้ 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