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 เพื่อทดสอบได้ว่าโปรแกรมคุณให้ผลลัพธ์ใกล้เคียงกับโปรแกรมตรวจหรือไม่

การคำนวณ

• เอกสาร 1 - การคำนวณจุดชน
• เอกสาร 2 - การสะท้อน และการปัดค่า

การคำนวณเวกเตอร์สำหรับสะท้อน

ถ้าเรามีเวกเตอร์ $w=\left({\begin{array}{c}w_{x}\\w_{y}\end{array}}\right)$ เวกเตอร์ที่ตั้งฉากกับ $w$ คือเวกเตอร์ที่มีผล dot product กับ w เท่ากับ 0 หนึ่งในนั้นคือ $w'=\left({\begin{array}{c}-w_{y}\\w_{x}\end{array}}\right)$

การจับเวลา

ใน Linux เราสามารถใช้ฟังก์ชัน gettimeofday ในการอ่านเวลาเพื่อจับเวลาได้ อ่านคู่มือ ฟังก์ชันนี้จะเขียนค่าลงใน struct timeval ซึ่งจะมี member หนึ่งคือ tv_sec ระบุเวลาที่ผ่านมาจากวันที่ 1 ม.ค. 1970 เป็นวินาที ซึ่งเรานำมาใช้เพื่อจับเวลาโปรแกรมของเราได้

ตัวอย่างโปรแกรมที่จับเวลาไม่ให้เกิน 10 วินาที (จะเลิกเมื่อถึง 9 วินาที) <geshi lang="c">

1. include <sys/time.h>
2. 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">

1. 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

แฟ้มเก็บวิถีวิ่ง 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