Day 21 — Advent of Code 2020
สวัสดีย้อนหลังถึงวันที่ 21 ของ Advent of Code 2020 นะครับ
สำหรับใครที่สนใจเล่น สามารถเข้าไปใน Link ด้านล่างนี้ได้เลยครับ
Day 21: Allergen Assessment
โจทย์ของวันที่ 21 เกี่ยวกับการหาว่าผลิตภัณฑ์อาหารใดที่มีส่วนผสมอะไรบ้าง โดยแต่ละผลิตภัณฑ์ระบุ Ingredient เอาไว้ในรูปแบบของภาษาที่เราอ่านไม่ออก
mxmxvkd kfcds sqjhc nhmsแต่ยังดีที่มีการระบุส่วนประกอบที่อาจทำให้แพ้ (Allergens) เอาไว้เป็นภาษาอังกฤษ ซึ่ง Allergen ก็ถูกระบุไว้ในส่วน Ingredient เช่นกัน
โจทย์กำหนด Input File มาในลักษณะดังนี้
mxmxvkd kfcds sqjhc nhms (contains dairy, fish)
trh fvjkl sbzzf mxmxvkd (contains dairy)
sqjhc fvjkl (contains soy)
sqjhc mxmxvkd sbzzf (contains fish)ต้องการหาว่า Ingredient ใดที่ไม่ได้เป็น Allergen แน่ๆ
สำหรับวิธีการคิดของผมในโจทย์นี้เกิดจาก Assumption ที่ว่า การที่ Ingredient นั้นๆ จะเป็น Allergen ได้ Ingredient นั้นจะต้องอยู่ในทุกผลิตภัณฑ์ที่มี Allergen นั้นกำกับ
เช่น Allergen dairy อยู่ใน mxmxvkd kfcds sqjhc nhms และ trh fvjkl sbzzf mxmxvkd และ Ingredient ที่อยู่ในทุกผลิตภัณฑ์มีแค่ mxmxvkd เท่านั้น
พูดในเชิงทฤษฎี การหา Ingredient ที่เป็น Allergen นั้น เกิดจากการนำ Ingredient ทั้งหมดของทุกผลิตภัณฑ์ที่มี Allergen มา Intersect กัน
จากตัวอย่างข้างบน พบว่า
dairy -> {mxmxvkd kfcds sqjhc nhms} ^ {trh fvjkl sbzzf mxmxvkd} = {mxmxvkd}
fish -> {mxmxvkd kfcds sqjhc nhms} ^ {sqjhc mxmxvkd sbzzf} = {mxmxvkd sqjhc}
soy -> {sqjhc fvjkl}ดังนั้นตัวที่อยู่ใน Set ผลลัพธ์ของ Allergen ทุกตัว คือ Ingredient ที่มีโอกาสเป็น Allergen นั้นๆ ได้
โจทย์ต้องการจำนวนของ Ingredient ที่ไม่ใช่ Allergen ทั้งหมด ดังนั้นเราเพียงแค่นับตัวที่ไม่ได้อยู่ใน Set ข้างต้นเพียงเท่านั้น
สำหรับโจทย์ในส่วนที่ 2 โจทย์ให้เรา Map ว่า Ingredient แต่ละตัวเป็น Allergen ใดบ้าง
วิธีคิด คือ หา Allergen ที่มี Ingredient ที่เป็นไปได้แค่ตัวเดียวก่อน แล้วค่อยๆ ตัด Choice ของแต่ละ Allergen ไปเรื่อยๆ ตามตัวอย่างด้านล่างนี้
dairy -> {mxmxvkd}
fish -> {mxmxvkd sqjhc}
soy -> {sqjhc fvjkl}dairy = mxmxvkd
fish -> {sqjhc}
soy -> {sqjhc fvjkl}fish = sqjhc
soy -> {fvjkl}soy = fvjkl
สำหรับโจทย์ในวันที่ 21 ก็ใช้ปรับทุกข์ของโจทย์ในวันที่ 20 ได้ดีมากเลยครับ รู้สึกว่ากลับมาง่ายเหมือนช่วงสัปดาห์ที่แล้วอีกครั้งนึง 😅
สุดท้ายนี้ขอขอบคุณทุกคนที่ยังติดตามจนถึงวันนี้นะครับ
หากใครต้องการดู Source Code ทั้งหมดของ Advent of Code 2020 ของผม สามารถเข้าไปดูได้ใน GitHub Repository ของผมด้านล่างนี้ครับ
