Day 13 — Advent of Code 2020
เข้าสู่วันที่ 13 ของ Advent of Code 2020 แล้วครับ ซึ่งก็เป็นการเดินทางมากว่าครึ่งทางแล้ว
จริงๆ แล้ว วันนี้ผมแอบไปเห็นคนบอกว่าโจทย์เริ่มยากขึ้นแล้ว ผมเลยเอาภาษา Java เจ้าเก่าในการ Implement ครับ 😅
และ Blog ในวันนี้ก็น่าจะเป็นอีก Blog นึงที่ยาวอยู่ ผมจะพยายามอธิบายให้เข้าใจได้ง่ายที่สุดนะครับ
เช่นเคย ใครที่สนใจลองแก้โจทย์ Advent of Code 2020 สามารถไปที่ Link ด้านล่างนี้ได้เลยครับ
Day 13: Shuttle Search
โจทย์ในวันนี้เกี่ยวกับตารางเวลาเดินรถบัสครับ โดยเราต้องการนั่งรถบัสไปยังสนามบิน
สำหรับตารางการเดินรถบัส มีลักษณะดังนี้
7,13,x,x,59,x,31,19ในตารางการเดินรถบัส จะเขียน Bus ID เอาไว้ โดย Bus ID นอกจากใช้ระบุตัวรถบัสแล้ว ยังใช้บอกเวลาที่รถบัสจะมาด้วยเช่นกัน
ตัวอย่างเช่น รถบัสที่มี Bus ID เท่ากับ 5 รถคันนี้จะมาทุกๆ 5, 10, 15, … นาที
สำหรับ x หมายถึง ไม่มีรถให้บริการ
โจทย์ต้องการรู้ว่า ถ้าเรามารอรถบัสเวลา timestamp แล้ว รถบัสคันไหนจะมาถึงก่อน หากรถบัสทุกคันเริ่มออกวิ่งที่เวลา 0
สำหรับคำตอบที่โจทย์ต้องการ คือ ผลคูณของ Bus ID และเวลาที่เราต้องรอรถบัส เช่น เรามารอรถบัสในเวลา 5 แล้วรถบัสที่มี Bus ID เท่ากับ 7 มาในเวลา 7 หมายความว่าเราต้องรอรถ 2 หน่วย ดังนั้นคำตอบจึงเป็น 2 * 7 = 14 ครับ
โดย timestamp จะถูกระบุอยู่ในบรรทัดบนสุดของ Input File ลักษณะประมาณนี้ครับ
939
7,13,x,x,59,x,31,19วิธีคิดโจทย์ในส่วนนี้ เราสามารถ Brute Force ไล่ timestamp ตั้งแต่ 0 จนถึงค่า timestamp ได้ แล้วดูว่ารถบัส ID ใดจะมาก่อน
แต่วิธีที่ดีกว่านั้นคือการใช้คณิตศาสตร์เข้ามาช่วยครับ ยกตัวอย่างดังนี้ครับ
เราสามารถรู้ได้ว่ารถบัสที่มาทุกๆ เวลา x หน่วย มาในเวลาไหนได้โดยดูว่า x | timestamp (timestamp หารด้วย x ลงตัว) หรือไม่
เช่น หากเรามารอรถบัสในเวลา 10 แล้ว รถบัสที่มี Bus ID เท่ากับ 5 จะมาในเวลา 10 ได้พอดี เนื่องจาก 5 | 10 (10 หารด้วย 5 ลงตัว) เป็นจริง
ในรูปแบบเดียวกัน หากเกิดการหารไม่ลงตัว หมายความว่ารถบัสไม่ได้มาพอดีกับเรา โดยเศษที่ได้จากการหาร หมายถึง เวลาที่รถบัสออกไปแล้ว
เช่น หากเรามารอรถบัสในเวลา 12 แล้ว รถบัสที่มี Bus ID เท่ากับ 5 คันล่าสุดออกไปในเวลา 10 หมายความว่า รถบัสออกไปแล้ว 2 หน่วยเวลา (12 หารด้วย 5 เหลือเศษ 2)
กลับกัน ถ้าเราอยากรู้เวลาที่เราต้องรอ เราเพียงแค่นำเศษที่ได้ไปลบกับเวลาของรถบัส (หรือ Bus ID) เราจะได้เวลาที่เราต้องรอรถบัส
ถ้าตามตัวอย่างก่อนหน้า รถบัสออกไปแล้ว 2 หน่วยเวลา หมายความว่าเราจะต้องรออีก 3 นาที (5 ลบด้วย 2) รถบัสที่มี Bus ID เท่ากับ 5 คันถัดไปจะมาถึง (ในเวลา 15)
ถึงตรงนี้ ผมคิดว่าเราสามารถ Implement แนวคิดข้างต้นได้แล้วครับ
remainingTime = (busTime - timestamp) % busTimeโดยเราจะต้องหา remainingTime ที่น้อยที่สุดเอาไว้ด้วย ซึ่งสามารถทำได้ด้วยการ Implement Algorithm สำหรับการหาค่าที่ตำ่ที่สุดครับ
และนี่คือ Source Code สำหรับโจทย์ในส่วนแรกครับผม
เห็นได้ว่า โจทย์ในส่วนแรกไม่ได้ยากมากครับ เป็นแค่การเอาคณิตศาสตร์มาประยุกต์ใช้แบบพื้นฐานเท่านั้น
สำหรับโจทย์ในส่วนที่ 2 เกี่ยวกับการหาเวลาที่รถบัสจะมาในรูปแบบที่กำหนดให้ครับ
โดยรูปแบบที่ว่า อยู่ใน Input File ที่ผมได้เกริ่นไปก่อนหน้า
7,13,x,x,59,x,31,19โจทย์อยากทราบเวลาที่รถบัสแต่ละคันใน Input File มาตามลำดับ โดยหากรถบัสคันแรกใน Input File มาในเวลา t แล้ว รถบัสคันถัดมาจะต้องมาในเวลา t + 1 และ t + 2 ไปเรื่อยๆ ทั้งนี้จะต้องเพิ่มค่า t ไปแม้เจอ x ใน Input File ด้วย
ในตัวอย่าง Input File ข้างต้น หมายความว่า
t -> 7
t+1 -> 13
t+4 -> 59
t+6 -> 31
t+7 -> 19โดยโจทย์ต้องการให้เราหาค่า t ที่น้อยที่สุด ซึ่งมีคำเตือนเอาไว้ว่าคำตอบที่ได้มีค่ามากกว่า 100000000000000 (10¹⁴) แน่นอน
เนื่องจากโจทย์ระบุ Contraint มาว่าค่าที่ได้มากกว่า 10¹⁴ หมายความว่าเราไม่สามารถ Brute Force ตรงๆ ได้อย่างแน่นอน
ถึงตรงนี้ ผมขอสรุปว่า โจทย์นี้คือโจทย์ประเภท Discrete Optimization แบบต้องการ Exact Solution นะครับ
และหลังจากนี้ผมขออธิบายวิธีคิดของผม (ซึ่งผมไม่ขอบอกว่าเป็นวิธีที่ดีที่สุดนะครับ)
โดยในวิธีคิดของผม ผมจะใช้ตัวอย่าง Input File เป็น
17,x,13,19ผมเริ่มจากการเปลี่ยนรูปแบบ Input File ข้างต้นให้เป็นสมการ ดังนี้ครับ
t = 17x ...(1)
t+2 = 13y ...(2)
t+3 = 19z ...(3)จากสมการ (1) ถึง (3) ข้างต้น ผมขอปรับให้อยู่ในรูป t = ... ทั้งหมด
t = 13y - 2 ...(4)
t = 19z - 3 ...(5)เมื่อได้รูปแบบนี้แล้ว จะพบว่าฝั่งขวา (RHS) ของสมการที่ (1) (4) (5) มีค่าเท่ากัน (เนื่องจากเท่ากับ t) ทั้งหมด ดังนั้นผมสามารถสร้างสมการได้ดังนี้
17x = 13y - 2 = 19z - 3 ...(6)และผมสามารถสร้างสมการอื่นๆ จากสมการที่ (6) ได้ คือ
17x = 13y - 2 ...(7)
17x = 19z - 3 ...(8)
13y - 2 = 19z - 3 ...(9)โดยแต่ละสามารถ ผมสามารถทำ Integer Programming แบบ Brute Force เพื่อหาค่าของแต่ละตัวแปรได้
เช่น จากสมการ (7) ผมสามารถเขียนเป็น 17x — 13y = -2 แล้ว Loop หาค่า x ที่สอดคล้องกับสมการนี้ได้ ดังนี้ครับ
สำหรับสอง Column แรก ผมคิดว่าน่าจะเข้าใจกัน แต่สำหรับ Column ที่ 3 มันเกิดจากการคำนวณโดยเอา y ที่เหมาะสมมาคำนวณด้วย
โดยค่า y ที่เหมาะสมนั้น มาจาก Assumption ของผมที่ว่า เมื่อ 17x — 13y มีผลลัพธ์เป็นค่าลบแล้วนั้น หมายความว่า 13y > 17x และเนื่องจากเราต้องการ Minimize ค่า x ด้วย ผมจึงเลือกใช้ค่า y ที่มีค่าสูงกว่า x ไม่เกิน 13 (มาจาก Coefficient ของตัวแปร y)
หากไม่เข้าใจ ลองดูตัวอย่างต่อไปนี้ครับ
102 - 13y = -2
104 = 13yซึ่งพบว่า 13 | 104 เป็นจริง เราจึงสามารถแก้สมการหาค่า y ออกมาได้ พร้อมทั้งพบว่าที่ x = 6 นั้น เป็นค่า x ที่ตำ่ที่สุดที่ทำให้สมการ 17x = 13y — 2 เป็นจริง
หากเขียนเป็นโปรแกรม ผมใช้ Expression ดังนี้
y = x - ((long)Math.ceil((double)x / (double)max) * max);ทั้งนี้ แม้จะรู้ค่า x ที่ตำ่ที่สุดที่เป็นไปได้ของสมการ 17x = 13y — 2 แล้ว ก็ไม่ได้หมายความว่าค่า x นี้ จะทำให้สมการ 17x = 13y — 2 = 19z — 3 เป็นจริงทั้งหมด แต่ในทางกลับกัน ถ้าสมการ 17x = 13y — 2 = 19z — 3 เป็นจริง สมการ 17x = 13y — 2 จะต้องเป็นจริงด้วย
นอกจาก Assumption ข้างต้นแล้ว เรายังพบว่าจากสมการ 17x — 13y = -2 แล้ว นอกจาก x = 6 แล้ว ทุกๆ x = 6 + 13n จะเป็นจริงทั้งหมด โดยสามารถทำ Direct Proof ได้ดังนี้
13 | 17(6 + 13n) + 2
13 | 102 + 221n + 2
13 | 325 + 221n
13(25 + 17n) + 0 = 325 + 221n (T)จากการพิสูจน์ข้างต้น ทำให้มั่นใจว่า ทุกๆ x = 6 + 13n ทำให้สมการ 17x — 13y = -2 เป็นจริงทั้งหมด
เมื่อทราบแล้ว หมายความว่าเราสามารถเพิ่มค่า t ที่มีค่าเท่ากับ 17x ได้ครั้งละ 17 * 13 หรือ lcm(17,13) คือ 221 โดยเริ่มจาก 17 * 6 คือ 102
หลังจากที่ทำส่วนนี้เสร็จ ผมจะต้องหาค่าของสมการอื่นๆ ด้วย เช่น 17x = 19z — 3 โดยในขั้นตอนการหา ผมเพียงแค่หาให้ได้ครบทุกพจน์ในสมการ 17x = 13y — 2 = 19z — 3 เท่านั้น
โดยจาก 17x = 19z — 3 หรือ 17x — 19z = -3 แล้ว ผมได้ว่า ทุกๆ x = 11 + 19n ทำให้สมการ 17x — 19z = -3 เป็นจริงทั้งหมด โดยหากให้สมการนี้เป็นหลัก เราสามารถเพิ่มค่า t ได้ครั้งละ 17 * 19 คือ 323 ซึ่งมากกว่า lcm(17,13) ข้างต้น
ดังนั้น หากเรา Brute Force เพื่อหาค่า x y z จากสมการ 17x = 13y — 2 = 19z — 3 โดยเพิ่มครั้งละ 323 ควรจะได้คำตอบเร็วกว่า
ในการตรวจสอบว่าค่า x y z ที่ใช้ถูกต้องหรือไม่ เราสามารถรันค่า t ที่เป็นไปได้ของแต่ละสมการเทียบกัน และเมื่อเจอค่าที่เหมือนกันค่าแรกสุด เราสามารถนำไปใช้เป็นคำตอบได้
แต่วิธีนี้ ทำให้เราต้องคำนวณผลคูณของทุกสมการ ผมจึงใช้อีกวิธีนึงแทน
โดยจากสมการรูปแบบ t = c + kn ข้างต้นแล้ว ถ้าคำตอบที่ได้ (เช่น 3417) หรือ t ทำให้ k | t — c ของทุกสมการเป็นจริง หมายความว่า t ตรงตามเงื่อนไข
สาเหตุที่เราสามารถทำแบบนี้ได้เลย เนื่องจากว่าทุก Bus ID ที่โจทย์กำหนดให้ใน Input File เป็น Prime Number (จำนวนเฉพาะ) ทั้งหมด ดังนั้น k ในสมการข้างต้นจึงเป็น biprime (ผลคูณของ Prime 2 จำนวน) ซึ่งถ้า t — c ไม่มีตัวประกอบร่วมกับ k แล้ว (ซึ่ง c คือ ผลคูณของ Prime อื่นๆ 2 ตัวอยู่แล้ว) จะไม่มีทางที่ k | t — c จะเป็นจริงได้เลย
(ในส่วนนี้ ผมอธิบายยังไม่ค่อยชัดเจนเท่าไหร่ ถ้ามีโอกาสจะมาอธิบายเพิ่มเติมนะครับ)
ดังนั้นผมขอสรุปวิธีคิดของผม ดังนี้
- แก้สมการที่ได้มาจาก Bus ID และลำดับของรถบัสใน Input File เพื่อหา
cและkของแต่ละคู่รถบัส - Loop หาค่าที่เหมือนกันของทุกคู่รถบัส โดยค่าที่เหมือนกันเป็นค่าแรกคือคำตอบ
และนอกจากวิธีคิดข้างต้น เราสามารถเพิ่มความเร็วของการ Loop ได้โดยการใช้ค่า k ที่สูงที่สุดเป็นตัว Loop
โดยเราสามารถหาค่า k ที่สูงที่สุดได้จากการนำสมการของ Bus ID ที่สูงที่สุดเป็นจับคู่กับสมการของ Bus ID ที่สูงรองลงมา อย่างในกรณีข้างต้น เราสามารถเพิ่มค่าของ Loop ได้มากที่สุด 17 * 19 คือ 323
ดังนั้นผมจะเก็บค่า Bus ID สูงที่สุด เอาไว้ก่อน เพื่อใช้ในการจับคู่
หลังจากนี้เป็นการ Implement ของวิธีคิดทั้งหมดนะครับ โดยเริ่มจากการเก็บ Bus ID ที่สูงที่สุด
ถัดมาผมจะจับคู่ เพื่อความง่าย ผมจะจับทุกสมการคู่กับสมการที่มี Bus ID สูงที่สุดเสมอ (เราสามารถมั่นใจว่าเราจะได้ค่า k สูงที่สุดได้)
สังเกตได้ว่าผมมีตัวแปร maxIncrement เอาไว้สำหรับเก็บค่า k ที่สูงที่สุด รวมถึง Array starts เอาไว้เก็บค่า c ของแต่ละสมการ รวมถึง Array lcm (ผมตั้งชื่อจาก LCM ที่มาจาก Least Common Multiple หรือ ครน.) เอาไว้เก็บค่า k ของแต่ละสมการ
โดยภายใน Loop ของแต่ละสมการ (ยกเว้นสมการ max) เราจะต้องคำนวณหาค่า k และ c ของแต่ละสมการ โดยค่า k สามารถคำนวณได้จาก LCM ของ maxID และ currentID หรือ ผลคูณของ maxID และ currentID ได้เลย (เนื่องจากเป็น Prime ทั้งคู่)
สำหรับการคำนวณค่า c ของแต่ละสมการ (ถ้าจำได้) คือการ Loop ค่า x ของแต่ละสมการเพื่อให้ได้ค่า y ที่เหมาะสม
โดยผมแบ่งเป็น 2 กรณี ในกรณีที่ ax + by = d แล้ว d < 0 หมายความว่า by > ax ดังนั้นผมจะใช้ Expression by = ((long)Math.ceil((double)ax / (double)max) * max) หรือ ผมปัด ax / b ขึ้น เพื่อให้ได้ผลคูณในลำดับถัดไปของ y แล้วค่อยคูณด้วย b กลับไป
ยกตัวอย่างเช่น หากผมต้องการได้ผลคูณตัวถัดไปที่หารด้วย 8 ลงตัวและใกล้เคียง 45 มากที่สุด ผมจึง 45 / 8 = 5... ซึ่งมีทศนิยม หมายความว่า 8 * 6 คือผลคูณที่ใกล้เคียงกับ 45 มากที่สุดและหารด้วย 8 ลงตัว รวมถึง 45 — (8 * 6)ยังเป็นค่าลบซึ่งตรงตามเงื่อนไข ax + by = d ที่ d < 0 ด้วย
ในกรณีที่ ax + by = d แล้ว d > 0 เพียงเปลี่ยนให้เป็นปัดลงก็เรียบร้อยแล้วครับ
ส่วนกรณีที่ ax + by = d แล้ว d = 0 ไม่สามารถเกิดขึ้นได้ครับ เนื่องจาก d คือความต่างของลำดับ และไม่มีสมการคู่ไหนจับคู่กับตัวเอง หมายความว่าไม่มีลำดับเดียวกัน
สุดท้ายแล้ว ค่า c จะต้องถูกหักลบด้วยลำดับเสมอ เนื่องจากสมการ ax + by = d เมื่อแทนค่า x และ y ให้เป็นจริงแล้ว มันจะเป็นจริงกับ t + i แทน
สมมติว่าเราเอา Bus ID ลำดับที่ 2 (x) และ 3 (y) มารวมกันเป็นสมการ เราจะได้สมการ t = c + kn ที่มีค่า t ที่แท้จริงเป็น t + 2 แทน (เพิ่มขึ้นตามลำดับของ x) ดังนั้นจาก t + 2 = c + kn แล้วเราอยากได้ t เราสามารถ t = (c — 2) + kn แทน หรือ c — i แทนครับ
เมื่อเราได้ค่า c และ k ของแต่ละสมการกันแล้ว เราต้อง Loop โดยมีค่าเริ่มจาก c ของสมการที่มีค่ามากที่สุด คือ Bus ID ที่สูงที่สุด และ Bus ID ที่สูงรองลงมา
ใน (i % lcm[j] — starts[j]) % lcm[j] != 0 หมายถึงการตรวจสอบว่า k | t — c ของแต่ละสมการเป็นจริงหรือไม่ โดยผมเลือกที่จะนำ i % lcm[j] ก่อนเพื่อเพิ่มความเร็วในการลบครับ
คร่าวๆ ของโจทย์ในส่วนนี้เป็นประมาณนี้ครับ โดย Source Code ของโจทย์ส่วนนี้มีดังนี้
สรุปง่ายๆ เลยว่า โจทย์ในส่วนที่สองเนี่ยยากขึ้นกว่าวันก่อนๆ มากครับ ที่สำคัญคือตอนผมรันครั้งแรก ผม Print Debug ออกมาในทุก Loop ด้วย (การ Print Debug ทำให้โปรแกรมทำงานนานขึ้นมากนะครับ) จนผมนั่งดูมัน Run ไป 30 นาที ผมเลยตัดสินใจเอา Debug ออก สุดท้ายเหลือ 30 วินาทีครับ 😂
(ทีแรกผมนึกว่าผมมาผิดทางแล้วนะครับเนี่ย)
ต้องขอบคุณ Google Sheet ที่มาช่วยในการคำนวณด้วยนะครับ (ถ้าไม่มี ผมว่าผมไม่รอดแน่)
เท่าที่ผมดูจากหลายๆ แหล่ง Part 2 เขาจะใช้วิธี CRT (Chinese Remainder Theorem) กันครับ
สุดท้ายนี้ Blog นี้อาจจะยาวหน่อย และอาจจะมีบางจุดไม่ Clear บ้าง (เพราะตอนนี้ผมอึนใช้ได้เลยครับ) ต้องขออภัยไว้ด้วยนะครับ ถ้ามีโอกาสจะเข้ามาปรับปรุงอีกครั้งนึง
และขอขอบคุณที่อ่านมาจนถึงตอนนี้ด้วยครับ
สำหรับคนที่ต้องการดู Source Code สามารถเข้าไปใน GitHub Repository ของผมได้ตามนี้ครับ
