Beware Butterfly Effect -โจทย์การแข่งเขียนโปรแกรมภายใน อย่างเป็นทางการ ครั้งแรกของ THiNKNET
ภายใต้โปรเจ็ค “Code Prime” เราได้พาโปรแกรมเมอร์ท่องโลกของการแข่งขันเขียนโปรแกรม ด้วยโจทย์ที่ต้องแก้ปัญหาด้วยมันสมองในเวลาจำกัด
ICPC ACM , Google Code Jam , Facebook Hacker Cup, Coding Olympic
และอีกหลาย ๆ รายการที่โปรแกรมเมอร์หลายคนคงเคยได้ยินและร่วมงานแข่งเขียนโปรแกรมกันอีกนับไม่ถ้วน…และในรอบนี้ THiNKNET เราก็เลยลองเอาบ้าง!
เราได้ลองจัดการแข่งขันเขียนโปรแกรมภายในขึ้นมาแบบเพื่อให้ Programmer ทั้งที่เคยและไม่เคยแข่งเขียนโปรแกรม ได้สัมผัสบรรยากาศของ Competitive Programming กันภายใต้ Project Code Prime ซึ่งแบ่งออกเป็น 2 Part
Part ที่ 1 : Code Prime Exercise — ใช้กิจกรรมนี้ถูกจัดขึ้นมานำร่อง ให้ทุกคนได้ลองทำความคุ้นเคย จากโจทย์ต่างๆ ที่เราหยิบมาให้เหล่า Programmer ได้ลองเล่นกัน แบบปรึกษา หาไอเดียกันได้
Part ที่ 2 : Code Prime 2018 — ถูกจัดขึ้น เมื่อวันที่ 13 กรกฏาคม 2018 รอบนี้สิ ของจริง !
“แข่งจริง มีสกอร์จริง โจทย์ต้องไม่ซ้ำ”
พอได้โจทย์นี้มา เหล่า Prime staff ทั้งหลายก็ต้องแบ่งกันไปคิดหาโจทย์ด้วยเงื่อนไข 1 ข้อ
— ไม่ยากไป ไม่ง่ายไป
ด้วยคอนเซ็ปเหล่านี้เราจึงต้องไปนั่งคิด นอนคิด ยืนคิด เอาทฤษฏีและเรื่องราวต่าง ๆ รอบตัวมาประกอบจิ๊กซอว์ให้กลายเป็นโจทย์ที่ผู้แข่งขันได้เอาไปขบคิดทำความเข้าใจ ฝึกฝนแปลงโจทย์ให้กลายเป็น Logic … ไปดูกัน
“เอาล่ะฮะ นี่คือหนึ่งในโจทย์”
เราจะพามาดูโจทย์ที่ใช้ในการแข่งอีกหนึ่งข้อ ซึ่งข้อที่หยิบมานำเสนอนั้น คือข้อที่ชื่อว่า “Beware Butterfly Effect”
Beware Butterfly Effect
“การเปลี่ยนแปลงอดีตเพื่อหนีความชั่วร้าย อาจทำให้เจอสิ่งที่ชั่วร้ายยิ่งกว่า”
โลก ที่มนุษย์ได้เริ่มประดิษฐ์คิดค้นหุ่นยนต์ขึ้นมาเพื่อความสะดวกสบายและใช้แรงงานต่าง ๆ จนมาถึงยุคที่มนุษย์สามารถสร้าง AI ที่สามารถคิดตัดสินใจและใช้ชีวิตแทนได้ จนวันหนึ่งก็เริ่มมี Android ที่อยากมีชีวิตเป็นของตัวเองและก่อตั้งกลุ่มปฏิวัติระหว่าง Android และมนุษย์ขึ้นมา เรียกเหตุการณ์นี้ว่า “Become Human”
400 ปีหลังจากเหตุการณ์ Become Human ได้เกิดการปฏิวัติอย่างต่อเนื่องของเครื่องจักรและ Android ทำให้โลกถูกวิวัฒด้านเทคโนโลยีและความรู้ด้านฟิสิกส์อย่างก้าวกระโดดจากเหล่าปัญญาประดิษฐ์และเป็นผลทำให้มนุษย์มีประชากรลดน้อยลงอย่างต่อเนื่องจนแทบจะเป็นเพียงชนกลุ่มน้อยบนโลก
ในทางกลับกันพวกหุ่นยนต์มีจำนวนมากขึ้นเรื่อย ๆ และอยู่ได้นานกว่ามนุษย์หลายเท่า ทำให้เหล่าวิศวกรและนักวิทยาศาสตร์ทั่วโลกหันกลับมาร่วมมือกันแก้ปัญหาและวางแผนทวงคืนสิทธิให้กับมนุษยชาติ มนุษย์ได้ทำการสร้าง Time Machine ได้สำเร็จและใช้มันเพื่อย้อนกลับไปแก้ปัญหา ด้วยการกลับไปทำลายอัลกอริทึมที่อาจทำให้เกิดการปฏิวัติได้ แต่สิ่งที่ต้องระวังให้มากก็คือ “หากเราย้อนเวลาไปเปลี่ยนแปลงอดีต ผลที่ตามมาอาจเปลี่ยนแปลงปัจจุบันไปในทางที่ดีหรือแย่ได้เสมอและนั่นจะส่งผลกระทบเป็นวงกว้างออกไปเรื่อยๆ ไม่มีสิ้นสุด (Butterfly Effect)” เพราะฉะนั้นพวกเขาต้องกลับไปเปลี่ยนแปลงอดีตให้น้อยที่สุดและเปลี่ยนมันเฉพาะในส่วนที่สำคัญที่สุด
“คุณ” เป็นวิศวกรที่ได้รับหน้าที่ในการวิเคราะห์และคำนวณเพื่อออกแบบแผนการแก้ไข Timeline ในอดีตเพื่อไม่ให้อนาคตนำไปสู่เหตุการณ์ Become Human ดังที่กล่าวมานี้
โดย จากการวิเคราะห์พบว่ามี Timeline ในอดีตที่จำเป็นต้องแก้ไขอยู่จำนวน T Timeline
ซึ่งในแต่ละ Timeline จะเป็นการเชื่อมโยงของเหตุการณ์ต่างๆ จำนวน M คู่เหตุการณ์
โดยผลลัพธ์จากการวางแผน คือ เส้นทางการดำเนินเหตุการณ์ตั้งแต่จุดเริ่มต้นของเหตุการณ์ S ไปจนถึง สิ้นสุดของเหตุการณ์ D ใน Timeline นั้น
โดยต้องเข้าไปยุ่งเกี่ยวกับเหตุการณ์ต่างๆ ในอดีตให้น้อยที่สุด เพื่อป้องกันไม่ให้เกิดผลข้างเคียงในอนาคตที่นอกเหนือการควบคุมได้
หากมีเส้นทางมากกว่า 1 เส้นทาง ให้เลือกเส้นทางแรกที่พบ
โดยเรียงจาก a < b < c < d < … < zและหากไม่พบเส้นทาง ให้แสดงค่า “IMPOSSIBLE!“
- Input Description -
— บรรทัดแรกรับ T แทนจำนวน Timeline ตามด้วยข้อมูลแต่ละ Timeline
— ในแต่ละข้อมูลของ Timeline บรรทัดแรกจะเป็น S, D และ M (ขั้นด้วย whitespace) แทนเหตุการณ์เริ่มต้น, สิ้นสุดที่ต้องการเส้นทาง และจำนวนคู่เหตุการณ์ที่มีใน Timeline นั้น ตามลำดับ
— อีก M บรรทัดต่อไป บรรทัดที่ i จะเป็นการเชื่อมโยงของเหตุการณ์ ในรูปแบบ Fi Ti แทนการเชื่อมโยงระหว่างเหตุการณ์ Fi กับ Ti
— โดยที่ S,D,Fi, Ti ∈ {‘a’, ‘b’, ‘c’, … , ‘z’}
- Output Description -
— ผลลัพธ์ที่ได้ต่อหนึ่งชุดทดสอบ แต่ละบรรทัดจะอยู่ในรูปแบบ “Case #x: y” โดยที่ x คือหมายเลข Timeline และ
— y คือ เส้นทางเหตุการณ์ใน Timeline จากเริ่มต้น ไปยัง จุดสิ้นสุดที่ได้จากการวางแผนของคุณ
— หากไม่พบเส้นทาง ให้แสดงค่า “IMPOSSIBLE!“ แทน
- Limit -
Small
T = 100
5 ≤ M ≤ 8
Large
T = 100
22 ≤ M ≤ 26
- Sample Input -
3
j q 8
j k
k l
k o
l m
m n
n o
o p
p q
t v 5
s t
s v
t u
u v
v w
k p 6
i j
j k
k l
l m
m n
o p- Sample Output -
Case #1: jkopq
Case #2: tsv
Case #3: IMPOSSIBLE!
โจทย์ข้อนี้ถ้าอ่านตั้งแต่แรกจะรู้สึกเหมือนธาตุไฟเข้าแทรก นี่มันอะไรกันวะเนี่ย เรื่องราวยาวเฟื้อย มีย้อนเวลา มีปรับสมดุลจักรวาลอะไรก็ไม่รู้
ใจเย็น ๆ แล้วลองดูบรรทัดนี้
“โดยผลลัพธ์จากการวางแผน คือ เส้นทางการดำเนินเหตุการณ์ตั้งแต่จุดเริ่มต้นของเหตุการณ์ S ไปจนถึง สิ้นสุดของเหตุการณ์ D ใน Timeline นั้น”
ดูเหมือนว่าโจทย์ต้องการจะบอกว่าเรามี “การเดินทาง” “จุดเริ่มต้น” “ไปจนถึง” “จุดปลายทาง”
และตามมาด้วยบรรทัดนี้
“โดยต้องเข้าไปยุ่งเกี่ยวกับเหตุการณ์ต่างๆ ในอดีตให้ น้อยที่สุด เพื่อป้องกันไม่ให้เกิดผลข้างเคียงในอนาคตที่นอกเหนือการควบคุมได้”
“น้อยที่สุด” keyword อีก 1 คำที่โผล่เข้ามาอย่างมีนัยยะ
ถ้าเอา keyword ที่เราเจอในโจทย์มารวม ๆ กันดูจะพบว่ามีคำที่โปรแกรมเมอร์น้อยใหญ่น่าจะต้องได้ยินกันมาบ้าง และแน่นอนหลายคนที่ยังงงกับโจทย์ พออ่านมาถึงบรรทัดนี้คงคิดออกแล้ว
ใช่! มันคือ Graph และเป็น Graph ที่เราต้องหาระยะทางที่สั้นที่สุดด้วย
ฟังดูก็ไม่มีอะไรแปลกใหม่จากที่เราได้เคยเรียนในวิชา Data structure กันมา
ถูกแล้ว! เดี๋ยวเรามาทบทวนคอนเซ็ปกันอีกสักครั้ง เผื่อเป็นไอเดียให้ไปลองเล่นกัน
เริ่มจาก เราต้องนำ input ทุกตัว ที่จับคู่กันอยู่มาร้อยกันให้เป็น graph จริงๆ เสียก่อน
ตัวอย่าง
j q 8
j k
k l
k o
l m
m n
n o
o p
p q
จะเห็นว่า input บรรทัดแรกถูกกำหนดให้เป็นเป้าหมายของเส้นทาง จาก j ไป q โดยให้มีการรับ input คู่ของ node ที่เชื่อมต่อกันอีก 8 คู่ กราฟจะออกมาแบบนี้
แน่นอนว่าถ้าอ่านจากโจทย์จะไม่มีเรื่องการนำน้ำหนักของระยะทางเข้ามาเกี่ยวข้อง แสดงว่าโจทย์ข้อนี้ต้องการหาเพียง การเดินทางผ่าน Node ให้น้อยที่สุด
จากโจทย์เราจะเริ่มกันที่ Node j และเราจะหาทางที่สั้นที่สุด (Shortest path) โดยเราจะเริ่มไล่ทีละ Node แล้วหาเส้นทางลงไปที่ Node ลูกไปเรื่อยๆ โดยนำค่าของ edge (ที่มีค่าเป็น 1 เท่ากันทุกเส้น) บวกเข้าไปแล้วเก็บไว้ที่ Node ที่เดินทางผ่าน แล้วเพื่อเทียบหาว่าเส้นทางใดเป็นเส้นทางที่ใกล้ที่สุด
Step
- start จาก Source ที่มีผลรวมระยะทาง Node j = 0
- เดินทางไปใน Node ที่เชื่อมต่อกับ Source โดยทุกครั้งที่เดินทางไปให้นำค่าผลรวมจาก Node แม่ไปบวก 1 (ค่าคงที่ของระยะทาง edge) แล้วเก็บไว้ที่ Node k เพราะฉะนั้น Node k จะมีค่าเป็น 1
- เดินทางต่อจาก Node k ไปหา l และ o พร้อมเพิ่มค่าไปเก็บไว้ที่ Node ทั้งสอง แล้วตรวจสอบว่า Node ที่เดินทางไปนั้นเป็น Destination แล้วหรือยัง ถ้ายังก็..
- วนลูปทำสเต็ปแบบนี้ไปเรื่อย ๆ ไปบน Node อื่น ๆ จนกว่าจะถึงจุด Destination
- แต่โจทย์บอกว่าเรา ถ้าได้ผลลัพธ์เท่ากันจะต้องเลือกผลลัพธ์แรกโดยนับจากการเรียงตามพจนานุกรม
- จึงใช้วิธีนำ Input เข้าฟังก์ชัน Sort ธรรมดาๆ จากนั้น เวลาวนลูป search ก็จะเริ่มตามพจนานุกรมเรียบร้อย
ผลลัพธ์ก็คือ j > k > o > p > q
ให้รูปอธิบาย
จบแล้ว สำหรับแนวคิดการทำโจทย์ที่เนื้อเรื่องยาวเป็นกิโล อ่านเพลินจนลืมว่ากำลังทำโจทย์อยู่ สำหรับบล็อกหน้าจะมาเล่าให้ฟังแบบ Full story เรื่อง Project Code Prime ของ THiNKNET อีกทีนะครับ
