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 ได้อีก 🙂

NSC 2011 project

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

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

ถัดมาผมบอกเพื่อนว่าจะทำ Greenscreen บน Kinect ซึ่งต่อมาผมไปค้นรายละเอียดก็ปรากฎว่ามีคนทำแล้ว ก็โยนทิ้งไปเพราะยังไม่มีไอเดียที่จะปรับปรุงดีกว่าเค้า

ต่อมาผมจะพัฒนาโปรแกรม ซึ่งถ้าใช้ Windows แทบจะไม่มี open source, Linux มันจะไม่สวยงาม และ Mac ก็มีทั้งสวยงาม และ open source นิดๆ เลยซื้อ MacBook Pro มา *(ชอบทัชแพดมันด้วยแหละ แล้วก็อยากอัพเกรดคอมแล้ว)* ปรากฎว่า XCode ง่ายกว่าที่คิด แต่ยังไม่เข้าใจ คิดว่าจะทุบ project นี้ทิ้งแล้วหาไอเดียใหม่

ปัญหาคือ เดือนหน้าผมต้องเริ่มงานให้แล้วเสร็จในหนึ่งเดือนแล้ว นี่ไอเดียยังไม่มีเลย :3

ก็แปลก NSC โปรแกรมประยุกต์นักเรียน ไม่มีใครใช้อุปกรณ์อะไรแปลกๆ หรือเทคโนโลยีสมัยใหม่เลย เหมือนว่า Mobile Web ผมจะเป็นอะไรที่ดูแปลกใหม่นะ แต่ก็ยังไม่ใช่ที่ต้องการของกรรมการ (แต่สำหรับผมแล้วมันคืออะไรที่สะดวกในการใช้งานมาก)