summaryrefslogtreecommitdiff
path: root/5_2023.py
blob: 22e40319d027280477ae1767e667827eb618c482 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import sys
import re
from collections import defaultdict

D = open(sys.argv[1]).read().strip()
L = D.split("\n")

parts = D.split("\n\n")
seed, *others = parts
seed = [int(x) for x in seed.split(":")[1].split()]


class Function:
    def __init__(self, S):
        lines = S.split("\n")[1:]  # throw away name
        # dst src sz
        self.tuples: list[tuple[int, int, int]] = [
            [int(x) for x in line.split()] for line in lines
        ]

    def apply_one(self, x: int) -> int:
        for dst, src, sz in self.tuples:
            if src <= x < src + sz:
                return x + dst - src
        return x

    # list of [start, end) ranges
    def apply_range(self, R):
        A = []
        for dest, src, sz in self.tuples:
            src_end = src + sz
            NR = []
            while R:
                # [st                                     ed)
                #          [src       src_end]
                # [BEFORE ][INTER            ][AFTER        )
                (st, ed) = R.pop()
                # (src,sz) might cut (st,ed)
                before = (st, min(ed, src))
                inter = (max(st, src), min(src_end, ed))
                after = (max(src_end, st), ed)
                if before[1] > before[0]:
                    NR.append(before)
                if inter[1] > inter[0]:
                    A.append((inter[0] - src + dest, inter[1] - src + dest))
                if after[1] > after[0]:
                    NR.append(after)
            R = NR
        return A + R


Fs = [Function(s) for s in others]


def f(R, o):
    A = []
    for line in o:
        dest, src, sz = [int(x) for x in line.split()]
        src_end = src + sz


P1 = []
for x in seed:
    for f in Fs:
        x = f.apply_one(x)
    P1.append(x)
print(min(P1))

P2 = []
pairs = list(zip(seed[::2], seed[1::2]))
for st, sz in pairs:
    # inclusive on the left, exclusive on the right
    # e.g. [1,3) = [1,2]
    # length of [a,b) = b-a
    # [a,b) + [b,c) = [a,c)
    R = [(st, st + sz)]
    for f in Fs:
        R = f.apply_range(R)
    P2.append(min(R)[0])
print(min(P2))