Imgcity

Appearance

Imgcity✍️ Online Judge 題解AdventOfCode202401

01 ​

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

Prob1 ​

題目 ​

輸入會給出兩個數組，要計算他們之間的距離，計算方式如下：

  • 拿出兩邊最小的數，相減取絕對值。
  • 拿出兩邊次小的數，相減儲絕對值。
  • ...
  • 把所有絕對值加總，得出距離

範例 ​

Input ​

兩個數組：[1, 2, 3] 和 [3, 2, 4]

1   3
2   2
3   4

Output ​

|1−2|+|2−3|+|3−4|=3
3

解法 ​

兩個數組都排序後，直接把相同 index 的數字相減取絕對值加總。

python
import sys

xs = []
ys = []

for line in sys.stdin:
	x, y = map(int, line.split('   '))
	xs.append(x)
	ys.append(y)

xs.sort()
ys.sort()

ans = 0

for x, y in zip(xs, ys):
	ans += abs(x - y)

print(ans)

Prob2 ​

題目 ​

輸入會給出兩個數組，要計算他們之間的相似性，計算方式如下：

  • 先看第一個數組第一個數字，然後這個數字在第二個數組的出現次數，計算數字x第二個數組的出現次數，
  • 第二個數字也是如此，以此類推...
  • 加總起來

Input ​

兩個數組：[1, 2, 3] 和 [3, 2, 2]

1   3
2   2
3   2

Output ​

1×0+2×2+3×1=7
7

解法 ​

把兩個數組都做成 count table: 數字對應到出現次數。然後計算數字x第一數組出現次數x第二數組出現次數，最後都加總起來。

python
import sys

xs = {}
ys = {}

for line in sys.stdin:
	x, y = map(int, line.split('   '))
	xs.setdefault(x, 0)
	xs[x] += 1
	ys.setdefault(y, 0)
	ys[y] += 1

ans = 0
for x, cnt in xs.items():
    ans += x*cnt*ys.get(x, 0)

print(ans)

Changelog

Just observe 👀