Day 9 — Advent of Code 2020
สวัสดีกับวันพุธและวันที่ 9 ของ Advent of Code 2020 แล้วครับ
วันนี้ผมเปลี่ยนบรรยากาศมาใช้ภาษา Python ซึ่งเป็นภาษาสุดฮิตของสาย Data Science เพราะมี Module จำนวนมากให้ใช้
ตอนนี้ Tab Language ใน GitHub Repository ของผมเป็นประมาณนี้ครับ
ก็ถือว่ามีภาษาต่างๆ ปะปนกันไปเรื่อยๆ ซึ่งผมตั้งใจจะทำให้ได้อย่างน้อย 10 ภาษาใน Advent of Code 2020 ครับ
โดยในวันพรุ่งนี้ ผมจะลองใช้ภาษา Julia ในการแก้ไขโจทย์กันบ้างครับ
Day 9: Encoding Error
โจทย์ต้องการให้เราหา Weakness ของ Cipher ที่ชื่อว่า eXchange-Masking Addition System (XMAS)
การทำงานของ XMAS คือ การสร้างตัวเลขขึ้นมาเรื่อยๆ และเมื่อครบ 25 ตัวแล้ว ตัวถัดไปจะต้องมีคุณสมบัติที่ว่าเป็นผลบวกของคู่ตัวเลขก่อนหน้าไป 25 ตัว
เช่น ถ้า 25 ตัวแรกคือ 1 ถึง 25 แล้ว ตัวเลขที่ 26 จะต้องเกิดจากผลบวกของตัวเลขที่อยู่ระหว่าง 1 ถึง 25 แบบไม่ซำ้กัน เช่น 42 = 20 + 22 (ตรงตามเงื่อนไข)
โดยการโจมตีระบบนี้ผ่าน Weakness ที่ว่า เราต้องหาตัวเลขแรกสุดที่ไม่ตรงตามเงื่อนไขข้างต้น หรือ ไม่พบผลบวกในระยะ 25 ตัวเลขก่อนหน้าที่ทำให้ได้ตัวเลขนี้
วิธีคิดของผม คือ การสร้าง Stack เก็บข้อมูลไปเรื่อยๆ เมื่อ Stack มีตัวเลขเกิน 25 ตัว (หรือ 26 ตัว) ผมจะ Pop Stack ออก เพื่อให้ตัวเลขใน Stack มีเพียง 25 ตัวที่อยู่ก่อนหน้าตัวเลขปัจจุบัน
สำหรับ Implementation ในภาษา Python ตัว List เองมี Operation push() กับ pop() อยู่แล้ว ดังนั้นผมจึงใช้เป็น List และก็ทำตามแนวคิดที่ผมได้เกริ่นไปก่อนหน้า
ถัดมา ผมจะ Brute Force หาผลบวกที่เป็นไปได้ทั้งหมดของ List ที่มี 25 ตัวเลข โดย Time Complexity ของการกระทำแบบนี้ คือ O(25²) = O(625) ซึ่งไม่มาก แต่ทุกครั้งที่ Push ข้อมูลใหม่เข้า Stack ก็ต้องทำแบบนี้เรื่อยๆ หมายความว่า Time Complexity จริงๆ คือ O(625n) ครับ
เพียงเท่านี้ก็ได้คำตอบของโจทย์ในส่วนแรกแล้วครับ
ถัดมาโจทย์ให้เราใช้คำตอบของส่วนแรก ในการหา Contiguous Set (เซตของสมาชิกที่ติดกัน) ที่ประกอบด้วยตัวเลขอย่างน้อย 2 ตัวในลำดับตัวเลข ซึ่งมีผลบวกรวมกันเท่ากับคำตอบของส่วนแรก
ซึ่งถ้าคิดแบบ Brute Force ตรงๆ การหาผลบวกที่เป็นไปได้แบบไม่จำกัดจำนวนตัวบวก มันคือ O(n³) ซึ่ง n = 1000 หมายความว่า 1000000000 (1 พันล้าน) ครั้ง ซึ่งน่าจะต้องใช้หลักนาทีในการคำนวณ
โดยหากจะ Filter ข้อมูลบางอย่างไป ก็อาจจะทำได้ เช่น ตัดตัวเลขที่อยู่ลำดับหลังจากคำตอบของส่วนแรกออกไป แต่มันก็ยังคงมีมากอยู่ดี
เพราะฉะนั้น ตามหลักแล้ว Time Complexity กับ Space Complexity มักจะวิ่งสวนทางกัน ดังนั้นถ้าเราเพิ่ม Space Complexity เข้าไปน่าจะช่วยลด Time Complexity ได้
(พึ่งรู้ว่ามีชื่อเรียกเป็น Space-time tradeoff ด้วยนะเนี่ย)
โดยแนวคิดของผมในส่วนนี้ คือ การทำ Memo หรือ Memoization
สำหรับคำนี้ ผมเคยเกริ่นไปในวันที่ 7 บ้างแล้ว แต่ผมจะอธิบายแบบสั้นๆ เพื่อให้เข้าใจสิ่งที่ผมกำลังจะทำนะครับ
Memoization คือ การจดผลลัพธ์ของคำตอบเอาไว้ เวลาที่เกิดการคำนวณแบบเดิมซำ้ เราจะได้ไม่ต้องไปเสียเวลาคำนวณใหม่
ตัวอย่างที่ Classic มากๆ คือ Factorial
n! = n * n - 1 * n - 2 * ... * 1
n! = n * (n - 1)!ถ้าเกิดเราอยากจะหาผลลัพธ์ของ 1! จนถึง 10! ถ้าเราคำนวณใหม่ทั้งหมด หมายความว่า เราต้องใช้ Time Complexity O(n²) แต่หากเรา Memo คำตอบเอาไว้
1! = 1
2! = 2 * 1! = 2
3! = 3 * 2! = 6
4! = 4 * 3! = 24
...จะเห็นว่า ถ้าเราเก็บผลลัพธ์ของ (n — 1)! เอาไว้ เราสามารถคำนวณหา n! ได้ทันที โดยใช้ Time Complexity แค่ O(n) เพิ่มเติมด้วย Space Complexity อีก O(n)
แนวคิด Memoization ถูกใช้ใน Algorithm ประเภท Dynamic Programming เยอะมากๆ
โดยแนวคิดในการแก้โจทย์ส่วนนี้ของผม คือ การคำนวณหาผลบวกสะสมของแต่ละตัวเลขเอาไว้ก่อน
เมื่อมีผลบวกสะสมแล้ว การคำนวณผลบวกไล่ตั้งแต่ i จนถึง j ก็สามารถทำได้อย่างง่าย ดังนี้
sum from i to j = cumulative(j) - cumulative(i - 1)ซึ่งการทำเช่นนี้ ใช้ Time Complexity แบบ Constant หรือว่า O(1) เท่านั้น เพิ่มเติมกับ Space Complexity อีก O(n)
เมื่อลด Loop in range n ออกจาก Time Complexity จาก O(n³) แล้ว เราจะเหลือ O(n²) คือ 1,000,000 ครั้ง (หายไป 1,000 เท่า) ซึ่งอยู่ในระดับที่ดีเพียงพอแล้วกับการแก้ไขปัญหา
สำหรับคำตอบของโจทย์ส่วนนี้ คือ ผลบวกของค่าที่น้อยที่สุดและค่าที่มากที่สุดใน Contiguous Set
โดยผมเพียงเพิ่ม Implementation ของ Algorithm min, max ทั่วๆ ไปเข้าไปเป็นอันเรียบร้อยครับ
สำหรับ Source Code ทั้งหมดของวันนี้เป็นแบบนี้ครับ
สำหรับวันนี้ผมรีบเขียนไปหน่อยนะครับ ถ้าผิดพลาดประการไหนสามารถบอกได้เลยนะครับ
เบื้องต้น ผมว่าวันนี้ไม่ยากมากครับ แต่โจทย์เริ่มให้เราคิดถึง Space Complexity มากขึ้นด้วย (ซึ่งมันค่อนข้าง Counterintuitive หรือตรงข้ามกับความคิดทั่วไปของเราขึ้นเรื่อยๆ แล้วครับ)
สุดท้ายนี้ ขอบคุณที่อ่านมาจนถึงตรงนี้นะครับ :)
ปล. Link GitHub Repository ของ Advent of Code 2020 เช่นเคยครับ
