PAtS.Computainment

สวัสดีครับ :)
หลังจากแป๊กกันไปแล้ว กับประโยค
ybtb ng uhaqerq qvi guerr cyhf sbhe.cv naq n dhnegre bs sbhe fvk guerr qbhoyr h

ที่มีคนแปลได้แล้วว่าเป็น
logo at hundred div three plus four.pi and a quarter of four six three double u

แต่ก็ยังไม่มีใครมาคอมเมนท์ตอบเลยว่าเป็นโลโก้อะไร Y-Y
มีเพื่อนบอกว่าอย่าเพิ่งเฉลย รอเค้าหาก่อน อิอิ
เพราะฉะนั้น มาว่าเรื่อง Google treasure hunt ดีกว่า :D

หลังจากเมื่อวาน คำถามข้อที่ 3 จาก 4 ข้อได้ปล่อยออกมา
สร้างความงุงงงอย่างยิ่งว่า.. ทำไมมันง่ายฟร่ะ!!!

ก่อนอื่น ขอเล่าปัญหา และเฉลยก่อนล่ะกัน
ใครยังไม่ได้เล่นไปเล่นก่อน อ่านเฉลยแล้วไม่มัน

ข้อแรก.. ปัญหาการเดินของหุ่นยนต์

ปัญหาคือ มีตารางขนาด n x k อยู่ มีหุ่นยนต์อยู่มัมบนซ้าย ให้เดินไปมุมล่างขวา
โดยหุ่นสามารถเดินได้แค่สองทางคือ.. ขวา กับ ล่าง
ให้หาว่ามีทางเดินทั้งหมดกี่รูปแบบ ตอบเป็นตัวเลขฐานสิบแบบเป๊ะๆ



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

จากที่ว่ามา... ก็จะเห็นเลยว่า รูปแบบการเดินทั้งหมดก็จะเท่ากับ
จำนวนรูปแบบการเลือกเดินในทิศทางใดทิศทางหนึงจากระยะตลอดเส้นทาง
เอิ่ม งง.. (เขียนเองก็งง) สรุปเป็นสูตรเลยดีกว่า

ตาราง n x k จะมีระยะเดิน (n - 1 + k - 1) = (n + k -2)
สามารถเดินไปทางขวาได้ (n - 1) ล่างได้ (k - 1)
(คุ้นๆ ยัง)

เอาไปเข้าสูตรของการเลือก (Combination)
ได้รูปแบบการเดิน (n + k - 2)!/((k - 1)! (n - 1)!)

ง่ายไหม?
ปัญหาอีกอย่างของข้อนี้คือ ตัวเลขที่มหาศาล (ลองคิดถึง 60! ดู)
แต่ไม่เป็นไรครับ อิอิ ผมมี Powertoy Calculator คิดได้มากสุดถึง 512 หลัก อิอิ
(จะบอกว่า รอบแรกตอบไปผิด.. ลืม -1 แหละ เหอๆ)

จบข้อแรก

---

ข้อถัดมา บวกเลขในไฟล์

มันก็เป็นการบวกเลขธรรมดานี่แหละครับ แต่ยุ่งหน่อยที่ตัวเลขมันอยู่ในไฟล์
ปัญหาข้อนี้ เค้าจะให้ไฟล์ zip มาไฟล์นึง ข้างในมีไฟล์และไดเร็กทอรี่มากมาย
แล้วก็จะให้เงื่อนไขว่า ให้บวกเลขในบรรทัดที่ xxx ของไฟล์ที่มี abc ในชิ่อ
และลงท้ายด้วย .def อะไรทำนองนี้... บางคนอาจจะนั่งบวกมือไป.. ก็ได้นะ แต่เหนื่อยหน่อย

วิธีง่ายๆ มากๆ คือใช้ unix command แล้วก็ pipe ไปเรื่อยๆ แต่... ผมใช้ไม่เป็น!!
ก็เลยเขียนสคริปโง่ๆ มาตัวนึง เป็น directory traversal ใน PHP

โค้ดตามนี้

$root = "/path/to/the/extracted/files/";
$stack = array($root);
$line = line number;
$sum = 0;

while(count($stack) > 0) {
  $c = array_pop($stack);
  $d = opendir($c);
      while (($file = readdir($d)) !== false) {
        if (($file == '.') | ($file == '..')) {
          continue;
        }
        $fpath = "{$c}{$file}";
        $ftype = filetype($fpath); 
        if ($ftype == 'dir') {
          array_push($stack, "{$fpath}/");
        } else {
           if (preg_match("/regexp here/i", $fpath) == 1) {
            $fc = file($fpath);
            $sum += (count($fc) > $line)?$fc[$line]:0;
          }
        }
      }
  closedir($d);
}
echo "{$sum}\n";

รู้สึกว่าข้อนี้จะยากที่สุด เพราะต้องเขียนสคริปท์ (ยาวด้วยง่ะ) - -"
จริงๆ ถ้ารู้คำสั่ง linux คงง่ายกว่านี้มาก

จบข้อสอง

---

ข้อสุดท้าย (ข้อสาม ข้อปัจจุบัน) เป็นปัญหาเน็ตเวิร์คครับ
โดยเค้าจะให้ routing table มา กำหนดจุด source, destination ให้หา path

(ตัวอย่าง)


ข้อนี้ ถือว่าเป็นข้อที่ง่ายที่สุดในบรรดาสามข้อ
วิธีคือ.. มองไปทีจุดเริ่ม (source) แล้วดูในตารางว่า destination ip ไปตกช่องไหน
เช่น ถ้าเราต้องไป 123.1.2.3 แล้วมีช่องนึงเขียนว่า 123.1.2.3 => 4.5.6.56
ก็ให้ไปหาโหนดต่อไป ที่มี ip = 4.5.6.56 แล้วก็บันทึกไว้เป็นโหนดในเส้นทาง
และก็มองหาต่อไปว่าในบรรทัดของโหนดนี้ มีช่องไหนตรงกับ dest ip อีก
(สังเกตว่า เรามองอยู่ ip เดียวเลย.. คือจะไป dest ip ให้ได้)
ถ้าหาไม่เจอ ก็ไปดูที่ช่องสุดท้าย default route ไล่ๆ ไป จนถึงปลายทางที่ต้องการ

ผมใช้เวลาไปนานมาก.. จริงๆ ควรตอบได้ภายใน 1-2 นาที ความรู้คืนอาจารย์หมด Y-Y


ที่มาเขียนเล่า และเฉลยให้ดูนี่ ก็เพื่อจะบอกว่า...

เห็นไหม?.. มันไม่ยากเลยซักนิด!!

ไปชวนเพื่อนเล่น มันบอกว่าขี้เกียจ เล่นไม่เป็น ยาก ฯลฯ
คิดไปเองครับ :p

สมองคนไทย ไม่แพ้ชาติใดในโลก (ที่เราแพ้ เพราะเราเอาแต่ประท้วง และปฏิวัติ!!)

สัปดาห์หน้า จะมีถามสุดท้าย ข้อที่ 4 ยังไงก็มาเล่นกันนะครับ
ติดตามรายละเอียดได้ที่บล็อกของกูเกิ้ล

และอย่าลืม.. ช่วยหาโลโก้ที่ผมให้หาหน่อยเถอะ.. นะๆ จุ๊บๆ