Day 2: Red-Nosed Reports | Advent of Code 2024 | Swift | 中文

題目

https://adventofcode.com/2024/day/2

---

第一部分

題目會給像是這樣的數組。以每一行為單位，需要判斷這一行是不是「安全」。最後回傳「安全」的個數。

7 6 4 2 1
1 2 7 8 9
9 7 6 2 1
1 3 2 4 5
8 6 4 4 1
1 3 6 7 9

安全的條件

• 數組是單一方向的「遞增」或「遞減」
  • 只要當其中一個數的增減方向和其他數字不同，就判定為不安全
• 兩元素的差必須介於 1 ~ 3 （包含 1, 3）之間

以題目的數組為例：

7 6 4 2 1 // 安　全 | 遞減 | 兩元素之差都在 1 到 3 之間
1 2 7 8 9 // 不安全 | 遞增 | 2 和 7 的差是 5
9 7 6 2 1 // 不安全 | 遞減 | 6 和 2 的差是 4
1 3 2 4 5 // 不安全 | 遞增 | 2 相對於 3 是減
8 6 4 4 1 // 不安全 | 遞減 | 4 和 4 的差是 0
1 3 6 7 9 // 安　全 | 遞增 | 兩元素之差都在 1 到 3 之間

判斷「安全」程式碼

func isSafe(row: [Int]) -> Bool {
    let isIncrease = row[1] > row[0]

    for index in 1..<row.count {
        let previous = row[index - 1]
        let current = row[index]
        let diff = current - previous
        if (isIncrease && (diff < 1 || diff > 3)) ||
           (!isIncrease && (diff > -1 || diff < -3)) {
            return false
        }
    }

    return true
}

主要程式碼

func safeReport(with puzzle: String) -> Int {
    // 1. 格式化資料源
    let puzzle = puzzle
        .components(separatedBy: "\n")
        .map { row in
            row
                .components(separatedBy: " ")
                .compactMap(Int.init)
        }

    // 2. 初始化計數用的變數
    var result = 0

    // 3. 走訪 puzzle 的每一行
    for row in puzzle {
        result += isSafe(row: row) ? 1 : 0
    }

    return result
}

複雜度分析

令所有數值數量為 n

• 時間複雜度： O(n)
• 空間複雜度： O(n)

---

第二部分

因為科學家發現依照原先的判斷方式安全率太低了，於是想出一個辦法：

如果可以只移除一個元素就可以變成「安全」的話，就視為是個安全的數組

解法

暴力解，如果一行數祖先被判定為「不安全」，就進行以下處理和判斷：

1. 逐一移除一個元素
2. 傳入 isSafe 判斷
3. 只要在走訪過程中有發現只要有一個移除方式被視為安全，則提早結束，將 result 加上 1

程式碼

func alteredSafeReport(with puzzle: String) -> Int {
    let puzzle = puzzle
        .components(separatedBy: "\n")
        .map { row in
            row
                .components(separatedBy: " ")
                .compactMap(Int.init)
        }

    var result = 0

    for row in puzzle {
        if isSafe(row: row) {
            result += 1
        } else {
+           for index in 0..<row.count {
+               var localRow = row
+               localRow.remove(at: index)
+               if isSafe(row: localRow) {
+                   result += 1
+                   break
+               }
            }
        }
    }

    return result
}

複雜度分析

令所有數值為 n * m ，m 為最長 column 數。

• 時間複雜度： O(nxmxm)
  • 在矯正不合格為合格的過程為 O(mxm)
• 空間複雜度： O(nxm)

結語

如果有寫錯或有建議請留言讓我知道。如果有找到更好的解法，我會再多發一篇補充。