Google Treasure Hunt

เล่นมั่ง ๆ

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

เข้าเว็บ http://treasurehunt.appspot.com/ ปุ๊บคราวนี้ได้ข้อ 3 (network) เลย ลองอันนี้ก่อนละกัน พบว่าง่ายมาก ๆ สำหรับคนที่เข้าใจเรื่อง routing table ของระบบเน็ตเวิร์คแบบ TCP/IP หลักการคือดูว่าจากต้นทางจะไปหาปลายทางต้องเดินผ่าน node ไหนบ้าง เช่นผมเริ่มจาก G ต้องไป A ก็ดูว่า ip ของ A คืออะไร แล้วดูในตารางว่า แถว G มี route ไปหา A ไหม ซึ่งดูได้จากคอลัมน์ของ routing 3 คอลัมน์แรก ถ้ามีก็ให้ไป ip นั้นเลย ถ้าไม่มี ให้ไป default route คือคอลัมน์สุดท้าย เช่นของผมไม่มีใน 3 คอลัมน์แรก ก็ให้ดู ip ในคอลัมน์สุดท้ายซึ่งบอกให้ไป ip หนึ่ง ดูในตารางพบว่าเป็นของ H ก็จดในกระดาษว่า GH แล้วก็ทำเช่นเดียวกันไปเรื่อย ๆ สุดท้ายก็พบว่าเส้นทางเดินคือ GHIJKCOLMBA ก็คือคำตอบที่ต้องส่งไป คำถามนี้ใช้เวลา 2-3 นาทีก็เสร็จ ถูกในครั้งแรกเลยด้วย

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

ตารางขนาด 1x1 หุ่นยนต์อยู่ที่ตำแหน่งเดียวกับปลายทาง คำตอบ = 0
ตารางขนาด 1x2 คำตอบ = 1
ตารางขนาด 1xn คำตอบ = 1
ตารางขนาด nx1 คำตอบ = 1 เช่นกัน

ตารางขนาด 2x2 คำตอบ = 2
ตารางขนาด 2x3, 3x2 คำตอบ = 3
ตารางขนาด 3x3 คำตอบ = 6

ไล่ต่อไปอีกหน่อย ก็เริ่มจับทางได้ว่า จำนวนวิธีการเดินของตารางขนาด mxn ก็คือ จำนวนวิธีการเดินของตารางขนาด (m-1) x n + จำนวนวิธีการเดินของตารางขนาด m x (n-1)

เขียนให้สวย ๆ ก็ได้ว่า f(m,n) = f(m-1,n) + f(m,n-1) แบบนี้มัน recursive ชัด ๆ ว่าแล้วก็จับ python มาเขียนโค้ด ได้ว่า

def r(a,b):
  if (a == 1) and (b == 1):
    return 0
  elif (a == 1) or (b == 1):
    return 1
  else:
    return r(a-1,b)+r(a,b-1)

m, n = 4, 5
print r(m,n)

ลองค่า m และ n น้อย ๆ ดูแล้วถูกต้องดี อืมม ไม่เลว ๆ แต่พอใส่ค่าจริง ๆ ลงไป คือ 43, 49 ปรากฏว่าเงียบไปนานมาก ดูท่าไม่ดีละ ลองลดลงเหลือ 20, 20 ก็ยังนาน เฮ่ย ไม่ธรรมดาแฮะ แสดงว่าจำนวนทางเดินมันเยอะมาก ทำ recursive ไม่ไหวแล้ว เปลี่ยนมาเป็น array ละกัน

a=43
b=49

d=[]
for i in range(a):
  d[i:]=[[]]
  for j in range(b):
    if (i == 0) and (j == 0):
      d[i][j:] = [0]
    elif (i == 0) or (j == 0):
      d[i][j:] = [1]
    else:
      d[i][j:] = [d[i][j-1] + d[i-1][j]]

print d[a-1][b-1]

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

คำถามข้อที่ 2 ให้ดาวน์โหลดไฟล์ .zip มาไฟล์หนึ่ง พร้อมโจทย์

Unzip the archive, then process the resulting files to obtain a numeric result. You'll be taking the sum of lines from files matching a certain description, and multiplying those sums together to obtain a final result. Note that files have many different extensions, like '.pdf' and '.js', but all are plain text files containing a small number of lines of text.

Sum of line 4 for all files with path or name containing stu and ending in .pdf
Sum of line 4 for all files with path or name containing zzz and ending in .js
Hint: If the requested line does not exist, do not increment the sum.

Multiply all the above sums together and enter the product below.
(Note: Answer must be an exact, decimal representation of the number.)

โอว แบบนี้ต้องเขียนโปรแกรมเท่านั้น และหนทางหาคำตอบที่ดีที่สุดคือ shell programming ครับพี่น้อง ไม่ยากเลย แต่ครั้งแรกตีโจทย์ผิด อ่านไม่ดีเอง คือคิดว่าชื่อแฟ้มมี stu และนามสกุล .pdf เท่านั้น ที่จริงแล้วในชื่อ path ก็ได้ รอบแรกผิดแค่ตรงนี้เอง

มีอีกจุดที่ต้องระวังคือ โจทย์ให้เอาบรรทัดที่ 4 มา แต่ถ้าจำนวนบรรทัดมีไม่ถึง ก็ไม่ต้องเพิ่มค่า sum ดีที่โจทย์เตือนไว้ เพราะไม่อย่างนั้น ถ้าใช้แค่ head + tail จะได้บรรทัดสุดท้ายมาเสมอ โดยอาจจะไม่ใช่บรรทัดที่ 4 ก็ได้ ผลคือได้ shell script หน้าตาอย่างนี้มา

ln1=4
st1="stu"
ext1=".pdf"

ln2=4
st2="zzz"
ext2=".js"

repeat(){
 n=1
 while [ ${n} -le ${1} ]; do
   n=$(($n+1))
   echo 0
 done
}

s=0
for a in `find . | grep ${st1} | grep ${ext1}$`; do
  s=$((`repeat ${ln1} | cat ${a} - | head -n ${ln1} | tail -n 1`+${s}))
done

t=0
for a in `find . | grep ${st2} | grep ${ext2}$`; do
  t=$((`repeat ${ln2} | cat ${a} - | head -n ${ln2} | tail -n 1`+${t}))
done

echo "s= ${s}"
echo "t= ${t}"
echo "s*t= $((${s}*${t}))"

ซึ่งผมได้คำตอบคือ 2683982036 ส่งไปในครั้งที่สองก็ถูกต้องเรียบร้อยดี

รออาทิตย์หน้าจะมีคำถามใหม่มาอีก แต่ไม่รู้วันไหน เห็นว่าตอบถูกหมดเป็นคนแรกมีรางวัลให้ ทำอย่างไรจะได้เป็นคนแรกล่ะนี่ เอาน่าเผื่อมีรางวัลปลอบใจเป็น invite ให้ลองใช้ google app engine ก็คงจะดี