summaryrefslogtreecommitdiff
path: root/2023/05/step2.py
blob: 95e276d42833d7c3b135c21744e6b7106b13de3f (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
import argparse
import collections
import re

p = argparse.ArgumentParser()
p.add_argument("file", type=argparse.FileType("r"), help="input file")
options = p.parse_args()

m = collections.defaultdict(list)
steps = []

for line in options.file:
    line = line.strip()
    if not line:
        pass
    elif line.startswith("seeds:"):
        seeds = [int(s) for s in line.split()[1:]]
        seeds = [(s, s + sn) for s, sn in zip(seeds[0::2], seeds[1::2])]
    elif line.endswith("map:"):
        pmap = line.split()[0]
        steps.append(pmap)
    else:
        [dst, src, n] = [int(s) for s in line.split()]
        m[pmap].append((dst, src, n))

mini = None

for seed in seeds:
    done = [seed]
    for step in steps:
        todo = done
        done = []
        for dst, src, n in m[step]:
            src1 = src
            src2 = src + n
            newtodo = []
            for s1, s2 in todo:
                if s1 < src1:
                    newtodo.append((s1, min(s2, src1)))
                if s2 > src2:
                    newtodo.append((max(s1, src2), s2))
                if s2 > src1 and s1 < src2:
                    done.append((max(s1, src1) - src + dst, min(s2, src2) - src + dst))
            todo = newtodo
        done.extend(todo)
    print(done)
    s = min(s1 for s1, s2 in done)
    if mini is None or s < mini:
        mini = s

print(mini)