Online Judge (grader) design

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

ในภาคซอฟต์แวร์จะมีกิจกรรมอยู่อันนึงครับคือ SOSCamp เป็นการติวโปรแกรมมิ่งให้น้องใหม่ซึ่งก็จะมีการทำโจทย์ พอทำโจทย์ก็ต้องมีระบบตรวจ เพื่อนรีเควสมานานมากกกแล้วว่าอยากรู้ design ของระบบก็เลยเขียนสักหน่อย

## Overall

ระบบแบ่งเป็น 3 ส่วนครับคือ UI, API, Grader ซึ่งผมเลือกเป็น PHP หมดเลยเพราะช่วงนั้นเห่อ [Laravel](http://laravel.io) และ [Silex](http://silex.sensiolabs.org) นิดๆ และถ้ามีคนจะช่วยทำ ใช้ Silex บน PHP น่าจะง่ายกว่าใช้ Django โดยเฉพาะคนที่เขียน Java มา คือ Silex ค่อนข้างจะ low level มาก เขียนอะไรๆ มันจะตรงไปตรงมาไม่มีลัดเท่าไร แล้วก็ PHP Class มันหน้าตาเกือบ Java ตัด type

## UI

ตัว UI เขียนด้วย AngularJS ทั้งหมดเลยเพราะผมอยากลองเล่น [AngularJS](http://angularjs.org) พอดี เขียนเสร็จก็เรียนรู้มันไปเยอะแต่รู้สึกว่ายากอยู่ ตอนหลังมารื้อทำใหม่แล้วเอาระบบ resolve ออกพบว่าเขียนง่ายขึ้นเป็นกอง

ด้วยสไตล์ของ Angular อยู่แล้ว ตัว UI ทั้งหมดออกแบบเป็นแบบ single page app คือมี HTML file เดียวรันทุกอย่าง ไม่มีการเปลี่ยนหน้าใดๆ นอกจากการใช้ AJAX ดึงข้อมูลมาแสดง ตรงนี้การเลือกใช้ Angular + Angular-ui-router ทำให้เขียนง่ายและดีมากๆ

ข้อดีอย่างนึงของการทำ Single page app คือมันบังคับให้ทุกอย่างเป็น API พอจะทำใหม่ก็ทำได้ง่ายๆ แค่เขียนตัวครอบ API ขึ้นมาใหม่ จบ

## API

ฝั่ง API ใช้ Silex ครับ ผมลองเขียนแบบ OOP ดูโดยทำคลาสที่สามารถ extend มันมาแล้วระบุชื่อ Eloquent model และ URL (Eloquent เป็น library สำหรับต่อ database ของ Laravel ซึ่งผมดึงมาใช้เดี่ยวๆ ไม่เอา Laravel มาทั้งตัว เป็น ORM ตัวเดียวใน PHP ที่ผมชอบ) จะได้เป็น API ที่สามารถ List, read, write ลง database ได้ทันทีพร้อมระบบ access control ซึ่งก็ลดเวลาพัฒนาไปได้มาก ตอนหลังผมแกะระบบตัวนี้ไปใช้ในระบบลงทะเบียนงานบายเนียร์ด้วย วันเดียวก็เขียนระบบเสร็จ

## Grader

ส่วนสำคัญที่สุดของโปรแกรมแน่นอนว่าต้องเป็นตัวเกรดเดอร์เอง ซึ่งตัวเกรดเดอร์นั้นใช้ไลบรารีหลายตัวช่วยในการพัฒนา (ผมคิดว่าบางตัวเป็น extra ไม่ใช้ก็ได้ แต่ใช้แล้วมันทำให้โปรแกรมเท่ขึ้น พวก Symfony/Console Symfony/Process พวกนี้)

ตัว grader จะต่อเข้ากับคิวงานกลาง ซึ่งระบบเก็บคิวงานที่ผมใช้คือโปรแกรม beanstalkd และใช้ library pheanstalk เพื่อเชื่อมต่อจาก PHP เมื่อมีการส่งงานเข้ามาใน API ก็จะโยนรายละเอียดงานเข้าไปใน beanstalk

ตัว grader ที่ต่อกับคิวงานนั้นจะมี infinite loop รับงานใหม่อยู่ เมื่อได้รับงานแล้วก็จะเข้าสู่ logic ในการตรวจ ซึ่งจะมีกระบวนการคือ

### 1. รันโค้ด generate test case

ตัวระบบ test case generator ผมอยากให้มันทรงพลัง สุ่มโจทย์ได้ และเป็นธรรมชาติที่สุด ก็เลยใช้วิธีเขียนโปรแกรมมาครอบโปรแกรมที่ใส่ไว้ในโจทย์ ข้อเสียคือรองรับการส่งได้แค่ภาษาที่มีโปรแกรมครอบ

หน้าที่ของโปรแกรมครอบไม่ยากครับ ขั้นแรกโปรแกรมจะ include โปรแกรมที่โจทย์กำหนดเข้ามา (ใน Java ใช้ reflection, Python ใช้ exec ซึ่งผมว่าไม่ดีเพราะ \__name__ มันไม่เปลี่ยน, PHP ใช้ include) ทีนี้ขั้นต่อมาจะแยกตามภาษา

– **PHP:** มันคือ `echo json_encode(run());` นั่นล่ะครับ
– **Java:** มันจะส่ง `LinkedList` เข้าไปโดย pass by reference แล้วเอา LinkedList ตัวนั้นส่งเข้า GSON ออกมา
– **Python:** ผมจำไม่ชัวร์แต่น่าจะประมาณว่าเอา for in วนเพื่อทำเป็น list แล้วโยนใส่ `json.dumps`

จริงๆ มันก็ดูไม่ช่วยเท่าไรนะ แต่ผมว่า python เนี่ยมันเขียนสนุกดีตรงที่ `yield` รัวๆ ไม่ต้องเอาข้อมูลไปพักใส่ array อะไรแล้ว return ออกมาทีเดียวเหมือนภาษาอื่นๆ (PHP ก็มี yield แต่มันใหม่เกินไป)

### 2. คอมไพล์โค้ดเฉลยและโค้ดคำตอบ

มาถึงขั้นตอนสำคัญครับคือการคอมไพล์โค้ด ซึ่งก็ไม่มีอะไรยากเท่าไรคือรัน compiler ตามแต่ภาษาแล้วให้มันออกมาที่ไฟล์ที่กำหนดก็เสร็จ แต่ความยุ่งยากอยู่ที่ Java ซึ่งชื่อคลาสจะต้องเป็นไปตามชื่อไฟล์ด้วย ผมก็เลยใช้วิธีโกงๆ คือตั้งชื่อไฟล์ว่า Input.java แล้วคอมไพล์ ถ้ามันผ่านก็จบ ไม่ผ่านตัว `javac` จะบอกมาว่า should be named ….java ก็ให้โปรแกรมมันอ่าน error ตัวนี้ไปแล้ว rename file ให้ (และเก็บชื่อคลาสไว้ด้วยเพราะตอนรันต้องใช้)

### 3. Run

ขั้นตอนการรันก็รันแบบตรงไปตรงมาครับ ทีนี้จะพูดถึงเทคนิคการ sandbox หรือป้องกันความปลอดภัยของโค้ดสักหน่อย ซึ่งจริงๆ มันทำงานมาตั้งแต่ส่วน generate test case แล้ว

ตัว grader จะใช้โปรแกรม docker ในการรันครับ ซึ่งหลักการคร่าวๆ ของ docker มันคือการใช้ความสามารถ namespace, cgroup ของ linux kernel ใหม่ๆ ช่วยแยกการทำงาน คนที่อยู่ namespace อื่นๆ จะมองไม่เห็นกันเอง แต่ข้างนอกสุดมองเห็นข้างในได้ นอกจากนี้มันยังสามารถกำหนดทรัพยากรให้ cgroup ได้อีกด้วย (คล้ายๆ virtualization แบบ virtualbox อะไรพวกนี้อะครับ แต่มัน overhead ต่ำกว่ามากเพราะรันอยู่ใน kernel ตัวเดียวกันเลย)

ข้อดีอย่างนึงของ docker คือสภาวะข้างในมันคงที่ถ้าเราก๊อปไป นั่นหมายความว่าถ้าเราเซตดีๆ version ของ compiler, runtime, library จะเหมือนกันหมดเลยถึงเราจะกระจาย grader ไปหลายๆ เครื่องก็ตาม

ทีนี้เวลารันด้วยความสามารถจำกัดทรัพยากรก็ทำให้สะดวกโยธินในการจัดการแล้วครับ

– memory limit บังคับด้วย cgroup ได้เลยตรงๆ
– networking ก็บังคับได้เลยว่าไม่ให้มีการ์ดแลน
– time limit อันนี้ใช้ symfony/process จับเวลาเอา ถ้าเกินแล้วก็สั่งให้ docker kill ทิ้ง
– privileges ก็สั่งให้ docker รันใน user ปกติ (ปกติ docker จะรันด้วย root) ก็เรียบร้อย

### 4. Cleanup

เสร็จแล้วก่อนจะจากก็ต้องลบไฟล์พวกที่เป็นผลจากการคอมไพล์ต่างๆ และตัว container ออก (ใส่เข้ามาทีหลังตอนเทส fork bomb ดู) เป็นอันเสร็จ

### 5. Submit

ตัว grader จะส่งงาน 2 รอบคือตอนที่ได้งานมา (เพื่อแสดงสถานะ grading) และเมื่อเสร็จแล้วจะส่งข้อมูลกลับเข้าไปใน API อีกครั้งหนึ่ง ซึ่งก็เป็น JSON ธรรมดา โดยอาศัยการยึนยันตัวแบบ shared secret คือ API, grader จะมี string ตัวหนึ่งเปรียบเสมือนรหัสผ่านที่ต้องส่งให้ API ทุกครั้งที่จะอัพเดตสถานะงาน

## อื่นๆ

จริงๆ แล้วไม่ใช้ docker ก็ได้นะครับ เช่น elab ใช้โปรแกรม box ถ้าผมจำไม่ผิดมันจะใช้ความสามารถ ptrace คือเมื่อโปรแกรมลูกมีการเรียกฟังก์ชั่นของระบบ โปรแกรมแม่ (นั่นคือ box) จะถูกถามว่าอนุญาตหรือไม่ก่อนที่จะทำงานได้ (chrome เก่าๆ รู้สึกว่าจะใช้เทคนิคนี้เหมือนกันบนลินุกซ์) ตอนหลัง box มีรุ่นใหม่คือ isolate ซึ่งก็ใช้ cgroup เหมือนกัน แต่ผมเดาว่าน่าจะ overhead น้อยกว่า docker

(ผมไม่ได้เช็ค fact ตรงนี้นะ ไปค้นดูละเอียดๆ เองดูก่อนถ้าจะลองทำดู)

หรือจะใช้วิธีดิบเถื่อนรันไปตรงๆ เลยก็ได้ ซึ่งผมเดาว่ารุ่นพี่คงจะใช้กันเพราะมันเขียนง่ายดี แต่อาศัยความเชื่อใจว่าจะไม่มีใครส่งอะไรน่ากลัวเข้าไปในระบบ ยิ่งบางทีไม่ได้เขียน time limit ไว้ด้วย ส่ง infinite loop เข้าไปก็เรียบร้อย

ผมคิดไว้ทีนึงว่าวิธีนึงที่ทำให้มันเร็วขึ้นคือรัน docker แช่ไว้เลยแล้วข้างในมีโปรแกรมที่เขียนในภาษานั้นๆ แล้วข้างนอกแค่บอกให้รันโค้ด ซึ่งมันจะตัด overhead เรื่องการ start, stop ตัว docker และ runtime ของภาษานั้นๆ ไปได้พอสมควรเลย แต่ข้อเสียคือเรื่อง memory leak และการ limit ต่างๆ จะทำได้ยากกว่า ใน source ของ grader จะมีคลาส EnhancedJava อยู่ซึ่งผมก็ใช้หลักการตรงนี้ แต่เขียนไม่เสร็จเพราะเขียนๆ ไปแล้วนึกถึงเรื่องการจับ limit นี่แหละแล้วคิดว่าเลิกทำดีกว่า ให้ผมคุมเองน่าจะมีปัญหา security ตามมาแหงๆ

Codejam 2013 Qualification Round

ก็ผ่านไปแล้วนะครับกับ Codejam 2013 รอบคัดเลือก ปีนี้กฎค่อนข้างโหดคือ 35 คะแนน ซึ่งปกติคะแนนผมก็น่าจะเกินแหละแต่โจทย์มันยากขึ้นด้วยก็เลยต้องระวังตัวหน่อยๆ

# Tic Tac Toe Tomek

เกม XO แบบสี่แถวครับ ให้กระดานมาถามว่าใครชนะ ยังเล่นไม่จบ หรือ เสมอ

โค้ดผมใช้ [cjlib](https://github.com/whs/cjlib) นะครับ เพิ่ง open source เมื่อวาน เขียนไว้ตั้งแต่โค้ดจมรอบซ้อมมือ เอาไว้รับ input และข้อไหนจะโหดก็ใช้ multiprocessing ขยายให้ใช้ CPU 8 core ให้คุ้มได้ (ผมเซต default mode เป็น thread ด้วย แต่เอาจริงๆ ก็ไม่ค่อยช่วยเท่าไรเพราะติด global interpreter lock อยู่ดี)

ข้อนี้โปรแกรมมันหา​ “XXX” “OOO” + “T” ในแถวนึง ถ้าเจอก็คือชนะ ถ้าไม่เจอก็พลิกกระดานหาอีกที แล้วก็ลองเช็คทะแยง นี่ถ้ามันเอา XXX สามตัวนี่ทะแยงเขียนกันสนุกเลยครับ

Algorithm หมุนกระดาน ผมตั้งใจจะหมุนตามเข็มนะครับ แต่มันดันหมุนแบบ flip horizontal + flip vertical ซึ่งก็โอเคไม่มีปัญหาใช้ได้เหมือนกัน

ปรากฏว่า ผมพลาดข้อ Large ไปได้ยังไงไม่รู้ พอเช็คกับโปรแกรมคนอื่นมาเจอ OOTO *speechless*

ปกติในรอบคัดเลือก Codejam ตัวเทสเคสจะช่วยเราดักบัีกพวกนี้นะ แต่ปีนี้ไม่ช่วยกันเลย

# Lawnmover

[ถ้าชีวิตกูต้องเจอเรื่องแบบนี้ กูไปตัดหญ้าดีกว่า](https://www.facebook.com/pages/%E0%B8%96%E0%B9%89%E0%B8%B2%E0%B8%8A%E0%B8%B5%E0%B8%A7%E0%B8%B4%E0%B8%95%E0%B8%95%E0%B8%A3%E0%B8%B9%E0%B8%A7%E0%B8%A7%E0%B8%A7%E0%B8%A7%E0%B8%A7%E0%B8%A7%E0%B8%A7%E0%B8%A7-%E0%B8%95%E0%B9%89%E0%B8%AD%E0%B8%87%E0%B9%80%E0%B8%88%E0%B8%AD%E0%B9%80%E0%B8%A3%E0%B8%B7%E0%B9%88%E0%B8%AD%E0%B8%87%E0%B9%81%E0%B8%9A%E0%B8%9A%E0%B8%99%E0%B8%B5%E0%B9%89%E0%B8%99%E0%B8%B0-%E0%B8%95%E0%B8%A3%E0%B8%B9%E0%B9%84%E0%B8%9B%E0%B8%95%E0%B8%B1%E0%B8%94%E0%B8%AD%E0%B9%89%E0%B8%AD%E0%B8%A2%E0%B8%94%E0%B8%B5%E0%B8%81%E0%B8%A7%E0%B9%88%E0%B8%B2/288729314481614) แต่เนื่องจากโปรแกรมเมอร์ดันมีเครื่องตัดหญ้าขั้นเทพครับกดทีเดียวเกรียนทั้งแถบ ส่วนคนตัดดันอยากตัดเป็นรูปพิสดารอีกต่างหาก เลยต้องมาดูกันว่าเครื่องตัดหญ้าที่ตัดเกรียนทั้งแถบจะทำรูปนั้นได้มั้ย

บางคนเค้ามี algorithm ที่ solve ได้เลยว่ามันตัดได้มั้ย แต่อย่างผมแล้วต้องบอกวิธีตัดได้ด้วยครับ ก็เลยใช้วิธีหาหญ้าสูงที่สุดที่ยังไม่ได้ตัด (`notFinishedList` จะทำให้แถวที่ตัดแล้วเป็น 0 เพื่อไม่ให้ `max` ไปเจอแถวนั้น จริงๆ ผมใช้ `max` มาตรฐานก็ได้ แต่เขียน myMax ไว้ตอนใช้ algorithm อีกอันที่ลบไปเลยแล้วเลยลืมเปลี่ยน) พอเจอแถวที่ไม่ได้ตัดแล้วก็ไถแถวนั้นให้สูงเท่่าที่ต้องการ แล้วก็ไถไปเรื่อยๆ ทั้งสองแนว

สังเกตฟังก์ชั่น `cutX`,`cutY` นะครับ `cutY` จะตัดไปในแนวแกน x ส่วน `cutX` ตัดไปในแนวแกน y เพราะชื่อฟังก์ชั่นบอกว่า input เป็น x หรือ y ครับ

จริงๆ ถ้าเขียนตัวหมุนกระดานได้แล้วผมใช้วิธีหมุนน่าจะไวกว่าเขียนแยก `cutX`/`cutY` แต่ข้อนี้เพิ่งตื่น

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

# palindrome

ข้อนี้ผมเขียนใหม่นะครับ ของเดิมไปโหลดจาก codejam ได้ ผมไม่ได้เซฟไว้

โจทย์ข้อนี้คือให้หาปริมาณของจำนวนที่เป็นพาลินโดรม และถอดรูทได้พาลินโดรมเช่นกัน (พาลินโดรมคือเลขที่อ่านจากหน้าหลังได้เหมือนกัน รวมถึงเลข 0-9 ทุกจำนวนด้วย เช่น 121 1441 400080004)

ข้อนี้เสียดาย Large-1 มากครับ ผมเพิ่งรู้ว่า Large ลองได้รอบเดียวแล้วจะล็อค ไม่งั้นคงได้คะแนนไปแล้ว

ตัวโปรแกรมที่ผมใช้ทำ small นั้นก็ไม่ยากครับ วิ่งจาก start – end ทีละตัวแล้วเช็คเงื่อนไข แต่พอข้อ large เลยมาใช้วิธีเขียน palindrome generator แทน (เขียนบนมอเตอร์เวย์ด้วย ^^)

ต่อมาผมเห็น @icez ลอง large-2 ก็เลยทำมั่ง​ โดยใช้วิธีที๋โคตรโกงที่สุดคือ เนื่องจากว่า palindrome มันสามารถรู้ล่วงหน้าได้ก็เลยเขียน offline generator ตั้งแต่ 1-1E100 รันไปตั้งแต่เที่ยงยันบ่ายสาม แต่โปรแกรมดันค้างซะอีก (เหมือนจะ overflow มั้ง ผมไม่ได้ debug ดู)

ก็คือ save-palins.py จะรัน fas.py (จากด้านบนที่ผมใช้แก้โจทย์) เสร็จแล้วผมเซฟลง file ชื่อ palins แล้วก็ fas-cache.py จะรันดูว่าใน range ที่กำหนดมีจำนวนในไฟล์ palins กี่จำนวน

แน่นอนว่าผิดครับ เพราะ 4000000008000000004 ไม่อยู่ในช่วงน้อยของจำนวนใดๆ ใน large input 2 เลย TT มันต้อง gen เยอะกว่านี้

(อันนี้ผมเขียนรีบไปหน่อย จริงๆผมควรตัดช่วง 1E100 เป็นช่วงย่อยๆ แล้วใช้ TaskRunner แยกกันไป gen palins ออกมา จะได้กระจาย 8 core ได้เต็มที่)

# Treasure

ข้อนี้คือเราจะมีกุญแจชนิดต่างๆ อยู่ตามที่กำหนด และเรารู้ว่าในหีบแต่ละใบใช้กุญแจชนิดไหนเปิด และมีกุญแจชนิดใดอยู่ข้างใน ถามว่าต้องเปิดหีบอย่างไรถึงจะเปิดได้ครบ​ (ถ้ามีวิธี)

ข้อนี้ดูน่าจะเป็นทฤษฎีกราฟครับ ผมงงกับเรื่องนี้คือโรงเรียนผมไม่มีสอน แต่โรงเรียนกวดวิชามีให้ลง ผมก็เคยลงแต่ลืมไปหมดแล้ว (ก็โรงเรียนไม่ได้สอบเลยอะ) และมันไม่มีเรื่องกราฟที่มีน้ำหนักขอบ

โปรแกรมแนวๆ นี้เคยลองกับโจทย์อีกข้อนึงที่มันชื่อหอฝึกยุทธครับ จำไม่ได้แต่เป็นโจทย์ภาษาไทย วิธีคิดก็คือ left-first search ลองมันทั้งหมดโดยไต่จากด้านซ้ายไปก่อน (โจทย์บังคับด้วยการบอกว่าต้องเอาเลขน้อยขึ้นก่อน)

ปรากฏว่ารัน small ไม่ทันครับ (เพิ่งเคยเจอครั้งแรกที่แก้ได้แล้วรัน small ไม่ทัน) และใน scoreboard ผมก็ไม่มีใครทันเลย

——-

สรุปคือไม่ได้ใช้ algorithm อะไรทั้งนั้นล่ะครับ คิดมือยังไงผมก็ทำแบบนั้นนี่แหละ แต่ optimize for multicore เต็มเหนี่ยว อิอิ

รอบนี้เข้ารอบด้วย 60 คะแนน, 14:37:06 (ถ้าไม่ทำ C-large + B ผมคงได้เวลาสองสามชั่วโมง แต่ตกรอบ น่าจะเอา B ไปทำก่อน C), Rank 11121