CodingTour —
ARTS #80

Algorithm

本周选择的算法题是：Day 1: Report Repair

规则

Part1

…

Specifically, they need you to find the two entries that sum to 2020 and then multiply those two numbers together.

For example, suppose your expense report contained the following:

1721
979
366
299
675
1456

In this list, the two entries that sum to 2020 are 1721 and 299. Multiplying them together produces 1721 * 299 = 514579, so the correct answer is *514579*.

Of course, your expense report is much larger. Find the two entries that sum to 2020; what do you get if you multiply them together?

Part2

…

In your expense report, what is the product of the three entries that sum to 2020?

Solution

Advent Of Code 是场景题，简单来说 Part1 是从 input 中找出两个相加为 2020 的数，Part2 则是找出三个。为了一次解决这两个问题，我们可以实现一个 n-sum 的解法：

def n_sum(nums: [int], begin: int, end: int, target: int, n: int) -> [int]:
    if n == 2: 
        return search(nums, begin, end, target)
    for i in range(begin, end):
        if nums[i] + sum(ans := n_sum(nums, i + 1, end, target - nums[i], n - 1)) == target and len(ans)+1 == n:
            return [nums[i]] + ans
    return []

def search(nums: [int], begin: int, end: int, target: int) -> [int, int]:
    while begin < end:
        sum = nums[begin] + nums[end]
        if sum == target:
            break
        elif sum < target:
            begin += 1
        else:
            end -= 1
    if (num1 := nums[begin]) + (num2 := nums[end]) == target:
        return [num1, num2]
    return []

测试代码：

if __name__ == '__main__':
    nums = []
    with open(os.path.join(os.path.dirname(__file__), "input.txt"), "r") as file:
            for line in file.readlines():
                nums.append(int(line))
    nums.sort()

    print(n_sum(nums, 0, len(nums)-1, 2020, 2))
    print(n_sum(nums, 0, len(nums)-1, 2020, 3))
    print(n_sum(nums, 0, len(nums)-1, 2020, 4))
    print(n_sum(nums, 0, len(nums)-1, 2020, 5))

Review

Implement the Clean VIPER Architecture in iOS

在 iOS 里实现一个清晰的 VIPER 架构。

文章里配的 VIPER 角色交互图很经典：

相比 MVC、MVVM，VIPER 将职责的粒度定义的更细：

  • View
    • 负责视图的布局、更新
    • 为 Presenter 提供更新视图的接口
    • 为 Presenter 提供事件源
  • Presenter
    • 接收并处理来自 View 的事件
    • 接收并处理来自 Interactor 的通知
    • 通过 Interactor 执行业务逻辑
    • 将 View 数据提供给 Interactor 处理
    • 通知 View 更新视图
    • 通过 Router 跳转到其他 View
  • Router
    • 提供 View 之间的路由解析
  • Interactor
    • 为 Presenter 提供业务功能
    • 维护 Entity
    • 向 Presenter 提供业务相关的变更事件
  • Entity
    • 数据模型

VIPER 保持了适当的耦合，虽然将角色职责拆分的很细、增加了设计层级，但每个组件在功能上是内聚的，组件之间的接口设计良好且耦合度低，满足模块化的单体架构对功能逻辑的分组要求和模块间明确定义边界的要求。

Tip

Python attrs by Example.

Share

分享一篇持续集成系统的物理架构：CI 物理架构。