Day 1: Historian Hysteria | Advent of Code 2024 | Swift | 中文

引子

看了 Advent of Code 要開始的推文一直猶豫要不要跳進來；因為往年年末無論是自己上 Qiita 開坑，或是鐵人賽到最後不是失敗就是都很累。

不過因為最後東看西看，最近也有在做 LeetCode POTD ，雖然晚了一天還是決定來做了

---

題目

• https://adventofcode.com/2024/day/1

題目形式

分成兩個部分

• Part 1 - 算出星星之間的距離總和
• Part 2 - 算出相似值

---

資料整形

藉由觀察，資料源以 \n 分行，並用 三個空格 分隔左右半邊

3   4
4   3
2   5
1   3
3   9
3   3

puzzle 的宣告方式

官方會根據不同的帳號提供不一樣的 puzzle ，這邊我直接複製貼到 Xcode 去執行。請自行替換自己的 puzzle 。

let puzzle = """
3   4
4   3
2   5
1   3
3   9
3   3
"""

程式碼

在這裡就把資料源通過 兩次分割 以及 轉型 整理成兩個整數陣列：

func grouping(with puzzle: String) -> (left: [Int], right: [Int]) {
    puzzle
        // 分行
        .components(separatedBy: "\n")
        .map {
            /// !!!: 為求文章表示簡潔，這裡不做 error handling
            /// 1) 分隔字串 -> 2) 轉型成整數
            $0.components(separatedBy: "   ").compactMap(Int.init)
        }
        .reduce(into: (left: [Int](), right: [Int]())) {
            $0.left.append($1[0])
            $0.right.append($1[1])
        }
}

為了可讀性，也可以另外宣告一個結構來替代 tupple 。

---

第一部分

前半一大段其實都在說故事，沒有解題的關鍵資訊（笑）

題意

數列分 左數列 和 右數列，題目要求個字排列之後，算出數值之間的總和 - 最小和最小的距離、第二小和第二小的距離，以此類推到最大和最大的距離。

當計算距離的相減後有可能會是 負值，因此在加總前可以使用 abs 方法取絕對值作為距離。

程式碼

func totalDistance(with puzzle: String) -> Int {
    var (left, right) = grouping(with: puzzle)
    left.sort()
    right.sort()

    var sum = 0

    for index in 0..<left.count {
        sum += abs(right[index] - left[index])
    }

    return sum
}

執行

let puzzle = """
  ... 省略
"""

let result = totalDistance(with: puzzle)

result 及為結果

複雜度分析

• 時間複雜度 O(nlogn)
  • O(nlogn + n) -> O(nlogn)
    • 排序 - O(nlogn)
    • 走訪 - O(n)
• 空間複雜度 O(n)
  • 有建立 2 個陣列來存放，省略常數項後為 O(n)

---

第二部分

題意

計算相對於 左 半邊數列的相似度，算出每一行的 當前值 * 出現次數 後再加總。以官方的範例為例：

3   4
4   3
2   5
1   3
3   9
3   3

左半邊數列

3 => 右數列中出現 3 次 => 3 * 3 = 9
4 => 右數列中出現 1 次 => 4 * 1 = 4
2 => 右數列中出現 0 次 => 2 * 0 = 0
1 => 右數列中出現 0 次 => 1 * 0 = 0
3 => 右數列中出現 3 次 => 3 * 3 = 9
3 => 右數列中出現 3 次 => 3 * 3 = 9

總和：

9 + 4 + 0 + 0 + 9 + 9 = 31

資料結構與想法

首先，先用 hash map 來計數每個數字在右數列中的出現次數。

接著再走訪左數列，再邊用題目提供的算式把總和算出來。

程式碼

func similarity(with puzzle: String) -> Int {
    let (left, right) = grouping(with: puzzle)
    var map = [Int: Int]()

    for number in right {
        map[number, default: 0] += 1
    }

    var sum = 0

    for number in left {
        sum += number * map[number, default: 0]
    }

    return sum
}

或是加總的地方也可以用 reduce

func simularity(puzzle: String) -> Int {
    let (left, right) = grouping(with: puzzle)
    var map = [Int: Int]()

    for number in right {
        map[number, default: 0] += 1
    }

    // 改寫的部分
    return left.reduce(into: 0) {
        $0 += $1 * map[$1, default: 0]
    }
}

執行

let puzzle = """
  ... 省略
"""

let result = similarity(with: puzzle)

result 及為結果

複雜度分析

• 時間複雜度 O(n)
  • 這個部分都只有線性走訪
• 空間複雜度 O(n)
  • 左右數列： O(2n) -> O(n)
  • 計數用的 hash map： 最壞情形就是每個數值都不一樣 -> O(n)

---

結語

以上，希望能 Advent of Code 2024 能做完。

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