Google Code Jam 2011 รอบคัดเลือก

**เข้ารอบฮะ!!**

เห็นทวีตกันมาว่าจะถึง codejam ในไม่กี่ชั่วโมง ผมตัดสินใจตอนตีหนึ่งกดสมัครมันตอนนั้น ไม่กี่ชั่วโมงก่อนเริ่มการแข่งขัน

พอโจทย์ออกมานะครับ ข้อแรกผมฮามากมาย เพราะมันล้อเลียน Portal 2 กัน

โอเค มาดูโค๊ดกันดีกว่า ว่าผมทำยังไง ผมไปดูของพวกที่มันชนะแล้วง่ายกว่านี้เยอะครับ ของผมจะใช้วิธีตามที่โจทย์กำหนดมา ไม่มีเอาอะไรมาปน (ข้อ Gorosort เกือบจะทำครับ แต่หมดแรงแล้วตอนนั่ง optimize splitting)

ข้อแรกนะครับ หุ่นสองตัวต้องไปกดปุ่มตามลำดับที่กำหนด ห้ามกดปุ่มพร้อมกัน แต่สองตัวนี้เดิมได้อย่างอิสระ เช่นตัวนึงกดอีกตัวเดินได้ แต่ห้ามกดกับกดพร้อมกัน

ผมใช้วิธี parse format ด้วย regex ครับ ผมไม่ชอบ format ลักษณะนี้ เหมือนมันดู legacy มาก ทั้งๆ ที่มันควรจะเป็น JSON แล้ว พอได้แล้วก็กำหนดว่า สีฟ้าไปไหน สีส้มไปไหน และ ลำดับคำสั่งนั้นลำดับที่เท่าไร เสร็จแล้วก็ให้มันเดินไปถ้ายังไม่ถึง ถ้าถึงแล้วก็ให้หยุดรอ แล้วรอดูว่าอีกตัวลำดับก่อนหรือหลัง ถ้าก่อนก็ให้หยุดรอไปเรื่อยๆ ถ้าหลังก็รันได้เลย

script ตัวนี้ใช้เวลาประมวลผลเร็วมากครับ เพราะใช้ threading (แต่ข้อสาม ผมจะว่าต่อว่า threading ไม่ใช่คำตอบ)

ข้อแรกนี้ผมทำผิดไปหลายรอบครับ รอบแรกผมพลาดลืมลบ debug code รอบสองไม่แน่ใจว่าลืมอะไร


ข้อสองนะครับ มีลำดับให้ ถ้าลำดับสองอันที่กำหนดติดกัน มันจะเปลี่ยน แต่ถ้าใส่ตัวเข้าไปตัวนึงปุ๊บแล้วไปเจออีกตัวในลำดับเดิมที่ใส่เข้าไปแล้ว ถ้ามันไม่เปลี่ยนธาตุ มันจะระเบิดทำให้ตารางหายหมด ทีนี้มาดูของผมนะครับ

อันนี้ผมใช้ parser แบบ step by step เพราะผมไม่แน่ใจว่าลำดับธาตุเปลี่ยน กับธาตุตรงข้ามมันมีกี่อัน ส่วนการประมวลผล ก็ทำเหมือนข้อเดิมครับ คือ ใส่เข้าไปทีละตัว ถ้ามันเปลี่ยนก็เปลี่ยน ระเบิดก็ระเบิด จุดที่ผมเกือบพลาดคือพอเปลี่ยนแล้วต้องลบธาตุเดิมออกด้วย ไม่ใช่ใส่ธาตุใหม่อย่างเดียว​(บรรทัด 68, 76 ที่ต้องแก้)

——

ข้อต่อมา ยากเอาการเลยครับ แทบจะโดดจากข้ออื่น คือ น้องมันโง่ไม่ทดเลข อันนี้คือโค๊ดที่ผมใช้ในการส่งแข่งขันครับ

ฟังก์ชั่น noobAdd มันจะเปลี่ยนเป็น binaryแล้วตัดส่วนหัว string ที่บอกว่าเป็น binary ใน python ออก แล้วก็บวกๆ กัน แล้วก็แปลกกลับครับ ตามคำสั่งเป๊ะ

เสร็จแล้วใน loop จะหา combination ทั้งหมดที่แบ่งได้ครับ โดยเริ่มจากจำนวนขนมครึ่งหนึ่งก่อน ทำให้โปรแกรมช้า

ปรากฎว่า ส่งไปรอบแรกไม่ผ่านครับ ผมลนลานรีบใส่ textmate เลยว่าน่าจะมีอะไรผิด เช่นลืมใส่ trailing newline ต่อมารอบสองก็ผิดครับ แต่พอก่อนนอนได้ไอเดียดูว่าข้อไหนผิด ปรากฎว่า ข้อ 4 ผิดครับ เลขมันคือ 5 5 ดังนั้นดูปุ๊บน่าจะตอบได้เลยว่าถ้าแบ่งให้เลขเท่ากันก็แบ่ง 5 กับ 5 สิ แต่โปรแกรมผมมัน error ครับ เพราะจำนวนขนมไม่พอแบ่ง เลยต้อง fix คำตอบไป (บรรทัด 39-41)

ทีนี้มาถึง large set ครับ โปรแกรมเดิมประมวลผลไม่ทันครับเพราะ permutation เยอะมาก ผมพยายามปรับหลายๆ ส่วนก็ไม่ได้ ก็เลยหันไปเลือกใช้มอดูล multiprocessing แทน เพราะมอดูล threading นั้น ผมสังเกตว่าต่อให้แตกไป 100 thread โปรแกรมก็รัน 100% CPU 1 Core อยู่ดี เลยแตกไปข้อละ process แล้วให้แต่ละโพรเซส แตกตัวหา permutation เป็น thread (เช่น เลือกขนมทีละ 2, 3, 4, 5 ชิ้น ก็เป็น 4 thread ส่วนแต่ละข้อจะเป็น process) ทำให้มัน launch ถึง 100+ process แต่ละโพรเซสมี 40-100 thread ครับ (thread ระบบตอนนั้นสองพันกว่า จากปกติ 600 กว่า) ปรากฎว่า คอมค้างครับ รัน small set ได้ปกติ คำตอบถูก แต่พอ large set เครื่องค้างหาคำตอบไม่ได้ครับ

แข่งจบ ผมเพิ่งไปดูของคนอื่นครับ เค้าใช้ bit shift เข้ามาแก้ อันนี้ผมก็ไม่รู้เรื่องเพราะไม่เคยไปยุ่งกับ binary ครับ (น่าจะเป็นครั้งแรกๆ ที่ผมเข้ามายุ่ง binary เลย) สำหรับข้ออื่นๆ ผมไปดูเค้าก็จะใช้อะไรที่มัน optimize มากกว่านี้

เจอกันรอบสองนะครับ ถ้ามีข้อไหน step-by-step หรือ brute force ได้อีก 🙂

Don’t even try, feels like a trial

ไอ้เห้นท (@ihearNoth) มันเชียร์ให้เขียนอยู่นานแล้ว ก็เพิ่งได้มาเขียนหลังจากเขียน recommendation ใน Steam ไป

ผมเล่นเกมแครกเยอะมาก เยอะกว่าเกมแท้ (แน่นอน) แต่ Portal 2 เป็นเกมนึงที่ผมยอมจะจ่ายตังก่อนจะได้เล่นเลย เพราะมันเป็นเกมที่น่าเชื่อได้ว่าจะดีด้วยเหตุผลหลายประการ

1. ชื่อของ Valve ประกันคุณภาพอยู่แล้ว ผมเสพติด FPS สไตล์ Valve และผมจะไม่ชอบ FPS สไตล์ทั่วไป จุดเด่นของ Valve คือเกมมันจะง่ายแบบปัญญาอ่อน โดยเฉพาะปืนที่มันโหลดเป็นนัด ท่าโหลดใส่เป็นแม็กกาซีนแต่ก็นับนัดได้ ทำให้ไม่ต้องลังเลเวลาโหลด แล้วก็เกมมันจะ Linear โคตรๆ เพราะกลัวคนเล่นหลง​ (ใน commentary ของ Left 4 Dead จะบอกไว้ว่าทำด่านซับซ้อนแล้วคนเล่นจะหลง) และยังมี no-return area เยอะมากทำให้เราไม่เดินวกไปวนมา เรียกได้ว่าทุกเกมมันแพ้ชนะกันที่ฝีมือการเล่นและการแพ้ puzzle ล้วนๆ การออกแบบเกมไม่มีผล
2. เกมเลข 2 Valve ทุกเกมไม่ผิดหวังครับ ถ้านับดูก็จะมี Team Fortress 2 ที่ออกมาตั้งหลายปีแล้วยังมีอัพเดตอยู่เรื่อยๆ, Left 4 Dead 2 ที่แพทช์รอง TF2 เลย ส่วนเกมภาคต่อที่ไม่มีเลข 2 ก็แทบจะถูกทิ้งร้าง อย่าง Half-Life: Source, Day of Defeat: Source (มีใครรู้จักมั้ย), Counter-Strike: Source ทำให้ผมเชื่อได้ว่าซื้อมาแล้วจะไม่ถูกปล่อยทิ้ง
3. Coop
4. ARG

แต่สุดท้ายก็ไม่ได้ซื้อก่อนหรอกครับ เพราะว่าในไทยดันขายถูกกว่าครึ่ง และร้านประจำของผมอย่าง Zest ก็ไม่มี pre-order (แต่ดันให้มี preorder Darkspore ก่อนวันนึง) ที่จะต้องซื้อกับ zest เพราะผมมี e-cash ค้างอยู่ 400 กว่า เนื่องจากมันเลิกขายบัตร RuneScape (UGC) ไป เมลไปทวงก็บอกแต่ว่าจะหาบัตรเทียบเท่ามาขาย​​(นั่นคือ zynga card แต่ไม่เห็นจะเทียบเท่าตรงไหน)

Portal 2 ไม่ใช่แค่ว่าประสบการณ์เล่นเกมจะอยู่เฉพาะในเกมนะครับ แต่รวมไปถึงประสบการณ์ก่อนเกมออกในส่วนของ ARG (Alternate Reality Game) ด้วย ซึ่งมี Potato sack pack มาขายในราคาพอๆ กับเกม​ (หลังจากจบ ARG แล้วผมเสียดายที่ไม่ได้ซื้อ แต่ก่อนนั้นผมไม่คิดจะซื้อเพราะมันแพงมากกับเกมที่ไม่รู้จัก) โดยมี puzzle ออกมาทั้งในเกมและใน Social media ซึ่งระหว่างสามสัปดาห์นี้ผมนั่ง refresh valvearg.com ทั้งวัน ดึกดื่นก่อนนอนก็ต้อง refresh ก่อน และเมื่อถืงในส่วนของเฟสสุดท้าย คือ [GLaDOS@Home](http://aperturescience.com/glados@home/) ผมก็ทำ [@gladosAtHome](http://twitter.com/gladosAtHome) ซึ่ง follower สองวันกว่าก็ 400 กว่า เล่นเอา follower ผมหนาวๆ ร้อนๆ ไปเลย และในช่วงนี้ก็มีคนบริจาค Defense Grid ให้ผมเล่น ซึ่งเล่นแล้วก็รู้สึกว่าเกมนี้ทำได้ดี และสำหรับใครที่เล่น puzzle ในเกมเหล่านี้ผ่าน​​ก็จะได้มันฝรั่งติด profile ซึ่งมันจะเป็นตัวคูณใน GLaDOS@Home ทำให้มีคนทำสูตรออกมาหลายประเภท ตั้งแต่ autosolver (Cogs) ตัดเพลง (Audiosurf) savegame (Defense Grid) หรือแม้แต่แก้ไฟล์เกม ที่คนเขียนเค้ารัน checksum แต่ดันพลาดไปรันเฉพาะตอนเปิดเกม (Amnesia มั้ง) และใครที่เล่นผ่านทุกเกมจะได้มันฝรั่งทองติดถาวร (ณ​ ตอนนี้) และยังได้รับ Valve Complete Pack อีกด้วยครับ (ราคาน่าจะสักสองสามเท่าของ Potato sack)

ทีนี้มาถึงของ Portal 2 มันมาในซองครับ ผมยังตั้งข้างๆ อยู่ไม่เอาไปเก็บเพราะซองมันใหญ่ ไม่รู้จะไว้ไหน คือถ้าเป็นกล่อง​ โอเค ผมเก็บกล่องไว้เยอะแยะ StarCraft 2 ยังตั้งอยู่ได้ แต่อันนี้มันยังไง และก็ของข้างใน ถือว่าพอรับได้ แต่ถ้ามองว่าจ่ายเพิ่ม 200 ไม่เอากล่องดีๆ มาเอาของแถม ผมว่าไม่อะ (คนอื่นๆ ก็มองแบบนี้อยู่หลายคนครับ แต่ผมจะคิดเสียว่า 200 เป็นค่า early adopter แล้วกัน เหมือนว่าเสื้อตัวใหม่ขายแพง ทิ้งไว้สักพัก SALE ลด 50% อะไรอย่างนี้)

สำหรับตัวเกม puzzle บางอันทำผมนั่งจ้องอยู่ ผมพยายามเล่นไม่ดูบทสรุปและทำได้สำเร็จยกเว้นใน Coop ครับ โดยใน Single player มันออกแบบตามสไตล์ Valve อยู่แล้ว คุณไม่มีทางหลงไปนอก puzzle ได้ ผมก็เลยใช้เวลาสำรวจอะไรๆ หน่อย ก็ใช้เวลาเล่นกันกว่าครึ่งวันครับสำหรับในรอบแรกสุด แต่ถึงจะสำรวจดีๆ แล้วผมก็ยังพลาด Portrait of a Lady กับ Exile Vilify สองสิ่งไม่ควรพลาดในเกม (มีคนบอกว่า และผมก็เห็นด้วยว่า Exile Vilify ใน YouTube กับในเกมมันเพลงเดียวกัน แต่ไม่เหมือนกัน) สำหรับในรอบที่ผมได้แผ่นมาแล้วเล่นเก็บ achievement ใช้เวลาประมาณ 3.5 ชั่วโมงครับ เก็บได้ไม่ครบต้องเล่นซ้ำบางด่าน​ โดยอันที่ผมพยายามมากสุดก็คือ Overclocker และอันที่ไม่น่าพลาด (เล่นรอบแรกผมควรจะได้) คือ Door prize ครับ

มีคนแนะนำว่า Portal 2 เป็นเกมที่เราโดดเดี่ยวอยู่กับหุ่นใน Aperture Laboratories ดังนั้นควรจะปิดไฟเล่น ไม่ใช่เพราะเกมนี้น่ากลัวอย่าง Half-Life หรือ Dead Space 2 แต่เพราะเราจะได้สัมผัสถึงความโดดเดี่ยว และถึงผมจะเล่นกลางวัน แต่นั่งคนเดียวในที่เงียบๆ ก็ทำให้รู้สึกได้ถึงความโดดเดี่ยวนั้นครับ และแน่นอนว่า การได้ฟังสิ่งที่ “เป็นมนุษย์” อย่าง Exile Vilify ท่ามกลางป่าคอนกรีตนั้นมันย่อมรู้สึกวังเวงกว่าการฟังใน YouTube แน่นอน (ในเกมจะมีเสียงการทำลายล้าง เหล็กเสียดสี ดังเป็นพื้นหลังเรื่อยๆ)

มาถึงในส่วนของ coop ก็ถือว่าเป็นประสบการณ์ที่สนุกนะครับในการแก้ปัญหารอบแรก ติดไปด้วยกัน ผ่านไปด้วยกัน แต่ข้อจำกัดของ Portal ทั้งในโหมด sp และ mp คือ replayability เวลาผมเล่นรอบสองจะไม่ชอบมากๆ ถ้าเพื่อนร่วมทีมเล่นไม่ดี คือ ping เฉลยให้หมดแล้วแต่ไม่สามารถทำได้ ถึงมันจะเกิดจากการ lag มันก็ไม่สนุกที่จะนั่งกดปุ่มรัวๆ ให้เพื่อน และก็ การเล่นซ้ำมันจะทำให้เพื่อนร่วมทีมที่ไม่เคยเล่นไม่สนุกเหมือนตอนเราเล่นใหม่ทั้งสองคนครับ ตรงนี้เป็นจุดที่ไม่น่าจะสามารถแก้ได้สำหรับเกม puzzle เพราะถ้าทำ procedural generation แบบ Left 4 Dead 2 puzzle มันจะไม่สนุก เหมือนเป็น filler มากกว่า

Meme ในเกมนี้ ผมยังไม่เห็นแนวโน้มอะไรมากกว่าเอาคำพูดมา ซึ่งก็ยังไม่เห็นว่าคำไหนจะฮอตฮิตนะครับ แต่ ประตู cake ทำผมนั่งอ่านด้วยความงงอยู่ว่า ไหนว่าไม่มี Cake​ (ผมอ่าน commentary ก่อนเล่นเกมครั้งแรกครับ) แล้วนี่อะไร surprise?

สำหรับเพลง ระหว่างรอโหลดเกมผมฟัง Re: Your Brains ของ Jonathan Coulton ผู้แต่งทั้ง Still Alive และ Want you gone และผมไม่เคยฟัง Want you gone มาก่อนเลย พบว่าเพลงมันคนละโทนกับ Still Alive ออกจะสดใสกว่า แต่ฟังแล้วไม่รู้สึกว่าเจ๋งเท่ากับ Still Alive และ Re: Your Brains มันยังติดหูอยู่ ส่วนเพลงอย่าง Exile Vilify นี่ผมเปิดฟังเป็นสิบๆ รอบ มันสื่ออารมณ์ได้ทั้ง Portal และชอบที่มันใช้คำที่ความหมายหนักสื่ออารมณ์

**สรุป** ถ้ามองอย่างเกม Portal 2 ไม่คุ้มครับ เกม multiplayer ผมจะยินดีซื้อเพราะมันสามารถเล่นได้ไม่รู้จบ แต่ Portal 2 ไม่ใช่ ดังนั้นต้องมองว่า Portal 2 เป็นหนัง คุณสามารถเข้าชมได้ในราคา 899 พร้อมของแถมติดมือกลับบ้าน และชมซ้ำฟรีได้แต่คุณจะรู้พล็อตหนังหมดแล้ว (แต่แน่นอนคุณจะต้องกลับไปดูซ้ำเพื่อหาจุดเล็กๆ ที่ผู้สร้างใส่เอาไว้ และเก็บรายละเอียดต่างๆ เพื่อรู้ลึก รู้จริงเกี่ยวกับหนัง)

แต่เอ่อม ผมเสียค่าเครื่องคอมใหม่มาเล่น Portal 2 ด้วยอะ :3 หวังว่ามันจะทำให้เล่นเกมใหม่ๆ ได้ไปอีกหลายปี

ปล. หลายๆ part ใน entry นี้เก็บมาเขียนจากที่อ่านใน youtube และ steam forum

ปล2. แต่ถึงจะดูหนังก็เถอะ ตั๋วหนังสี่รอบมันยังไม่แพงเท่า Portal 2 เลย