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

One thought on “Google Code Jam 2011 รอบคัดเลือก”

  1. อ่านเฉลยมาตกใจมากครับ

    • Gorosort คำตอบคือจำนวนเลขที่ไม่ได้เรียงอยู่ (ไว้รอบหน้าจะนั่งหา pattern มันก่อนทำ script)
    • Bot Trust มันมีข้อที่ใช้ 10k turn ด้วยครับ โปรแกรมผม limit ไว้ที่ 2000 เพราะเคยรัน infinite แล้วมันค้าง พอผมปลด limit ให้เป็นหลายล้านมันก็ถูกหมดเลย TT

Comments are closed.