ตามล่าหาขุมทรัพย์สุดขอบฟ้ากับ Google Treasure Hunt

ภาพยนตร์เรื่อง Indiana Jones and the Kingdom of the Crystal Skull กำลังจะเข้าฉาย Google ก็มีเกมสนุกๆ เกี่ยวกับการตามล่าหาสมบัติมาให้เล่นกัน ไม่จำเป็นต้องใส่หมวกถือแส้ แค่มีคอมพิวเตอร์ อินเทอร์เน็ต และสมองที่จะใช้ไขปัญหาที่ Google คอยหยอดทิ้งไว้ให้ก็พอ

วันที่ 8 พฤษภาคม 2551 Google Australia Blog ได้เปิดเผยถึงการแข่งขันตามล่าหาขุมทรัพย์ที่จะท้าทายความสามารถในการแก้ไขปัญหา (problem-solving) ของคุณ โดย Google มีปริศนา 4 ชุดที่จะทยอยเปิดเผยออกมาทุกสัปดาห์ ปริศนาเหล่านี้จะต้องใช้ความรู้เกี่ยวกับวิทยาศาสตร์คอมพิวเตอร์ ระบบเครือข่าย และความรู้ด้าน UNIX ในระดับลึก ใครที่สามารถไขปริศนาแต่ละข้อได้เป็นคนแรก คนนั้นจะได้รับรางวัล (อะไรไม่รู้)

ใน Google Australia Blog ไม่ได้บอกว่าจะพบกับปริศนาชุดแรกได้ที่ไหนและเมื่อไร แต่ได้ทิ้งคำใบ้ไว้ว่า แผนที่ของปริศนาแรกคือ aHR0cDovL3RyZWFzdXJlaHVudC5hcHBzcG90LmNvbS8= และเวลาที่ปริศนานี้จะเปิดเผยออกมาคือ 1210550400 วิธีการไขคำใบ้ทั้งสองมีดังนี้

คำใบ้แรกของ Google Treasure Hunt

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

<?php echo base_decode(“aHR0cDovL3RyZWFzdXJlaHVudC5hcHBzcG90LmNvbS8=”); ?>

ผลลัพธ์ที่ได้ก็คือ http://treasurehunt.appspot.com/ ซึ่งเป็น URL ของปริศนาชุดแรก URL นี้เป็น Web Application ที่โฮสต์อยู่บน Google App Engine

ส่วนตัวเลข 10 หลักก็คือ UNIX Timestamp ใช้ PHP ถอดรหัสได้ดังนี้

<?php echo date(“Y-m-d H:i:s”, 1210550400); ?>

ผลลัพธ์ที่ได้ก็คือ 2008-05-12 08:00:00 เป็นวันและเวลาที่ปริศนาชุดแรกจะถูกปล่อยออกมา

เมื่อเข้าไปที่เว็บไซต์ http://treasurehunt.appspot.com/ ก็จะได้พบกับปริศนาชุดแรก ซึ่งทุกคนจะพบกับโจทย์เดียวกัน แต่ตัวเลขไม่เหมือนกัน ทำให้ไม่สามารถ search หาคำตอบในเว็บอื่นๆ ได้

โจทย์ที่ว่านี้ก็คือมีหุ่นยนต์อยู่ที่มุมบนซ้ายของตารางหมากรุก และมีเส้นชัยที่มุมล่างขวา โดยที่ตารางหมากรุกนี้มีขนาด Width × Height ซึ่งตัวเลขนี้จะเปลี่ยนไปถ้าคุณหาคำตอบของปริศนานี้ได้แล้วและกลับมาเล่นซ้ำ เป้าหมายของคุณคือหาเส้นทางที่เป็นไปได้ทั้งหมดที่จะพาหุ่นยนต์ไปยังเส้นชัย โดยที่หุ่นยนต์สามารถเคลื่อนที่ไปทางขวาหรือลงข้างล่างเพียงเท่านั้น

Google Treasure Hunt: Robot Maze

ต่อไปนี้ผมจะเริ่มอธิบายวิธีไขปริศนานี้ ใครที่อยากลองเล่นดูก่อนโดยไม่อยากถูกสปอยก็อย่าเพิ่งอ่านนะครับ

โจทย์ความน่าจะเป็นแบบนี้เป็นโจทย์คณิตศาสตร์ ม.ปลาย เรื่อง Combination C(n, r) หากใครพอจะจำได้ เป็นโจทย์ประเภทเดียวกับมีลูกบอลห้าสีในกล่อง หลับตาหยิบออกมาสองลูก จะมีความเป็นไปได้กี่รูปแบบ

น่าเสียดายที่ผมคืนความรู้ให้อาจารย์ไปหมดแล้ว ผมเลยไม่ได้ไขปริศนานี้ด้วยสูตรทางคณิตศาสตร์ อย่างไรก็ตาม มีฝรั่งที่เขาแก้ออกมาให้ดูดังนี้ครับ

สมมุติว่าตัวแปร w แทนจำนวนช่องในทางกว้าง และตัวแปร h แทนจำนวนช่องในทางสูง ความเป็นไปได้ของเส้นทางการเดินทั้งหมดของหุ่นยนต์ก็คือ C(w-1 + h-1, w-1) แก้สมการออกมาได้ดังนี้

= (w-1 + h-1)! ÷ ( (w-1)! × (w-1 + h-1 – (w-1))! )
= (w+h-2)! ÷ ( (w-1)! × (h-1)! )

โดยที่ x! คือ Factorial
x! = x · (x-1) · (x-2) · … · 3 · 2 · 1
เช่น 5! = 5 · 4 · 3 · 2 · 1 = 120

แต่การรู้สมการเพียงเท่านี้ยังไม่พอครับ เพราะถ้าคุณเจอตารางที่มีขนาดอย่างเช่น 66×60 คุณจะไม่มีทางหาคำตอบของตัวเลขที่ใหญ่ขนาดนี้ได้ ถึงแม้จะใช้ Microsoft Excel ก็ตาม ตัวเลขที่ได้จะไม่ใช่ตัวเลขที่ถูกต้องเป๊ะ (exact) แบบที่ Google Treasure Hunt ต้องการ สาเหตุจะอธิบายต่อไปครับ

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

ผมเริ่มต้นด้วยการวาดตารางขนาดเล็ก 3×3 เพื่อดูว่ามนุษย์มีวิธีแก้ปริศนาอย่างไร แล้วค่อยเขียนโปรแกรมจำลองวิธีคิดของมนุษย์เพื่อใช้แก้ปริศนาที่มีขนาดใหญ่จนมนุษย์คิดเองไม่ไหว ใช้คอมพิวเตอร์คิดให้สบายกว่า

Google Treasure Hunt: Robot Maze Visualize

จะเห็นได้ว่าตารางแบบ 3×3 มีความเป็นไปได้ 6 เส้นทาง แล้วตารางแบบ 66×60 จะมีกี่เส้นทาง?

วิธีคิดที่ง่ายที่สุดก็คือการแบ่งงานใหญ่ให้เป็นงานเล็ก แบ่งตารางใหญ่ออกเป็นตารางเล็ก ด้วยการทำให้ตารางขนาด 66×60 ลดลงเป็น 65×60 64×60 63×60 ไปเรื่อยๆ จนถึง 3×60 2×60 และ 1×60 ซึ่งเมื่อตารางมีขนาดเหลือเพียง 1×60 เส้นทางที่เป็นไปได้ก็จะเหลือเพียง 1 เส้นทาง จากนั้นก็คิดย้อนกลับขึ้นมาที่ตารางขนาด 2×60 แล้วลดขนาดลงเป็น 2×59 2×58 2×57 ไปเรื่อยๆ จนถึง 2×3 2×2 และ 2×1 จำนวนเส้นทางทั้งหมดที่เป็นไปได้ของตารางขนาด 2×60 ก็คือ 60 เส้นทาง จากนั้นย้อนขึ้นไปที่ตารางขนาด 3×60 แล้วทำแบบนี้ไปเรื่อยๆ

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

โปรแกรมที่ผมเขียนมีหน้าตาเป็นแบบนี้ครับ

<?php
function walk($w, $h) {
global $path;
if($w > 1) walk($w-1, $h);
if($h > 1) walk($w, $h-1);
if($w == 1 && $h == 1) $path++;
}
$path = 0;
walk(66, 60);
echo $path;
?>

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

ผมเลยตัดสินใจเปลี่ยนวิธีใหม่ โดยใช้โปรแกรม walk ช่วยหาจำนวนเส้นทางในตารางขนาดเล็กก่อน เริ่มจากขนาด 1×1 2×1 3×1 ไปถึง 10×1 ต่อไปก็ 2×1 2×2 2×3 ไปถึง 2×10 ไปเรื่อยๆ จนถึง 10×1 10×2 10×3 ไปถึง 10×10 ได้คำตอบออกมาดังนี้

Google Treasure Hunt: Robot Maze 10x10

ตอนนี้ผมเริ่มสังเกตเห็นความสัมพันธ์บางอย่างในตารางนี้แล้ว (แอบนึกว่าตัวเองเป็น Robert Langdon ใน The Da Vinci Code) ผมพบว่าจำนวนเส้นทางของตารางขนาด W×H เท่ากับจำนวนเส้นทางของตารางขนาด (W-1)×H บวกกับจำนวนเส้นทางของตารางขนาด W×(H-1) เช่น จำนวนเส้นทางของตารางขนาด 9×10 (24,310) เท่ากับ จำนวนเส้นทางของตารางขนาด 8×10 (11,440) บวกจำนวนเส้นทางของตารางขนาด 9×9 (12,870) นั่นเอง

นั่นแปลว่าถ้าผมต้องการหาคำตอบของตารางขนาด 66×60 ก็แค่หาคำตอบของ 65×60 และ 66×59 ให้ได้ ถ้าจะหาคำตอบของ 65×60 ให้ได้ก็หา 64×60 และ 65×59 ให้ได้ ทำแบบนี้ไปเรื่อยๆ ซึ่งก็เป็น Recursive อีกเหมือนกัน ผมเลยใช้ Excel ใส่สูตรนี้ไปเรื่อยๆ จนครบ 66×60 แล้วเอาคำตอบที่อยู่ในเซลสุดท้ายส่งให้ Google Treasure Hunt ด้วยความดีใจ

10 นาทีต่อมา ผมก็ได้ทราบว่าคำตอบของผมผิด…

ด้วยความงงว่าเกิดอะไรขึ้นเลยมานั่งดูตาราง Excel จนพบความผิดปกติบางอย่าง คือยิ่งคำตอบเป็นตัวเลขใหญ่มากๆ ก็มีเลข 0 อยู่ด้านท้ายมาก เช่น คำตอบของตารางขนาด 36×51 คือ 896,386,644,186,594,000,000,000 ซึ่งไม่น่าเป็นไปได้ เพราะคำตอบมันเกิดจากการบวกเลข มันไม่น่าบังเอิญบวกกันแล้วลงตัวด้วยเลข 0 แบบนี้

พอลองหาสาเหตุดูถึงได้พบว่า Excel จะบันทึกตัวเลขมากสุดแค่ 15 หลักเท่านั้น ถ้ามากกว่านี้จะเริ่มปัดเศษ ซึ่งเป็นไปตามมาตรฐาน IEEE 754 ทำให้คำตอบที่ได้มีความผิดเพี้ยน ไม่ใช่คำตอบแบบเป๊ะ (exact) ตามที่ Google Treasure Hunt ต้องการ

เอาล่ะสิ… ทำไงดีล่ะ?

ก็เลยต้องเขียนโปรแกรมแทนที่จะใช้ Excel โดยใช้ array สองมิติแทนตารางใน Excel โปรแกรมมีหน้าตาแบบนี้

<?php
$w = 66; $h = 60;
for($i=0; $i<$w; $i++) $arr[0][$i] = 1; // Initial for first row
for($i=1; $i<$h; $i++) {
$arr[$i][0] = 1; // Initial for first column
for($j=1; $j<$w; $j++) {
$arr[$i][$j] = $arr[$i-1][$j] + $arr[$i][$j-1];
}
}
?>

ปรากฎว่า PHP ก็มีปัญหาเหมือนกับ Excel เลย คือใช้ตัวเลขได้มากสุดแค่ 15 หลัก เลยโดนปัดเศษเหมือนกัน ตอนนี้เลยเริ่มคิดจะเก็บตัวเลขทั้งหมดเป็นสตริงแล้วเขียน function สำหรับบวกเลขเอง แต่โชคดีที่ไปเจอ function bcadd เข้าก่อน เลยแก้โปรแกรมนิดหน่อย เปลี่ยนตัวเลขให้เป็นสตริง และใช้ bcadd แทนการ +

สุดท้ายก็ได้คำตอบออกมา ส่งคำตอบไปแล้ว Google Treasure Hunt บอกว่าคำตอบถูกต้อง ดีใจเหมือนเจอขุมทรัพย์เลย ถึงผมจะไม่ใช่คนที่ตอบถูกเป็นคนแรกของโลก ไม่ได้รับรางวัลอะไร แต่ปริศนานี้ก็ทำให้ได้เรียนรู้หลายอย่าง ไม่ว่าจะเป็นข้อจำกัดเลข 15 หลัก หรือ function bcadd

เมื่อหาคำตอบได้แล้ว Google Treasure Hunt ก็ได้ทิ้งแผนที่สำหรับปริศนาที่สองไว้ใน Official Google Blog ซึ่งเขียนด้วยภาษาแบบโจรสลัด โดยมีคำใบ้ดังนี้

คำใบ้ที่สองของ Google Treasure Hunt

ถ้าลองแปลแบบผิวเผินดู เวลาของปริศนาต่อไปก็คือ “936266827 วินาทีก่อนปี 2038” เขียนเป็นโปรแกรมดังนี้

<?php echo date(“Y-m-d H:i:s”, mktime(0, 0, 0, 1, 1, 2038) – 936266827); ?>

คำตอบที่ได้คือ 2008-05-01 14:52:53 ซึ่งดูแปลกๆ หน่อยเพราะมันผ่านมาแล้ว

จริงๆ แล้วคำใบ้ 936266827 seconds before Y2K38 มันมีอะไรที่ลึกซึ้งกว่านั้น แต่ผมยังไม่เฉลยตอนนี้ครับ ไว้ถึงเวลานั้นแล้วจะมาเฉลย

ส่วนสถานที่สำหรับปริศนาต่อไป ผมไม่แน่ใจว่าใช่เว็บเดิมหรือเปล่า คำว่า Mountain View mother ship อาจจะมีความหมายบางอย่างแฝงอยู่ก็ได้

ถ้าอ่านแล้วชอบ ฝากแชร์ด้วยนะครับ
  •  
  •  
  •  
  •  
  •  
  •  
  •  

,