HLP Hackathon 2011 r1

ก็จบไปแล้วนะครับกับรอบแรกของ [HLP Hackathon 2011](http://www.hlphackathon.com) สำหรับโจทย์รอบวันเสาร์ถือว่าอ่านแล้วเข้าใจยากมาก คือมันอธิบายคลุมเครือ ผมนั่งอ่านอยู่หลายรอบกว่าจะเข้าใจ คำสำคัญมันคือสูตรนั่นแหละครับที่ว่า `width*width*4*2` ถ้าใครถอดกลับเป็น width ได้ (มันคือคณิตศาสตร์ม. ต้น `fileSize = width*width*4*2`) ก็แทบจะเรียกได้ว่าทำได้ ส่วนที่เหลือ Python-Imaging (PIL) ทำงานแทนให้เราเกือบหมด

ทีนี้ตอนส่งรอบ Noob เรานั่งอ่านตัว file ที่สองไปทีละไบต์แล้วก็รัน ord มา ซึ่งแน่นอนจะเจอ bytecode แปลกๆ แต่เราพบว่ารันเฉพาะ bytecode ที่มันมีค่าให้หมุนภาพก็ส่งผ่านแล้ว (และทำให้เข้ารอบเลย) ต่อมาก็พยายามจะทำรอบ Pro เลยดัดแปลงต่อ (ผมถึงไม่มีของ noob มาโชว์) โดยอ่าน bytecode จริงๆ จังๆ มี hash แต่เหมือนการจับ hash ผมผิดมันเลยไม่ผ่านระดับ Pro โค้ดที่เหลือก็ได้เท่านี้ครับ

(โค้ดนี้เอาไปรับกับด่าน Noob แล้วจะ error สงสัยผม port มาผิดเพราะตัว if เดิมมันรันในฐานสิบ แต่ตอนนี้มันรันใน string ฐานสอง)

ทีนี้ของข้อวันพฤหัส พ่อไม่ให้นอนดึก ผมเลยรีบเล่นในเวลา 30 นาทีก็เรียกได้ว่าเขียนเสร็จแล้ว แต่มันบั๊ก (โจทย์พวกนี้ถ้าบั๊กผมแก้ไม่ถูกหรอกครับ เหมือนข้อ Pro ตะกี้)

เหมือนจะมีอะไรมากกว่านี้ แต่ลืมๆ ไปละ พอแค่นี้ก่อนแล้วกัน เจอกันเสาร์หน้าถ้าว่าง (มันช่วงสอบ)

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