DEV Community

vc7
vc7

Posted on

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

#adventofcode #swift #中文

引子

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

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

題目

題目形式

分成兩個部分

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

資料整形

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

3 4 4 3 2 5 1 3 3 9 3 3
Enter fullscreen mode Exit fullscreen mode

puzzle 的宣告方式

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

let puzzle = """ 3 4 4 3 2 5 1 3 3 9 3 3 """
Enter fullscreen mode Exit fullscreen mode

程式碼

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

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

為了可讀性，也可以另外宣告一個結構來替代 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 }
Enter fullscreen mode Exit fullscreen mode

執行 

let puzzle = """ ... 省略 """ let result = totalDistance(with: puzzle)
Enter fullscreen mode Exit fullscreen mode

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

左半邊數列

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

總和：

9 + 4 + 0 + 0 + 9 + 9 = 31
Enter fullscreen mode Exit fullscreen mode

資料結構與想法

首先，先用 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 }
Enter fullscreen mode Exit fullscreen mode

或是加總的地方也可以用 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] } }
Enter fullscreen mode Exit fullscreen mode

執行 

let puzzle = """ ... 省略 """ let result = similarity(with: puzzle)
Enter fullscreen mode Exit fullscreen mode

result 及為結果

複雜度分析

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

結語

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

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

Top comments (0)