07

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

Prob1

題目

給一串數字 $x_i$ ，問有沒有辦法經過以下操作得到 $a$。

1. 把 $x$ 的前面兩個數字拿出來相加，再放回 $x$ 前面
2. 把 $x$ 的前面兩個數字拿出來相乘，再放回 $x$ 前面

輸入會給很多組數字和其對應的$a$，把可行的 $a$ 都加起來作為輸出。

範例

Input

100: 10 10
191: 19 10
120: 10 2 10

Output

1. 100 是可行的 $10\times 10=100$
2. 191 是不可行的
3. 120 是可行的 $(10+2)\times 10=120$

220

解法

直接搜索無法剪枝，所以從尾巴逆著搜索，可以用結果是否不小於數字或整除數字來判斷。

import sys

from typing import List


def test(target: int, xs: List[int]) -> bool:
    if len(xs) == 1:
        return target == xs[0]

    if target < xs[0]:
        return False

    if xs[0] > 0 and target % xs[0] == 0:
        if test(target//xs[0], xs[1:]):
            return True

    return test(target - xs[0], xs[1:])


ans = 0

for line in sys.stdin:
    target, xs_str = line.strip().split(':')
    target = int(target)
    xs = list(map(int, xs_str.strip().split(' ')))
    xs.reverse()
    if test(target, xs):
        ans += target

print(ans)

Prob2

題目

給一串數字 $x_i$ ，問有沒有辦法經過以下操作得到 $a$。

1. 把 $x$ 的前面兩個數字拿出來相加，再放回 $x$ 前面
2. 把 $x$ 的前面兩個數字拿出來相乘，再放回 $x$ 前面
3. 把 $x$ 的前面兩個數字拿出來用字串組合的方式加起來，再放回 $x$ 前面 ("1" + "2" = "12")

輸入會給很多組數字和其對應的$a$，把可行的 $a$ 都加起來作為輸出。

範例

Input

100: 10 10
191: 19 10
1020: 10 2 10

Output

1. 100 是可行的 $10\times 10=100$
2. 191 是不可行的
3. 1020 是可行的 $(10|2)\times 10=120$

1120

解法

一樣從尾巴逆著搜索，字串組合更好剪。

import sys

from typing import List


def test(target: int, xs: List[int]) -> bool:
    if len(xs) == 1:
        return target == xs[0]

    if target < xs[0]:
        return False

    if xs[0] > 0 and target % xs[0] == 0:
        if test(target//xs[0], xs[1:]):
            return True

    if target != xs[0] and str(target).endswith(str(xs[0])):
        new_target = int(str(target).removesuffix(str(xs[0])))
        if test(new_target, xs[1:]):
            return True

    return test(target - xs[0], xs[1:])


ans = 0

for line in sys.stdin:
    target, xs_str = line.strip().split(':')
    target = int(target)
    xs = list(map(int, xs_str.strip().split(' ')))
    xs.reverse()
    if test(target, xs):
        ans += target

print(ans)

Changelog

Last edited about 1 month ago

View full history

fba0b10-Update