Google Codejam 2016 Qualification Round

ปีนี้ใช้คอมใหม่ (ยังไม่ได้บล็อคเรื่องคอมใหม่สักที) ไม่ได้จัดอุปกรณ์ต่างๆ ที่สะสมไว้ให้เรียบร้อย ก็เลยต้องเริ่มจาก 0 และด้วยคิดว่า cjlib runner มันไม่จำเป็น มันเป็น overhead ก็เลยมีความคิดว่า เออ ลองเขียนเป็น C++ ดูดีกว่า น่าจะสนุก

Counting sheep

โจทย์ข้อนี้คือให้ N มา แล้วให้นับตั้งแต่ N, 2N, 3N, 4N, … โดยแต่ละครั้งให้จดตัวเลขในแต่ละหลักไว้ด้วย ถ้าเลขที่จดมีครบ 0-9 เมื่อไรให้คืนค่า xN ออกมา

ข้อนี้พบว่าพอเป็น C++ แล้วมันก็บังคับวิธีคิดเราอีกแบบ คือในลูปบรรทัดที่ 19 ถ้าเป็น Python เราจะ cast เป็น string แล้ววน ซึ่งมันเข้าใจง่ายกว่าการใช้ int (ที่ต้องมีบรรทัด 20 + 23 ให้อ่านแล้วต้องตีความ)

พบว่า cin ก็อ่าน input ง่ายดีนะ

Revenge of the Pancakes

โจทย์ข้อนี้ให้ string --+- มา แล้วให้ทำให้เป็น ++++ ทั้งหมด โดยใช้วิธีกลับเครื่องหมายทุกตัวตั้งแต่ตัวที่ 0 – n ได้ เช่น n = 2 ก็จะกลายเป็น ++-+

ที่สงสัยคือวิธีคิดเราง่ายมาก แต่ content analysis กลับคิดอะไรยากมากจนเรางงว่าวิธีเรามันผิดในทางคณิตศาสตร์หรือยังไง runtime ที่ใช้รันข้อ large เราก็แค่ 0.003s ด้วย

วิธีที่ใช้คือแบบนี้ครับ นับจากขวามือ เจอตัว - ตัวแรกเมื่อไรให้หยุดแล้วกลับทุกตัวด้านหน้ารวมถึงตัวนั้น ฉะนั้นจากข้อตัวอย่างก็จะเป็น

ครั้งที่ n (0-index) Output
เริ่ม --+-
1 3 ++-+
2 2 --++
3 1 ++++

ข้อนี้พบปัญหากับ cin นิดหน่อย คือมันไม่อ่าน \n เข้ามา ทำให้ต้องมาอ่านทิ้งอีกในบรรทัดที่ 49

Coin Jam

ข้อนี้จะใช้ C++ แล้วก็พบว่าใช้ itertools น่าจะไวกว่า ก็เลยจัด itertools + mathapi ตามสไตล์เดิมมา

ข้อนี้ผมก็ใช้วิธีตรงๆ โง่ๆ นี่แหละครับ

  1. Generate ตัวเลขมาก่อน โดยใช้ itertools.product('01', repeat=n-2) สร้างตรงกลางมา แล้วเอา 1 ประกบหน้าหลังตามที่โจทย์กำหนดว่าต้องขึ้นต้นและลงท้ายด้วย 1 ตรงนี้ดีที่ itertools สร้างเป็น tuple ออกมาทำให้มัน generate กรณีที่มี 0 นำได้ไม่มีปัญหา
  2. Cast และ cache เป็นเลขฐานต่างๆ ตั้งแต่ 2-10
  3. เช็คว่าเลขแต่ละตัวเป็น prime number ไหม ตรงนี้ใช้ mathapi เลย ง่ายและไวดี
  4. ถ้าใช่ก็ให้ mathapi หา factor แล้วตอบ

โค้ดที่เห็นนี่ optimize ไปนิดหน่อยละครับ แต่ก็ไม่ต่างกับเดิมมากนัก

ปัญหาของข้อยากคือ ผมก็ไม่เอะใจว่ามันให้ข้อยากมากแล้ว คือโจทย์ก็เขียนนะว่าไฟล์รับเข้าให้มาหมดแล้ว แต่ผมก็เห็นแค่ของ small ไม่เห็น large เลยนึกว่าไม่มี ปรากฏว่ามันให้เป็นตัวเลขมาแล้วไปเขียนไฟล์เอง ก็เลยไม่ได้ลองรันดู พอรันดูจริงๆ ก็พบว่าตัวเลขมันใหญ่มาก prime รันไม่ทัน ก็เลยเปลี่ยนแผนกลางอากาศขณะที่ timer วิ่งอยู่ (ตอนนั้นไม่รู้ว่า large หมดเวลาแล้วขอใหม่ไม่ได้)

แผนแรกก็คือไปใช้ C++ เผื่อจะรันไวขึ้น แต่ก็พบว่าเลขรับเข้าใหญ่กว่า 64 bit int เก็บไม่พอ library หา prime ที่ได้มาก็หา prime ได้สูงสุดแค่ uint64_t

อีกแผนคือ generate prime database ไว้ก่อนเลย ก็นั่ง generate ไปจนปาเข้าไป 40GB แล้ว ตอนนั้นเวลา countdown ใกล้หมดแล้วเลยกดหยุด และผมเชื่อว่าโปรแกรมที่ generate นั่นเหมือนจะออกมาแค่ uint64_t อีกแน่ๆ เพราะเป็น frontend ของ library เดียวกัน

Building Blue: bd2.in.th

ผมเป็นคนนึงครับที่ชอบอ่านเรื่องเบื้องหลังเว็บไซต์ต่างๆ มาก ใน Feed reader ผมจะมี Facebook Engineering, Twitter Engineering, Github blog ไว้เลยเพื่อจะอ่านเรื่องพวกนี้ ก็เลยว่าอยากลองมาเขียนเองบ้าง

สำหรับวันนี้โปรเจกท์ที่นำเสนอคือ bd2.in.th ครับ เป็นโปรเจกท์นึงที่ผมภูมิใจมากเพราะระบบมันค่อนข้างจะล้ำสมัยกว่าเว็บไซต์อื่นๆ เลยนะครับ

หน้า bd2.in.th ในปัจจุบัน

ในยุคแรกนั้นมีเว็บไซต์ dek-bd2.com ของ @ntklp ครับ เป็นเว็บประกาศข่าว แล้ว @icedrummer ก็ยืมวิทยุออนไลน์ของผมที่อยู่บนเซิร์ฟเวอร์ผมไปจัดเป็นวิทยุ ซึ่งก็จัดนานๆ ครั้ง ผมเองไม่ได้เกี่ยวกับโครงการนั้นก็ไม่ได้เข้าไปดูครับ ต่อมา @ntklp @ByakkoHD และคนอื่นๆ ก็ได้รวมกันทำเว็บบอร์ดขึ้นมาใหม่ให้เป็นรูปเป็นร่าง โดยตอนนั้นอยู่ที่ dek-bd2.whsgroup.ath.cx และแน่นอนว่ามันเครื่องผม ถึงผมจะไม่ค่อยอยากยุ่งแต่ก็ต้องเข้าไปดู maintain ต่างๆ จนกลายมาเป็น coder นิดๆ หน่อยๆ ครับ จนมาวันนึงเราคิดว่าขี้เกียจเมนเทน hosted sites แล้ว เลยผลักดันให้เว็บต่างๆ ออกไปข้างนอก ก็จะกลายมาเป็น bd2.in.th ครับ (ค่าโดเมนปีแรกสนับสนุนโดย @2DaDream) โดยใช้โฮสต์ clnox ที่ผมซื้อเอาไว้ทำ thaifedora.com มาก่อน (ตอนหลังมีคนรับไปอุปการะครับ แต่ผมเองไม่ค่อยว่างจะไปดูเว็บนั้น) และก็ได้พัฒนามาหลายรุ่นเลยครับ

– dek-bd2.com ใช้ WordPress เว็บบอร์ดผมไม่แน่ใจว่ามีไหม
– dek-bd2.whsgroup.ath.cx ใช้ SMF
– bd2.in.th ใช้ Drupal เป็นหน้าแรก และมี SMF เป็นบอร์ด รุ่นนี้มีธีมหลายตัวเลยครับ ตัวแรกสุดที่ผมทำจะเป็นหน้าเหมือน wordpress.org และตัวต่อมาเป็นตัวสุดท้ายที่มีพื้นเป็นก้อนเมฆ​ (จริงๆ มีรูปเมือง รูปก้อนเมฆ และรูปใต้ดิน) และบอร์ดก็จะใช้ธีมนี้ด้วยครับ​ โดยธีมนี้ได้แรงบันดาลใจจาก f0nt.com

ธีม bd2.in.th บนเซิร์ฟเวอร์ทดสอบ
ธีม FunBD2 บนเซิร์ฟเวอร์ทดสอบ

– ยุคต่อมา @ntklp ได้ตัดสินใจใช้ WordPress ผมเองก็ไม่ค่อยอยากยุ่งกับตรงนั้นแล้ว (ผลจากที่ผมเบื่อที่จะต้องมาทำธีมหลายๆ ที) เลยปล่อยให้ไปทำเอาเอง
– @ntklp ขอผมใช้วิทยุอีกครั้งนึงและได้เปิดเป็น Blue Wave Radio โดยรุ่นแรกใช้หน้าเว็บพื้นๆ เป็น HTML file เดียว ฟังได้อย่างเดียว ไม่มีชื่อเพลงไม่มีอะไรทั้งนั้น
– รุ่นต่อมาของ Blue Wave Radio ผมได้พัฒนาเป็นหน้าเว็บเต็มรูปแบบ รุ่นแรกๆ มีการแสดงชื่อเพลง และมีการดึง cover art โดยใช้ Covershare API

Bluewave รุ่นแรกๆ บนเซิร์ฟเวอร์ทดสอบ (ไอเดียจากหน้า ไก่คุ้ยตุ่ยเขี่ย เว็บ Green Wave)
Bluewave รุ่นสอง ใช้ช่วงปีใหม่ 2554 (ใช้ Blueprint CSS)

– รุ่นต่อมาอีกมีการแชทครับ แรกๆ ใช้ irc.freenode.net ห้อง #dekbd2 ผมได้ปรับ @willwillBot รุ่น IRC ให้มีความสามารถรองรับการขอเพลงต่างๆ โดยอาศัยว่าระบบขอเพลงนั้นยังอยู่บนเครื่องผมเลยทำให้ sync ข้อมูลกันได้โดยง่าย
– ต่อมามันมีคนมาฟลัชประจำ ผมจะแบนก็ไม่ได้เพราะใช้ webchat กัน เลยตัดสินใจเปลี่ยนมาเขียนแชทเองโดย integrate กับ SMF, Facebook, ฐานข้อมูลนักเรียน ใช้เวลาเขียนระบบแชทครึ่งวันครับ! (โมโหมาก) และก็แก้บั๊กมหาศาลอีกวันนึงก็เข้าขั้นพอใช้ได้แล้ว
– นอกจากนี้บลูเวฟยังมีการปรับหน้าตาอีกหลายครั้งครับ รุ่นสุดท้ายก่อนมาใช้โทนมืดในปัจจุบันจะมีรายการเพลงที่ขอให้คนดูดูด้วยครับ

รุ่นนี้ออกมาได้วันเดียวก็เลิกใช้เพราะคนฟังบอกว่ารกมาก

– ต่อมาเปิดเทอม 1/2554 เราได้จัดตั้งเป็นชมรม bd2.in.th (ชื่อชมรมชื่อนี้) ในโรงเรียนครับ มีสมาชิกประมาณ 25 คนในระดับม. 3, 5, 6
– ประชุมชมรมแรกๆ ผมได้เสนอและได้ทำการเปลี่ยนเว็บบอร์ดให้เป็น Vanilla ครับ เนื่องด้วยว่า @ntklp ให้ดูตัวอย่างจากเว็บอื่นๆ เช่นสวนบอร์ดและบดินทรโซน ซึ่งจะเน้นบอร์ดน้อย และมีหน้ารวมกระทู้ โดย Vanilla เองสามารถทำแบบนั้นได้ หรือจะแยกบอร์ดก็ได้
– @ntklp ได้หาเทมเพลทมาให้ผมทำ Blue wave UI ใหม่ และก็ได้มาเป็นบลูเวฟรุ่นในปัจจุบันครับ​ ซึ่งตัดฟีเจอร์ออกไปจำนวนมากเลยเพื่อให้มันครบถ้วนในหน้าเดียว
– ผมได้เขียน Plugin ของ Vanilla ให้มีการทำ notify แบบ Google+ ได้ครับ

มาดูเบื้องหลังเว็บดีกว่าครับ ว่าอะไรอยู่กับอะไร เริ่มแรกที่ส่วนหัวเว็บก่อนนะครับ หัวเว็บ bd2.in.th จะมีแถบ ซึ่งผมเรียกมันว่า Dickbar ตามชื่อของ UIDickbar ใน Twitter for iPhone (แต่ UIDickbar หน้าตาเหมือนแผ่นประกาศเที่ยวบินตามสนามบินนะครับ ไม่ใช่แถบแบบนี้) โดยผมบอกสมาชิกชมรมว่า เว็บไซต์จะใช้ธีมอะไรก็ได้ ใช้ CMS อะไรก็ได้ ไม่จำเป็นต้องเหมือนกันหมด แต่ต้องมีสิ่งหนึ่งบอกว่าเรายังอยู่ในเว็บ bd2.in.th นะ ไม่ได้หลุดไปที่อื่น เลยโค้ดออกมาเป็นตัวนี้ครับ

ตัว dickbar นี้ใช้ WordPress API ครับ หน้าที่จะมี Dickbar ทุกหน้าจะต้องเรียก WordPress เข้าไปก่อนแล้วค่อย include file เข้าไป ซึ่งไฟล์นี้ไฟล์เดียวเรียกปุ๊บจะได้ทั้งแถบเลยครับ โดยประกอบด้วยแถบเมนูที่ดึงมาจาก menu ของ WordPress และ CSS, JavaScript ประกอบ (เมนู drop down ที่เห็นนั่น Pure CSS นะครับ ส่วน JavaScript จะใช้ในส่วนของ unread notify และเดิมจะมีระบบ notify ของบอร์ดด้วยครับ แต่ถูกถอดไปแล้วเพราะแทนด้วยระบบ unread notify นอกจากนี้ยังเคยมี countdown ไปวันสอบ (ไม่มีแล้วเพราะใช้ปฎิทินแทน))

Dickbar

ส่วนต่อมานะครับ คือ unread notify ของบอร์ด ตัวนี้ผมใช้ iframe เข้าไปในบอร์ดครับ โดยผมเขียน module เองเพื่อมาแสดง notify และใช้ parent.window เพื่อบอกให้ JavaScript ของ Dickbar ทราบว่ามี unread เท่าไร แม้ไม่ต้องคลิกก็สามารถรู้ตัวเลขได้ (อันนี้ต้องใช้ทริกนิดหน่อยครับเพื่อให้สามารถข้าม subdomain ได้) สำหรับตัวนี้ ตอนแรกวางแผนจะใช้ WebSocket ครับ แต่เปลี่ยนใช้ให้มัน reload หน้า iframe เอาดีกว่าเพราะข้อความไม่ได้เร่งด่วน

อ้อ สำหรับเว็บบอร์ดนั้นผมลองดึง WordPress เข้าไปแล้วครับ แน่นอนว่าพังครับ ฉะนั้น Dickbar ของบอร์ดนั้นผม copy markup จากหน้าอื่นเข้าไปใส่ในธีมเอาครับ

สำหรับส่วนสุดท้ายนะครับ มีความซับซ้อนที่สุดคือระบบบลูเวฟครับ ผมเคยลองเขียนไดอะแกรมแสดงการทำงานแล้วพบว่าเขียนยากอยู่เหมือนกันเพราะมันซับซ้อนครับ

– เมื่อเปิดเข้าไปหน้า [live.bd2.in.th](http://live.bd2.in.th) นะครับ โปรแกรมจะโหลด WordPress มาแสดง Bar และก็แสดงหน้าให้เรียบร้อย
– จะมีการยิง AJAX request เข้าไปสองที่ครับ ที่แรกเพื่อดูสถานะว่ากำลังเล่นเพลงอะไร และที่ที่สองเพื่อดึงว่าขณะนี้ DJ ตั้งค่าระบบอย่างไร (มีสามค่าครับ คือข้อความประกาศข้างบน การเปิดปิด request และเวลาที่ห้ามขอหลังจากขอไปแล้ว)
– หลังจากนั้นแล้วหากมี DJ จัดปกติ โปรแกรมจะเปิดวิทยุครับ โดยตอนแรกผมใช้ [flowplayer ](http://flowplayer.org) แต่ด้วยข้อจำกัดด้านเนื้อที่เลยมาใช้ [SoundManager](http://www.schillmania.com/projects/soundmanager2/) + [jQuery UI](http://jqueryui.com) แทน
– นอกจากนั้นแล้วโปรแกรมยังจะเปิด​ WebSocket ไปด้วยครับ​​ โดยผมเลือกใช้ [Faye](http://faye.jcoglan.com/) เป็น server ครับเพราะมีลักษณะเป็นห้องๆ และยังสามารถใช้วิธีอื่นๆ ได้หากเครื่องไม่รองรับ WebSocket ด้วยครับ
– ขณะเล่นเพลงอยู่ WebSocket server จะ poll มาหาเพลงที่กำลังเล่นครับ (ไฟล์เดียวกับที่ request ไปตอนเปิดหน้านั่นแหละครับ ผมขี้เกียจ port ลง JavaScript ด้วยปัญหา encoding ต่างๆ) แล้วก็จะปาเข้าไปใน stream ด้วย ทำให้ client ไม่ต้อง poll server เองพร้อมกันหลายๆ คน ส่วน state นั้นเมื่อดีเจอัพเดตข้อมูล โปรแกรมจะส่งเข้ามาใน faye อยู่แล้วครับ ไม่จำเป็นต้อง poll
– Faye สามารถรับส่งได้สองทางครับ เพื่อป้องกันไม่ให้ client ส่งข้อความเข้าไป ผมได้มีการยึนยันด้วย Shared secret ครับ โดยมีรหัสผ่านนึงที่ทั้งสองฝั่งจะทราบและต้องส่งไปด้วย ถ้าไม่มีหรือไม่ถูกแปลว่าปลอมแน่นอนครับ ยกเว้นห้อง user online ผมอนุญาตให้ client ส่งเข้าไปได้เลย แต่จะมี shared secret อีกอันหนึ่งที่จะ sign กำกับข้อมูลที่ส่ง ซึ่ง server generate ให้ ดังนั้นหากมีการเปลี่ยนแปลงข้อมูลไม่ตรงกับที่ server กำหนดมาให้ ถึงจะส่งเข้าไปได้แต่เซิร์ฟเวอร์ก็ไม่รับครับ

สำหรับด้าน backend ของ DJ นะครับ เดิมทีผมจะใช้ htdigest authentication ฉะนั้นดีเจทุกคนจึงมีรหัสเดียวกัน (ผมขี้เกียจครีหลายอัน) ก็จะมีปัญหาตอนจะเอาดีเจออกเพราะมันต้องเปลี่ยนรหัส จนตอนเขียนแชทใหม่ผมเลยได้รื้อ backend ครับ (โค้ดเดิมมันเน่ามากเพราะเขียนแบบ Quick & Dirty ปัจจุบันโค้ดมันก็ก๊อปแปะจากตรงนั้นมาบางส่วนก็ยังเน่าๆ อยู่ครับ) โดยให้ยึนยันตัวด้วย WordPress แทน และใช้ Permission ของ WordPress ไปเลย และ Request ที่ขอมาจะเก็บลง Redis server ครับ และยังจะ push ไปยัง websocket ของ DJ ด้วยนะครับ (DJ มีห้อง websocket ต่างหาก) หลังจากดีเจเปิดเพลงให้แล้วมันจะพุชมาทาง websocket ครับและ client จะหาว่าใช่ของตัวเองมั้ย ถ้าใช่ก็ให้แสดงข้อความว่าเปิดเพลงให้แล้วนะ (ข้อมูลนี้ไม่ใช่ความลับครับ ฉะนั้นจึงให้วิ่งกระจายไปได้เลย) และด้านเซิร์ฟเวอร์ก็จะเซฟลง MySQL เพื่อใช้เป็นข้อมูลในการ Autocomplete ต่อไป

ระบบขอเพลง

ส่วนสุดท้ายในเว็บครับ คือส่วนของออโต้บอทจัดเพลง โดยผมใช้โปรแกรม ices ครับ ที่ผมแพทช์ไว้นิดนึงให้มันไม่ปิดตัวเองเมื่อต่อไม่ได้หลายครั้ง เพราะว่าเมื่อดีเจเตะบอททิ้งแล้วบอตจะหลุด และพอต่อไม่ได้บอตจะปิดตัวเองทำให้เมื่อดีเจจัดเสร็จแล้วบอตไม่กลับมา วิธีนี้ทำให้บอตกลับมาได้เอง โดยไม่ต้องกดเปิดบอตครับ​ (ผมยังคิดวิธีเปิดบอตที่ปลอดภัยไม่ได้เลยนะครับ เพราะบอตมันรันคนละ user กันด้วย) โดย ices อนุญาตให้เขียนสคริปต์ควบคุมได้ครับ ผมใช้ Python เขียนควบคุม โดยมีหลายโค้ดดังนี้ครับ

– ทุกเพลงจะสุ่ม 25% มีโอกาสเปิดจิงเกิ้ล​​ (ตอนหลังผมแก้ไว้ว่าห้ามเปิดจิ้งเกิ้ลต่อเนื่อง เพราะเคยมีบั๊กเปิดต่อกันห้ารอบแล้วนะครับ)
– เวลาแปดโมงเช้า หกโมงเย็น จะเปิดเพลงชาติไทย และเปิดจิ้งเกิ้ลตาม (ID3 Tag ของเพลงชาติและจิ้งเกิ้ลผม hard code ไว้ครับ เพลงอื่นมันจะดึง ID3 เองได้)
– บอตจะไม่เปิดเพลงศิลปินเดิมติดกัน (เพราะเคยมีบอตเปิดเฉลียงซ้ำๆ จนคนฟังเบื่อ)
– ก่อนจะเข้าระบบ playlist บอตจะดึงข้อมูลจาก redis ว่ามีเพลง request ใหม่หรือไม่ ถ้ามีก็จะเปิดให้ พร้อมแสดงชื่อคนขอให้เสร็จสรรพครับ
– การเตะบอตทำที่หน้า DJ Backend โดยมันจะเตะที่ shoutcast ครับ ไม่ได้เตะโพรเซสบอต เมื่อเตะแล้ว​ DJ จึงต้องรีบเข้ามาจัดต่อทันที

สำหรับ caching ในเว็บ ผมไม่แน่ใจว่าใน CMS ผมเซตอะไรบ้างนะครับ (ใช้ W3 Total Cache ด้วยนะครับ บล็อคผมที่ท่านอ่านอยู่นี้ก็ใช้) แต่ว่าสำหรับใน Blue wave เดิมทีไม่มีแคชครับ (มันเคยบั๊กเลยปลด ก่อนหน้านี้เป็น memcached) ปัจจุบันแคชเพลงที่กำลังเปิดใช้ Redis ครับ