02

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

Prob1

題目

給堆數組，數有多少數組是「安全」的。安全的定義如下：

1. 不是嚴格遞增，就是嚴格遞減
2. 相鄰數字差距最多為 $3$

範例

Input

1 2 3 4 5
5 4 3 1
1 5 6 7
1 3 1

Output

1 2 3 4 5 符合安全條件。 5 4 3 1 符合安全條件。 1 5 6 7 中的 1 5 距離為 $4$ ，不安全。 1 3 1 非嚴格遞增或遞減，不安全。

2

解法

直接按照題目給的條件判斷。

import sys

import typing


def is_safe(xs: typing.List[int]):
    if len(xs) <= 1:
        return True

    if xs[0] == xs[1]:
        return False

    for i in range(1, len(xs)):
        diff = abs(xs[i-1] - xs[i])
        if diff == 0 or diff > 3:
            return False

        if (xs[0] - xs[1])*(xs[i-1] - xs[i]) < 0:
            return False

    return True


safe_cnt = 0

for line in sys.stdin:
    xs = list(map(int, line.split()))
    if is_safe(xs):
        safe_cnt += 1


print(safe_cnt)

Prob2

題目

安全條件一樣，但想確認拿掉一個數字可以讓數組變安全的數量。

Input

1 2 3 4 5
5 4 3 1
1 5 6 7
1 3 1

Output

1 2 3 4 5 符合安全條件。 5 4 3 1 符合安全條件。 1 5 6 7 中的 1 5 距離為 $4$ ，不安全。 1 3 1 非嚴格遞增或遞減，但移除第一個 1 或最後一個 1，就可以變安全。

3

解法

應該是有 $O(N)$ 的作法，但看題目實際給的數組長度沒有很長，直接暴力嘗試移除每個數字 $O(N^2)$。

import sys

import typing


def is_safe(xs: typing.List[int]):
    if len(xs) <= 1:
        return True

    if xs[0] == xs[1]:
        return False

    for i in range(1, len(xs)):
        diff = abs(xs[i-1] - xs[i])
        if diff == 0 or diff > 3:
            return False

        if (xs[0] - xs[1])*(xs[i-1] - xs[i]) < 0:
            return False

    return True


safe_cnt = 0

for line in sys.stdin:
    xs = list(map(int, line.split()))

    ok = False
    for i in range(len(xs)):
        ys = xs[0:i] + xs[i+1:]
        if is_safe(ys):
            ok = True
            break

    if ok:
        safe_cnt += 1


print(safe_cnt)

Changelog

Last edited about 1 month ago

View full history

fba0b10-Update