DEV Community

vc7
vc7

Posted on

2

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
Enter fullscreen mode Exit fullscreen mode

安全的條件

  • 數組是單一方向的「遞增」或「遞減」
    • 只要當其中一個數的增減方向和其他數字不同,就判定為不安全
  • 兩元素的差必須介於 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 之間
Enter fullscreen mode Exit fullscreen mode

判斷「安全」程式碼

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
}
Enter fullscreen mode Exit fullscreen mode

主要程式碼

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
}
Enter fullscreen mode Exit fullscreen mode

複雜度分析

令所有數值數量為 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
}
Enter fullscreen mode Exit fullscreen mode

複雜度分析

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

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

結語

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

Sentry image

Hands-on debugging session: instrument, monitor, and fix

Join Lazar for a hands-on session where you’ll build it, break it, debug it, and fix it. You’ll set up Sentry, track errors, use Session Replay and Tracing, and leverage some good ol’ AI to find and fix issues fast.

RSVP here →

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay