สวัสดีครับทุกคน ... ยินดีต้อนรับสู่บล็อก Quackbase อีกครั้งหลังจากเปิดบทความแรกไปด้วยบทความของเบิ้ล (@tanaphon) ในรอบนี้ผมอยากพูดถึงกิจกรรมที่ผ่านไปไม่นานในช่วงเดือนธันวาคมที่ผ่านมา ซึ่งก็คือ Advent of Code 2024 ว่าแล้วเรามาเริ่มต้นด้วยการทำความรู้จัก AOC กันก่อนครับ

Advent of Code คืออะไร

ซึ่งเป็นกิจกรรมที่เปิดให้ทุกคนเข้ามาแก้โจทย์ปัญหาโดยการเขียนโค้ดหรือแม้แต่การใช้ Tools ก็ทำได้แล้วแต่ความคิดสร้างสรรค์ของแต่ละคน โดยจะมีโจทย์มาวันละข้อเริ่มจากวันที่ 1 ถึงวันที่ 25 เหมือนเป็นการเขียนโค้ดแก้โจทย์เพื่อเป็นการพักผ่อนจากงานแถมได้บรรยากาศ Festive หน่อย ๆ 😆

ซึ่งโจทย์ละข้อจะมีทั้งหมด 2 Parts ซึ่งเมื่อเราทำได้แต่ละ Part ก็จะได้ดาว 1 ดวงเมื่อทำครบทั้ง 25 ก็จะ ได้ดาวทั้งหมด 50 ดวง ในบทความนี้ผมจะนำโจทย์คิดว่าทำแล้วสนุกและไม่ยากไปที่จะเอามาเขียนบล็อกมาพูดคุยนะครับซึ่งก็คือโจทย์วันที่ 19 (ความจริง 21 ก็อยากเขียนแต่เดี๋ยวจะยาวไป) ว่าแล้วเราก็เริ่มกันเลย !

Day 19 - Part 1

โจทย์ข้อนี้มีอยู่ว่าเราะต้องเรียงผ้าขนหนู (towels) ให้ได้ตามดีไซน์ (design) ที่กำหนดมา ซึ่งแต่ละผ้าขนหนูแต่ะผืนจะมีลาย (strip) เป็นแถบสีต่าง ๆ ประกอบด้วย white (w), blue (u), black (b), red (r) และ or green (g) โดยที่โจทย์ก็คือเราต้องหาว่าดีไซน์ที่ให้มานั้นสามารถนำผ้าขนหนูมาเรียงกันได้หรือไม่ โดยที่ผ้าขนหนูมีไม่จำกัดแต่มีลายที่จำกัดตาม Input ที่ให้มา มาดูให้เข้าใจกว่านี้จากตัวอย่าง Input กันครับ

Example Input

r, wr, b, g, bwu, rb, gb, br

brwrr
bggr
ubwu

จากตัวอย่าง Input จะเห็นได้ว่ามี 2 ส่วน ซึ่งส่วนแรกคือผ้าขนหนูลายต่าง ๆ ยกตัวอย่างเช่น bwu คือลายที่มีสีดำ (b), ขาว (w), น้ำเงิน (u) หรือผ้าขนหนูที่มีแค่สีเดียวอย่างเช่นดำ (b)

ส่วนในส่วนที่สองนั้นก็คือดีไซน์ที่เราจะต้องหาว่านำผ้าขนหนูมาเรียงกันได้หรือไม่อย่างเช่นในตัวอย่างจะมี 3 ดีไซน์ brwrr, bggr และ gbbr หากเราแยกมาดูแต่ละดีไซน์จะเห็นว่ามี 2 ดีไซน์ที่นำผ้าขนหนูมาเรียงกันได้และ 1 ดีไซน์ที่ทำไม่ได้ดังนี้

• brwrr สามารถใช้ผ้าขนหนู br, wr, r หรือ b, r, wr, r
• bggr สามารถใช้ผ้าขนหนู b, g, g, r
• ubwu ไม่สามารถสร้างลายจากผ้าขนหนูที่มีได้

ซึ่งใน Part 1 นั้นได้ถามว่าจำนวนดีไซน์ที่สามารถสร้างได้มีเท่าไหร่ซึ่งคำตอบก็คือ 2

เอาหล่ะพอรู้โจทย์แล้วเรามาเริ่มแก้โจทย์กันเลยดีกว่าครับ 👽

เริ่มจากส่วนรับ Input

fn main() {
    let mut lines = io::stdin().lines();
    let mut designs: Vec<String> = vec![];

    let towels: HashSet<String> = lines
        .next()
        .unwrap()
        .unwrap()
        .split(", ")
        .map(String::from)
        .collect();
    lines.next(); // Skip empty line
    designs.extend(lines.filter_map(|l| l.ok()));

    // TODO
    // Solve Part 1 and Part 2
}

พอได้ทำรู้สึกว่า Rust เหมาะแก่การรับ stdin  แปลก ๆ กว่า Go เยอะเลยเนื่องจาก Higher-Order Functions ให้ใช้เยอะ ซึ่งจากประสบการการใช้ Go เล่น AOC ปีอื่นรู้สึกเหนื่อยและค่อนข้างน่าเบื่อที่จะแปลง Input ในแต่ละข้อ

มาถึงขั้นตอนการแก้ปัญหาเราจะแก้กันยังไงดีซึ่งจริง ๆ แล้วปัญหานี้หากคิดง่าย ๆ เราสามารถแก้ด้วย Recursive ได้ง่าย ๆ ยกตัวอย่างเช่น brwrr เราสามารถแตกเป็น Recursion Tree ได้ดังนี้

f("brwrr")
│
├── b + f("rwrr")
│   │
│   └── r + f("wrr")
│       │
│       └── wr + f("r")
│           │
│           └── r --> ok!
│
└── br + f("wrr")
    │
    └── wr + f("wrr")
        │
        └── r --> ok!

เมื่อผมลองสังเกตซักพักก็เห็นว่ามันสามารถเขียนเป็น Dynamic Programming (DP) ได้แล้วเพราะจะเห็นว่าเราสามารถแตกเป็นปัญหาย่อย ๆ ได้ (subproblem) แล้วสามารถแก้แบบ Bottom-Up ได้ แล้วก็คิดว่าหาก Recursive ไปตรง ๆ ก็คงจะไม่ผ่าน Part 2 อยู่ดีเพราะ Input ของจริงนั้นยาวกว่าตัวอย่างมากอย่างเช่น ggbrbwgbbugwrwgbgrrugwrrbgwubuurrrwgbrwbbuwggububuwurbwbg

ผมก็เลยตัดสินใจเขียนเป็นแบบ DP ตั้งแต่ Part 1 เลย (ในบทความนี้จะไม่ได้ลงอธิบาย DP ตั้งแต่เริ่มนะครับ) เมื่อเราเลือกที่จะทำ DP กันเรามาเขียน Recurrence Formula กันก่อนครับ โดย base case ให้เป็นเมื่อ function ได้ทำงานจนเลยตัวอักษรสุดท้ายของ design ที่ได้รับมาซึ่งหมายความว่า design ได้ถูกเติมจนครบหมดแล้ว โดยเราจะให้ base case เป็น true (boolean) หมายความว่า design นี้สามารถสร้างได้

สุดท้ายแล้วจะได้ Recurrence Formula มาดังนี้

Given:
n = the lenght of the design
design = the string of the design

Recurrence Formula:
dp[n] = true (base case)
dp[i] = ⋁(dp[j + 1]) where:
    - i ≤ j < n
    - design[i..j] ∈ towels

เราสามารถเปลี่ยนเป็น Rust ได้ดังนี้

fn is_possible(design: &String, towels: &HashSet<String>) -> bool {
    let n = design.len();
    let mut dp = vec![false; n + 1];
    dp[n] = true;
    for i in (0..n).rev() {
        for j in i..n {
            let word = design[i..=j].to_string();
            if towels.contains(&word) {
                dp[i] = dp[i] | dp[j + 1];
            }
        }
    }
    dp[0]
}

fn part_1(designs: Vec<String>, towels: HashSet<String>) {
    println!(
        "{}",
        designs.iter().filter(|d| is_possible(d, &towels)).count()
    )
}

หลังจากนำ Puzzle Input มาลองรันแล้วส่งคำตอบก็ผ่านได้ไม่มีปัญหาครับสำหรับ Part 1 ซึ่งคิดว่าน่าจะผ่าน Part 2 ได้ไม่ยากเพราะรู้สึกว่า Time Complexity นั้นดีแล้ว ในข้ออื่นนั้นมีหลาย ๆ ครั้งที่ทำ Part 1 ไปแล้วต้องรื้อทำ Part 2 ใหม่เพราะว่าดันไปเขียน Brute Force แก้ปัญหาแบบง่าย ๆ 😅 (เราจะไม่เห็นโจทย์ Part 2 ก่อนที่จะทำ Part 1 ผ่าน) โอเค ... ไปต่อกันที่ Part 2 เลยครับ

Day 19 - Part 2

โจทย์ Part 2 ก็คือว่าจากเดิมเราต้องหาว่าดีไซน์ที่ให้มาสามารถสร้างได้มั้ยเปลี่ยนเป็นว่าดีไซน์ที่ให้มาสามารถนำผ้าขนหนูมาจัดเรียงได้กี่รูปแบบ แล้วนำจำนวนรูปแบบของแต่ละดีไซน์มาบวกกันเป็นคำตอบสุดท้าย อย่างเช่นตัวอย่างเดิม

• brwrr สามารถใช้ผ้าขนหนู br, wr, r หรือ b, r, wr, r => 2 รูปแบบ
• bggr สามารถใช้ผ้าขนหนู b, g, g, r => 1 รูปแบบ
• ubwu ไม่สามารถสร้างลายจากผ้าขนหนูที่มีได้

คำตอบสุดท้ายก็คือ 1+2 = 3 รูปแบบ

ดังนั้นเราก็แค่เปลี่ยนจากการ OR ให้เป็นการบวกแทนซึ่งจะเขียน Recurrence ใหม่ได้ดังนี้

Given:
n = the lenght of the design
design = the string of the design

Recurrence Formula:
dp[n] = 1 (base case)
dp[i] = Σ(dp[j + 1]) where:
    - i ≤ j < n
    - design[i..j] ∈ towels

ผมก็แก้ Code ใหม่ซึ่งก็จะใช้หาคำตอบใน Part 1 ไปด้วยเลย

fn is_possible_with_count(design: &String, towels: &HashSet<String>) -> u64 {
    let n = design.len();
    let mut dp = vec![0; n + 1];
    dp[n] = 1;
    for i in (0..n).rev() {
        for j in i..n {
            let word = design[i..=j].to_string();
            if towels.contains(&word) {
                dp[i] = dp[i] + dp[j + 1];
            }
        }
    }
    dp[0]
}

fn part_1_and_2(designs: Vec<String>, towels: HashSet<String>) {
    let possible_patterns: Vec<u64> = designs
        .iter()
        .map(|d| is_possible_with_count(d, &towels))
        .filter(|&n| n > 0)
        .collect();

    println!("Part 1: {}", possible_patterns.len());
    println!("Part 2: {}", possible_patterns.iter().sum::<u64>());
}

เรียบร้อยครับเมื่อส่งคำตอบมาก็ถูกต้องจะเห็นว่าโจทย์ข้อนี้ถ้าใช้ DP นั้นค่อนข้างตรงตัวครับทำให้ผ่านได้ไม่ยากมากแต่ความจริงคิดว่าเขียน Recursive แล้วใช้ Memorization ก็ผ่านได้เหมือนกันครับไม่ยากมาก ยังไงก็ลองไปเล่นกันดูนะครับ

ส่งท้าย

อยากให้ทุกคนไปลองเล่นกันเยอะ ๆ ลองเลือกภาษาที่ตัวเองอยากฝึกเครื่องมือใหม่ ๆ ที่อยากลองใช้ ส่วนใครต้องการตัวช่วยสามารถเข้าไปที่ Community ใน Reddit ได้ครับ r/adventofcode แล้วพบกันใหม่ใน AOC2025 ครับ รอดูว่าจะเป็นภาษาอะไร :)