DEV Community

vc7
vc7

Posted on

1

Day 1: Historian Hysteria | Advent of Code 2024 | 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 能做完。

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

Sentry blog image

The Visual Studio App Center’s retiring

But sadly….you’re not. See how to make the switch to Sentry for all your crash reporting needs.

Read more

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Immerse yourself in a wealth of knowledge with this piece, supported by the inclusive DEV Community—every developer, no matter where they are in their journey, is invited to contribute to our collective wisdom.

A simple “thank you” goes a long way—express your gratitude below in the comments!

Gathering insights enriches our journey on DEV and fortifies our community ties. Did you find this article valuable? Taking a moment to thank the author can have a significant impact.

Okay