Code

AoC 2019 Advent of Code (Python)

By telleropnul, December 31, 2019

Advent of Code AoC) is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like. Go check it out: Advent of Code

Input files: adventofcode2019inputs.zip [To be uploaded still…]

INTCODE reference: https://esolangs.org/wiki/Intcode

2019 Day 25

Automated walkthrough.
python -m pip install sortedcollections

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
139
140
141
142
143
144
145
146
147
148
149
150
151
152

 
import collections
import copy
import math
import re
import sys
import sortedcollections
 
class Intcode:
    def __init__(self, prog, pc=0, name=''):
        self.prog = prog[:]
        self.pc = pc
        self.name = name
        self.relbase = 0
        # stopped in out
        self.state = None
        self.outputq = None
        self.inputq = None
        self._run()
    def _pset(self, i, v):
        if i >= len(self.prog):
            self.prog.extend(0 for _ in range(1 + i - len(self.prog)))
        self.prog[i] = v
    def _pget(self, i):
        if i >= len(self.prog):
            self.prog.extend(0 for _ in range(1 + i - len(self.prog)))
        return self.prog[i]
    def outputs(self):
        while self.state == 'out':
            yield self.nextout()
    def nextout(self):
        assert self.state == 'out', self.state
        assert self.outputq is not None
        o = self.outputq
        self.outputq = None
        self.state = None
        self._run()
        return o
    def send(self, *inp):
        for v in inp:
            assert self.state == 'in', self.state
            self._pset(self.inputq, v)
            self.inputq = None
            self.state = None
            self._run()
        return self
    def _run(self):
        if self.state:
            raise ValueError(self.state)
        arity = {99: 0, 1: 3, 2: 3, 3: 1, 4: 1, 5: 2, 6: 2, 7: 3, 8: 3, 9: 1}
        def parse():
            op = self._pget(self.pc)
            self.pc += 1
            vals = []
            locs = []
            for i in range(arity[op % 100]):
                mode = (op // (10 ** (2 + i))) % 10
                vals.append(
                    self._pget(self.pc) if mode == 1 else
                    self._pget(self._pget(self.pc) + self.relbase) if mode == 2 else
                    self._pget(self._pget(self.pc))
                )
                locs.append(
                    None if mode == 1 else
                    self._pget(self.pc) + self.relbase if mode == 2 else
                    self._pget(self.pc)
                )
                self.pc += 1
            return op % 100, vals, locs
        while True:
            if self._pget(self.pc) == 99:
                self.state = 'stopped'
                return
            opc = self.pc
            op, vals, locs = parse()
            if op == 1:
                self._pset(locs[2], vals[0] + vals[1])
            elif op == 2:
                self._pset(locs[2], vals[0] * vals[1])
            elif op == 3:
                assert self.inputq is None
                self.state = 'in'
                self.inputq = locs[0]
                return
            elif op == 4:
                assert self.outputq is None
                self.state = 'out'
                self.outputq = vals[0]
                return
            elif op == 5:
                if vals[0] != 0:
                    self.pc = vals[1]
            elif op == 6:
                if vals[0] == 0:
                    self.pc = vals[1]
            elif op == 7:
                self._pset(locs[2], int(vals[0] < vals[1]))
            elif op == 8:
                self._pset(locs[2], int(vals[0] == vals[1]))
            elif op == 9:
                self.relbase += vals[0]
            else:
                assert False
 
with open('input') as f:
    lines = [l.rstrip('\n') for l in f]
    prog = [[int(i) for i in l.split(',')] for l in lines][0]
 
    p = Intcode(prog)
 
    bfs = collections.deque([(0, 0, frozenset(), p)])
    seen = {}
    rooms = {}
    msgseen = set()
    while bfs:
        x, y, ic, p = bfs.popleft()
        state = ''.join(map(chr, p.outputs())).splitlines()
        if len(state) >= 5:
            roomname = state[4]
            if (roomname,ic) in seen:
                continue
            seen[(roomname,ic)] = True
        else:
            print('huh?', ic, state)
            break
        print(x, y, ic)
        state1 = ' '.join(state)
        if state1 not in msgseen:
            msgseen.add(state1)
            print(state1)
        if "You can't go that way." in state:
            continue
 
        def f(p, ic):
            if '- north' in state:
                bfs.append((x-1,y,ic, copy.deepcopy(p).send(*(ord(c) for c in 'north\n'))))
            if '- south' in state:
                bfs.append((x+1,y,ic, copy.deepcopy(p).send(*(ord(c) for c in 'south\n'))))
            if '- east' in state:
                bfs.append((x,y+1,ic, copy.deepcopy(p).send(*(ord(c) for c in 'east\n'))))
            if '- west' in state:
                bfs.append((x,y-1,ic, copy.deepcopy(p).send(*(ord(c) for c in 'west\n'))))
        f(p, ic)
        if 'Items here:' in state:
            it = state[state.index('Items here:')+1][2:]
            assert not state[state.index('Items here:')+2].startswith('- ')
            if it not in ('escape pod', 'infinite loop', 'giant electromagnet', 'photons'):
                p2 = copy.deepcopy(p).send(*(ord(c) for c in f'take {it}\n'))
                tkm = ''.join(map(chr, p2.outputs())).splitlines()
                print('took', tkm)
                if p2.state != 'stopped':
                    f(p2, ic.union([it]))

2019 Day 25

Interactive, simply enter commands at the input prompt.

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

def mod1(oxxoo, nums, pos, relativebase):
    if oxxoo == 0:
        return int(nums[int(nums[pos])])
    elif oxxoo == 1:
        return int(nums[pos])
    elif oxxoo == 2:
        return int(nums[(int(nums[pos]))+relativebase])
 
def mod2(xoooo, nums, pos, relativebase):
    if xoooo == 0:
        return int(nums[pos])
    elif xoooo == 1:
        return int(pos)
    elif xoooo == 2:
        return int(int(nums[pos]) + relativebase)
 
h = open("input")
nums = h.read().split(",")
for e in range(2000):
    nums.append("0")
 
output = []
e = 0
relativebase = 0
counter = 0
past = ''
while e < len(nums):
    steps = 4
    if int(nums[e]) < 99999:
        zeros = 5 - len(str(nums[e]))
        nums[e] = (zeros * "0" + str(nums[e]))
    xoooo = int(nums[e][0])
    oxooo = int(nums[e][1])
    ooxoo = int(nums[e][2])
    oooxx = int(nums[e][3:])
    if xoooo < 3 and oxooo < 3 and ooxoo < 3:
        if oooxx == 1:
            nums[mod2(xoooo, nums, e+3, relativebase)] = mod1(ooxoo, nums, e+1, relativebase) + mod1(oxooo, nums, e+2, relativebase)
        elif oooxx == 2:
            nums[mod2(xoooo, nums, e+3, relativebase)] = mod1(ooxoo, nums, e+1, relativebase) * mod1(oxooo, nums, e+2, relativebase)
        elif oooxx == 3:
            steps = 2
            if ooxoo != 1:
                if counter == 0:
                    for z in output:
                        print(z, end='')
                    temp = input()
                    past += temp + "-"
                if counter < len(temp):
                    nums[mod2(ooxoo, nums, e+1, relativebase)] = ord(temp[counter])
                    counter += 1
                elif counter == len(temp):
                    nums[mod2(ooxoo, nums, e+1, relativebase)] = 10
                    counter = 0
                    print(past)
        elif oooxx == 4:
            steps = 2
            print(chr((int(nums[mod2(ooxoo, nums, e+1, relativebase)]))), end='')
        elif oooxx == 5:
            steps = 3
            if mod1(ooxoo, nums, e+1, relativebase) != 0:
                steps = 0
                e = mod1(oxooo, nums, e+2, relativebase)
        elif oooxx == 6:
            steps = 3
            if mod1(ooxoo, nums, e+1, relativebase) == 0:
                steps = 0
                e = mod1(oxooo, nums, e+2, relativebase)
        elif oooxx == 7:
            if mod1(ooxoo, nums, e+1, relativebase) < mod1(oxooo, nums, e+2, relativebase):
                nums[mod2(xoooo, nums, e+3, relativebase)] = 1
            else:
                nums[mod2(xoooo, nums, e+3, relativebase)] = 0
        elif oooxx == 8:
            if mod1(ooxoo, nums, e+1, relativebase) == mod1(oxooo, nums, e+2, relativebase):
                nums[mod2(xoooo, nums, e+3, relativebase)] = 1
            else:
                nums[mod2(xoooo, nums, e+3, relativebase)] = 0
        elif oooxx == 9:
            steps = 2
            relativebase += mod1(ooxoo, nums, e+1, relativebase)
        elif oooxx == 99:
            break   
    e += steps
 
print(output)

2019 Day 24 Part 02

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

def num_below(field, level, pos):
    if pos[0] == 1:
        return sum(field[level-1][0][x] == "#" for x in range(5))
 
    if pos[0] == 3:
        return sum(field[level-1][4][x] == "#" for x in range(5))
 
    if pos[1] == 1:
        return sum(field[level-1][y][0] == "#" for y in range(5))
 
    if pos[1] == 3:
        return sum(field[level-1][y][4] == "#" for y in range(5))
 
 
def num_neighbors(field, level, pos):
    count = 0
 
    for side in [(0, -1), (-1, 0), (0, 1), (1, 0)]:
        new_pos = (pos[0] + side[0], pos[1] + side[1])
 
        if new_pos[0] == 2 and new_pos[1] == 2:
            count += num_below(field, level, pos)
 
        elif new_pos[0] == -1:
            if field[level+1][1][2] == "#":
                count += 1
 
        elif new_pos[0] == 5:
            if field[level+1][3][2] == "#":
                count += 1
 
        elif new_pos[1] == -1:
            if field[level+1][2][1] == "#":
                count += 1
 
        elif new_pos[1] == 5:
            if field[level+1][2][3] == "#":
                count += 1
 
        elif field[level][new_pos[0]][new_pos[1]] == "#":
            count += 1
 
    return count
 
 
def evolve(field, iterations):
    new_field = [[["." for x in range(5)] for y in range(5)] for z in range(iterations*2+3)]
 
    for level in range(iterations*2+1):
        for y in range(5):
            for x in range(5):
                if x == 2 and y == 2:
                    continue
 
                if field[level][y][x] == "#":
                    if num_neighbors(field, level, (y, x)) == 1:
                        new_field[level][y][x] = "#"
 
                else:
                    if num_neighbors(field, level, (y, x)) == 1 or num_neighbors(field, level, (y, x)) == 2:
                        new_field[level][y][x] = "#"
 
    return new_field
 
 
input = open('input').readlines()
iterations = 200
field = [[["." for x in range(5)] for y in range(5)] for z in range(iterations*2+3)]
 
for y in range(5):
    for x in range(5):
        field[iterations+1][y][x] = input[y][x]
 
for step in range(iterations):
    field = evolve(field, iterations)
 
print(sum(field[level][y][x] == "#" for level in range(iterations*2+3) for y in range(5) for x in range(5)))

2019 Day 24 Part 01

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

 
def num_neighbors(field, pos):
    count = 0
    for side in [(0, -1), (-1, 0), (0, 1), (1, 0)]:
        x, y = pos[1] + side[1], pos[0] + side[0]
        if x >= 0 and x <= 4 and \
           y >= 0 and y <= 4 and \
           field[y][x] == "#":
                count += 1
    return count
 
def evolve(field):
    new_field = [["." for x in range(5)] for y in range(5)]
 
    for y in range(5):
        for x in range(5):
            if field[y][x] == "#":
                if num_neighbors(field, (y, x)) == 1:
                    new_field[y][x] = "#"
            elif num_neighbors(field, (y, x)) == 1 or \
                 num_neighbors(field, (y, x)) == 2:
                new_field[y][x] = "#"
 
    return new_field
 
def bio_diversity(field):
    result, multi = 0, 1
 
    for y in range(5):
        for x in range(5):
            if field[y][x] == "#":
                result += multi
            multi *= 2
    return result
 
 
field = input = open('input').readlines()
known = set()
 
while (bio := bio_diversity(field)) not in known:
    known.add(bio)
    field = evolve(field)
 
print(bio)

2019 Day 23 Part 02

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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174

from collections import defaultdict, deque
 
class Game:
    def __init__(self, prog):
        self.prog       = prog
        self.ip         = 0
        self.input      = deque()
        self.output     = deque()
        self.rel_base   = 0
        self.halt       = False
        self.is_waiting = False
 
def split_instruction(instruction):
    instruction = f"{instruction:05}"
    return instruction[3:], instruction[0:3]
 
def get_values(input, pos, op, modes, game):
    mode_a, mode_b, mode_c = modes
    values = []
    offset = 0
 
    if op in ["01", "02", "04", "05", "06", "07", "08", "09"]:
        if mode_c == "0":
            values.append(input[input[pos+1]])
        elif mode_c == "1":
            values.append(input[pos+1])
        elif mode_c == "2":
            values.append(input[input[pos+1]+game.rel_base])
 
        if op in ["01", "02", "05", "06", "07", "08"]:
            if mode_b == "0":
                values.append(input[input[pos+2]])
            elif mode_b == "1":
                values.append(input[pos+2])
            elif mode_b == "2":
                values.append(input[input[pos+2]+game.rel_base])
 
            if op in []:
                if mode_a == "0":
                    values.append(input[input[pos+3]])
                elif mode_a == "1":
                    values.append(input[pos+3])
                elif mode_a == "2":
                    values.append(input[input[pos+3]+game.rel_base])
 
    if op in ["01", "02", "07", "08"]:
        if mode_a == "2":
            offset = game.rel_base
 
    if op in ["03"]:
        if mode_c == "2":
            offset = game.rel_base
 
    return values, offset
 
def send_input(game, input):
    game.input.extend(input)
 
def read_output(game):
    if len(game.output):
        return game.output.popleft()
    return None
 
def run_game(game):
    if game.prog[game.ip] != 99:
        op, modes = split_instruction(game.prog[game.ip])
        values, offset = get_values(game.prog, game.ip, op, modes, game)
 
        if op == "01": # Addition
            game.prog[game.prog[game.ip+3] + offset] = values[0] + values[1]
            game.ip += 4
 
        if op == "02": # Multiplication
            game.prog[game.prog[game.ip+3] + offset] = values[0] * values[1]
            game.ip += 4
 
        if op == "03": # Read and Store input
            if len(game.input):
                game.prog[game.prog[game.ip+1] + offset] = game.input.popleft()
                game.is_waiting = False
            else:
                game.prog[game.prog[game.ip+1] + offset] = -1
                game.is_waiting = True
            game.ip += 2
 
        if op == "04": # Print Output
            game.output.append(values[0])
            game.ip += 2
            return
 
        if op == "05": # Jump-if-True
            if values[0]:
                game.ip = values[1]
            else:
                game.ip += 3
 
        if op == "06": # Jump-if-False
            if not values[0]:
                game.ip = values[1]
            else:
                game.ip += 3
 
        if op == "07": # Less than
            if values[0] < values[1]:
                game.prog[game.prog[game.ip+3] + offset] = 1
            else:
                game.prog[game.prog[game.ip+3] + offset] = 0
            game.ip += 4
 
        if op == "08": # Equals
            if values[0] == values[1]:
                game.prog[game.prog[game.ip+3] + offset] = 1
            else:
                game.prog[game.prog[game.ip+3] + offset] = 0
            game.ip += 4
 
        if op == "09": # Adjust Relative Base
            game.rel_base += values[0]
            game.ip += 2
    else:
        game.halt = True
 
def create_program(input):
    prog = defaultdict(int)
 
    for i in range(len(input)):
        prog[i] = int(input[i])
 
    return prog
 
def create_network(input):
    network, network_queue = [], []
 
    for network_address in range(50):
        prog = create_program(input)
        game = Game(prog)
        send_input(game, [network_address])
        network.append(game)
        network_queue.append([])
 
    return network, network_queue
 
def is_idle(network, network_queue):
    for network_address in range(50):
        if len(network_queue[network_address]) or \
           not network[network_address].is_waiting:
            return False
    return True
 
def find_double_nat_y(network, network_queue):
    nat, last_nat = [], None
 
    while True:
        for network_address in range(50):
            run_game(network[network_address])
            if (output := read_output(network[network_address])):
                network_queue[network_address].append(output)
                if len(network_queue[network_address]) == 3:
                    if network_queue[network_address][0] == 255:
                        nat = network_queue[network_address][1:]
                    else:
                        send_input(network[network_queue[network_address][0]], network_queue[network_address][1:])
                    network_queue[network_address] = []
 
        if is_idle(network, network_queue) and len(nat):
            if nat[1] == last_nat:
                return last_nat
            send_input(network[0], nat)
            last_nat, nat = nat[1], []
 
 
input = open('input').read().split(",")
network, network_queue = create_network(input)
print(find_double_nat_y(network, network_queue))

2019 Day 23 Part 01

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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156

from collections import defaultdict, deque
 
class Game:
    def __init__(self, prog):
        self.prog     = prog
        self.ip       = 0
        self.input    = deque()
        self.output   = deque()
        self.rel_base = 0
        self.halt     = False
 
def split_instruction(instruction):
    instruction = f"{instruction:05}"
    return instruction[3:], instruction[0:3]
 
def get_values(input, pos, op, modes, game):
    mode_a, mode_b, mode_c = modes
    values = []
    offset = 0
 
    if op in ["01", "02", "04", "05", "06", "07", "08", "09"]:
        if mode_c == "0":
            values.append(input[input[pos+1]])
        elif mode_c == "1":
            values.append(input[pos+1])
        elif mode_c == "2":
            values.append(input[input[pos+1]+game.rel_base])
 
        if op in ["01", "02", "05", "06", "07", "08"]:
            if mode_b == "0":
                values.append(input[input[pos+2]])
            elif mode_b == "1":
                values.append(input[pos+2])
            elif mode_b == "2":
                values.append(input[input[pos+2]+game.rel_base])
 
            if op in []:
                if mode_a == "0":
                    values.append(input[input[pos+3]])
                elif mode_a == "1":
                    values.append(input[pos+3])
                elif mode_a == "2":
                    values.append(input[input[pos+3]+game.rel_base])
 
    if op in ["01", "02", "07", "08"]:
        if mode_a == "2":
            offset = game.rel_base
 
    if op in ["03"]:
        if mode_c == "2":
            offset = game.rel_base
 
    return values, offset
 
def send_input(game, input):
    game.input.extend(input)
 
def read_output(game):
    if len(game.output):
        return game.output.popleft()
    return None
 
def run_game(game):
    if game.prog[game.ip] != 99:
        op, modes = split_instruction(game.prog[game.ip])
        values, offset = get_values(game.prog, game.ip, op, modes, game)
 
        if op == "01": # Addition
            game.prog[game.prog[game.ip+3] + offset] = values[0] + values[1]
            game.ip += 4
 
        if op == "02": # Multiplication
            game.prog[game.prog[game.ip+3] + offset] = values[0] * values[1]
            game.ip += 4
 
        if op == "03": # Read and Store input
            if len(game.input):
                game.prog[game.prog[game.ip+1] + offset] = game.input.popleft()
            else:
                game.prog[game.prog[game.ip+1] + offset] = -1
            game.ip += 2
 
        if op == "04": # Print Output
            game.output.append(values[0])
            game.ip += 2
            return
 
        if op == "05": # Jump-if-True
            if values[0]:
                game.ip = values[1]
            else:
                game.ip += 3
 
        if op == "06": # Jump-if-False
            if not values[0]:
                game.ip = values[1]
            else:
                game.ip += 3
 
        if op == "07": # Less than
            if values[0] < values[1]:
                game.prog[game.prog[game.ip+3] + offset] = 1
            else:
                game.prog[game.prog[game.ip+3] + offset] = 0
            game.ip += 4
 
        if op == "08": # Equals
            if values[0] == values[1]:
                game.prog[game.prog[game.ip+3] + offset] = 1
            else:
                game.prog[game.prog[game.ip+3] + offset] = 0
            game.ip += 4
 
        if op == "09": # Adjust Relative Base
            game.rel_base += values[0]
            game.ip += 2
    else:
        game.halt = True
 
def create_program(input):
    prog = defaultdict(int)
 
    for i in range(len(input)):
        prog[i] = int(input[i])
 
    return prog
 
def create_network(input):
    network, network_queue = [], []
 
    for network_address in range(50):
        prog = create_program(input)
        game = Game(prog)
        send_input(game, [network_address])
        network.append(game)
        network_queue.append([])
 
    return network, network_queue
 
def find_first_nat_package(network, network_queue):
    while True:
        for network_address in range(50):
            run_game(network[network_address])
            if (output := read_output(network[network_address])):
                network_queue[network_address].append(output)
                if len(network_queue[network_address]) == 3:
                    if network_queue[network_address][0] == 255:
                        return network_queue[network_address]
                    send_input(network[network_queue[network_address][0]], network_queue[network_address][1:])
                    network_queue[network_address] = []
 
 
input = open('input').read().split(",")
network, network_queue = create_network(input)
 
print(find_first_nat_package(network, network_queue)[2])

2019 Day 22 Part 02

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

from collections import deque
 
def apply_operation(operations, addi, multi, size):
    operation = operations.popleft()
 
    if len(operations):
        addi, multi = apply_operation(operations, addi, multi, size)
 
    if operation[-2] == "cut":
        addi  += int(operation[-1]) * multi
    elif operation[-1] == "stack":
        multi *= -1
        addi  += multi
    else:
        multi *= pow(int(operation[-1]), -1, size)
 
    return addi, multi
 
 
input = open('input').read().splitlines()
operations = deque(reversed([line.split(" ") for line in input]))
 
position    = 2020
size        = 119315717514047
iterations  = 101741582076661
 
addi, multi = apply_operation(operations, 0, 1, size)
 
all_multi   = pow(multi, iterations, size)
all_addi    = addi * (1 - pow(multi, iterations, size)) * pow(1 - multi, -1, size)    
 
print((position * all_multi + all_addi) % size)

2019 Day 22 Part 01

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

def cut(deck, amount):
    if amount > 0:
        return deck[amount:] + deck[:amount]
    elif amount < 0:
        return deck[len(deck)+amount:] + deck[:len(deck)+amount]
    return deck
 
def deal_into_new_stack(deck):
    return deck[::-1]
 
def deal_with_increment(deck, amount):
    new_deck = [0 for _ in range(len(deck))]
    for i in range(len(deck)):
        new_deck[(i*amount)%len(deck)] = deck[i]
    return new_deck
 
input = open('input').read().splitlines()
instructions = [line.split(" ") for line in input]
 
deck = [num for num in range(10007)]
 
for instruction in instructions:
    if instruction[-2] == "cut":
        deck = cut(deck, int(instruction[-1]))
 
    elif instruction[-1] == "stack":
        deck = deal_into_new_stack(deck)
 
    else:
        deck = deal_with_increment(deck, int(instruction[-1]))
 
print(deck.index(2019))

2019 Day 21 Part 02

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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

from collections import defaultdict, deque
 
class Game:
    def __init__(self, prog):
        self.prog     = prog
        self.ip       = 0
        self.input    = deque()
        self.output   = deque()
        self.rel_base = 0
        self.halt     = False
 
def split_instruction(instruction):
    instruction = f"{instruction:05}"
    return instruction[3:], instruction[0:3]
 
def get_values(input, pos, op, modes, game):
    mode_a, mode_b, mode_c = modes
    values = []
    offset = 0
 
    if op in ["01", "02", "04", "05", "06", "07", "08", "09"]:
        if mode_c == "0":
            values.append(input[input[pos+1]])
        elif mode_c == "1":
            values.append(input[pos+1])
        elif mode_c == "2":
            values.append(input[input[pos+1]+game.rel_base])
 
        if op in ["01", "02", "05", "06", "07", "08"]:
            if mode_b == "0":
                values.append(input[input[pos+2]])
            elif mode_b == "1":
                values.append(input[pos+2])
            elif mode_b == "2":
                values.append(input[input[pos+2]+game.rel_base])
 
            if op in []:
                if mode_a == "0":
                    values.append(input[input[pos+3]])
                elif mode_a == "1":
                    values.append(input[pos+3])
                elif mode_a == "2":
                    values.append(input[input[pos+3]+game.rel_base])
 
    if op in ["01", "02", "07", "08"]:
        if mode_a == "2":
            offset = game.rel_base
 
    if op in ["03"]:
        if mode_c == "2":
            offset = game.rel_base
 
    return values, offset
 
def read_output(game):
    if len(game.output):
        return game.output.popleft()
    return None
 
def run_game(game, input = []):
    if len(input):
        game.input.extend(input)
 
    while game.prog[game.ip] != 99:
        op, modes = split_instruction(game.prog[game.ip])
        values, offset = get_values(game.prog, game.ip, op, modes, game)
 
        if op == "01": # Addition
            game.prog[game.prog[game.ip+3] + offset] = values[0] + values[1]
            game.ip += 4
 
        if op == "02": # Multiplication
            game.prog[game.prog[game.ip+3] + offset] = values[0] * values[1]
            game.ip += 4
 
        if op == "03": # Read and Store input
            game.prog[game.prog[game.ip+1] + offset] = game.input.popleft()
            game.ip += 2
 
        if op == "04": # Print Output
            game.output.append(values[0])
            game.ip += 2
            return
 
        if op == "05": # Jump-if-True
            if values[0]:
                game.ip = values[1]
            else:
                game.ip += 3
 
        if op == "06": # Jump-if-False
            if not values[0]:
                game.ip = values[1]
            else:
                game.ip += 3
 
        if op == "07": # Less than
            if values[0] < values[1]:
                game.prog[game.prog[game.ip+3] + offset] = 1
            else:
                game.prog[game.prog[game.ip+3] + offset] = 0
            game.ip += 4
 
        if op == "08": # Equals
            if values[0] == values[1]:
                game.prog[game.prog[game.ip+3] + offset] = 1
            else:
                game.prog[game.prog[game.ip+3] + offset] = 0
            game.ip += 4
 
        if op == "09": # Adjust Relative Base
            game.rel_base += values[0]
            game.ip += 2
 
    game.halt = True
 
def create_program(input):
    prog = defaultdict(int)
 
    for i in range(len(input)):
        prog[i] = int(input[i])
 
    return prog
 
 
input  = open('input').read().split(",")
prog   = create_program(input)
game   = Game(prog)
 
output = 0
 
while output != 10:
    run_game(game)
    if (output := read_output(game)):
        print(chr(output), end ="")
 
instruction = "NOT C J\n" + \
                "NOT B T\n" + \
                "OR T J\n"  + \
                "NOT A T\n" + \
                "OR T J\n"  + \
                "AND D J\n" + \
                "NOT E T\n" + \
                "NOT T T\n" + \
                "OR H T\n"  + \
                "AND T J\n" + \
                "RUN\n"
 
print(instruction)
run_game(game, [ord(char) for char in instruction])
 
while not game.halt:
    if (output := read_output(game)):
        if output > 255:
            print(output)
        else:
            print(chr(output), end ="")
    run_game(game)

2019 Day 21 Part 01

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
139
140
141
142
143
144
145
146
147
148
149
150
151
152

from collections import defaultdict, deque
 
class Game:
    def __init__(self, prog):
        self.prog     = prog
        self.ip       = 0
        self.input    = deque()
        self.output   = deque()
        self.rel_base = 0
        self.halt     = False
 
def split_instruction(instruction):
    instruction = f"{instruction:05}"
    return instruction[3:], instruction[0:3]
 
def get_values(input, pos, op, modes, game):
    mode_a, mode_b, mode_c = modes
    values = []
    offset = 0
 
    if op in ["01", "02", "04", "05", "06", "07", "08", "09"]:
        if mode_c == "0":
            values.append(input[input[pos+1]])
        elif mode_c == "1":
            values.append(input[pos+1])
        elif mode_c == "2":
            values.append(input[input[pos+1]+game.rel_base])
 
        if op in ["01", "02", "05", "06", "07", "08"]:
            if mode_b == "0":
                values.append(input[input[pos+2]])
            elif mode_b == "1":
                values.append(input[pos+2])
            elif mode_b == "2":
                values.append(input[input[pos+2]+game.rel_base])
 
            if op in []:
                if mode_a == "0":
                    values.append(input[input[pos+3]])
                elif mode_a == "1":
                    values.append(input[pos+3])
                elif mode_a == "2":
                    values.append(input[input[pos+3]+game.rel_base])
 
    if op in ["01", "02", "07", "08"]:
        if mode_a == "2":
            offset = game.rel_base
 
    if op in ["03"]:
        if mode_c == "2":
            offset = game.rel_base
 
    return values, offset
 
def read_output(game):
    if len(game.output):
        return game.output.popleft()
    return None
 
def run_game(game, input = []):
    if len(input):
        game.input.extend(input)
 
    while game.prog[game.ip] != 99:
        op, modes = split_instruction(game.prog[game.ip])
        values, offset = get_values(game.prog, game.ip, op, modes, game)
 
        if op == "01": # Addition
            game.prog[game.prog[game.ip+3] + offset] = values[0] + values[1]
            game.ip += 4
 
        if op == "02": # Multiplication
            game.prog[game.prog[game.ip+3] + offset] = values[0] * values[1]
            game.ip += 4
 
        if op == "03": # Read and Store input
            game.prog[game.prog[game.ip+1] + offset] = game.input.popleft()
            game.ip += 2
 
        if op == "04": # Print Output
            game.output.append(values[0])
            game.ip += 2
            return
 
        if op == "05": # Jump-if-True
            if values[0]:
                game.ip = values[1]
            else:
                game.ip += 3
 
        if op == "06": # Jump-if-False
            if not values[0]:
                game.ip = values[1]
            else:
                game.ip += 3
 
        if op == "07": # Less than
            if values[0] < values[1]:
                game.prog[game.prog[game.ip+3] + offset] = 1
            else:
                game.prog[game.prog[game.ip+3] + offset] = 0
            game.ip += 4
 
        if op == "08": # Equals
            if values[0] == values[1]:
                game.prog[game.prog[game.ip+3] + offset] = 1
            else:
                game.prog[game.prog[game.ip+3] + offset] = 0
            game.ip += 4
 
        if op == "09": # Adjust Relative Base
            game.rel_base += values[0]
            game.ip += 2
 
    game.halt = True
 
def create_program(input):
    prog = defaultdict(int)
 
    for i in range(len(input)):
        prog[i] = int(input[i])
 
    return prog
 
 
input  = open('input').read().split(",")
prog   = create_program(input)
game   = Game(prog)
 
output = 0
 
while output != 10:
    run_game(game)
    if (output := read_output(game)):
        print(chr(output), end ="")
 
instruction = "NOT C J\n" + \
                "NOT A T\n" + \
                "OR T J\n"  + \
                "AND D J\n" + \
                "WALK\n"
 
print(instruction)
run_game(game, [ord(char) for char in instruction])
 
while not game.halt:
    if (output := read_output(game)):
        if output > 255:
            print(output)
        else:
            print(chr(output), end ="")
    run_game(game)

2019 Day 20 Part 02

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
139
140

from collections import defaultdict
from copy import copy
 
class Dungeon:
    def __init__(self, layout):
        self.area         = defaultdict(str)
        self.size_x       = len(layout[2])+4
        self.size_y       = len(layout)
        self.portals      = defaultdict(list)
        self.portal_names = defaultdict(str)
        self.paths        = defaultdict(list)
 
        for y in range(self.size_y):
            for x in range(self.size_x):
                if x < len(layout[y]):
                    self.area[(x, y)] = layout[y][x]
 
        self.reduce_dungeon()
        self.find_portals()
        self.find_paths()
 
    def is_dead_end(self, pos, keys_allowed = False):
        tile = self.area[pos]
        if tile == "#" or tile == "@" or (not keys_allowed and tile.islower()):
            return False
 
        count = sum(self.area[(pos[0] + side[0], pos[1] + side[1])] != "#" for side in [(-1,0), (0,-1), (1,0), (0,1)])
 
        if count <= 1:
            return True
        return False
 
    def reduce_dungeon(self):
        reduced = True
        while reduced:
            reduced = False
            for y in range(1, self.size_y):
                for x in range(1, self.size_x):
                    if self.is_dead_end((x, y)):
                        self.area[(x, y)] = "#"
                        reduced = True
 
    def find_portals(self):
        for y in range(self.size_y):
            for x in range(self.size_x):
                if self.area[(x, y)].isupper():
                    if x > 10 and y > 10 and \
                       x < self.size_x - 10 and y < self.size_y - 10:
                        id = 1
                    else:
                        id = -1
 
                    if self.area[(x+1, y)].isupper():
                        name = self.area[(x, y)] + self.area[(x+1, y)]
                        if self.area[(x+2, y)] == ".":
                            self.portals[(name, id)].append((x+2, y))
                            self.portal_names[(x+1, y)] = (name, id)
                        elif self.area[(x-1, y)] == ".":
                            self.portals[(name, id)].append((x-1, y))
                            self.portal_names[(x, y)] = (name, id)
 
                    elif self.area[(x, y+1)].isupper():
                        name = self.area[(x, y)] + self.area[(x, y+1)]
                        if self.area[(x, y+2)] == ".":
                            self.portals[(name, id)].append((x, y+2))
                            self.portal_names[(x, y+1)] = (name, id)
                        elif self.area[(x, y-1)] == ".":
                            self.portals[(name, id)].append((x, y-1))
                            self.portal_names[(x, y)] = (name, id)
 
    def find_paths(self):
        for name, positions in self.portals.items():
            for pos in positions:
                next_search = defaultdict(int)
                next_search[pos] = 1
 
                changes = True
                steps   = 0
 
                while changes or not steps:
                    changes = False
                    steps  += 1
                    search = copy(next_search)
 
                    for position, state in search.items():
                        if state == -1:
                            del next_search[position]
                        if state == 1:
                            next_search[position] = -1
                            for side in [(-1,0), (0,-1), (1,0), (0,1)]:
                                side_pos = (position[0] + side[0], position[1] + side[1])
                                if self.area[side_pos] != "#" and \
                                 not search[side_pos]:
                                    del search[side_pos]
                                    changes = True
                                    next_search[side_pos] = 1
                                    if self.area[side_pos].isupper():
                                        next_search[side_pos] = -1
                                        if steps > 1:
                                            target_name = self.portal_names[(side_pos)]
                                            self.paths[name].append((target_name, steps-1))
 
def find_shortest_way(dungeon, path = [("AA", -1, 0)], best_steps = 1e8, steps = 0):
    depth = path[-1][2]
    if depth > 25:
        return 1e8
    if depth == -1:
        return steps
 
    for next_portal in sorted(dungeon.paths[(path[-1][0], path[-1][1])], key = lambda x: x[1], reverse = True):
        situation = (next_portal[0][0], next_portal[0][1], depth)
 
        if situation in path:
            continue
        if (situation[0] == "AA" or situation[0] == "ZZ") and situation[2] > 0:
            continue
        if (situation[0] != "AA" and situation[0] != "ZZ") and situation[1] == -1 and situation[2] == 0:
            continue
 
        next_steps = steps + next_portal[1] + 1
        if next_steps >= best_steps:
            continue
 
        if next_portal[0][1] == -1:
            id = 1
        else:
            id = -1
 
        next_path = path + [situation] + [(next_portal[0][0], id, depth + next_portal[0][1])]
        this_steps = find_shortest_way(dungeon, next_path, best_steps, next_steps)
 
        if this_steps < best_steps:
            best_steps = this_steps
 
    return best_steps
 
 
input = open('input').readlines()
dungeon = Dungeon(input)
print(find_shortest_way(dungeon) - 1)

2019 Day 20 Part 01

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

from collections import defaultdict
from copy import copy
 
class Dungeon:
    def __init__(self, layout):
        self.area         = defaultdict(str)
        self.size_x       = len(layout[2])+4
        self.size_y       = len(layout)
        self.portals      = defaultdict(list)
        self.portal_names = defaultdict(str)
        self.paths        = defaultdict(list)
 
        for y in range(self.size_y):
            for x in range(self.size_x):
                if x < len(layout[y]):
                    self.area[(x, y)] = layout[y][x]
 
        self.reduce_dungeon()
        self.find_portals()
        self.find_paths()
 
    def is_dead_end(self, pos, keys_allowed = False):
        tile = self.area[pos]
        if tile == "#" or tile == "@" or (not keys_allowed and tile.islower()):
            return False
 
        count = sum(self.area[(pos[0] + side[0], pos[1] + side[1])] != "#" for side in [(-1,0), (0,-1), (1,0), (0,1)])
 
        if count <= 1:
            return True
        return False
 
    def reduce_dungeon(self):
        reduced = True
        while reduced:
            reduced = False
            for y in range(1, self.size_y):
                for x in range(1, self.size_x):
                    if self.is_dead_end((x, y)):
                        self.area[(x, y)] = "#"
                        reduced = True
 
    def find_portals(self):
        for y in range(self.size_y):
            for x in range(self.size_x):
                if self.area[(x, y)].isupper():
                    if self.area[(x+1, y)].isupper():
                        name = self.area[(x, y)] + self.area[(x+1, y)]
                        if not name in [p[0] for p in self.portals]:
                            id = 0
                        else:
                            id = 1
                        if self.area[(x+2, y)] == ".":
                            self.portals[(name, id)].append((x+2, y))
                            self.portal_names[(x+1, y)] = (name, id)
                        elif self.area[(x-1, y)] == ".":
                            self.portals[(name, id)].append((x-1, y))
                            self.portal_names[(x, y)] = (name, id)
 
                    elif self.area[(x, y+1)].isupper():
                        name = self.area[(x, y)] + self.area[(x, y+1)]
                        if not name in [p[0] for p in self.portals]:
                            id = 0
                        else:
                            id = 1
                        if self.area[(x, y+2)] == ".":
                            self.portals[(name, id)].append((x, y+2))
                            self.portal_names[(x, y+1)] = (name, id)
                        elif self.area[(x, y-1)] == ".":
                            self.portals[(name, id)].append((x, y-1))
                            self.portal_names[(x, y)] = (name, id)
 
    def find_paths(self):
        for name, positions in self.portals.items():
            for pos in positions:
                next_search = defaultdict(int)
                next_search[pos] = 1
 
                changes = True
                steps   = 0
 
                while changes or not steps:
                    changes = False
                    steps  += 1
                    search = copy(next_search)
 
                    for position, state in search.items():
                        if state == -1:
                            del next_search[position]
                        if state == 1:
                            next_search[position] = -1
                            for side in [(-1,0), (0,-1), (1,0), (0,1)]:
                                side_pos = (position[0] + side[0], position[1] + side[1])
                                if self.area[side_pos] != "#" and \
                                 not search[side_pos]:
                                    del search[side_pos]
                                    changes = True
                                    next_search[side_pos] = 1
                                    if self.area[side_pos].isupper():
                                        next_search[side_pos] = -1
                                        if steps > 1:
                                            target_name = self.portal_names[(side_pos)]
                                            self.paths[name].append((target_name, steps-1))
 
def find_shortest_way(dungeon, path = [("AA", 0)], best_steps = 1e8, steps = 0):
    if path[-1] == ("ZZ", 1):
        return steps
 
    for next_portal in dungeon.paths[path[-1]]:
        if next_portal[0] in path:
            continue
 
        next_steps = steps + next_portal[1] + 1
        if next_steps >= best_steps:
            continue
 
        if next_portal[0][1] == 0:
            id = 1
        else:
            id = 0
 
        next_path = path + [next_portal] + [(next_portal[0][0], id)]
        this_steps = find_shortest_way(dungeon, next_path, best_steps, next_steps)
 
        if this_steps < best_steps:
            best_steps = this_steps
 
    return best_steps
 
 
input = open('input').readlines()
dungeon = Dungeon(input)
print(find_shortest_way(dungeon) - 1)

2019 Day 19 Part 02

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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182

from collections import defaultdict, deque
from copy import copy
 
class Game:
    def __init__(self, prog):
        self.prog     = prog
        self.ip       = 0
        self.input    = deque()
        self.output   = deque()
        self.rel_base = 0
        self.halt     = False
 
def split_instruction(instruction):
    instruction = f"{instruction:05}"
    return instruction[3:], instruction[0:3]
 
def get_values(input, pos, op, modes, game):
    mode_a, mode_b, mode_c = modes
    values = []
    offset = 0
 
    if op in ["01", "02", "04", "05", "06", "07", "08", "09"]:
        if mode_c == "0":
            values.append(input[input[pos+1]])
        elif mode_c == "1":
            values.append(input[pos+1])
        elif mode_c == "2":
            values.append(input[input[pos+1]+game.rel_base])
 
        if op in ["01", "02", "05", "06", "07", "08"]:
            if mode_b == "0":
                values.append(input[input[pos+2]])
            elif mode_b == "1":
                values.append(input[pos+2])
            elif mode_b == "2":
                values.append(input[input[pos+2]+game.rel_base])
 
            if op in []:
                if mode_a == "0":
                    values.append(input[input[pos+3]])
                elif mode_a == "1":
                    values.append(input[pos+3])
                elif mode_a == "2":
                    values.append(input[input[pos+3]+game.rel_base])
 
    if op in ["01", "02", "07", "08"]:
        if mode_a == "2":
            offset = game.rel_base
 
    if op in ["03"]:
        if mode_c == "2":
            offset = game.rel_base
 
    return values, offset
 
def read_output(game):
    if len(game.output):
        return game.output.popleft()
    return None
 
def run_game(game, input = []):
    if len(input):
        game.input.extend(input)
 
    while game.prog[game.ip] != 99:
        op, modes = split_instruction(game.prog[game.ip])
        values, offset = get_values(game.prog, game.ip, op, modes, game)
 
        if op == "01": # Addition
            game.prog[game.prog[game.ip+3] + offset] = values[0] + values[1]
            game.ip += 4
 
        if op == "02": # Multiplication
            game.prog[game.prog[game.ip+3] + offset] = values[0] * values[1]
            game.ip += 4
 
        if op == "03": # Read and Store input
            game.prog[game.prog[game.ip+1] + offset] = game.input.popleft()
            game.ip += 2
 
        if op == "04": # Print Output
            game.output.append(values[0])
            game.ip += 2
            return
 
        if op == "05": # Jump-if-True
            if values[0]:
                game.ip = values[1]
            else:
                game.ip += 3
 
        if op == "06": # Jump-if-False
            if not values[0]:
                game.ip = values[1]
            else:
                game.ip += 3
 
        if op == "07": # Less than
            if values[0] < values[1]:
                game.prog[game.prog[game.ip+3] + offset] = 1
            else:
                game.prog[game.prog[game.ip+3] + offset] = 0
            game.ip += 4
 
        if op == "08": # Equals
            if values[0] == values[1]:
                game.prog[game.prog[game.ip+3] + offset] = 1
            else:
                game.prog[game.prog[game.ip+3] + offset] = 0
            game.ip += 4
 
        if op == "09": # Adjust Relative Base
            game.rel_base += values[0]
            game.ip += 2
 
    game.halt = True
 
def create_program(input):
    prog = defaultdict(int)
 
    for i in range(len(input)):
        prog[i] = int(input[i])
 
    return prog
 
def try_y(prog, y, box_size = 100):
    output = 0
    x = y
 
    while output == 0:
        x += 1
        game = Game(copy(prog))
        run_game(game, [x, y])
        output = read_output(game)
 
    x1 = x
 
    while output == 1:
        x += 1
        game = Game(copy(prog))
        run_game(game, [x, y])
        output = read_output(game)
 
    x2 = x - 1
 
    if x2 - x1 + 1 < box_size:
        return -1, None
 
    game = Game(copy(prog))
    run_game(game, [x2-(box_size-1), y+box_size-1])
 
    if read_output(game) == 1:
        game = Game(copy(prog))
        run_game(game, [x2-(box_size-1), y+box_size])
        if read_output(game) == 0:
            return 0, (x2-(box_size-1), y)
        return 1, None
    return -1, None
 
 
input  = open('input').read().split(",")
prog   = create_program(input)
game   = Game(prog)
 
mini, maxi = 50, 1000
check = 1
 
while check:
    middle = (maxi + mini) // 2
    check, corner = try_y(prog, middle)
    if check == -1:
        mini = middle
    elif check == 1:
        maxi = middle
 
while not check:
    middle -= 1
    check, corner = try_y(prog, middle)
    if not check:
        real_corner = corner
 
print(real_corner[0] * 10000 + real_corner[1])

2019 Day 19 Part 01

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
139
140

from collections import defaultdict, deque
from copy import copy
 
class Game:
    def __init__(self, prog):
        self.prog     = prog
        self.ip       = 0
        self.input    = deque()
        self.output   = deque()
        self.rel_base = 0
        self.halt     = False
 
def split_instruction(instruction):
    instruction = f"{instruction:05}"
    return instruction[3:], instruction[0:3]
 
def get_values(input, pos, op, modes, game):
    mode_a, mode_b, mode_c = modes
    values = []
    offset = 0
 
    if op in ["01", "02", "04", "05", "06", "07", "08", "09"]:
        if mode_c == "0":
            values.append(input[input[pos+1]])
        elif mode_c == "1":
            values.append(input[pos+1])
        elif mode_c == "2":
            values.append(input[input[pos+1]+game.rel_base])
 
        if op in ["01", "02", "05", "06", "07", "08"]:
            if mode_b == "0":
                values.append(input[input[pos+2]])
            elif mode_b == "1":
                values.append(input[pos+2])
            elif mode_b == "2":
                values.append(input[input[pos+2]+game.rel_base])
 
            if op in []:
                if mode_a == "0":
                    values.append(input[input[pos+3]])
                elif mode_a == "1":
                    values.append(input[pos+3])
                elif mode_a == "2":
                    values.append(input[input[pos+3]+game.rel_base])
 
    if op in ["01", "02", "07", "08"]:
        if mode_a == "2":
            offset = game.rel_base
 
    if op in ["03"]:
        if mode_c == "2":
            offset = game.rel_base
 
    return values, offset
 
def read_output(game):
    if len(game.output):
        return game.output.popleft()
    return None
 
def run_game(game, input = []):
    if len(input):
        game.input.extend(input)
 
    while game.prog[game.ip] != 99:
        op, modes = split_instruction(game.prog[game.ip])
        values, offset = get_values(game.prog, game.ip, op, modes, game)
 
        if op == "01": # Addition
            game.prog[game.prog[game.ip+3] + offset] = values[0] + values[1]
            game.ip += 4
 
        if op == "02": # Multiplication
            game.prog[game.prog[game.ip+3] + offset] = values[0] * values[1]
            game.ip += 4
 
        if op == "03": # Read and Store input
            game.prog[game.prog[game.ip+1] + offset] = game.input.popleft()
            game.ip += 2
 
        if op == "04": # Print Output
            game.output.append(values[0])
            game.ip += 2
            return
 
        if op == "05": # Jump-if-True
            if values[0]:
                game.ip = values[1]
            else:
                game.ip += 3
 
        if op == "06": # Jump-if-False
            if not values[0]:
                game.ip = values[1]
            else:
                game.ip += 3
 
        if op == "07": # Less than
            if values[0] < values[1]:
                game.prog[game.prog[game.ip+3] + offset] = 1
            else:
                game.prog[game.prog[game.ip+3] + offset] = 0
            game.ip += 4
 
        if op == "08": # Equals
            if values[0] == values[1]:
                game.prog[game.prog[game.ip+3] + offset] = 1
            else:
                game.prog[game.prog[game.ip+3] + offset] = 0
            game.ip += 4
 
        if op == "09": # Adjust Relative Base
            game.rel_base += values[0]
            game.ip += 2
 
    game.halt = True
 
def create_program(input):
    prog = defaultdict(int)
 
    for i in range(len(input)):
        prog[i] = int(input[i])
 
    return prog
 
 
input  = open('input').read().split(",")
prog   = create_program(input)
game   = Game(prog)
 
result = 0
 
for y in range(50):
    for x in range(50):
        game = Game(copy(prog))
        run_game(game, [x, y])
        if read_output(game):
            result += 1
 
print (result)

2019 Day 18 Part 02

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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185

from collections import defaultdict
from copy import copy, deepcopy
 
class Key:
    def __init__(self, dungeon, position, type):
        self.position         = position
        self.type             = type
        self.distance_to_keys = self.get_key_distances(dungeon)
        self.bot              = self.get_bot()
        self.blocked_by_doors = self.get_blocking_doors(dungeon)
 
    def get_key_distances(self, dungeon):
        next_search = defaultdict(int)
        next_search[self.position] = 1
        keys = {}
        changes = True
        steps   = 0
 
        while changes or not steps:
            changes = False
            steps  += 1
            search = copy(next_search)
 
            for position, state in search.items():
                if state == -1:
                    del next_search[position]
                if state == 1:
                    next_search[position] = -1
                    for side in [(-1,0), (0,-1), (1,0), (0,1)]:
                        side_pos = (position[0] + side[0], position[1] + side[1])
                        if dungeon.area[side_pos] != "#" and \
                           not search[side_pos]:
                            del search[side_pos]
                            changes = True
                            next_search[side_pos] = 1
                            if dungeon.area[side_pos].islower() or dungeon.area[side_pos].isnumeric():
                                keys[dungeon.area[side_pos]] = steps
        return keys
 
    def get_blocking_doors(self, dungeon):
        if self.type.isnumeric():
            return []
 
        next_search = defaultdict(list)
        next_search[dungeon.bot_pos[self.bot]] = [1]
 
        while True:
            search = copy(next_search)
 
            for position, state in search.items():
                if state[0] == -1:
                    del next_search[position]
                if state[0] == 1:
                    next_search[position] = [-1]
                    for side in [(-1,0), (0,-1), (1,0), (0,1)]:
                        side_pos = (position[0] + side[0], position[1] + side[1])
                        if dungeon.area[side_pos] != "#" and \
                           not search[side_pos]:
                            del search[side_pos]
                            next_search[side_pos] = copy(state)
                            if dungeon.area[side_pos] == self.type:
                                return state[1:]
                            elif dungeon.area[side_pos].isupper():
                                next_search[side_pos].append(dungeon.area[side_pos])
 
    def get_bot(self):
        for key in self.distance_to_keys.keys():
            if key.isnumeric():
                return int(key)
 
 
class Dungeon:
    def __init__(self, layout):
        self.area         = defaultdict(str)
        self.size_x       = len(layout[0])
        self.size_y       = len(layout)
        self.position     = (0, 0)
        self.key_pos      = {}
        self.bot_pos      = []
 
        for y in range(self.size_y):
            for x in range(self.size_x):
                self.area[(x, y)] = layout[y][x]
                if self.area[(x, y)].islower():
                    self.key_pos[self.area[(x, y)]] = (x, y)
                elif self.area[(x, y)] == "@":
                    self.position = (x, y)
 
        self.reduce_dungeon()
        self.patch_dungeon()
 
    def patch_dungeon(self):
        self.area[self.position] = "#"
        for side in [(-1,0), (0,-1), (1,0), (0,1)]:
            side_pos = (self.position[0] + side[0], self.position[1] + side[1])
            self.area[side_pos] = "#"
        for side_id in range(4):
            side = [(-1,1), (1,-1), (1,1), (-1,-1)][side_id]
            side_pos = (self.position[0] + side[0], self.position[1] + side[1])
            self.area[side_pos] = str(side_id)
            self.bot_pos.append(side_pos)
            self.key_pos[str(side_id)] = side_pos
 
    def is_dead_end(self, pos, keys_allowed = False):
        tile = self.area[pos]
        if tile == "#" or tile == "@" or (not keys_allowed and tile.islower()):
            return False
 
        count = sum(self.area[(pos[0] + side[0], pos[1] + side[1])] != "#" for side in [(-1,0), (0,-1), (1,0), (0,1)])
 
        if count <= 1:
            return True
        return False
 
    def reduce_dungeon(self):
        reduced = True
        while reduced:
            reduced = False
            for y in range(1, self.size_y):
                for x in range(1, self.size_x):
                    if self.is_dead_end((x, y)):
                        self.area[(x, y)] = "#"
                        reduced = True
 
def create_keys(dungeon):
    keys = {}
    for type, position in dungeon.key_pos.items():
        keys[type] = Key(dungeon, position, type)
 
    for bot_id in range(4):
        keys[str(bot_id)] = Key(dungeon, dungeon.bot_pos[bot_id], str(bot_id))
 
    return keys
 
def get_reachable_keys(keys, keys_taken, doors_opened):
    reachable = set()
    for key in keys.values():
        if len(set(key.blocked_by_doors) & doors_opened) == len(key.blocked_by_doors) and \
           key.type not in keys_taken:
            reachable.add(key)
    return reachable
 
def fetch_keys(key_pos, bot_pos, keys, keys_taken, doors_opened, known_best = 1e8, path = 0, known_situations = {}):
    if len(keys_taken) == len(keys):
        return path
 
    best_path = known_best
    reachable_keys = get_reachable_keys(keys, keys_taken, doors_opened)
 
    for next_key in reachable_keys:
        for current_key, position in key_pos.items():
            if bot_pos[next_key.bot] == position:
                break
 
        next_path = path + keys[current_key].distance_to_keys[next_key.type]
 
        current_situation = tuple(sorted(list(keys_taken)) + [bot_pos[bot_id] for bot_id in range(4)])
 
        if current_situation in known_situations:
            if next_path >= known_situations[current_situation]:
                continue
 
        known_situations[current_situation] = next_path
 
        if next_path >= best_path:
            continue
 
        next_keys_taken   = keys_taken   | set(next_key.type)
        next_doors_opened = doors_opened | set(next_key.type.upper())
        next_bot_pos      = deepcopy(bot_pos)
        next_bot_pos[next_key.bot] = copy(key_pos[next_key.type])
 
        this_path = fetch_keys(key_pos, next_bot_pos, keys, next_keys_taken, next_doors_opened, best_path, next_path, known_situations)
        if this_path < best_path:
            best_path = this_path
 
    return best_path
 
input        = open('input').read().splitlines()
dungeon      = Dungeon(input)
keys         = create_keys(dungeon)
keys_taken   = set(str(bot_id) for bot_id in range(4))
doors_opened = set()
 
print(fetch_keys(dungeon.key_pos, dungeon.bot_pos, keys, keys_taken, doors_opened))

2019 Day 18 Part 01

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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

from collections import defaultdict
from copy import copy
 
class Key:
    def __init__(self, dungeon, position, type):
        self.position         = position
        self.type             = type
        self.distance_to_keys = self.get_key_distances(dungeon)
        self.blocked_by_doors = self.get_blocking_doors(dungeon)
 
    def get_key_distances(self, dungeon):
        next_search = defaultdict(int)
        next_search[self.position] = 1
        keys    = {}
        changes = True
        steps   = 0
 
        while changes or not steps:
            changes = False
            steps  += 1
            search = copy(next_search)
 
            for position, state in search.items():
                if state == -1:
                    del next_search[position]
                if state == 1:
                    next_search[position] = -1
                    for side in [(-1,0), (0,-1), (1,0), (0,1)]:
                        side_pos = (position[0] + side[0], position[1] + side[1])
                        if dungeon.area[side_pos] != "#" and \
                           not search[side_pos]:
                            del search[side_pos]
                            changes = True
                            next_search[side_pos] = 1
                            if dungeon.area[side_pos].islower():
                                keys[dungeon.area[side_pos]] = steps
        return keys
 
    def get_blocking_doors(self, dungeon):
        if self.type == "@":
            return []
 
        next_search = defaultdict(list)
        next_search[dungeon.position] = [1]
 
        while True:
            search = copy(next_search)
 
            for position, state in search.items():
                if state[0] == -1:
                    del next_search[position]
                if state[0] == 1:
                    next_search[position] = [-1]
                    for side in [(-1,0), (0,-1), (1,0), (0,1)]:
                        side_pos = (position[0] + side[0], position[1] + side[1])
                        if dungeon.area[side_pos] != "#" and \
                           not search[side_pos]:
                            del search[side_pos]
                            next_search[side_pos] = copy(state)
                            if dungeon.area[side_pos] == self.type:
                                return state[1:]
                            elif dungeon.area[side_pos].isupper():
                                next_search[side_pos].append(dungeon.area[side_pos])
 
class Dungeon:
    def __init__(self, layout):
        self.area         = defaultdict(str)
        self.size_x       = len(layout[0])
        self.size_y       = len(layout)
        self.position     = (0, 0)
        self.key_pos      = {}
 
        for y in range(self.size_y):
            for x in range(self.size_x):
                self.area[(x, y)] = layout[y][x]
                if self.area[(x, y)].islower():
                    self.key_pos[self.area[(x, y)]] = (x, y)
                elif self.area[(x, y)] == "@":
                    self.position = (x, y)
 
        self.reduce_dungeon()
 
    def is_dead_end(self, pos, keys_allowed = False):
        tile = self.area[pos]
        if tile == "#" or tile == "@" or (not keys_allowed and tile.islower()):
            return False
 
        count = sum(self.area[(pos[0] + side[0], pos[1] + side[1])] != "#" for side in [(-1,0), (0,-1), (1,0), (0,1)])
 
        if count <= 1:
            return True
        return False
 
    def reduce_dungeon(self):
        reduced = True
        while reduced:
            reduced = False
            for y in range(1, self.size_y):
                for x in range(1, self.size_x):
                    if self.is_dead_end((x, y)):
                        self.area[(x, y)] = "#"
                        reduced = True
 
def create_keys(dungeon):
    keys = {}
    for type, position in dungeon.key_pos.items():
        keys[type] = Key(dungeon, position, type)
 
    keys["@"] = Key(dungeon, dungeon.position, "@")
 
    return keys
 
def get_reachable_keys(keys, keys_taken, doors_opened):
    reachable = set()
    for key in keys.values():
        if len(set(key.blocked_by_doors) & doors_opened) == len(key.blocked_by_doors) and \
           key.type not in keys_taken:
            reachable.add(key)
    return reachable
 
def fetch_keys(keys, keys_taken, doors_opened, current_key = "@", known_best = 1e8, path = 0, known_situations = {}):
    if len(keys_taken) == len(keys):
        return path
 
    best_path = known_best
    reachable_keys = get_reachable_keys(keys, keys_taken, doors_opened)
    reachable_keys = sorted(reachable_keys, key = lambda x: keys[current_key].distance_to_keys[x.type])
 
    for next_key in reachable_keys:
        next_path = path + keys[current_key].distance_to_keys[next_key.type]
 
        current_situation = tuple(sorted(list(keys_taken)) + [next_key.type])
 
        if current_situation in known_situations:
            if next_path >= known_situations[current_situation]:
                continue
 
        known_situations[current_situation] = next_path
 
        if next_path >= best_path:
            continue
 
        next_keys_taken   = keys_taken   | set(next_key.type)
        next_doors_opened = doors_opened | set(next_key.type.upper())
 
        this_path = fetch_keys(keys, next_keys_taken, next_doors_opened, next_key.type, best_path, next_path, known_situations)
        if this_path < best_path:
            best_path = this_path
 
    return best_path
 
 
input        = open('input').read().splitlines()
dungeon      = Dungeon(input)
keys         = create_keys(dungeon)
keys_taken   = set(("@"))
doors_opened = set()
 
print(fetch_keys(keys, keys_taken, doors_opened))

2019 Day 17 Part 01 + 02

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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349

from typing import Iterator, Callable
from collections import deque
from array import array
 
class IntCode:
    def __init__(self, filename: str = None) -> None:
        self.program    = []
        self.ip         = 0
        self.base       = 0
        self.lastInput  = None
 
        if not filename == None:
            with open(filename, 'rt') as data:
                for opcode in data.readline().split(','):
                    self.program.append(int(opcode))
 
    def save(self, filename: str) -> None:
        def pack(f):
            for c in self.memory:
                if c >= 0 and c < 256:
                    array('B', [c]).tofile(f)
                elif c < 0 and c > -128:
                    array('b', [c]).tofile(f)
                elif c > -32768 and c <= 32768:
                    array('i', [c]).tofile(f)
                else:
                    array('l', [c]).tofile(f)
 
        with open(filename, "wb") as data:
            pack(data)
 
    def clone(self):
        copy = IntCode()
        copy.program = self.program
        return copy
 
    def load(self) -> None:
        self.memory = [byte for byte in self.program]
        self.ip     = 0
        self.base   = 0
 
    def readNext(self) -> int:
        value = self.peek(self.ip)
        self.ip += 1
        return value
 
    def peek(self, address: int) -> int:
        if address < 0:
            raise Exception("invalid negative address")
        if address >= len(self.memory):
            extra = address+1-len(self.memory)
            self.memory.extend([0]*extra)
        return self.memory[address]
 
    def poke(self, address: int, value: int) -> None:
        if address < 0:
            raise Exception("invalid negative address")
        if address >= len(self.memory):
            extra = address+1-len(self.memory)
            self.memory.extend([0]*extra)
 
        self.memory[address] = value
 
    def getNextInstruction(self) -> (int, int, int, int):
        instruction = self.readNext()
        opcode = instruction % 100
        instruction = int((instruction-opcode)/100)
 
        modeA  = instruction % 10
        instruction = int((instruction-modeA)/10)
        modeB  = instruction % 10
        instruction = int((instruction-modeB)/10)
        modeC  = instruction % 10
 
        if not (modeA == 0 or modeA == 1 or modeA == 2):
            raise Exception("Mode not supported in IntCode")
        if not (modeB == 0 or modeB == 1 or modeB == 2):
            raise Exception("Mode not supported in IntCode")
        if not (modeC == 0 or modeC == 1 or modeC == 2):
            raise Exception("Mode not supported in IntCode")
 
        return (opcode, modeA, modeB, modeC)
 
    def readParameter(self, mode: int) -> int:
        address = self.readNext()
        if mode == 0:
            address = self.peek(address)
        elif mode == 2:
            address = self.peek(self.base+address)
        return address
 
    def writeParameter(self, mode: int, value: int) -> None:
        if not (mode == 0 or mode ==  2):
            raise Exception("Mode 1 not supported")
        address = self.readNext()
        if mode == 2:
            address += self.base
        self.poke(address, value)
 
    def step(self) -> int:
        opcode, mode1, mode2, mode3 = self.getNextInstruction()
 
        if opcode == 99: # halt
            self.ip = -1
 
        elif opcode == 1: # add
            a = self.readParameter(mode1)
            b = self.readParameter(mode2)
 
            self.writeParameter(mode3, a + b)
 
        elif opcode == 2: # multiply
            a = self.readParameter(mode1)
            b = self.readParameter(mode2)
            self.writeParameter(mode3, a * b)
 
        elif opcode == 3: # read input
            self.lastInput = next(self.input)
            self.writeParameter(mode1, self.lastInput)
 
        elif opcode == 4: # write output
            value = self.readParameter(mode1)
            self.output(value)
 
        elif opcode == 5: # jump if not 0
            v1 = self.readParameter(mode1)
            v2 = self.readParameter(mode2)
            if not v1 == 0:
                self.ip = v2
 
        elif opcode == 6: # jump if 0
            v1 = self.readParameter(mode1)
            v2 = self.readParameter(mode2)
            if v1 == 0:
                self.ip = v2
 
        elif opcode == 7: # less than
            v1 = self.readParameter(mode1)
            v2 = self.readParameter(mode2)
            self.writeParameter(mode3, 1 if v1 < v2 else 0)
 
        elif opcode == 8: # equals
            v1 = self.readParameter(mode1)
            v2 = self.readParameter(mode2)
            self.writeParameter(mode3, 1 if v1 == v2 else 0)
 
        elif opcode == 9: # adjusts the relative base
            v1 = self.readParameter(mode1)
            self.base += v1
 
        return opcode
 
    def initialize(self, input: Iterator[int], output: Callable[[int], None]) -> None:
        self.load()
        self.output = output
        self.input  = input
 
    def execute(self) -> None:
        self.ip   = 0
        self.base = 0
        while self.ip >= 0:
            self.step()
 
 
UP   = '^'
DOWN = 'v'
LEFT = '<'
RIGHT= '>'
 
def part1(program: IntCode) -> (int, [[chr], int, int]):
    def input():
        while True:
            yield 0
 
    map = []
 
    previousLine = []
    currentLine  = []
    robotX, robotY = 0, 0
    x, y, total = 0, 0, 0
 
    def output(ch: int) -> None:
        nonlocal previousLine, currentLine, x, y, total, robotX, robotY
 
        if ch == 10:
            map.append(currentLine)
            previousLine = currentLine
            currentLine  = []
            y += 1
            x  = 0
        else:
            ch = chr(ch)
            currentLine.append(ch)
            if ch == '^' or ch == '<' or ch == '>' or ch == 'v':
                robotX, robotY = x, y
            if y > 0 and ch != '.' and x > 1 and currentLine[x-1] != '.' and currentLine[x-2] != '.':
                if previousLine[x-1] != '.':
                    total += y * (x-1)
            x += 1
 
    program.initialize(input(), output)
    program.execute()
    if len(currentLine) != 0:
        map.append(currentLine)
 
    return total, map, robotX, robotY
 
def generatePath(map: [[chr]], x: int, y: int) -> [str]:
    robot = map[y][x]
    direction = (0, -1)
    if robot == UP:
        direction = (0, -1)
    elif robot == DOWN:
        direction = (0, 1)
    elif robot == LEFT:
        direction = (-1, 0)
    else:
        direction = (1, 0)
 
    def canGo(direction):
        xx = x + direction[0]
        yy = y + direction[1]
        if yy < 0 or yy >= len(map):
            return False
        if xx < 0 or xx >= len(map[yy]):
            return False
        return map[yy][xx] == '#'
 
    def turnRight(direction):
        if direction == (0, -1):
            return (1, 0)
        if direction == (0, 1):
            return (-1, 0)
        if direction == (1, 0):
            return (0, 1)
        if direction == (-1, 0):
            return (0, -1)
        raise Exception("Invalid direction")
 
    def turnLeft(direction):
        if direction == (0, -1):
            return (-1, 0)
        if direction == (0, 1):
            return (1, 0)
        if direction == (1, 0):
            return (0, -1)
        if direction == (-1, 0):
            return (0, 1)
        raise Exception("Invalid direction")
 
    moves = []
    while True:
        moveCount = 0
        while canGo(direction):
            x += direction[0]
            y += direction[1]
            moveCount += 1
        if moveCount > 0:
            moves.append(str(moveCount))
 
        if canGo(turnLeft(direction)):
            direction = turnLeft(direction)
            moves.append('L')
        elif canGo(turnRight(direction)):
            direction = turnRight(direction)
            moves.append('R')
        else:
            break
 
    return moves
 
def shrinkPath(moves: [str]) -> (str, []):
 
    def cleanPath(path: str) -> str:
        bad = [',', '-']
        while len(path) > 0 and path[0] in bad:
            path = path[1:]
        while len(path) > 0 and path[-1] in bad:
            path = path[:-1]
        return path
 
    def shrink(path: str, key: chr, result: str, patterns: [str]) -> (str, [str]):
        path = cleanPath(path)
        if len(path) == 0:
            if len(result) > 20:
                return None
            return result, patterns
 
        if key > 'C':
            return None
 
        i = path.find(',')
        while i < 20:
            p = path[0:i]
            if p.find('-') >= 0:
                return None
            patterns.append(p)
            good = shrink(path.replace(p, '-'), chr(ord(key)+1), result.replace(p, key), patterns)
            if good != None:
                return good
            patterns.pop()
            i = path.find(',', i+1)
 
        return None
 
    path = ','.join(moves)
    good = shrink(path, 'A', path, [])
    if good == None:
        raise Exception("No solution")
 
    return good
 
def part2(program: IntCode, map: [[chr]], x: int, y: int) -> int:
    moves = generatePath(map, x, y)
    path, patterns = shrinkPath(moves)
 
    result = None
 
    def input():
        for c in path:
            yield ord(c)
        yield 10
        for s in patterns:
            for c in s:
                yield ord(c)
            yield 10
 
        while True:
            yield ord('n')
            yield 10
 
    def output(code):
        nonlocal result
 
        if code > 256:
            result = code
        # else:
        #     print(chr(code), end="")
 
    program.initialize(input(), output)
    program.memory[0] = 2
    program.execute()
 
    return result
 
program = IntCode('input')
p1, map, robotX, robotY = part1(program)
print("Answer part 1 is", p1)
print("Answer part 2 is", part2(program, map, robotX, robotY))

2019 Day 16 Part 02

1
2
3
4
5
6
7
8
9

input = open('input').readline().strip()
offset   = int(input[:7])
elements = [int(num) for _ in range(10000) for num in input][offset:]
 
for _ in range(100):
    for i in range(-2, -len(elements)-1, -1):
        elements[i] = (elements[i] + elements[i+1]) % 10
 
print("".join(str(x) for x in elements[:8]))

2019 Day 16 Part 01

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

from collections import deque
 
input = open('input').readline().strip()
elements = [int(num) for num in input]
 
for phase in range(100):
    for pos in range(len(elements)):
        pattern = deque([p for p in [0, 1, 0, -1] for _ in range(pos+1)])
        pattern.rotate(-1)
 
        res = 0
        for i in range(len(elements)):
            res += elements[i] * pattern[0]
            pattern.rotate(-1)
        elements[pos] = abs(res) % 10
 
print("".join(str(x) for x in elements[:8]))

2019 Day 15 Part 02

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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264

from collections import defaultdict
from copy import copy
 
class Grid:
    def __init__(self, content = int):
        self.grid = defaultdict(content)
        self.pos = (0, 0)
 
    def up(self):
        self.pos = (self.pos[0], self.pos[1]+1)
 
    def right(self):
        self.pos = (self.pos[0]+1, self.pos[1])
 
    def down(self):
        self.pos = (self.pos[0], self.pos[1]-1)
 
    def left(self):
        self.pos = (self.pos[0]-1, self.pos[1])
 
    def set_pos(self, value):
        self.grid[self.pos] = value
 
    def wallbounce(self, direction):
        if direction == "up":
            self.up()
            self.set_pos("#")
            self.down()
        elif direction == "down":
            self.down()
            self.set_pos("#")
            self.up()
        elif direction == "left":
            self.left()
            self.set_pos("#")
            self.right()
        elif direction == "right":
            self.right()
            self.set_pos("#")
            self.left()
 
    def search(self, value):
        for k, v in self.grid.items():
            if v == value:
                return k
 
    def get_border(self):
        top, right, bottom, left = -1e8, -1e8, 1e8, 1e8
        for position, value in self.grid.items():
            if value:
                top     = max(top, position[1])
                right   = max(right, position[0])
                bottom  = min(bottom, position[1])
                left    = min(left, position[0])
        return top, right, bottom, left
 
    def draw(self):
        top, right, bottom, left = self.get_border()
        for y in range(bottom, top+1):
            for x in range(left, right+1):
                print(self.grid[(x, y)], end="")
                if self.grid[(x, y)] == "":
                    print(" ", end="")
            print()
 
class Game:
    def __init__(self, prog):
        self.prog     = prog
        self.ip       = 0
        self.output   = 0
        self.rel_base = 0
        self.halt     = False
 
def split_instruction(instruction):
    instruction = f"{instruction:05}"
    return instruction[3:], instruction[0:3]
 
def get_values(input, pos, op, modes, game):
    mode_a, mode_b, mode_c = modes
    values = []
    offset = 0
 
    if op in ["01", "02", "04", "05", "06", "07", "08", "09"]:
        if mode_c == "0":
            values.append(input[input[pos+1]])
        elif mode_c == "1":
            values.append(input[pos+1])
        elif mode_c == "2":
            values.append(input[input[pos+1]+game.rel_base])
 
        if op in ["01", "02", "05", "06", "07", "08"]:
            if mode_b == "0":
                values.append(input[input[pos+2]])
            elif mode_b == "1":
                values.append(input[pos+2])
            elif mode_b == "2":
                values.append(input[input[pos+2]+game.rel_base])
 
            if op in []:
                if mode_a == "0":
                    values.append(input[input[pos+3]])
                elif mode_a == "1":
                    values.append(input[pos+3])
                elif mode_a == "2":
                    values.append(input[input[pos+3]+game.rel_base])
 
    if op in ["01", "02", "07", "08"]:
        if mode_a == "2":
            offset = game.rel_base
 
    if op in ["03"]:
        if mode_c == "2":
            offset = game.rel_base
 
    return values, offset
 
def run_game(game, input = 0):
    while game.prog[game.ip] != 99:
        op, modes = split_instruction(game.prog[game.ip])
        values, offset = get_values(game.prog, game.ip, op, modes, game)
 
        if op == "01": # Addition
            game.prog[game.prog[game.ip+3] + offset] = values[0] + values[1]
            game.ip += 4
 
        if op == "02": # Multiplication
            game.prog[game.prog[game.ip+3] + offset] = values[0] * values[1]
            game.ip += 4
 
        if op == "03": # Read and Store input
            game.prog[game.prog[game.ip+1] + offset] = input
            game.ip += 2
 
        if op == "04": # Print Output
            game.output = values[0]
            game.ip += 2
            return game
 
        if op == "05": # Jump-if-True
            if values[0]:
                game.ip = values[1]
            else:
                game.ip += 3
 
        if op == "06": # Jump-if-False
            if not values[0]:
                game.ip = values[1]
            else:
                game.ip += 3
 
        if op == "07": # Less than
            if values[0] < values[1]:
                game.prog[game.prog[game.ip+3] + offset] = 1
            else:
                game.prog[game.prog[game.ip+3] + offset] = 0
            game.ip += 4
 
        if op == "08": # Equals
            if values[0] == values[1]:
                game.prog[game.prog[game.ip+3] + offset] = 1
            else:
                game.prog[game.prog[game.ip+3] + offset] = 0
            game.ip += 4
 
        if op == "09": # Adjust Relative Base
            game.rel_base += values[0]
            game.ip += 2
 
    game.halt = True
    return game
 
def create_program(input):
    prog = defaultdict(int)
 
    for i in range(len(input)):
        prog[i] = int(input[i])
 
    return prog
 
def get_best_dir(field, visited):
    all_dirs = [(0, 1), (0, -1), (-1, 0), (1, 0)]
 
    for dir in all_dirs:
        new_pos = (field.pos[0] + dir[0], field.pos[1] + dir[1])
        if field.grid[new_pos] != "":
            continue
 
        d = all_dirs.index(dir)+1
        return d
 
    least_visited = 1e8
    least_dir = -1
 
    for dir in all_dirs:
        new_pos = (field.pos[0] + dir[0], field.pos[1] + dir[1])
        if field.grid[new_pos] == "#":
            continue
 
        if least_visited > visited[new_pos]:
            least_dir = dir
            least_visited = visited[new_pos]
 
    d = all_dirs.index(least_dir) + 1
    return d
 
def get_map(game):
    visited = defaultdict(int)
    field = Grid(str)
    steps = 0
 
    while not game.halt and steps < 6000:
        dir = get_best_dir(field, visited)
        steps += 1
        run_game(game, dir)
 
        if game.output == 0:
            field.wallbounce(["up", "down", "left", "right"][dir-1])
 
        if game.output == 1:
            [field.up, field.down, field.left, field.right][dir-1]()
            field.set_pos(".")
 
        if game.output == 2:
            [field.up, field.down, field.left, field.right][dir-1]()
            field.set_pos("O")
 
        visited[field.pos] += 1
 
    return field
 
def fill_with_oxygen(field):
    search = defaultdict(int)
    search[field.search("O")] = 1
    new_search = copy(search)
    top, right, bottom, left = field.get_border()
    steps = 0
    finished = False
 
    while not finished:
        finished = True
        for y in range(bottom, top+1):
            for x in range(left, right+1):
                if search[(x, y)] == 1:
                    new_search[(x, y)] = -1
                    for dir in [(-1, 0),(0, -1),(1, 0),(0, 1)]:
                        new_pos = (x + dir[0], y + dir[1])
                        if search[new_pos] == -1:
                            continue
                        if field.grid[new_pos] == ".":
                            new_search[new_pos] = 1
                            finished = False
 
        search = copy(new_search)
        steps += 1
 
    return steps - 1
 
 
input  = open('input').read().split(",")
prog   = create_program(input)
game   = Game(prog)
field  = get_map(game)
 
print(fill_with_oxygen(field))

2019 Day 15 Part 01

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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262

from collections import defaultdict
from copy import copy
 
 
class Grid:
    def __init__(self, content = int):
        self.grid = defaultdict(content)
        self.pos = (0, 0)
 
    def up(self):
        self.pos = (self.pos[0], self.pos[1]+1)
 
    def right(self):
        self.pos = (self.pos[0]+1, self.pos[1])
 
    def down(self):
        self.pos = (self.pos[0], self.pos[1]-1)
 
    def left(self):
        self.pos = (self.pos[0]-1, self.pos[1])
 
    def set_pos(self, value):
        self.grid[self.pos] = value
 
    def wallbounce(self, direction):
        if direction == "up":
            self.up()
            self.set_pos("#")
            self.down()
        elif direction == "down":
            self.down()
            self.set_pos("#")
            self.up()
        elif direction == "left":
            self.left()
            self.set_pos("#")
            self.right()
        elif direction == "right":
            self.right()
            self.set_pos("#")
            self.left()
 
    def search(self, value):
        for k, v in self.grid.items():
            if v == value:
                return k
 
    def get_border(self):
        top, right, bottom, left = -1e8, -1e8, 1e8, 1e8
        for position, value in self.grid.items():
            if value:
                top     = max(top, position[1])
                right   = max(right, position[0])
                bottom  = min(bottom, position[1])
                left    = min(left, position[0])
        return top, right, bottom, left
 
    def draw(self):
        top, right, bottom, left = self.get_border()
        for y in range(bottom, top+1):
            for x in range(left, right+1):
                print(self.grid[(x, y)], end="")
                if self.grid[(x, y)] == "":
                    print(" ", end="")
            print()
 
class Game:
    def __init__(self, prog):
        self.prog     = prog
        self.ip       = 0
        self.output   = 0
        self.rel_base = 0
        self.halt     = False
 
def split_instruction(instruction):
    instruction = f"{instruction:05}"
    return instruction[3:], instruction[0:3]
 
def get_values(input, pos, op, modes, game):
    mode_a, mode_b, mode_c = modes
    values = []
    offset = 0
 
    if op in ["01", "02", "04", "05", "06", "07", "08", "09"]:
        if mode_c == "0":
            values.append(input[input[pos+1]])
        elif mode_c == "1":
            values.append(input[pos+1])
        elif mode_c == "2":
            values.append(input[input[pos+1]+game.rel_base])
 
        if op in ["01", "02", "05", "06", "07", "08"]:
            if mode_b == "0":
                values.append(input[input[pos+2]])
            elif mode_b == "1":
                values.append(input[pos+2])
            elif mode_b == "2":
                values.append(input[input[pos+2]+game.rel_base])
 
            if op in []:
                if mode_a == "0":
                    values.append(input[input[pos+3]])
                elif mode_a == "1":
                    values.append(input[pos+3])
                elif mode_a == "2":
                    values.append(input[input[pos+3]+game.rel_base])
 
    if op in ["01", "02", "07", "08"]:
        if mode_a == "2":
            offset = game.rel_base
 
    if op in ["03"]:
        if mode_c == "2":
            offset = game.rel_base
 
    return values, offset
 
def run_game(game, input = 0):
    while game.prog[game.ip] != 99:
        op, modes = split_instruction(game.prog[game.ip])
        values, offset = get_values(game.prog, game.ip, op, modes, game)
 
        if op == "01": # Addition
            game.prog[game.prog[game.ip+3] + offset] = values[0] + values[1]
            game.ip += 4
 
        if op == "02": # Multiplication
            game.prog[game.prog[game.ip+3] + offset] = values[0] * values[1]
            game.ip += 4
 
        if op == "03": # Read and Store input
            game.prog[game.prog[game.ip+1] + offset] = input
            game.ip += 2
 
        if op == "04": # Print Output
            game.output = values[0]
            game.ip += 2
            return game
 
        if op == "05": # Jump-if-True
            if values[0]:
                game.ip = values[1]
            else:
                game.ip += 3
 
        if op == "06": # Jump-if-False
            if not values[0]:
                game.ip = values[1]
            else:
                game.ip += 3
 
        if op == "07": # Less than
            if values[0] < values[1]:
                game.prog[game.prog[game.ip+3] + offset] = 1
            else:
                game.prog[game.prog[game.ip+3] + offset] = 0
            game.ip += 4
 
        if op == "08": # Equals
            if values[0] == values[1]:
                game.prog[game.prog[game.ip+3] + offset] = 1
            else:
                game.prog[game.prog[game.ip+3] + offset] = 0
            game.ip += 4
 
        if op == "09": # Adjust Relative Base
            game.rel_base += values[0]
            game.ip += 2
 
    game.halt = True
    return game
 
def create_program(input):
    prog = defaultdict(int)
 
    for i in range(len(input)):
        prog[i] = int(input[i])
 
    return prog
 
def get_best_dir(field, visited):
    all_dirs = [(0, 1), (0, -1), (-1, 0), (1, 0)]
 
    for dir in all_dirs:
        new_pos = (field.pos[0] + dir[0], field.pos[1] + dir[1])
        if field.grid[new_pos] != "":
            continue
 
        d = all_dirs.index(dir)+1
        return d
 
    least_visited = 1e8
    least_dir = -1
 
    for dir in all_dirs:
        new_pos = (field.pos[0] + dir[0], field.pos[1] + dir[1])
        if field.grid[new_pos] == "#":
            continue
 
        if least_visited > visited[new_pos]:
            least_dir = dir
            least_visited = visited[new_pos]
 
    d = all_dirs.index(least_dir) + 1
    return d
 
def get_map(game):
    visited = defaultdict(int)
    field = Grid(str)
    steps = 0
 
    while not game.halt and steps < 6000:
        dir = get_best_dir(field, visited)
        steps += 1
        run_game(game, dir)
 
        if game.output == 0:
            field.wallbounce(["up", "down", "left", "right"][dir-1])
 
        if game.output == 1:
            [field.up, field.down, field.left, field.right][dir-1]()
            field.set_pos(".")
 
        if game.output == 2:
            [field.up, field.down, field.left, field.right][dir-1]()
            field.set_pos("O")
 
        visited[field.pos] += 1
 
    return field
 
def find_oxygen(field):
    search = defaultdict(int)
    search[(0, 0)] = 1
    new_search = copy(search)
    top, right, bottom, left = field.get_border()
    steps = 0
 
    while True:
        steps += 1
        for y in range(bottom, top+1):
            for x in range(left, right+1):
                if search[(x, y)] == 1:
                    new_search[(x, y)] = -1
                    for dir in [(-1, 0),(0, -1),(1, 0),(0, 1)]:
                        new_pos = (x + dir[0], y + dir[1])
                        if search[new_pos] == -1:
                            continue
                        if field.grid[new_pos] == ".":
                            new_search[new_pos] = 1
                        if field.grid[new_pos] == "O":
                            return steps
 
        search = copy(new_search)
 
 
input  = open('input').read().split(",")
prog   = create_program(input)
game   = Game(prog)
field  = get_map(game)
 
print(find_oxygen(field))

2019 Day 14 Part 02

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

from collections import defaultdict
 
def produce(comp, amount, requirements, rest = None):
    if rest == None:
        rest = defaultdict(int)
 
    for prod, sources in requirements.items():
        if prod[1] == comp:
            break
 
    made = rest[prod[1]]
 
    if not (amount - made) % prod[0]:
        rest[prod[1]] = 0
        a = (amount - made) // prod[0]
    else:
        rest[prod[1]] = prod[0] - ((amount - made) % prod[0])
        a = (amount - made) // prod[0] + 1
 
    ore = 0
 
    for source in sources:
        if source[1] == "ORE":
             ore += source[0]*a
        else:
            cost = produce(source[1], source[0]*a, requirements, rest)
            ore += cost
 
    return ore
 
 
input = open('input').read().splitlines()
 
req = defaultdict(list)
 
for line in input:
    line = list(line)
    while "," in line:
        line.remove(",")
    line = "".join(line)
 
    x = line.split(" ")
    comps = (len(x) - 3) // 2
    for i in range(comps):
        req[(int(x[-2]), x[-1])].append((int(x[i*2]), x[i*2+1]))
 
available = 1000000000000
 
low = available // produce("FUEL", 1, req)
high = 2 * low
 
while high - low > 1:
    middle = (high + low) // 2
    cost = produce("FUEL", middle, req)
    if cost <= available:
        low = middle
    else:
        high = middle
 
print(low)

2019 Day 14 Part 01

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

from collections import defaultdict
 
def produce(comp, amount, requirements, rest = None):
    if rest == None:
        rest = defaultdict(int)
 
    for prod, sources in requirements.items():
        if prod[1] == comp:
            break
 
    made = rest[prod[1]]
 
    if not (amount - made) % prod[0]:
        rest[prod[1]] = 0
        a = (amount - made) // prod[0]
    else:
        rest[prod[1]] = prod[0] - ((amount - made) % prod[0])
        a = (amount - made) // prod[0] + 1
 
    ore = 0
 
    for source in sources:
        if source[1] == "ORE":
             ore += source[0]*a
        else:
            cost = produce(source[1], source[0]*a, requirements, rest)
            ore += cost
 
    return ore
 
 
input = open('input').read().splitlines()
requirements = defaultdict(list)
 
for line in input:
    parts = line.replace(",", "").split(" ")
    for i in range((len(parts) - 3) // 2):
        requirements[(int(parts[-2]), parts[-1])].append((int(parts[i*2]), parts[i*2+1]))
 
print(produce("FUEL", 1, requirements))

2019 Day 13 Part 02

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
139
140
141
142
143
144
145

from collections import defaultdict
 
class Game:
    def __init__(self, prog):
        self.prog     = prog
        self.ip       = 0
        self.output   = 0
        self.rel_base = 0
        self.halt     = False
 
def split_instruction(instruction):
    instruction = f"{instruction:05}"
    return instruction[3:], instruction[0:3]
 
def get_values(input, pos, op, modes, game):
    mode_a, mode_b, mode_c = modes
    values = []
    offset = 0
 
    if op in ["01", "02", "04", "05", "06", "07", "08", "09"]:
        if mode_c == "0":
            values.append(input[input[pos+1]])
        elif mode_c == "1":
            values.append(input[pos+1])
        elif mode_c == "2":
            values.append(input[input[pos+1]+game.rel_base])
 
        if op in ["01", "02", "05", "06", "07", "08"]:
            if mode_b == "0":
                values.append(input[input[pos+2]])
            elif mode_b == "1":
                values.append(input[pos+2])
            elif mode_b == "2":
                values.append(input[input[pos+2]+game.rel_base])
 
            if op in []:
                if mode_a == "0":
                    values.append(input[input[pos+3]])
                elif mode_a == "1":
                    values.append(input[pos+3])
                elif mode_a == "2":
                    values.append(input[input[pos+3]+game.rel_base])
 
    if op in ["01", "02", "07", "08"]:
        if mode_a == "2":
            offset = game.rel_base
 
    if op in ["03"]:
        if mode_c == "2":
            offset = game.rel_base
 
    return values, offset
 
def run_game(game, input = 0):
    while game.prog[game.ip] != 99:
        op, modes = split_instruction(game.prog[game.ip])
        values, offset = get_values(game.prog, game.ip, op, modes, game)
 
        if op == "01": # Addition
            game.prog[game.prog[game.ip+3] + offset] = values[0] + values[1]
            game.ip += 4
 
        if op == "02": # Multiplication
            game.prog[game.prog[game.ip+3] + offset] = values[0] * values[1]
            game.ip += 4
 
        if op == "03": # Read and Store input
            game.prog[game.prog[game.ip+1] + offset] = input
            game.ip += 2
 
        if op == "04": # Print Output
            game.output = values[0]
            game.ip += 2
            return game
 
        if op == "05": # Jump-if-True
            if values[0]:
                game.ip = values[1]
            else:
                game.ip += 3
 
        if op == "06": # Jump-if-False
            if not values[0]:
                game.ip = values[1]
            else:
                game.ip += 3
 
        if op == "07": # Less than
            if values[0] < values[1]:
                game.prog[game.prog[game.ip+3] + offset] = 1
            else:
                game.prog[game.prog[game.ip+3] + offset] = 0
            game.ip += 4
 
        if op == "08": # Equals
            if values[0] == values[1]:
                game.prog[game.prog[game.ip+3] + offset] = 1
            else:
                game.prog[game.prog[game.ip+3] + offset] = 0
            game.ip += 4
 
        if op == "09": # Adjust Relative Base
            game.rel_base += values[0]
            game.ip += 2
 
    game.halt = True
    return game
 
def create_program(input):
    prog = defaultdict(int)
 
    for i in range(len(input)):
        prog[i] = int(input[i])
 
    return prog
 
def get_joy(ball, paddle):
    if ball > paddle:
        return 1
    elif ball == paddle:
        return 0
    else:
        return -1
 
 
input = open('input').read().split(",")
prog = create_program(input)
prog[0] = 2
 
game = Game(prog)
ball, paddle = 0, 0
coord = defaultdict(int)
 
while not game.halt:
    for output in ["x", "y", "tile"]:
        run_game(game, get_joy(ball, paddle))
        coord[output] = game.output
    if coord["tile"] == 3:
        paddle = coord["x"]
    elif coord["tile"] == 4:
        ball = coord["x"]
    if coord["x"] == -1:
        score = coord["tile"]
 
print(score)

2019 Day 13 Part 01

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

from collections import defaultdict
 
class Game:
    def __init__(self, prog):
        self.prog     = prog
        self.ip       = 0
        self.output   = 0
        self.rel_base = 0
        self.halt     = False
 
def split_instruction(instruction):
    instruction = f"{instruction:05}"
    return instruction[3:], instruction[0:3]
 
def get_values(input, pos, op, modes, game):
    mode_a, mode_b, mode_c = modes
    values = []
    offset = 0
 
    if op in ["01", "02", "04", "05", "06", "07", "08", "09"]:
        if mode_c == "0":
            values.append(input[input[pos+1]])
        elif mode_c == "1":
            values.append(input[pos+1])
        elif mode_c == "2":
            values.append(input[input[pos+1]+game.rel_base])
 
        if op in ["01", "02", "05", "06", "07", "08"]:
            if mode_b == "0":
                values.append(input[input[pos+2]])
            elif mode_b == "1":
                values.append(input[pos+2])
            elif mode_b == "2":
                values.append(input[input[pos+2]+game.rel_base])
 
            if op in []:
                if mode_a == "0":
                    values.append(input[input[pos+3]])
                elif mode_a == "1":
                    values.append(input[pos+3])
                elif mode_a == "2":
                    values.append(input[input[pos+3]+game.rel_base])
 
    if op in ["01", "02", "07", "08"]:
        if mode_a == "2":
            offset = game.rel_base
 
    if op in ["03"]:
        if mode_c == "2":
            offset = game.rel_base
 
    return values, offset
 
def run_game(game, input = 0):
    while game.prog[game.ip] != 99:
        op, modes = split_instruction(game.prog[game.ip])
        values, offset = get_values(game.prog, game.ip, op, modes, game)
 
        if op == "01": # Addition
            game.prog[game.prog[game.ip+3] + offset] = values[0] + values[1]
            game.ip += 4
 
        if op == "02": # Multiplication
            game.prog[game.prog[game.ip+3] + offset] = values[0] * values[1]
            game.ip += 4
 
        if op == "03": # Read and Store input
            game.prog[game.prog[game.ip+1] + offset] = input
            game.ip += 2
 
        if op == "04": # Print Output
            game.output = values[0]
            game.ip += 2
            return game
 
        if op == "05": # Jump-if-True
            if values[0]:
                game.ip = values[1]
            else:
                game.ip += 3
 
        if op == "06": # Jump-if-False
            if not values[0]:
                game.ip = values[1]
            else:
                game.ip += 3
 
        if op == "07": # Less than
            if values[0] < values[1]:
                game.prog[game.prog[game.ip+3] + offset] = 1
            else:
                game.prog[game.prog[game.ip+3] + offset] = 0
            game.ip += 4
 
        if op == "08": # Equals
            if values[0] == values[1]:
                game.prog[game.prog[game.ip+3] + offset] = 1
            else:
                game.prog[game.prog[game.ip+3] + offset] = 0
            game.ip += 4
 
        if op == "09": # Adjust Relative Base
            game.rel_base += values[0]
            game.ip += 2
 
    game.halt = True
    return game
 
def create_program(input):
    prog = defaultdict(int)
 
    for i in range(len(input)):
        prog[i] = int(input[i])
 
    return prog
 
 
input  = open('input').read().split(",")
prog   = create_program(input)
game   = Game(prog)
result = 0
 
while not game.halt:
    for i in range(3):
        run_game(game)
    if game.output == 2:
        result += 1
 
    print(result)

2019 Day 12 Part 02

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

from re import findall
 
def get_prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors
 
def calculate_lcm(steps):
    primes_per_dimension = [get_prime_factors(step) for step in steps]
    all_primes = set([prime for primes in primes_per_dimension for prime in primes])
 
    lcm = 1    
    for prime in all_primes:
        amount = max(primes_per_dimension[dim].count(prime) for dim in range(3))
        lcm *= prime**amount
    return lcm
 
def apply_gravity(moons_dim, velocities_dim):
    for m_1 in range(3):
        for m_2 in range(m_1+1, 4):
            if moons_dim[m_1] > moons_dim[m_2]:
                velocities_dim[m_1] -= 1
                velocities_dim[m_2] += 1
            elif moons_dim[m_1] < moons_dim[m_2]:
                velocities_dim[m_1] += 1
                velocities_dim[m_2] -= 1
 
def apply_velocity(moons_dim, velocities_dim):
    for m in range(4):
        moons_dim[m] += velocities_dim[m]
 
def matches_start_state(moons, velocities, moons_dim, velocities_dim, dim):
    for i in range(4):
        if moons[i][dim] != moons_dim[i] or \
           velocities[i][dim] != velocities_dim[i]:
            return False
    return True
 
 
lines = open('input').readlines()
lines = [findall(r'-?\d+', line) for line in lines]
moons      = [list(map(int, line)) for line in lines]
velocities = [[0 for x in range(3)] for y in range(4)]
 
steps = [0, 0, 0]
 
for dim in range(3):
    moons_dim = [moon[dim] for moon in moons]
    velocities_dim = [velocity[dim] for velocity in velocities]
 
    while True:
        apply_gravity(moons_dim, velocities_dim)
        apply_velocity(moons_dim, velocities_dim)
 
        steps[dim] += 1
 
        if matches_start_state(moons, velocities, moons_dim, velocities_dim, dim):
            break
 
print(calculate_lcm(steps))

2019 Day 12 Part 01

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

from re import findall
 
def apply_gravity(moons, velocities):
    for m_1 in range(3):
        for m_2 in range(m_1+1, 4):
            for dim in range(3):
                if moons[m_1][dim] > moons[m_2][dim]:
                    velocities[m_1][dim] -= 1
                    velocities[m_2][dim] += 1
                elif moons[m_1][dim] < moons[m_2][dim]:
                    velocities[m_1][dim] += 1
                    velocities[m_2][dim] -= 1
 
def apply_velocity(moons, velocities):
    for m in range(4):
        for dim in range(3):
            moons[m][dim] += velocities[m][dim]
 
def calculate_energy(moons, velocities):
    e = 0
    for i in range(4):
        pot = sum([abs(moon) for moon in moons[i]])
        kin = sum([abs(velocity) for velocity in velocities[i]])
        e += pot * kin
    return e
 
 
lines = open('input').readlines()
lines = [findall(r'-?\d+', line) for line in lines]
moons      = [list(map(int, line)) for line in lines]
velocities = [[0 for x in range(3)] for y in range(4)]
 
for _ in range(1000):
    apply_gravity(moons, velocities)
    apply_velocity(moons, velocities)
 
print(calculate_energy(moons, velocities))

2019 Day 11 Part 02

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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173

from collections import defaultdict
 
class Painter:
    def __init__(self, prog):
        self.prog     = prog
        self.ip       = 0
        self.output   = 0
        self.rel_base = 0
        self.halt     = False
 
def split_instruction(instruction):
    instruction = f"{instruction:05}"
    return instruction[3:], instruction[0:3]
 
def get_values(input, pos, op, modes, painter):
    mode_a, mode_b, mode_c = modes
    values = []
    offset = 0
 
    if op in ["01", "02", "04", "05", "06", "07", "08", "09"]:
        if mode_c == "0":
            values.append(input[input[pos+1]])
        elif mode_c == "1":
            values.append(input[pos+1])
        elif mode_c == "2":
            values.append(input[input[pos+1]+painter.rel_base])
 
        if op in ["01", "02", "05", "06", "07", "08"]:
            if mode_b == "0":
                values.append(input[input[pos+2]])
            elif mode_b == "1":
                values.append(input[pos+2])
            elif mode_b == "2":
                values.append(input[input[pos+2]+painter.rel_base])
 
            if op in []:
                if mode_a == "0":
                    values.append(input[input[pos+3]])
                elif mode_a == "1":
                    values.append(input[pos+3])
                elif mode_a == "2":
                    values.append(input[input[pos+3]+painter.rel_base])
 
    if op in ["01", "02", "07", "08"]:
        if mode_a == "2":
            offset = painter.rel_base
 
    if op in ["03"]:
        if mode_c == "2":
            offset = painter.rel_base
 
    return values, offset
 
def run_booster(input, painter):
    while painter.prog[painter.ip] != 99:
        op, modes = split_instruction(painter.prog[painter.ip])
        values, offset = get_values(painter.prog, painter.ip, op, modes, painter)
 
        if op == "01": # Addition
            painter.prog[painter.prog[painter.ip+3] + offset] = values[0] + values[1]
            painter.ip += 4
 
        if op == "02": # Multiplication
            painter.prog[painter.prog[painter.ip+3] + offset] = values[0] * values[1]
            painter.ip += 4
 
        if op == "03": # Read and Store input
            painter.prog[painter.prog[painter.ip+1] + offset] = input
            painter.ip += 2
 
        if op == "04": # Print Output
            painter.output = values[0]
            #print(painter.output)
            painter.ip += 2
            return painter
 
        if op == "05": # Jump-if-True
            if values[0]:
                painter.ip = values[1]
            else:
                painter.ip += 3
 
        if op == "06": # Jump-if-False
            if not values[0]:
                painter.ip = values[1]
            else:
                painter.ip += 3
 
        if op == "07": # Less than
            if values[0] < values[1]:
                painter.prog[painter.prog[painter.ip+3] + offset] = 1
            else:
                painter.prog[painter.prog[painter.ip+3] + offset] = 0
            painter.ip += 4
 
        if op == "08": # Equals
            if values[0] == values[1]:
                painter.prog[painter.prog[painter.ip+3] + offset] = 1
            else:
                painter.prog[painter.prog[painter.ip+3] + offset] = 0
            painter.ip += 4
 
        if op == "09": # Adjust Relative Base
            painter.rel_base += values[0]
            painter.ip += 2
 
    painter.halt = True
    return painter
 
def create_program(input):
    prog = defaultdict(int)
 
    for i in range(len(input)):
        prog[i] = int(input[i])
 
    return prog
 
def turn_and_move(pos, dir, turn):
    if turn == 0:
        dir = (dir - 1) % 4
    else:
        dir = (dir + 1) % 4
 
    if dir == 0: # up
        pos = (pos[0], pos[1] + 1)
    elif dir == 1: # right
        pos = (pos[0]+1, pos[1])
    elif dir == 2: # down
        pos = (pos[0], pos[1] - 1)
    elif dir == 3: # left
        pos = (pos[0] - 1, pos[1])
 
    return pos, dir
 
def draw_panel(panel):
    top, right, bottom, left = -1e8, -1e8, 1e8, 1e8
    for position, value in panel.items():
        if value:
            top     = max(top, position[1])
            right   = max(right, position[0])
            bottom  = min(bottom, position[1])
            left    = min(left, position[0])
 
    for y in range(top, bottom-1, -1):
        for x in range(left, right+1):
            if panel[(x, y)] == 1:
                print("#", end="")
            if panel[(x, y)] == 0:
                print(" ", end="")
        print()
 
 
input = open('input').read().split(",")
prog = create_program(input)
 
panel = defaultdict(int)
painter = Painter(prog)
 
dir = 0
pos = (0, 0)
panel[(0, 0)] = 1
 
while not painter.halt:
    painter = run_booster(panel[pos], painter)
    color = painter.output
    painter = run_booster(panel[pos], painter)
    turn = painter.output
 
    panel[pos] = color
 
    pos, dir = turn_and_move(pos, dir, turn)
 
draw_panel(panel)

2019 Day 11 Part 01

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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157

from collections import defaultdict
 
class Painter:
    def __init__(self, prog):
        self.prog     = prog
        self.ip       = 0
        self.output   = 0
        self.rel_base = 0
        self.halt     = False
 
def split_instruction(instruction):
    instruction = f"{instruction:05}"
    return instruction[3:], instruction[0:3]
 
def get_values(input, pos, op, modes, painter):
    mode_a, mode_b, mode_c = modes
    values = []
    offset = 0
 
    if op in ["01", "02", "04", "05", "06", "07", "08", "09"]:
        if mode_c == "0":
            values.append(input[input[pos+1]])
        elif mode_c == "1":
            values.append(input[pos+1])
        elif mode_c == "2":
            values.append(input[input[pos+1]+painter.rel_base])
 
        if op in ["01", "02", "05", "06", "07", "08"]:
            if mode_b == "0":
                values.append(input[input[pos+2]])
            elif mode_b == "1":
                values.append(input[pos+2])
            elif mode_b == "2":
                values.append(input[input[pos+2]+painter.rel_base])
 
            if op in []:
                if mode_a == "0":
                    values.append(input[input[pos+3]])
                elif mode_a == "1":
                    values.append(input[pos+3])
                elif mode_a == "2":
                    values.append(input[input[pos+3]+painter.rel_base])
 
    if op in ["01", "02", "07", "08"]:
        if mode_a == "2":
            offset = painter.rel_base
 
    if op in ["03"]:
        if mode_c == "2":
            offset = painter.rel_base
 
    return values, offset
 
def run_booster(input, painter):
    while painter.prog[painter.ip] != 99:
        op, modes = split_instruction(painter.prog[painter.ip])
        values, offset = get_values(painter.prog, painter.ip, op, modes, painter)
 
        if op == "01": # Addition
            painter.prog[painter.prog[painter.ip+3] + offset] = values[0] + values[1]
            painter.ip += 4
 
        if op == "02": # Multiplication
            painter.prog[painter.prog[painter.ip+3] + offset] = values[0] * values[1]
            painter.ip += 4
 
        if op == "03": # Read and Store input
            painter.prog[painter.prog[painter.ip+1] + offset] = input
            painter.ip += 2
 
        if op == "04": # Print Output
            painter.output = values[0]
            #print(painter.output)
            painter.ip += 2
            return painter
 
        if op == "05": # Jump-if-True
            if values[0]:
                painter.ip = values[1]
            else:
                painter.ip += 3
 
        if op == "06": # Jump-if-False
            if not values[0]:
                painter.ip = values[1]
            else:
                painter.ip += 3
 
        if op == "07": # Less than
            if values[0] < values[1]:
                painter.prog[painter.prog[painter.ip+3] + offset] = 1
            else:
                painter.prog[painter.prog[painter.ip+3] + offset] = 0
            painter.ip += 4
 
        if op == "08": # Equals
            if values[0] == values[1]:
                painter.prog[painter.prog[painter.ip+3] + offset] = 1
            else:
                painter.prog[painter.prog[painter.ip+3] + offset] = 0
            painter.ip += 4
 
        if op == "09": # Adjust Relative Base
            painter.rel_base += values[0]
            painter.ip += 2
 
    painter.halt = True
    return painter
 
def create_program(input):
    prog = defaultdict(int)
 
    for i in range(len(input)):
        prog[i] = int(input[i])
 
    return prog
 
def turn_and_move(pos, dir, turn):
    if turn == 0:
        dir = (dir - 1) % 4
    else:
        dir = (dir + 1) % 4
 
    if dir == 0: # up
        pos = (pos[0], pos[1] + 1)
    elif dir == 1: # right
        pos = (pos[0]+1, pos[1])
    elif dir == 2: # down
        pos = (pos[0], pos[1] - 1)
    elif dir == 3: # left
        pos = (pos[0] - 1, pos[1])
 
    return pos, dir
 
 
input = open('input').read().split(",")
prog = create_program(input)
 
panel = defaultdict(int)
painted = defaultdict(int)
painter = Painter(prog)
 
dir = 0
pos = (0, 0)
 
while not painter.halt:
    painter = run_booster(panel[pos], painter)
    color = painter.output
    painter = run_booster(panel[pos], painter)
    turn = painter.output
 
    painted[pos] = 1
    panel[pos] = color
 
    pos, dir = turn_and_move(pos, dir, turn)
 
    print(len(painted))

2019 Day 10 Part 02

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

from math import atan, degrees
from collections import defaultdict
 
def greatest_common_divisor(x, y):
    if not x:
        return abs(y)
    if not y:
        return abs(x)
 
    while y:
        x, y = y, x % y
    return abs(x)        
 
# Get all directions where an asteroid can be seen from station
def get_directions(station, asteroids):
    directions = set()
    for asteroid in asteroids:
        if asteroid == station:
            continue
 
        vec = (asteroid[0] - station[0], asteroid[1] - station[1])
        gcd = greatest_common_divisor(vec[0], vec[1])
        vec = (vec[0] // gcd, vec[1] // gcd)
 
        directions.add(vec)
 
    return directions
 
def get_best_station(asteroids):
    asteroids_in_los = [len(get_directions(station, asteroids)) for station in asteroids]
    station_id = asteroids_in_los.index(max(asteroids_in_los))
    return asteroids[station_id]
 
def calc_angle(vector):
    if vector[1] == 0:
        return 90
    return degrees(atan(vector[0]/vector[1]))
 
def split_quadrants(directions):
    quadrants = []
    quadrants.append([x for x in directions if x[0] >= 0 and x[1] < 0])
    quadrants.append([x for x in directions if x[0] > 0  and x[1] >= 0])
    quadrants.append([x for x in directions if x[0] <= 0 and x[1] > 0])
    quadrants.append([x for x in directions if x[0] < 0  and x[1] <= 0])
    return quadrants
 
def shoot(quadrants, station, asteroids, size_x, size_y):
    target_amount = len(asteroids) - 200
    while True:
        for quadrant in quadrants:
            for direction in quadrant:
                multi = 1
                while True:
                    coord = (station[0] + direction[0] * multi, station[1] + direction[1] * multi)
 
                    if coord[0] < 0 or coord[0] > size_x or \
                       coord[1] < 0 or coord[1] > size_y:
                        break
 
                    if coord in asteroids:
                        asteroids.remove(coord)
 
                        if len(asteroids) == target_amount:
                            return coord[0]*100 + coord[1]
                        break
                    multi += 1
 
 
input = open('input').read().splitlines()
size_x, size_y = len(input[0]), len(input)
 
asteroids = [(x, y) for y in range(size_y) for x in range(size_x) if input[y][x] == "#"]
station = get_best_station(asteroids)
 
directions = list(get_directions(station, asteroids))
directions.sort(key = lambda direction:calc_angle(direction), reverse = True)
 
quadrants = split_quadrants(directions)
 
print(shoot(quadrants, station, asteroids, size_x, size_y))

2019 Day 10 Part 01

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

def greatest_common_divisor(x, y):
    if not x:
        return abs(y)
    if not y:
        return abs(x)
 
    while y:
        x, y = y, x % y
    return abs(x)        
 
# Get all directions where an asteroid can be seen from station
def get_directions(station, asteroids):
    directions = set()
    for asteroid in asteroids:
        if asteroid == station:
            continue
 
        vec = (asteroid[0] - station[0], asteroid[1] - station[1])
        gcd = greatest_common_divisor(vec[0], vec[1])
        vec = (vec[0] // gcd, vec[1] // gcd)
 
        directions.add(vec)
 
    return directions
 
 
input = open('input').read().splitlines()
size_x, size_y = len(input[0]), len(input)
 
asteroids = [(x, y) for y in range(size_y) for x in range(size_x) if input[y][x] == "#"]
 
print(max([len(get_directions(station, asteroids)) for station in asteroids]))

2019 Day 09 Part 01 + 02

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

from collections import defaultdict
 
class Booster:
    def __init__(self, prog):
        self.prog     = prog
        self.ip       = 0
        self.output   = 0
        self.rel_base = 0
 
def split_instruction(instruction):
    instruction = f"{instruction:05}"
    return instruction[3:], instruction[0:3]
 
def get_values(input, pos, op, modes, booster):
    mode_a, mode_b, mode_c = modes
    values = []
    offset = 0
 
    if op in ["01", "02", "04", "05", "06", "07", "08", "09"]:
        if mode_c == "0":
            values.append(input[input[pos+1]])
        elif mode_c == "1":
            values.append(input[pos+1])
        elif mode_c == "2":
            values.append(input[input[pos+1]+booster.rel_base])
 
        if op in ["01", "02", "05", "06", "07", "08"]:
            if mode_b == "0":
                values.append(input[input[pos+2]])
            elif mode_b == "1":
                values.append(input[pos+2])
            elif mode_b == "2":
                values.append(input[input[pos+2]+booster.rel_base])
 
            if op in []:
                if mode_a == "0":
                    values.append(input[input[pos+3]])
                elif mode_a == "1":
                    values.append(input[pos+3])
                elif mode_a == "2":
                    values.append(input[input[pos+3]+booster.rel_base])
 
    if op in ["01", "02", "07", "08"]:
        if mode_a == "2":
            offset = booster.rel_base
 
    if op in ["03"]:
        if mode_c == "2":
            offset = booster.rel_base
 
    return values, offset
 
def run_booster(input, booster):
    while booster.prog[booster.ip] != 99:
        op, modes = split_instruction(booster.prog[booster.ip])
        values, offset = get_values(booster.prog, booster.ip, op, modes, booster)
 
        if op == "01": # Addition
            booster.prog[booster.prog[booster.ip+3] + offset] = values[0] + values[1]
            booster.ip += 4
 
        if op == "02": # Multiplication
            booster.prog[booster.prog[booster.ip+3] + offset] = values[0] * values[1]
            booster.ip += 4
 
        if op == "03": # Read and Store input
            booster.prog[booster.prog[booster.ip+1] + offset] = input
            booster.ip += 2
 
        if op == "04": # Print Output
            booster.output = values[0]
            print(booster.output)
            booster.ip += 2
 
        if op == "05": # Jump-if-True
            if values[0]:
                booster.ip = values[1]
            else:
                booster.ip += 3
 
        if op == "06": # Jump-if-False
            if not values[0]:
                booster.ip = values[1]
            else:
                booster.ip += 3
 
        if op == "07": # Less than
            if values[0] < values[1]:
                booster.prog[booster.prog[booster.ip+3] + offset] = 1
            else:
                booster.prog[booster.prog[booster.ip+3] + offset] = 0
            booster.ip += 4
 
        if op == "08": # Equals
            if values[0] == values[1]:
                booster.prog[booster.prog[booster.ip+3] + offset] = 1
            else:
                booster.prog[booster.prog[booster.ip+3] + offset] = 0
            booster.ip += 4
 
        if op == "09": # Adjust Relative Base
            booster.rel_base += values[0]
            booster.ip += 2
 
    return booster
 
def create_program(input):
    prog = defaultdict(int)
 
    for i in range(len(input)):
        prog[i] = int(input[i])
 
    return prog
 
 
input   = open('input').read().split(",")
 
prog = create_program(input)
booster = Booster(prog)
booster = run_booster(1, booster)
print(booster.output)
 
prog = create_program(input)
booster = Booster(prog)
booster = run_booster(2, booster)
print(booster.output)

2019 Day 08 Part 02

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

from collections import defaultdict
 
def extract_layers(raw, size):
    layers = defaultdict(list)
    layer = -1
 
    for i in range(len(raw)):
        if not i % size:
            layer += 1
        layers[layer].append(raw[i])
 
    return layers
 
def print_image(layers):
    for y in range(6):
        for x in range(25):
            pos = x + y * 25
            for lay in range(100):
                if layers[lay][pos] == 2:
                    continue
                if layers[lay][pos] == 1:
                    print("#", end="")
                else:
                    print(" ", end="")
                break
        print()
 
 
input   = open('input').read().splitlines()
input   = [int(x) for x in input[0]]
 
size    = 25 * 6
layers  = extract_layers(input, size)
 
print_image(layers)

2019 Day 08 Part 01

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

from collections import defaultdict
 
def extract_layers(raw, size):
    layers = defaultdict(list)
    layer = -1
 
    for i in range(len(raw)):
        if not i % size:
            layer += 1
        layers[layer].append(raw[i])
 
    return layers
 
 
input   = open('input').read().splitlines()
input   = [int(x) for x in input[0]]
 
size    = 25 * 6
layers  = extract_layers(input, size)
 
zero_counts  = [pixels.count(0) for pixels in layers.values()]
result_layer = zero_counts.index(min(zero_counts))
 
print(layers[result_layer].count(1) * layers[result_layer].count(2))

2019 Day 07 Part 02

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

from itertools import permutations
 
class Amp:
    def __init__(self, prog):
        self.prog           = prog[:]
        self.ip             = 0
        self.output         = 0
        self.input_counter  = 0
        self.halt           = False
 
def split_instruction(instruction):
    instruction = f"{instruction:05}"
    return instruction[3:], instruction[0:3]
 
def get_values(input, pos, op, modes):
    mode_a, mode_b, mode_c = modes
    values = []
 
    if op in ["01", "02", "04", "05", "06", "07", "08"]:
        if mode_c == "0":
            values.append(input[input[pos+1]])
        else:
            values.append(input[pos+1])
 
        if op in ["01", "02", "05", "06", "07", "08"]:
            if mode_b == "0":
                values.append(input[input[pos+2]])
            else:
                values.append(input[pos+2])
 
            if op in []:
                if mode_a == "0":
                    values.append(input[input[pos+3]])
                else:
                    values.append(input[pos+3])
 
    return values
 
def run_amp(phase, input, amp):
    while amp.prog[amp.ip] != 99:
        op, modes = split_instruction(amp.prog[amp.ip])
        values = get_values(amp.prog, amp.ip, op, modes)
 
        if op == "01": # Addition
            amp.prog[amp.prog[amp.ip+3]] = values[0] + values[1]
            amp.ip += 4
 
        if op == "02": # Multiplication
            amp.prog[amp.prog[amp.ip+3]] = values[0] * values[1]
            amp.ip += 4
 
        if op == "03": # Read and Store input
            if not amp.input_counter:
                amp.prog[amp.prog[amp.ip+1]] = phase
            else:
                amp.prog[amp.prog[amp.ip+1]] = input
 
            amp.input_counter += 1
            amp.ip += 2
 
        if op == "04": # Print Output
            amp.output = values[0]
            amp.ip += 2
            return amp
 
        if op == "05": # Jump-if-True
            if values[0]:
                amp.ip = values[1]
            else:
                amp.ip += 3
 
        if op == "06": # Jump-if-False
            if not values[0]:
                amp.ip = values[1]
            else:
                amp.ip += 3
 
        if op == "07": # Less than
            if values[0] < values[1]:
                amp.prog[amp.prog[amp.ip+3]] = 1
            else:
                amp.prog[amp.prog[amp.ip+3]] = 0
            amp.ip += 4
 
        if op == "08": # Equals
            if values[0] == values[1]:
                amp.prog[amp.prog[amp.ip+3]] = 1
            else:
                amp.prog[amp.prog[amp.ip+3]] = 0
            amp.ip += 4
 
    amp.halt = True
    return amp
 
 
prog = open('input').readline().split(",")
prog = [int(x) for x in prog]
max_thrust = 0
 
for phases in permutations(range(5, 10), 5):
    amps = [Amp(prog) for i in range(5)]
    active = 0
 
    while not amps[4].halt:
        amps[active] = run_amp(phases[active], amps[active-1].output, amps[active])
        active       = (active + 1) % 5
 
    max_thrust = max(max_thrust, amps[4].output)
print(max_thrust)

2019 Day 07 Part 01

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

from itertools import permutations
 
def split_instruction(instruction):
    instruction = f"{instruction:05}"
    return instruction[3:], instruction[0:3]
 
def get_values(input, pos, op, modes):
    mode_a, mode_b, mode_c = modes
    values = []
 
    if op in ["01", "02", "04", "05", "06", "07", "08"]:
        if mode_c == "0":
            values.append(input[input[pos+1]])
        else:
            values.append(input[pos+1])
 
        if op in ["01", "02", "05", "06", "07", "08"]:
            if mode_b == "0":
                values.append(input[input[pos+2]])
            else:
                values.append(input[pos+2])
 
            if op in []:
                if mode_a == "0":
                    values.append(input[input[pos+3]])
                else:
                    values.append(input[pos+3])
 
    return values
 
def run_amp(phase, input, prog):
    input_counter = 0
    ip = 0
 
    while prog[ip] != 99:
        op, modes = split_instruction(prog[ip])
        values = get_values(prog, ip, op, modes)
 
        if op == "01": # Addition
            prog[prog[ip+3]] = values[0] + values[1]
            ip += 4
 
        if op == "02": # Multiplication
            prog[prog[ip+3]] = values[0] * values[1]
            ip += 4
 
        if op == "03": # Read and Store prog
            if not input_counter:
                prog[prog[ip+1]] = phase
            else:
                prog[prog[ip+1]] = input
            input_counter += 1
            ip += 2
 
        if op == "04": # Print Output
            output = values[0]
            ip += 2
 
        if op == "05": # Jump-if-True
            if values[0]:
                ip = values[1]
            else:
                ip += 3
 
        if op == "06": # Jump-if-False
            if not values[0]:
                ip = values[1]
            else:
                ip += 3
 
        if op == "07": # Less than
            if values[0] < values[1]:
                prog[prog[ip+3]] = 1
            else:
                prog[prog[ip+3]] = 0
            ip += 4
 
        if op == "08": # Equals
            if values[0] == values[1]:
                prog[prog[ip+3]] = 1
            else:
                prog[prog[ip+3]] = 0
            ip += 4
    return output
 
 
prog = open('input').readline().split(",")
prog = [int(x) for x in prog]
 
max_thrust = 0
 
for phases in permutations(range(5), 5):
    output = 0
 
    for phase in phases:
        output = run_amp(phase, output, prog)
    max_thrust = max(max_thrust, output)
 
print(max_thrust)

2019 Day 06 Part 02

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

def get_planet_position(orbits, planet):
    pos = 0
    while planet in orbits.keys():
        planet = orbits[planet]
        pos += 1
    return pos  
 
def get_planets(orbits, positions, planet):
    planets = []
 
    while planet in orbits.keys():
        planet = orbits[planet]
        planets.append(planet)
 
    return planets
 
def get_all_planets(input):
    return set(planet for line in input for planet in line.split(")"))
 
def get_all_positions(all_planets, orbits):
    positions = {}
 
    for planet in all_planets:
        positions[planet] = get_planet_position(orbits, planet)
 
    return positions
 
def generate_orbit_dict(input):
    orbits = dict()
 
    for line in input:
        planets = line.split(")")
        orbits[planets[1]] = planets[0]
 
    return orbits
 
 
input = open('input').read().splitlines()
 
orbits      = generate_orbit_dict(input)
all_planets = get_all_planets(input)
positions   = get_all_positions(all_planets, orbits)
 
san = get_planets(orbits, positions, "SAN")
you = get_planets(orbits, positions, "YOU")
 
maximum = max(positions[planet] for planet in set(san).intersection(set(you)))
 
print(positions["SAN"] + positions["YOU"] - 2 * maximum - 2)

2019 Day 06 Part 01

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

def get_pos(orbits, planet):
    pos = 0
    while planet in orbits.keys():
        planet = orbits[planet]
        pos += 1
    return pos 
 
def get_all_planets(input):
    return set(planet for line in input for planet in line.split(")"))
 
def generate_orbit_dict(input):
    orbits = {}
 
    for line in input:
        planets = line.split(")")
        orbits[planets[1]] = planets[0]
 
    return orbits
 
input = open('input').read().splitlines()
 
orbits      = generate_orbit_dict(input)
all_planets = get_all_planets(input)
 
print(sum(get_pos(orbits, k) for k in all_planets))

2019 Day 05 Part 02

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

def split_instruction(instruction):
    instruction = f"{instruction:05}"
    return instruction[3:], instruction[0:3]
 
def get_values(input, pos, op, modes):
    mode_a, mode_b, mode_c = modes
    values = []
 
    if op in ["01", "02", "04", "05", "06", "07", "08"]:
        if mode_c == "0":
            values.append(input[input[pos+1]])
        else:
            values.append(input[pos+1])
 
        if op in ["01", "02", "05", "06", "07", "08"]:
            if mode_b == "0":
                values.append(input[input[pos+2]])
            else:
                values.append(input[pos+2])
 
            if op in []:
                if mode_a == "0":
                    values.append(input[input[pos+3]])
                else:
                    values.append(input[pos+3])
 
    return values
 
 
prog = open('input').readline().split(",")
prog = [int(x) for x in prog]
 
ip   = 0
input = 5
 
while prog[ip] != 99:
    op, modes = split_instruction(prog[ip])
    values = get_values(prog, ip, op, modes)
 
    if op == "01": # Addition
        prog[prog[ip+3]] = values[0] + values[1]
        ip += 4
 
    if op == "02": # Multiplication
        prog[prog[ip+3]] = values[0] * values[1]
        ip += 4
 
    if op == "03": # Read and Store prog
        prog[prog[ip+1]] = input
        ip += 2
 
    if op == "04": # Print Output
        print(values[0])
        ip += 2
 
    if op == "05": # Jump-if-True
        if values[0]:
            ip = values[1]
        else:
            ip += 3
 
    if op == "06": # Jump-if-False
        if not values[0]:
            ip = values[1]
        else:
            ip += 3
 
    if op == "07": # Less than
        if values[0] < values[1]:
            prog[prog[ip+3]] = 1
        else:
            prog[prog[ip+3]] = 0
        ip += 4
 
    if op == "08": # Equals
        if values[0] == values[1]:
            prog[prog[ip+3]] = 1
        else:
            prog[prog[ip+3]] = 0
        ip += 4

2019 Day 05 Part 01

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

def split_instruction(instruction):
    instruction = f"{instruction:05}"
    return instruction[3:], instruction[0:3]
 
def get_values(input, pos, op, modes):
    mode_a, mode_b, mode_c = modes
    values = []
 
    if op in ["01", "02", "04"]:
        if mode_c == "0":
            values.append(input[input[pos+1]])
        else:
            values.append(input[pos+1])
 
        if op in ["01", "02"]:
            if mode_b == "0":
                values.append(input[input[pos+2]])
            else:
                values.append(input[pos+2])
 
            if op in []:
                if mode_a == "0":
                    values.append(input[input[pos+3]])
                else:
                    values.append(input[pos+3])
 
    return values
 
 
prog = open('input').readline().split(",")
prog = [int(x) for x in prog]
 
ip   = 0
input = 1
 
while prog[ip] != 99:
    op, modes = split_instruction(prog[ip])
    values = get_values(prog, ip, op, modes)
 
    if op == "01": # Addition
        prog[prog[ip+3]] = values[0] + values[1]
        ip += 4
 
    if op == "02": # Multiplication
        prog[prog[ip+3]] = values[0] * values[1]
        ip += 4
 
    if op == "03": # Read and Store prog
        prog[prog[ip+1]] = input
        ip += 2
 
    if op == "04": # Print Output
        print(values[0])
        ip += 2

2019 Day 04 Part 02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

def increases(num):
    num = list(str(num))
 
    if num == sorted(num):
        return True
    return False
 
def has_double(num):
    num = list(str(num))
 
    for i in range(5):
        if num[i] == num[i+1] and \
          (i == 0 or num[i] != num[i-1]) and \
          (i == 4 or num[i] != num[i+2]):
            return True
    return False
 
input = open('input').readlines()
start, end = [int(num) for num in input[0].split("-")]
print(sum(increases(num) and has_double(num) for num in range(start, end+1)))

2019 Day 04 Part 01

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def increases(num):
    num = list(str(num))
 
    if num == sorted(num):
        return True
    return False
 
def all_digits_unique(num):
    num = str(num)
    return len(num) == len(set(num))
 
input = open('input').readlines()
start, end = [int(num) for num in input[0].split("-")]
print(sum(increases(num) and not all_digits_unique(num) for num in range(start, end+1)))

2019 Day 03 Part 02

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

from collections import defaultdict
 
def get_wire_positions(wire):
    x, y = 0, 0   
    positions = set()
 
    for i in range(len(wire)):
        for _ in range(int(wire[i][1:])):
            direction = wire[i][0]
 
            if   direction == "R":
                x +=1
            elif direction == "L":
                x -=1
            elif direction == "D":
                y +=1
            elif direction == "U":
                y -=1
 
            positions.add((x, y))
 
    return positions
 
def get_distance_for_crossings(wire, crossings):
    crossing = defaultdict(int)
    distance = 0
    x, y = 0, 0
 
    for i in range(len(wire)):
        for _ in range(int(wire[i][1:])):
            direction = wire[i][0]
 
            if   direction == "R":
                x +=1
            elif direction == "L":
                x -=1
            elif direction == "D":
                y +=1
            elif direction == "U":
                y -=1
 
            distance += 1
 
            if (x, y) in crossings:
                crossing[(x, y)] = distance
 
    return crossing
 
input = open('input').readlines()
wire_1 = input[0].split(",")
wire_2 = input[1].split(",")
 
positions_1 = get_wire_positions(wire_1)
positions_2 = get_wire_positions(wire_2)
 
crossings = positions_1.intersection(positions_2)
 
crossing_distance_1 = get_distance_for_crossings(wire_1, crossings)
crossing_distance_2 = get_distance_for_crossings(wire_2, crossings)
 
print(min(crossing_distance_1[crossing] + crossing_distance_2[crossing] for crossing in crossings))

2019 Day 03 Part 01

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

def manhattan(pos):
    return abs(pos[0]) + abs(pos[1])
 
def get_wire_positions(wire):
    x, y = 0, 0   
    positions = set()
 
    for i in range(len(wire)):
        for _ in range(int(wire[i][1:])):
            direction = wire[i][0]
 
            if   direction == "R":
                x +=1
            elif direction == "L":
                x -=1
            elif direction == "D":
                y +=1
            elif direction == "U":
                y -=1
 
            positions.add((x, y))
 
    return positions
 
input = open('input').readlines()
wire_1 = input[0].split(",")
wire_2 = input[1].split(",")
 
positions_1 = get_wire_positions(wire_1)
positions_2 = get_wire_positions(wire_2)
 
crossings = positions_1.intersection(positions_2)
 
print(min(manhattan(pos) for pos in crossings))

2019 Day 02 Part 02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

input       = open('input').read().split(",")
input_store = [int(x) for x in input]
 
for noun in range(100):
    for verb in range(100):
        input = input_store[:]
        pos = 0
        input[1] = noun
        input[2] = verb
 
        while input[pos] != 99:
            if input[pos] == 1:
                input[input[pos+3]] = input[input[pos+1]] + input[input[pos+2]]
 
            if input[pos] == 2:
                input[input[pos+3]] = input[input[pos+1]] * input[input[pos+2]]
 
            pos += 4
 
        if input[0] == 19690720:
            print(100 * noun + verb)

2019 Day 02 Part 01

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

data = open('input').read().split(",")
data = [int(x) for x in data]
 
data[1] = 12
data[2] = 2
 
def calc(idx):
    if data[idx] == 1:
        data[data[idx+3]] = data[data[idx+1]] + data[data[idx+2]]
    elif data[idx] == 2:
            data[data[idx+3]] = data[data[idx+1]] * data[data[idx+2]]
    elif data[idx] == 99:
        print(data[0])
        exit()
    else:
         return -1
 
for idx in range (0, len(data), 4):
    calc(idx)

2019 Day 01 Part 02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

lines=open('input').read().splitlines()
lines = [int(line) for line in lines]
 
def calc_fuel(mass):
    fuel = int(int(mass) / 3) - 2
    if fuel < 0:
        fuel = 0
    return fuel
 
fuels = []
for line in lines:
    while line > 0:
        line = calc_fuel(line)
        fuels.append(line)
print(sum(fuels))

2019 Day 01 Part 02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

lines=open('input').read().splitlines()
 
def calc_fuel(mass):
    fuel = int(int(mass) / 3) - 2
    if fuel < 0:
        fuel = 0
    return fuel
 
fuels = []
for line in lines:
    fuel = calc_fuel(line)
    fuels.append(fuel)
    while fuel > 0:
        fuel = calc_fuel(fuel)
        fuels.append(fuel)
print(sum(fuels))

2019 Day 01 Part 01

1
2
3
4
5
6

lines=open('input').read().splitlines()
fuels = []
for line in lines:
    fuel = int(int(line) / 3) - 2
    fuels.append(fuel)
print(sum(fuels))