Grid2010
หน้านี้สำหรับให้ข้อมูลเกี่ยวกับการพัฒนาโปรแกรมในการแข่งขัน Grid Innovation 2010
เนื้อหา
ประกาศ
- มี viewer ตัวใหม่ที่แสดงหิน/เป้าหมายเล็ก ๆ ได้
- รวมรูปการชนแบบต่าง ๆ
- เพิ่มข้อควรระวัง
- (13/2) เพิ่มตัวอย่างการจับเวลา และการสุ่มจุดเริ่มต้น
- (12/2 14:42) มีตัวอย่าง upload ไปเพิ่มเติมแล้ว download
- (12/2 12:14) ในการชนหินหรือวงกลม จะถือว่าชน ก็ต่อเมื่อระยะห่างของจุดศูนย์กลางกับน้อยกว่า r - ZERO โปรแกรม shoot ถูกอัพเดทให้ใช้เงื่อนไขตามนี้แล้ว
- ประกาศสูตรคำนวณเวกเตอร์ตั้งฉาก
- รับประกันว่าสิ่งของบนกระดานจะไม่ทับกัน และในการวางกระจกสะท้อนสำหรับระดับอุดมศึกษา ห้ามวางทับสิ่งของอื่น ๆ
- (12/2 10:58) มีการอัพโหลดโปรแกรม shoot เวอร์ชันใหม่ คัดลอกได้ที่ ~jittat_fa/shoot
- (12/2 10:42) มีการแก้ไขโจทย์ดังนี้
- หน้าสอง Y2 < Y1
- ปรับขนาดข้อมูลเข้า N < 1,000
- มีการแก้ตัวอย่างข้อมูลป้อนเข้า ดูตัวอย่างด้านล่าง
การส่ง
ให้คัดลอกแฟ้มข้อมูลลงในไดเร็กทอรี nanobirds ในโฮมไดเร็กทอรีของผู้เข้าแข่งขันเอง
โดยให้คัดลอกไฟล์ดังนี้
- ไฟล์โปรแกรม
- ไฟล์ที่คอมไพล์แล้ว
- script สำหรับรัน (ไฟล์ที่มีนามสกุล .sh)
- ไฟล์ชื่อ README เขียนอธิบายวิธีการรันคร่าว ๆ และรายละเอียดอื่น ๆ สำหรับทีมงานในการตรวจ
ข้อควรระวัง
- ในบางสถานการณ์ มุมหรือจุดเริ่มต้นมีผลต่อคะแนนมาก ในการพิมพ์ผลลัพธ์ ถ้าพิมพ์ด้วยความละเอียดไม่สูงพอ จะทำให้ไม่ได้คะแนนตามที่คำนวณไว้ ขอแนะนำให้ใช้ความละเอียดประมาณ 20 ตำแหน่งทศนิยม ในการพิมพ์พิกัดเริ่มต้นและมุมเริ่มต้น
- ควรระวังในการปัดเศษ ในการทดสอบว่านกชนวงกลมหรือไม่ ให้ทดสอบว่าระยะห่างระว่างเส้นจากเวกเตอร์ น้อยกว่ารัศมีมากกว่า ZERO หรือ
dist < r - ZERO
ไม่เช่นนั้นผลการจำลองของคุณอาจจะไม่ตรงกับของโปรแกรมตรวจ สามารถใช้โปรแกรม shoot เพื่อทดสอบได้ว่าโปรแกรมคุณให้ผลลัพธ์ใกล้เคียงกับโปรแกรมตรวจหรือไม่
การคำนวณ
การคำนวณเวกเตอร์สำหรับสะท้อน
ถ้าเรามีเวกเตอร์ เวกเตอร์ที่ตั้งฉากกับ คือเวกเตอร์ที่มีผล dot product กับ w เท่ากับ 0 หนึ่งในนั้นคือ
การจับเวลา
ใน Linux เราสามารถใช้ฟังก์ชัน gettimeofday ในการอ่านเวลาเพื่อจับเวลาได้ อ่านคู่มือ ฟังก์ชันนี้จะเขียนค่าลงใน struct timeval ซึ่งจะมี member หนึ่งคือ tv_sec ระบุเวลาที่ผ่านมาจากวันที่ 1 ม.ค. 1970 เป็นวินาที ซึ่งเรานำมาใช้เพื่อจับเวลาโปรแกรมของเราได้
ตัวอย่างโปรแกรมที่จับเวลาไม่ให้เกิน 10 วินาที (จะเลิกเมื่อถึง 9 วินาที) <geshi lang="c">
- include <sys/time.h>
- include <cstdio>
struct timeval tp_start, tp_now;
main() {
gettimeofday(&tp_start,NULL); while(true) { // // do some work // gettimeofday(&tp_now,NULL); if(tp_now.tv_sec >= tp_start.tv_sec + 9) break; }
} </geshi>
การสุ่ม
ใน unix เรามีฟังก์ชัน rand สำหรับสุ่มตัวเลข ฟังก์ชันดังกล่าวจะคืนค่าเป็นจำนวนเต็มที่มีค่าระหว่าง 0 ถึงบางค่าที่มากกว่า 32767 ออกมา ในการใช้งานเราจะต้องนำค่าดังกล่าวไปหารเอาเศษด้วยขอบเขตของการสุ่มที่เราต้องการ
ตัวอย่างเช่น ถ้าเราต้องการค่าสุ่มระหว่าง 0 ถึง 3 เราจะสั่ง
rand() % 4
เราจะได้ค่าระหว่าง 0 ถึง 3
ก่อนจะใช้ฟังก์ชันดังกล่าว เราจะต้องใส่ seed หรือค่าเริ่มต้นสำหรับการสุ่มให้กับไลบรารีเสียก่อน ผ่านทางฟังก์ชัน srand เราจะต้องกำหนดค่าที่ไม่เหมือนเดิมให้กับฟังก์ชัน srand ไม่เช่นนั้นค่าสุ่มที่เราได้จะซ้ำ
วิธีหนึ่งที่ทำได้คือใช้ค่าเวลาปัจจุบัน ซึ่งสามารถอ่านได้ด้วยฟังก์ชัน time หรือจะใช้ค่าที่อ่านจากฟักง์ชัน gettimeofday ก็ได้
ตัวอย่างการกำหนดค่าเริ่มต้นให้กับการสุ่ม
<geshi lang="c">
- include <sys/time.h>
struct timeval tp_start;
main(int argc, char* argv[]) {
// .... gettimeofday(&tp_start,NULL); srand(tp_start.tv_sec);
// ...
} </geshi>
ควรระวัง: ฟังก์ชัน srand ให้เรียกครั้งเดียวเท่านั้นในโปรแกรม
การสุ่มจุดเริ่มต้นและทิศทางของนก
ฟังก์ชันด้านล่างเป็นตัวอย่างฟังก์ชันที่สุ่มจุดเริ่มต้นของนกที่ด้านใดด้านหนึ่งของกระดาน แล้วให้นกวิ่งเข้ามาด้านในแบบตรง ๆ
<geshi lang="c"> void random_start(double *x, double *y, double *dx, double *dy, double min_x, double max_x, double min_y, double max_y) {
int dir = (rand()>>2) % 4; int dir_array[][2] = { {0,-1}, {-1,0}, {0,1}, {1,0} }; if((dir==0) || (dir==2)) *x = min_x + rand() % (int)(max_x - min_x + 1); else { if(dir==1) *x = max_x; else *x = min_x; } if((dir==1) || (dir==3)) *y = min_y + rand() % (int)(max_y - min_y + 1); else { if(dir==0) *y = max_y; else *y = min_y; } *dx = dir_array[dir][0]; *dy = dir_array[dir][1];
} </geshi>
รูปแบบของแฟ้มข้อมูล
แฟ้ม input
ตัวอย่าง
-30 30 30 -30 10 5 5 4 0 0 -10 9 0 15 -10 5 0 24 0 5 0 5 0 1 1 7 0 1 2 9 1 1 1 11 1 1 2 13 1 1 2 15 1 1 1 1
แฟ้ม output
แฟ้มเก็บวิถีวิ่ง birds.rays
เพื่อแก้ปัญหาการคำนวณเพี้ยน ผู้เข้าแข่งขันสามารถส่งแฟ้ม birds.rays มาเพื่อให้ประกอบการตรวจด้วยได้ โดยแฟ้มมีข้อมูลดังนี้
- บรรทัดแรก เป็นจำนวนเต็มแทนจำนวนนกที่ใช้
- สำหรับนกแต่ละตัว (ให้ใช้ลำดับเดียวกับใน output) ให้แสดงผลลัพธ์ดังนี้
- บรรทัดแรก จำนวนครั้งที่ชนหินหรือกระจก
- แต่ละบรรทัดถัดไป พิกัดของจุดที่ชนแต่ละจุด พิมพ์ในรูปแบบ x,y โดยพิมพ์เป็นทศนิยม 20 ตำแหน่ง
- บรรทัดสุดท้ายให้ระบุคะแนนคิดคุณคิดว่าคุณควรจะได้
ตัวอย่างเช่น
2 3 -666.70333448469898485,-1337.510519895233756 -738.44848762473634451,-1469.6520772473377292 -690.80508056495136771,75.911641174563172285 4 -1103.7616613533821237,-282.03133327018258569 -701.79549861152429457,867.88491047159948266 -1308.2960224684338755,1586.5846059116165634 -620.03869179214211727,-1044.2695948731491171 11000
แฟ้มสำหรับ viewer: แฟ้ม trace
มีรูปแบบดังนี้
- บรรทัดแรกระบุจำนวนนก
- สำหรับนกแต่ละตัว
- บรรทัดแรกระบุจำนวนจุดที่ต้องการวาด
- จากนั้นตามด้วยลำดับของจุดที่ต้องการวาด ระบุในรูปแบบ พิกัดแกน x,พิกัดแกน y
- จากนั้นตามด้วยข้อมูลของกระจกที่เติมเข้าไป
- เริ่มด้วยบรรทัดเปล่า หรืออะไรก็ได้ (ในตัวอย่างเขียนว่า [mirrors])
- บรรทัดถัดจากนั้นระบุจำนวนกระจก
- สำหรับกระจกแต่ละอัน ระบุพิกัดของจุดปลาย เป็น x1 y1 x2 y2
ข้อมูลหลังจากนั้นตัว viewer ไม่สนใจ เช่น คะแนนที่ได้ ที่ shoot จะแสดงขึ้นมาด้วย
ตัวอย่าง 1
1 13 -30,2 2.35425,2 2.78799,-1.44272 5.08858,1.00098 12.167,-5.88003 8.40236,2.89668 20.534,3.60369 21.1352,9.77296 16.53,-5.23984 21.5494,9.69012 21.1557,4.11218 7.35801,8.23106 -557.291,833.562 [mirrors] 1 20 10 30 8 [score] Score = 1027
ตัวอย่าง 2
2 4 -30,0 1.45583,3.14558 -2.34683,-1.31136 -115.604,38.3486 3 30,0 28.999,-0.1001 147.83,-16.811 [mirrors] 0 [score] Score = 3
โปรแกรมจำลองสถานการณ์
สามารถคัดลอกได้จาก ~jittat_fa/shoot บนเครื่อง tera คัดลอกมาที่ไดเรกทอรีตัวเองด้วยคำสั่งต่อไปนี้
cp ~jittat_fa/shoot .
เรียกใช้ดังนี้
./shoot [ชื่อ input-file] [ชื่อ output-file]
การใช้งาน viewer
จะต้องป้อนแฟ้ม config และผลลัพธ์จากการ
python viewer.py [input-file] [trace-file]
โดยที่ input-file ระบุขนาดและตำแหน่งของของบนกระดาน ส่วน trace-file ระบุเส้นทางการวิ่งของนก และตำแหน่งของกระจก
ลิงก์เพื่อดาวน์โหลด
- ตัวอย่าง
- แฟ้ม cX.in จะเป็นข้อมูลป้อนเข้า ส่วน rX.out เป็นทิศทางและตำแหน่งของกระจกที่โปรแกรมต้องแสดงออกมา
- แฟ้ม vX.out เป็นแฟ้มที่โปรแกรมจำลองสถานการณ์คำนวณได้ เพื่อนำไปใส่ในโปรแกรมแสดงผลต่อไป
- โปรแกรมแสดงผล โปรแกรมแสดงผลใช้ Python และ wxPython ซึ่งผู้เข้าแข่งต้องติดตั้งก่อน
- Python ที่ใช้ ให้ใช้เวอร์ชัน 2.x Download
- ตัวอย่าง