aoc_2018/day13.py at master · a68366/aoc_2018 · GitHub

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
from copy import deepcopy


def get_data():
    with open('input') as f:
        data = [list(line) for line in f.readlines()]
        return data


def find_repl(i, j, data, val):
    repl = data[i][j]
    if repl not in '<>^v':
        return repl
    elif val in '<>':
        return '-'
    else:
        return '|'


def next_step(i, j, val):
    if val == '>':
        return i, j+1
    elif val == '<':
        return i, j-1
    elif val == '^':
        return i-1, j
    elif val == 'v':
        return i+1, j


def init(data):
    field = deepcopy(data)
    moving = set('v^<>')
    turns = {('v', 0): '>', ('v', 1): 'v', ('v', 2): '<',
             ('^', 0): '<', ('^', 1): '^', ('^', 2): '>',
             ('<', 0): 'v', ('<', 1): '<', ('<', 2): '^',
             ('>', 0): '^', ('>', 1): '>', ('>', 2): 'v'}
    turn_states = {}
    straight = '-|'
    simples = '\\/'
    simple_turns = {('\\', 'v'): '>', ('\\', '<'): '^', ('\\', '^'): '<', ('\\', '>'): 'v',
                    ('/', 'v'): '<', ('/', '<'): 'v', ('/', '^'): '>', ('/', '>'): '^'}
    carts_count = 0
    carts = set()
    for i, row in enumerate(data):
        for j, val in enumerate(row):
            if val in moving:
                carts_count += 1
                carts.add((i, j))

    return field, moving, turns, turn_states, straight, simples, simple_turns, carts, carts_count


def part_1(data):
    (field, moving, turns, turn_states,
     straight, simples, simple_turns, carts, _) = init(data)

    while True:
        new_carts = {}
        for i, j in sorted(carts):
            val = field[i][j]
            step = next_step(i, j, val)
            next_val = new_carts.get(step, field[step[0]][step[1]])
            if next_val in moving:
                return '{},{}'.format(*step[::-1])
            elif next_val in simples:
                new_carts[step] = simple_turns[(next_val, val)]
            elif next_val in straight:
                new_carts[step] = val
            else:
                turn = turn_states.get((i, j), 0) % 3
                new_carts[step] = turns[val, turn]
                turn_states[i, j] = turn + 1
            turn = turn_states.get((i, j))
            if turn is not None:
                turn_states[step[0], step[1]] = turn
                del turn_states[i, j]
            new_carts[(i, j)] = find_repl(i, j, data, val)

        carts.clear()
        for i, j in new_carts:
            val = new_carts[(i, j)]
            if val in moving:
                carts.add((i, j))
            field[i][j] = new_carts[(i, j)]


def part_2(data):
    (field, moving, turns, turn_states, straight,
     simples, simple_turns, carts, carts_count) = init(data)

    while carts_count > 1:
        new_carts = {}
        for i, j in sorted(carts):
            if (i, j) in new_carts:
                continue
            val = field[i][j]
            step = next_step(i, j, val)
            next_val = new_carts.get(step, field[step[0]][step[1]])
            if next_val in moving:
                carts_count -= 2
                new_carts[(i, j)] = find_repl(i, j, data, val)
                new_carts[step] = find_repl(step[0], step[1], data, next_val)
            elif next_val in simples:
                new_carts[step] = simple_turns[(next_val, val)]
            elif next_val in straight:
                new_carts[step] = val
            else:
                turn = turn_states.get((i, j), 0) % 3
                new_carts[step] = turns[val, turn]
                turn_states[i, j] = turn + 1
            turn = turn_states.get((i, j))
            if turn is not None:
                turn_states[step[0], step[1]] = turn
                del turn_states[i, j]
            new_carts[(i, j)] = find_repl(i, j, data, val)

        carts.clear()
        for i, j in new_carts:
            val = new_carts[(i, j)]
            if val in moving:
                carts.add((i, j))
            field[i][j] = new_carts[(i, j)]

    if carts:
        return '{},{}'.format(*reversed(next(iter(carts))))
    else:
        return 'No more carts'


def main():
    data = get_data()
    print('1:', part_1(data))
    print('2:', part_2(data))


if __name__ == '__main__':
    main()