Day 7 — Advent of Code 2020

สวัสดีกับวันที่ 7 ของ Advent of Code แล้วครับ (ไม่น่าเชื่อว่าจะทำมาครบ 1 สัปดาห์ได้)

ขอเกริ่นก่อนเลยว่า โจทย์วันนี้ถือว่าเริ่มยากขึ้นกว่า 6 วันที่แล้วครับ ดังนั้น Blog นี้อาจจะยาวหน่อยนะ

ใครที่สนใจเล่น สามารถเข้าไปยังเว็บไซต์ด้านล่างได้เลยครับ

Advent of Code

Day 7: Handy Haversacks

โจทย์ในวันนี้เกี่ยวกับกระเป๋า โดยโจทย์ต้องการให้เราหาว่า มีกระเป๋าทั้งหมดกี่สีที่สามารถใส่กระเป๋าสี shiny goldเข้าไปข้างในได้ตามเงื่อนไขที่ระบุเอาไว้

สำหรับเงื่อนไขของโจทย์ อยู่ใน Input File ของแต่ละคนเลยครับ มีลักษณะดังนี้

vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
faded blue bags contain no other bags.
dotted black bags contain no other bags.

แต่ละบรรทัดใน Input File คือเงื่อนไขแต่ละข้อ อย่างเช่น vibrant plum bags contain 5 faded blue bags, 6 dotted black bags. หมายความว่า กระเป๋าสี vibrant plum สามารถใส่กระเป๋าสี faded blue และ dotted black ได้ (สำหรับจำนวนใบ จะถูกนำไปใช้ในโจทย์ส่วนที่ 2)

โดยเราต้องการหาว่า กระเป๋าใบไหนบ้างที่สามารถใส่กระเป๋าสี shiny gold เข้าไปข้างในได้บ้าง ทั้งนี้ในกระเป๋าที่อยู่ในกระเป๋าก็ยังสามารถใส่กระเป๋าได้ ถ้าเงื่อนไขระบุเอาไว้ ลองดูตัวอย่างนี้ครับ

red bags contain 2 green bags.
green bags contain 3 shiny gold bags.
shiny gold bags contain no other bags.

จากตัวอย่าง กระเป๋าสี green เป็นหนึ่งในคำตอบแน่ๆ และกระเป๋าสี red ก็เป็นคำตอบเช่นกัน เพราะกระเป๋าสี red สามารถใส่กระเป๋าสี green ที่สามารถใส่กระเป๋าสี shiny gold ได้

(ผมกลัวว่าผมจะอธิบายไม่เข้าใจ ผมเลยวาดรูปขึ้นมาเลย)

จะเห็นว่า ทั้งกระเป๋าสี red และ green ก็สามารถมีกระเป๋าสี shiny gold ได้เหมือนกัน แปลว่ามีทั้งหมด 2 สีที่สามารถใส่กระเป๋าสี shiny gold ตามเงื่อนไขได้

พอเข้าใจตัวโจทย์คร่าวๆ แล้ว การ Implement ของโจทย์ในข้อนี้ ผมข้อแบ่งออกเป็น 2 ส่วนใหญ่ๆ คือ

1. สร้าง Inverted Index เพื่อเก็บว่า กระเป๋าสีไหนสามารถอยู่ในกระเป๋าสีใดได้บ้าง
2. ใช้ Depth First Search ในการค้นหาว่า กระเป๋าสี shiny gold สามารถไปอยู่ในกระเป๋าสีใดได้บ้าง

ฟังดูแล้วอาจจะงงๆ เดี๋ยวผมจะค่อยๆ อธิบายในแต่ละส่วนให้ฟัง พร้อม Source Code ประกอบนะครับ

ก่อนอื่นเลย Inverted Index คือ การแปลงข้อมูลจาก x -> f(x) ให้เป็น f(x) -> x แทน หรือถ้าพูดในบริบทของโจทย์ข้อนี้ ความหมายก็คือ แปลงจาก Input File ที่มีเงื่อนไขเป็น bag -> inner bags เป็น bag -> outer bags แทน

ผมขอยกตัวอย่าง Input File เพื่อให้เข้าใจมากขึ้นนะครับ

a contain b, c
c contain b
b contain d

หากเราสร้าง Inverted Index ของ Input File ข้างต้นแล้ว เราจะได้

a can be contained by -
b can be contained by a, c
c can be contained by a
d can be contained by b

หรือ เราจะได้เงื่อนไขที่บอกว่า กระเป๋าใบนี้สามารถอยู่ในกระเป๋าใบไหนได้บ้าง ซึ่งเงื่อนไขในลักษณะของ Inverted Index สามารถเอาไปใช้ต่อได้ง่ายกว่ารูปแบบเดิมครับ

ใครที่สนใจเรื่อง Inverted Index สามารถไปอ่านใน Link ต่างๆ ตามนี้ได้เลยครับ

Inverted index

Inverted Index - GeeksforGeeks

เบื้องต้น Inverted Index เอาไปใช้เกี่ยวกับพวก IR (Information Retrieval) เยอะมากๆ เลยครับ (อย่างพวก Search Engine) เพราะมันช่วยเพิ่มความเร็วในการค้นหาคำต่างๆ ได้

Information retrieval

สำหรับการ Implement ในส่วน Inverted Index เราต้องเริ่มจากการสร้าง Map (หรือ Dictionary)​ มารองรับข้อมูลจาก Input File ก่อนครับ

ลักษณะของ Map ที่ผมสร้างขึ้น ผมต้องการให้ Key เป็นสีของกระเป๋าซึ่งเป็น String และ Value เป็น Set ของสีของกระเป๋า หรือ Set<String> (ที่ผมใช้ Set เพราะไม่ต้องการให้มีสีของกระเป๋าที่ซำ้กันครับ เนื่องจากจะซำ้กัน หรือไม่ซำ้ก็ไม่มีผลต่อการหาอยู่แล้ว และหากมีตัวซำ้จะทำให้ Time และ Space มากขึ้นเปล่าๆ ด้วยครับ)

หลังจากนั้น ผมจะเริ่มอ่าน Input File มาทีละบรรทัด แล้วทำการ Split String

ก่อนอื่นเลย ผมอยากจะอธิบายลักษณะของเงื่อนไขอีกครั้ง เพื่อให้เข้าใจในส่วนการ Split String

vibrant plum bags contain 1 faded blue bag, 6 dotted black bags.

ลักษณะของเงื่อนไขในแต่ละบรรทัด ประกอบด้วย

1. สีของกระเป๋าด้านนอก (จากตัวอย่างเป็น vibrant plum)
2. จำนวนของกระเป๋าด้านใน (จากตัวอย่างเป็น 5 และ 6 ตามลำดับ)
3. สีของกระเป๋าด้านใน (จากตัวอย่างเป็น faded blue และ dotted black ตามลำดับ)

ดังนั้น ผมอาจจะสามารถเขียนเป็น Regular Expression คร่าวๆ ของเงื่อนไขได้ดังนี้

[outer_bag_color] bags contain ([inner_bag_number] [inner_bag_color] bag(s){0,1}(,|.))*

จากลักษณะของ Map ผมต้องการ Key เป็น [outer_bag_color] ดังนั้น ผมเพียงแค่ Split String โดยใช้ bags contain เป็น Delimiter ก็จะได้ [outer_bag_color] มาแล้ว

ใน Source Code ผมใช้ [outer_bag_color] เป็น bagColor แทนนะครับ

ถัดมา ผมจะต้องแยกแต่ละสีของกระเป๋าด้านในออกจากกัน โดยสิ่งที่ใช้แยกได้ คือ คำว่า bag หรือ bags ตามด้วยสัญลักษณ์ . หรือ ,

หลังจากนั้น ผมจะนำข้อมูลของเงื่อนไขในแต่ละบรรทัดใส่เข้าไปยัง Map ก่อนหน้า โดยสมาชิกใน innerBagArray แต่ละตัว ยังคงมี [inner_bag_number] อยู่ ดังนั้นจะต้องนำออกด้วยเช่นกัน นอกจากนั้นยังมีเงื่อนไข no other bags สำหรับกระเป๋าที่ไม่สามารถใส่กระเป๋าใดๆ เข้าไปได้ โดยผมจะข้ามกระเป๋านั้นไป

เมื่อทำทุกอย่างเสร็จ เราจะได้ Inverted Index ของเงื่อนไขทั้งหมดใน Input File มา

หลังจากนั้น เราจะนำ Inverted Index มาหาคำตอบของโจทย์ หรือ จำนวนกระเป๋าทั้งหมดที่สามารถใส่กระเป๋าสี shiny gold ได้

เบื้องต้น เนื่องจากคำตอบของข้อนี้คือจำนวนสีของกระเป๋า ซึ่งไม่ซำ้กัน ดังนั้นผมจะใช้ Set เป็น Data Structure ในการเก็บคำตอบ

สำหรับการหา ผมจะใช้แนวคิดของ Depth-First Search ครับ

Depth-First Search เป็น Graph Traversal Algorithm ประเภทหนึ่งที่ใช้ในการ Traverse ไปยังเป้าหมาย โดยกรณีที่แย่ที่สุด คือ การค้นหาข้อมูลทุกตัวแต่ไม่พบ

Depth-First Search มี Algorithm คู่เคียงอีกตัวนึง คือ Breadth-First Search โดยเป็น Graph Traversal Algorithm เช่นกัน เพียงแต่มีแนวคิดคนละแบบ และวิธี Implement คนละแบบ

สำหรับ Depth-First Search นั้น การค้นหาจะไปในทางใดทางหนึ่งในสุดก่อนแล้วจึงค่อยไปยังเส้นทางถัดไป

ผมขอยกตัวอย่างง่ายๆ เป็น สมมติว่ามีถํ้าอยู่ 2 ถํ้า แล้วเรารู้ว่าหนึ่งในนั้นมีสมบัติอยู่ การค้นหาแบบ Depth-First Search คือ การค้นหาในถํ้านึงในทั่วก่อน แล้วค่อยไปค้นหาอีกถํ้านึง (ส่วน Breadth-First Search จะค้นหาในถํ้านึงไปในระดับนึง แล้วย้อนกลับมาค้นหาในอีกถํ้านึงในปริมาณที่เท่ากันไปเรื่อยๆ)

ใครที่สนใจสามารถไปอ่านเพิ่มได้ใน Link ต่างๆ พวกนี้ครับ

Depth-first search

Breadth-first search

(เพิ่มเติมให้เล็กน้อยว่า DFS และ BFS ใช้กันบ่อยมากๆ ในโจทย์แก้ปัญหาแนวนี้ครับ)

จริงๆ ในโจทย์ข้อนี้ การใช้ DFS และ BFS ไม่ได้มีนัยสำคัญเท่าไหร่นะครับ จะใช้การค้นหาแบบใด Time และ Space Complexity น่าจะใกล้เคียงกันมากๆ (โดยส่วนตัวผมเป็น Big Fan ของ DFS มากกว่า แหะๆ)

สำหรับการ Implement DFS เราจะต้องใช้ Data Structure เป็น Stack เข้ามาช่วย (แต่ใน Implementation ผมจะใช้ java.util.Deque (Double Ended Queue) แทน เนื่องจากเหตุผลด้าน Performance ครับ)

Java Stack vs Queue performance

Double Ended Queue (Deque) คือ Queue ที่มีการ Implement ให้ Head อยู่ทั้งหน้าสุดและหลังสุด จึงสามารถใช้ Operation ของทั้ง Queue และ Stack ได้

Deque (Java Platform SE 7 )

ในการ Implement ส่วนของ DFS นั้น ผมจะให้โปรแกรมของผม Loop ตาม Inverted Index ไปเรื่อยๆ ว่า จากระเป๋าสี shiny gold มีกระเป๋าไหนที่ใส่ได้บ้าง แล้วกระเป๋าที่ใส่กระเป๋าสี shiny gold ได้ มีกระเป๋าที่ใส่กระเป๋านั้นได้อีกไปเรื่อยๆ

และสุดท้ายคือการแสดงค่าของจำนวนกระเป๋าตามที่โจทย์ต้องการ และเนื่องจากผมใช้ Set เป็น Data Structure อยู่แล้ว มันมี Method size() ให้ใช้อยู่ ก็สามารถใช้ได้ทันทีครับ

ดังนั้น Source Code ทั้งหมดในโจทย์ส่วนแรกของวันนี้มีดังนี้ครับ

สำหรับโจทย์ส่วนที่ 2 เขาต้องการให้หาจำนวนของกระเป๋าที่สามารถใส่ลงไปในกระเป๋าสี shiny gold 1 ใบได้

ประเด็นของโจทย์ส่วนที่ 2 คือ เราไม่ควรใช้ Inverted Index ครับ เราควรใช้ Index ปกติตามที่เขียนมาใน Input File เลย และหลังจากนั้นค่อยทำ DFS เพื่อหาว่าสามารถใส่กระเป๋าได้ทั้งหมดกี่ใบ

การสร้าง Index สำหรับโจทย์ส่วนที่สอง ผมเลือกใช้ Map โดยมี Key เป็นสีของกระเป๋าซึ่งเป็น String เหมือนเดิม แต่ผมเปลี่ยนให้ Value เป็น Map อีกอันนึง เนื่องจากผมต้องการเก็บ [inner_bag_number] ของแต่ละ [inner_bag_color] ด้วย

นอกจากตัว Data Structure ที่เปลี่ยนไปเล็กน้อย จะมีการ Split String ที่ต้องเปลี่ยน เนื่องจากเราต้องการ [inner_bag_number] ด้วย ดังนั้นผมจะ Split โดยใช้ ' ' (ช่องว่าง) ตัวแรกเป็น Delimiter แทน

อีกส่วนนึงที่ต้องเปลี่ยน คือ เราไม่ได้ทำ Inverted Index ดังนั้น เราสามารถ Map สีของกระเป๋ากับสีของกระเป๋าที่อยู่ข้างในได้โดยตรงเลย

เมื่อได้ Index ของเงื่อนไขทั้งหมดใน Input File มาแล้ว ถัดมาคือการทำ DFS เพื่อหาว่ากระเป๋าสี shiny gold สามารถใส่กระเป๋าข้างในได้ทั้งหมดกี่ใบ

สำหรับการคำนวณ ผมขอยกตัวอย่างเป็น Input File คร่าวๆ ดังนี้ครับ

shiny gold -> 2b, 5c
b -> 3c
c -> 2d
d -> (none)

จากเงื่อนไขข้างต้น กระเป๋าสี shiny gold สามารถใส่กระเป๋าสี b และ c รวมกัน 7 ใบ และภายในกระเป๋าสี b ยังสามารถใส่กระเป๋าสี c ได้อีก 3 ใบ รวมถึงกระเป๋าสี c ก็ยังสามารถใส่กระเป๋าสี d ได้อีก 2 ใบ หรือ

|shiny gold| = 2|b| + 5|c|
|b| = 3|c| + 3
|c| = 2|d| + 2
|d| = 0 + 1 = 1
then,
|c| = (2 * 1) + 1 = 3
|b| = (3 * 3) + 1 = 10
|shiny gold| = (2 * 10) + (5 * 3) = 35

หรือตามรูปนี้ครับ

จริงๆ ถ้าลองปรับสมการดู จะเห็นว่าลักษณะมันเป็น

|shiny gold| = (2 * ((3 * ((2 * 1) + 1)) + 1)) + ((2 * 1) + 1) = 22

จะสังเกตว่า มันมีการ Recursive ไปเรื่อยๆ (มองดูดีๆ เราอาจจะใช้แนวคิด Memoization ได้นะครับเนี่ย)

Memoization

แต่วิธีของผมจะใช้ Recursion แทน โดยจะ Recursive ผ่านการใช้ Stack เข้ามาช่วย (ซึ่งโดยส่วนตัว ผมคิดว่ามันคือ DFS ที่มี Search Space เป็นแต่ละ Function Call เช่นกัน)

Recursion and the Call Stack Explained By Reading A Book

แนวคิดการทำ Recursion ของผม ขออธิบายเป็นรูปดังนี้ครับ

ค่าที่อยู่ใน Stack แต่ละชั้น ประกอบด้วยค่าทั้งหมด 3 ค่า คือ สีของกระเป๋าปัจจุบัน จำนวนของกระเป๋า จำนวนตัวคูณ (ได้มาจากจำนวนกระเป๋าของชั้นก่อน)

โดยใน Implementation ของผม ผมเลือกแยก Stack ออกเป็น 3 Stacks แทน

การ Traverse ไปยังแต่ละ Node ของ Graph (ด้านซ้ายของ Stack ในรูป) มีการคำนวณ จำนวนกระเป๋าของ Node นั้นทั้งหมด (ไม่นับกระเป๋าข้างใน) หรือ จากรูป คือ ผลคูณสีแดง

ผมเลือกใช้ currentCount * parentCount ดังนั้นผมจะต้องส่งค่า parentCount เข้ามาใน Stack ด้วย

และสุดท้าย ค่า totalBagCount ที่ได้ มันนับรวมกระเป๋าสี shiny gold เข้าไปด้วย ดังนั้นเราจึงต้องหักลบกระเป๋านี้ออกไป

เป็นอันเรียบร้อยสำหรับโจทย์ส่วนที่ 2 ของวันนี้ครับ โดยด้านล่างจะเป็น Source Code ทั้งหมดของโจทย์ส่วนที่ 2

ว่ากันตามตรงว่า โจทย์ในวันนี้ใช้ความรู้เยอะกว่า 6 วันที่แล้วมากครับ ทั้ง Inverted Index, Graph Search, DFS มาหมดเลย

สำหรับวิธีคิดของผม ผมคิดว่าน่าจะยังพัฒนาต่อได้อีก อย่างเช่น เราอาจจะทำ Memoization เอาไว้ ทำให้ตอนคำนวณค่า เราไม่จำเป็นต้องมาคำนวณซำ้ซ้อน

สุดท้ายนี้ ขอบคุณทุกคนที่อ่านมาจนถึงตอนนี้นะครับ วันนี้เขียน Blog ยาวมากกก (เขียนไปเกือบ 3 ชั่วโมงได้เลย) ​ถ้าอ่านถึงตรงนี้ได้เนี่ย ผมนับถือเลย (ฮ่าๆ)

สำหรับ Repository ของ Advent of Code 2020 ของผมตาม Link นี้เลยครับ

PnXGUiDE/AoC2020

ฝากเพจเช่นเคยครับ https://www.facebook.com/PNXBlog

ขอบคุณมากฮะ 🙂