AoC 2024 Advent of Code (Python)
By telleropnul, December 1, 2024
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: adventofcode2024inputs.zip
2024 Day 25 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
| locks, keys = [], []
matrix_list = open("input").read().strip().split('\n\n')
for matrix in matrix_list:
matrix = [list(row) for row in matrix.split("\n")]
if all([cell == "#" for cell in matrix[0]]):
locks.append(matrix)
elif all([cell == "#" for cell in matrix[-1]]):
keys.append(matrix)
input = locks, keys
def get_cols(matrix):
cols = [-1] * len(matrix[0])
for row in matrix:
for j, cell in enumerate(row):
if cell == "#":
cols[j] += 1
return cols
def is_match(a, b):
combined = [aa + bb for aa, bb in zip(a, b)]
return all([c <= 5 for c in combined])
def p1(input):
locks, keys = input
ans = 0
for lock in locks:
l = get_cols(lock)
for key in keys:
k = get_cols(key)
if is_match(l, k):
ans += 1
return ans
print(p1(input)) |
locks, keys = [], []
matrix_list = open("input").read().strip().split('\n\n')
for matrix in matrix_list:
matrix = [list(row) for row in matrix.split("\n")]
if all([cell == "#" for cell in matrix[0]]):
locks.append(matrix)
elif all([cell == "#" for cell in matrix[-1]]):
keys.append(matrix)
input = locks, keys
def get_cols(matrix):
cols = [-1] * len(matrix[0])
for row in matrix:
for j, cell in enumerate(row):
if cell == "#":
cols[j] += 1
return cols
def is_match(a, b):
combined = [aa + bb for aa, bb in zip(a, b)]
return all([c <= 5 for c in combined])
def p1(input):
locks, keys = input
ans = 0
for lock in locks:
l = get_cols(lock)
for key in keys:
k = get_cols(key)
if is_match(l, k):
ans += 1
return ans
print(p1(input))
2024 Day 24 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
| wires_list, gates_list = open("input").read().strip().split('\n\n')
wires_list = wires_list.split("\n")
gates_list = gates_list.split("\n")
wires, gates = {}, {}
for w in wires_list:
wire, val = w.split(": ")
wires[wire] = int(val)
for gate in gates_list:
out = gate.split(" -> ")
a, b, c = out[0].split(" ")
gates[out[1]] = (a, b, c, out[1])
input = wires, gates
def output(wires, gates, gate):
a, op, b, c = gate
if gate in wires:
return wires[gate]
for val in [a, b]:
if val not in wires:
output(wires, gates, gates[val])
if op == "AND":
out = wires[a] & wires[b]
elif op == "OR":
out = wires[a] | wires[b]
elif op == "XOR":
out = wires[a] ^ wires[b]
wires[c] = out
return out
def solve(input):
wires, gates = input
num = []
for gate in gates:
out = output(wires, gates, gates[gate])
if gate.startswith("z"):
num.append((gate, out))
num.sort(reverse=True)
return "".join([str(n[1]) for n in num])
def make_wire(char, num):
return char + str(num).rjust(2, "0")
def verify_z(wire, num, gates):
if wire not in gates:
return False
op, x, y = gates[wire]
if op != "XOR":
return False
if num == 0:
return sorted([x, y]) == ["x00", "y00"]
return (
verify_intermediate_xor(x, num, gates)
and verify_carry_bit(y, num, gates)
or verify_intermediate_xor(y, num, gates)
and verify_carry_bit(x, num, gates)
)
def verify_intermediate_xor(wire, num, gates):
if wire not in gates:
return False
op, x, y = gates[wire]
if op != "XOR":
return False
return sorted([x, y]) == [make_wire("x", num), make_wire("y", num)]
def verify_carry_bit(wire, num, gates):
if wire not in gates:
return False
op, x, y = gates[wire]
if num == 1:
if op != "AND":
return False
return sorted([x, y]) == ["x00", "y00"]
if op != "OR":
return False
return (
verify_direct_carry(x, num - 1, gates)
and verify_recarry(y, num - 1, gates)
or verify_direct_carry(y, num - 1, gates)
and verify_recarry(x, num - 1, gates)
)
def verify_direct_carry(wire, num, gates):
if wire not in gates:
return False
op, x, y = gates[wire]
if op != "AND":
return False
return sorted([x, y]) == [make_wire("x", num), make_wire("y", num)]
def verify_recarry(wire, num, gates):
if wire not in gates:
return False
op, x, y = gates[wire]
if op != "AND":
return False
return (
verify_intermediate_xor(x, num, gates)
and verify_carry_bit(y, num, gates)
or verify_intermediate_xor(y, num, gates)
and verify_carry_bit(x, num, gates)
)
def verify(num, gates):
return verify_z(make_wire("z", num), num, gates)
def progress(gates):
i = 0
while True:
if not verify(i, gates):
break
i += 1
return i
def p1(input):
return int(solve(input), 2)
# https://github.com/hyperneutrino/advent-of-code/blob/main/2024/day24p2.py
def p2(input):
_, gates = input
for gate in gates:
val = gates[gate]
gates[gate] = (val[1], val[0], val[2])
swaps = []
for _ in range(4):
baseline = progress(gates)
for x in gates:
for y in gates:
if x == y:
continue
gates[x], gates[y] = gates[y], gates[x]
if progress(gates) > baseline:
break
gates[x], gates[y] = gates[y], gates[x]
else:
continue
break
swaps += [x, y]
return ",".join(sorted(swaps))
print(p1(input))
print(p2(input)) |
wires_list, gates_list = open("input").read().strip().split('\n\n')
wires_list = wires_list.split("\n")
gates_list = gates_list.split("\n")
wires, gates = {}, {}
for w in wires_list:
wire, val = w.split(": ")
wires[wire] = int(val)
for gate in gates_list:
out = gate.split(" -> ")
a, b, c = out[0].split(" ")
gates[out[1]] = (a, b, c, out[1])
input = wires, gates
def output(wires, gates, gate):
a, op, b, c = gate
if gate in wires:
return wires[gate]
for val in [a, b]:
if val not in wires:
output(wires, gates, gates[val])
if op == "AND":
out = wires[a] & wires[b]
elif op == "OR":
out = wires[a] | wires[b]
elif op == "XOR":
out = wires[a] ^ wires[b]
wires[c] = out
return out
def solve(input):
wires, gates = input
num = []
for gate in gates:
out = output(wires, gates, gates[gate])
if gate.startswith("z"):
num.append((gate, out))
num.sort(reverse=True)
return "".join([str(n[1]) for n in num])
def make_wire(char, num):
return char + str(num).rjust(2, "0")
def verify_z(wire, num, gates):
if wire not in gates:
return False
op, x, y = gates[wire]
if op != "XOR":
return False
if num == 0:
return sorted([x, y]) == ["x00", "y00"]
return (
verify_intermediate_xor(x, num, gates)
and verify_carry_bit(y, num, gates)
or verify_intermediate_xor(y, num, gates)
and verify_carry_bit(x, num, gates)
)
def verify_intermediate_xor(wire, num, gates):
if wire not in gates:
return False
op, x, y = gates[wire]
if op != "XOR":
return False
return sorted([x, y]) == [make_wire("x", num), make_wire("y", num)]
def verify_carry_bit(wire, num, gates):
if wire not in gates:
return False
op, x, y = gates[wire]
if num == 1:
if op != "AND":
return False
return sorted([x, y]) == ["x00", "y00"]
if op != "OR":
return False
return (
verify_direct_carry(x, num - 1, gates)
and verify_recarry(y, num - 1, gates)
or verify_direct_carry(y, num - 1, gates)
and verify_recarry(x, num - 1, gates)
)
def verify_direct_carry(wire, num, gates):
if wire not in gates:
return False
op, x, y = gates[wire]
if op != "AND":
return False
return sorted([x, y]) == [make_wire("x", num), make_wire("y", num)]
def verify_recarry(wire, num, gates):
if wire not in gates:
return False
op, x, y = gates[wire]
if op != "AND":
return False
return (
verify_intermediate_xor(x, num, gates)
and verify_carry_bit(y, num, gates)
or verify_intermediate_xor(y, num, gates)
and verify_carry_bit(x, num, gates)
)
def verify(num, gates):
return verify_z(make_wire("z", num), num, gates)
def progress(gates):
i = 0
while True:
if not verify(i, gates):
break
i += 1
return i
def p1(input):
return int(solve(input), 2)
# https://github.com/hyperneutrino/advent-of-code/blob/main/2024/day24p2.py
def p2(input):
_, gates = input
for gate in gates:
val = gates[gate]
gates[gate] = (val[1], val[0], val[2])
swaps = []
for _ in range(4):
baseline = progress(gates)
for x in gates:
for y in gates:
if x == y:
continue
gates[x], gates[y] = gates[y], gates[x]
if progress(gates) > baseline:
break
gates[x], gates[y] = gates[y], gates[x]
else:
continue
break
swaps += [x, y]
return ",".join(sorted(swaps))
print(p1(input))
print(p2(input))
2024 Day 23 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
| from collections import defaultdict
from functools import cache
lines = open("input").read().strip().split('\n')
conns = defaultdict(set)
nodes = set()
for line in lines:
a, b = line.split('-')
nodes.add(a)
nodes.add(b)
conns[a].add(b)
conns[b].add(a)
def directly_connected():
opts = set()
for root in nodes:
for child1 in conns[root]:
for child2 in conns[child1]:
if child2 in conns[root]:
opts.add(frozenset([root, child1, child2]))
return opts
def part1():
ts = 0
for st in directly_connected():
for x in st:
if x[0] == 't':
ts += 1
break
return ts
@cache
def clique_rec(st, n):
best = st
opts = conns[n]
if st.issubset(opts):
st |= frozenset([n])
best = st
for opt in opts:
if opt in st:
continue
candidate = clique_rec(st, opt)
if len(best) < len(candidate):
best = candidate
return best
def max_clique():
best = frozenset()
for n in nodes:
candidate = clique_rec(frozenset(), n)
if len(best) < len(candidate):
best = candidate
return best
def part2():
return ','.join(sorted(max_clique()))
print(part1())
print(part2()) |
from collections import defaultdict
from functools import cache
lines = open("input").read().strip().split('\n')
conns = defaultdict(set)
nodes = set()
for line in lines:
a, b = line.split('-')
nodes.add(a)
nodes.add(b)
conns[a].add(b)
conns[b].add(a)
def directly_connected():
opts = set()
for root in nodes:
for child1 in conns[root]:
for child2 in conns[child1]:
if child2 in conns[root]:
opts.add(frozenset([root, child1, child2]))
return opts
def part1():
ts = 0
for st in directly_connected():
for x in st:
if x[0] == 't':
ts += 1
break
return ts
@cache
def clique_rec(st, n):
best = st
opts = conns[n]
if st.issubset(opts):
st |= frozenset([n])
best = st
for opt in opts:
if opt in st:
continue
candidate = clique_rec(st, opt)
if len(best) < len(candidate):
best = candidate
return best
def max_clique():
best = frozenset()
for n in nodes:
candidate = clique_rec(frozenset(), n)
if len(best) < len(candidate):
best = candidate
return best
def part2():
return ','.join(sorted(max_clique()))
print(part1())
print(part2())
2024 Day 22 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
| from collections import defaultdict
def mix(a, b):
return a ^ b
def prune(num):
return num % 16777216
def secret(num):
a = prune(mix(num * 64, num))
b = prune(mix(a // 32, a))
c = prune(mix(b * 2048, b))
return c
def n_secrets(num, n):
output = [num]
for _ in range(n):
res = secret(num)
output.append(res)
num = res
return output
def diff(input):
output = []
n = len(input)
for i in range(1, n):
output.append(input[i] - input[i - 1])
return output
def p1(input):
return sum([n_secrets(num, 2000)[-1] for num in input])
def p2(input):
profits = defaultdict(int)
for num in input:
seen = set()
secrets = [n % 10 for n in n_secrets(num, 2000)]
differences = diff(secrets)
for i in range(len(differences) - 3):
key = tuple(differences[i : i + 4])
if key not in seen:
seen.add(key)
profits[key] += secrets[i + 4]
return max(profits.values())
lines = open("input").read().splitlines()
lines = [int(line) for line in lines]
print(p1(lines))
print(p2(lines)) |
from collections import defaultdict
def mix(a, b):
return a ^ b
def prune(num):
return num % 16777216
def secret(num):
a = prune(mix(num * 64, num))
b = prune(mix(a // 32, a))
c = prune(mix(b * 2048, b))
return c
def n_secrets(num, n):
output = [num]
for _ in range(n):
res = secret(num)
output.append(res)
num = res
return output
def diff(input):
output = []
n = len(input)
for i in range(1, n):
output.append(input[i] - input[i - 1])
return output
def p1(input):
return sum([n_secrets(num, 2000)[-1] for num in input])
def p2(input):
profits = defaultdict(int)
for num in input:
seen = set()
secrets = [n % 10 for n in n_secrets(num, 2000)]
differences = diff(secrets)
for i in range(len(differences) - 3):
key = tuple(differences[i : i + 4])
if key not in seen:
seen.add(key)
profits[key] += secrets[i + 4]
return max(profits.values())
lines = open("input").read().splitlines()
lines = [int(line) for line in lines]
print(p1(lines))
print(p2(lines))
2024 Day 21 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
| from collections import deque
from functools import cache
from itertools import product
def compute_seqs(keypad):
pos = {}
for r in range(len(keypad)):
for c in range(len(keypad[r])):
if keypad[r][c] is not None:
pos[keypad[r][c]] = (r, c)
seqs = {}
for x in pos:
for y in pos:
if x == y:
seqs[(x, y)] = ["A"]
continue
possibilities = []
q = deque([(pos[x], "")])
optimal = float("inf")
while q:
(r, c), moves = q.popleft()
for nr, nc, nm in [
(r - 1, c, "^"),
(r + 1, c, "v"),
(r, c - 1, "<"),
(r, c + 1, ">"),
]:
if nr < 0 or nc < 0 or nr >= len(keypad) or nc >= len(keypad[0]):
continue
if keypad[nr][nc] is None:
continue
if keypad[nr][nc] == y:
if optimal < len(moves) + 1:
break
optimal = len(moves) + 1
possibilities.append(moves + nm + "A")
else:
q.append(((nr, nc), moves + nm))
else:
continue
break
seqs[(x, y)] = possibilities
return seqs
def solve(string, seqs):
options = [seqs[(x, y)] for x, y in zip("A" + string, string)]
return ["".join(x) for x in product(*options)]
num_keypad = [["7", "8", "9"], ["4", "5", "6"], ["1", "2", "3"], [None, "0", "A"]]
num_seqs = compute_seqs(num_keypad)
dir_keypad = [[None, "^", "A"], ["<", "v", ">"]]
dir_seqs = compute_seqs(dir_keypad)
dir_lengths = {key: len(value[0]) for key, value in dir_seqs.items()}
@cache
def compute_length(seq, depth):
if depth == 1:
return sum(dir_lengths[(x, y)] for x, y in zip("A" + seq, seq))
length = 0
for x, y in zip("A" + seq, seq):
length += min(compute_length(subseq, depth - 1) for subseq in dir_seqs[(x, y)])
return length
def ans(input, depth):
total = 0
for line in input:
length = float("inf")
for seq in solve(line, num_seqs):
length = min(length, compute_length(seq, depth))
total += length * int(line[:-1])
return total
input = open("input").read().splitlines()
print(ans(input, 2))
print(ans(input, 25)) |
from collections import deque
from functools import cache
from itertools import product
def compute_seqs(keypad):
pos = {}
for r in range(len(keypad)):
for c in range(len(keypad[r])):
if keypad[r][c] is not None:
pos[keypad[r][c]] = (r, c)
seqs = {}
for x in pos:
for y in pos:
if x == y:
seqs[(x, y)] = ["A"]
continue
possibilities = []
q = deque([(pos[x], "")])
optimal = float("inf")
while q:
(r, c), moves = q.popleft()
for nr, nc, nm in [
(r - 1, c, "^"),
(r + 1, c, "v"),
(r, c - 1, "<"),
(r, c + 1, ">"),
]:
if nr < 0 or nc < 0 or nr >= len(keypad) or nc >= len(keypad[0]):
continue
if keypad[nr][nc] is None:
continue
if keypad[nr][nc] == y:
if optimal < len(moves) + 1:
break
optimal = len(moves) + 1
possibilities.append(moves + nm + "A")
else:
q.append(((nr, nc), moves + nm))
else:
continue
break
seqs[(x, y)] = possibilities
return seqs
def solve(string, seqs):
options = [seqs[(x, y)] for x, y in zip("A" + string, string)]
return ["".join(x) for x in product(*options)]
num_keypad = [["7", "8", "9"], ["4", "5", "6"], ["1", "2", "3"], [None, "0", "A"]]
num_seqs = compute_seqs(num_keypad)
dir_keypad = [[None, "^", "A"], ["<", "v", ">"]]
dir_seqs = compute_seqs(dir_keypad)
dir_lengths = {key: len(value[0]) for key, value in dir_seqs.items()}
@cache
def compute_length(seq, depth):
if depth == 1:
return sum(dir_lengths[(x, y)] for x, y in zip("A" + seq, seq))
length = 0
for x, y in zip("A" + seq, seq):
length += min(compute_length(subseq, depth - 1) for subseq in dir_seqs[(x, y)])
return length
def ans(input, depth):
total = 0
for line in input:
length = float("inf")
for seq in solve(line, num_seqs):
length = min(length, compute_length(seq, depth))
total += length * int(line[:-1])
return total
input = open("input").read().splitlines()
print(ans(input, 2))
print(ans(input, 25))
2024 Day 20 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
| from collections import deque
lines = open("input").read().splitlines()
matrix = [list(line) for line in lines]
start, end = None, None
for i, row in enumerate(matrix):
for j, cell in enumerate(row):
if cell == "#":
matrix[i][j] = 0
else:
if cell == "S":
start = (i, j)
elif cell == "E":
end = (i, j)
matrix[i][j] = 1
input = matrix, start, end
def bfs(matrix, start, end):
queue = deque([(start[0], start[1], 0)])
seen = {}
m, n = len(matrix), len(matrix[0])
while queue:
i, j, time = queue.popleft()
if seen.get((i, j), float("inf")) <= time:
continue
seen[(i, j)] = time
if (i, j) == end:
continue
for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and matrix[ni][nj]:
queue.append((ni, nj, time + 1))
return seen
def dist(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def reachable(curr, threshold):
for i in range(curr[0] - threshold, curr[0] + threshold + 1):
for j in range(curr[1] - threshold, curr[1] + threshold + 1):
d = dist(curr, (i, j))
if d <= threshold:
yield (i, j, d)
def solve(input, threshold, min_time=100):
matrix, start, end = input
seen = bfs(matrix, start, end)
ans = 0
for i, j in seen:
for p, q, d in reachable((i, j), threshold):
if (p, q) not in seen:
continue
new_time = seen[(i, j)] + d + seen[end] - seen[(p, q)]
if seen[end] - new_time >= min_time:
ans += 1
return ans
print(solve(input, 2))
print(solve(input, 20)) |
from collections import deque
lines = open("input").read().splitlines()
matrix = [list(line) for line in lines]
start, end = None, None
for i, row in enumerate(matrix):
for j, cell in enumerate(row):
if cell == "#":
matrix[i][j] = 0
else:
if cell == "S":
start = (i, j)
elif cell == "E":
end = (i, j)
matrix[i][j] = 1
input = matrix, start, end
def bfs(matrix, start, end):
queue = deque([(start[0], start[1], 0)])
seen = {}
m, n = len(matrix), len(matrix[0])
while queue:
i, j, time = queue.popleft()
if seen.get((i, j), float("inf")) <= time:
continue
seen[(i, j)] = time
if (i, j) == end:
continue
for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and matrix[ni][nj]:
queue.append((ni, nj, time + 1))
return seen
def dist(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def reachable(curr, threshold):
for i in range(curr[0] - threshold, curr[0] + threshold + 1):
for j in range(curr[1] - threshold, curr[1] + threshold + 1):
d = dist(curr, (i, j))
if d <= threshold:
yield (i, j, d)
def solve(input, threshold, min_time=100):
matrix, start, end = input
seen = bfs(matrix, start, end)
ans = 0
for i, j in seen:
for p, q, d in reachable((i, j), threshold):
if (p, q) not in seen:
continue
new_time = seen[(i, j)] + d + seen[end] - seen[(p, q)]
if seen[end] - new_time >= min_time:
ans += 1
return ans
print(solve(input, 2))
print(solve(input, 20))
2024 Day 19 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
| pats, desired = open("input").read().strip().split('\n\n')
pats = pats.split(', ')
desired = desired.split('\n')
def count(goal):
dp = [0]*(len(goal)+1)
dp[0] = 1
for end in range(1, len(goal)+1):
for cand in pats:
start = end - len(cand)
if start < 0:
continue
if goal[start:end] == cand:
dp[end] += dp[start]
return dp[len(goal)]
def part1():
tot = 0
for goal in desired:
if count(goal):
tot += 1
return tot
def part2():
tot = 0
for goal in desired:
tot += count(goal)
return tot
print(part1())
print(part2()) |
pats, desired = open("input").read().strip().split('\n\n')
pats = pats.split(', ')
desired = desired.split('\n')
def count(goal):
dp = [0]*(len(goal)+1)
dp[0] = 1
for end in range(1, len(goal)+1):
for cand in pats:
start = end - len(cand)
if start < 0:
continue
if goal[start:end] == cand:
dp[end] += dp[start]
return dp[len(goal)]
def part1():
tot = 0
for goal in desired:
if count(goal):
tot += 1
return tot
def part2():
tot = 0
for goal in desired:
tot += count(goal)
return tot
print(part1())
print(part2())
2024 Day 18 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
| lines = open("input").read().strip().split('\n')
corrupted = []
for line in lines:
x, y = list(map(int, line.split(',')))
corrupted.append((y, x))
moves = [(-1, 0), (0, 1), (1, 0), (0, -1)]
if len(corrupted) < 1000:
n = 12
h, w = 7, 7
goal = (6, 6)
else:
n = 1024
h, w = 71, 71
goal = (70, 70)
def solve(num_corrupted):
blocked = set(corrupted[:num_corrupted])
cur = [(0, 0)]
seen = set()
for i in range(h*w):
nxt = []
for loc in cur:
y, x = loc
if loc in seen or y < 0 or h <= y or x < 0 or h <= x:
continue
if loc in blocked:
continue
if loc == goal:
return i
seen.add(loc)
for (dy, dx) in moves:
nxt.append((y+dy, x+dx))
cur = nxt
return None
def part1():
return solve(n)
def pp():
for y in range(h):
l = ['.']*w
for (cy, cx) in set(corrupted[:n]):
if y == cy:
l[cx] = '#'
print(''.join(l))
def part2():
for i in range(len(corrupted)):
if solve(i+1) is None:
y, x = corrupted[i]
return ','.join(map(str, ((x, y))))
print(part1())
print(part2()) |
lines = open("input").read().strip().split('\n')
corrupted = []
for line in lines:
x, y = list(map(int, line.split(',')))
corrupted.append((y, x))
moves = [(-1, 0), (0, 1), (1, 0), (0, -1)]
if len(corrupted) < 1000:
n = 12
h, w = 7, 7
goal = (6, 6)
else:
n = 1024
h, w = 71, 71
goal = (70, 70)
def solve(num_corrupted):
blocked = set(corrupted[:num_corrupted])
cur = [(0, 0)]
seen = set()
for i in range(h*w):
nxt = []
for loc in cur:
y, x = loc
if loc in seen or y < 0 or h <= y or x < 0 or h <= x:
continue
if loc in blocked:
continue
if loc == goal:
return i
seen.add(loc)
for (dy, dx) in moves:
nxt.append((y+dy, x+dx))
cur = nxt
return None
def part1():
return solve(n)
def pp():
for y in range(h):
l = ['.']*w
for (cy, cx) in set(corrupted[:n]):
if y == cy:
l[cx] = '#'
print(''.join(l))
def part2():
for i in range(len(corrupted)):
if solve(i+1) is None:
y, x = corrupted[i]
return ','.join(map(str, ((x, y))))
print(part1())
print(part2())
2024 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
| import re
from collections import namedtuple
regs, prog = open("input").read().strip().split('\n\n')
regs = list(map(int, re.findall('\d+', regs)))
prog = list(map(int, re.findall('\d+', prog)))
A = 0
B = 1
C = 2
class Program:
def __init__(self, r, p):
self.ip = 0
self.r = r[:]
self.p = p[:]
self.out = []
def copy(p):
return Program(p.r[:], p.p, p.out[:])
def lit(p):
return p.p[p.ip+1]
def combo(p):
r = p.r
return {0:0, 1:1, 2:2, 3:3, 4:r[A], 5:r[B], 6:r[C]}[p.lit()]
def halted(p):
return len(p.p) <= p.ip
def step(p):
r = p.r
op = p.p[p.ip]
lit = p.lit()
combo = p.combo()
if op == 0:
r[A] = r[A]//(1 << combo)
if op == 1:
r[B] = r[B] ^ lit
if op == 2:
r[B] = combo & 0b111
if op == 3:
if r[A] != 0:
p.ip = lit - 2
if op == 4:
r[B] = r[B] ^ r[C]
if op == 5:
p.out.append(combo & 0b111)
if op == 6:
r[B] = r[A]//(1 << combo)
if op == 7:
r[C] = r[A]//(1 << combo)
p.ip += 2
def run(p):
while not p.halted():
p.step()
return p.out
def combo_arg_str(arg):
if arg <= 3:
return arg
if arg <= 6:
return 'ABC'[arg-4]
return '?'
def prog_to_funcalls(prog):
ops = ['adv', 'bxl', 'bst', 'jnz', 'bxc', 'out', 'bdv', 'cdv']
res = []
for i in range(len(prog)//2):
op = prog[2*i]
arg = prog[2*i + 1]
if op == 0:
den_mul = combo_arg_str(arg)
if isinstance(den_mul, int):
print('A = A // {}'.format(1 << den_mul))
else:
print('A = A // (1 << {})'.format(den_mul))
elif op == 1:
print('B = B ^', arg)
elif op == 2:
combo = combo_arg_str(arg)
if isinstance(combo, int):
print('B =', combo & 0b111)
else:
print('B = {} & 0b111'.format(combo))
elif op == 3:
print('goto', combo_arg_str(arg))
elif op == 4:
print('B = B ^ C')
elif op == 5:
print('print({} & 0b111)'.format(combo_arg_str(arg)))
elif op == 6:
den_mul = combo_arg_str(arg)
if isinstance(den_mul, int):
print('C = A // {}'.format(1 << den_mul))
else:
print('C = A // (1 << {})'.format(den_mul))
elif op == 7:
den_mul = combo_arg_str(arg)
if isinstance(den_mul, int):
print('C = A // {}'.format(1 << den_mul))
else:
print('C = A // (1 << {})'.format(den_mul))
def part1():
res = Program(regs, prog).run()
return ','.join(map(str, res))
def search(a, i):
# work on 3 and 3 bits (the program peeks at the 4/5th bit, hence this
# search)
if len(prog) == i:
return a
p = prog[-i-1:]
for j in range(0b1000):
r = regs[:]
r[A] = (a << 3) | j
res = Program(r, prog).run()
if res == p:
rec = search(r[A], i+1)
if rec:
return rec
return None
def part2():
return search(0, 0)
print(part1())
print(part2()) |
import re
from collections import namedtuple
regs, prog = open("input").read().strip().split('\n\n')
regs = list(map(int, re.findall('\d+', regs)))
prog = list(map(int, re.findall('\d+', prog)))
A = 0
B = 1
C = 2
class Program:
def __init__(self, r, p):
self.ip = 0
self.r = r[:]
self.p = p[:]
self.out = []
def copy(p):
return Program(p.r[:], p.p, p.out[:])
def lit(p):
return p.p[p.ip+1]
def combo(p):
r = p.r
return {0:0, 1:1, 2:2, 3:3, 4:r[A], 5:r[B], 6:r[C]}[p.lit()]
def halted(p):
return len(p.p) <= p.ip
def step(p):
r = p.r
op = p.p[p.ip]
lit = p.lit()
combo = p.combo()
if op == 0:
r[A] = r[A]//(1 << combo)
if op == 1:
r[B] = r[B] ^ lit
if op == 2:
r[B] = combo & 0b111
if op == 3:
if r[A] != 0:
p.ip = lit - 2
if op == 4:
r[B] = r[B] ^ r[C]
if op == 5:
p.out.append(combo & 0b111)
if op == 6:
r[B] = r[A]//(1 << combo)
if op == 7:
r[C] = r[A]//(1 << combo)
p.ip += 2
def run(p):
while not p.halted():
p.step()
return p.out
def combo_arg_str(arg):
if arg <= 3:
return arg
if arg <= 6:
return 'ABC'[arg-4]
return '?'
def prog_to_funcalls(prog):
ops = ['adv', 'bxl', 'bst', 'jnz', 'bxc', 'out', 'bdv', 'cdv']
res = []
for i in range(len(prog)//2):
op = prog[2*i]
arg = prog[2*i + 1]
if op == 0:
den_mul = combo_arg_str(arg)
if isinstance(den_mul, int):
print('A = A // {}'.format(1 << den_mul))
else:
print('A = A // (1 << {})'.format(den_mul))
elif op == 1:
print('B = B ^', arg)
elif op == 2:
combo = combo_arg_str(arg)
if isinstance(combo, int):
print('B =', combo & 0b111)
else:
print('B = {} & 0b111'.format(combo))
elif op == 3:
print('goto', combo_arg_str(arg))
elif op == 4:
print('B = B ^ C')
elif op == 5:
print('print({} & 0b111)'.format(combo_arg_str(arg)))
elif op == 6:
den_mul = combo_arg_str(arg)
if isinstance(den_mul, int):
print('C = A // {}'.format(1 << den_mul))
else:
print('C = A // (1 << {})'.format(den_mul))
elif op == 7:
den_mul = combo_arg_str(arg)
if isinstance(den_mul, int):
print('C = A // {}'.format(1 << den_mul))
else:
print('C = A // (1 << {})'.format(den_mul))
def part1():
res = Program(regs, prog).run()
return ','.join(map(str, res))
def search(a, i):
# work on 3 and 3 bits (the program peeks at the 4/5th bit, hence this
# search)
if len(prog) == i:
return a
p = prog[-i-1:]
for j in range(0b1000):
r = regs[:]
r[A] = (a << 3) | j
res = Program(r, prog).run()
if res == p:
rec = search(r[A], i+1)
if rec:
return rec
return None
def part2():
return search(0, 0)
print(part1())
print(part2())
2024 Day 16 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
| from heapq import *
from collections import defaultdict
data = open("input").read().strip()
grid = data.split('\n')
walls = set()
start, goal = None, None
moves = [(-1, 0), (0, 1), (1, 0), (0, -1)]
def rot90s(delta):
dy, dx = delta
return [(-dx, -dy), (dx, dy)] #?
for y, line in enumerate(grid):
for x, ch in enumerate(line):
if ch == '#':
walls.add((y,x))
if ch == 'S':
start =(y,x)
if ch == 'E':
goal = (y, x)
def backtrack(prevs, goal):
to_check = [(goal, delta) for delta in moves]
seen = set()
while to_check:
cur = to_check.pop()
if cur in seen:
continue
seen.add(cur)
to_check.extend(list(prevs[cur]))
locs = set(loc for loc, _ in seen)
return locs
def dijkstra(start, goal):
seen = defaultdict(lambda: 1e80)
prevs = defaultdict(set)
fst = (start, (0, 1))
heap = [(0, fst, None)]
best = float('Inf')
while heap:
cost, cur, prev = heappop(heap)
loc, delta = cur
if best < cost:
break
if seen[cur] < cost:
continue
if seen[cur] == cost and prev:
prevs[cur].add(prev)
continue
if loc == goal:
best = cost
prevs[cur].add(prev)
continue
seen[cur] = cost
if prev:
prevs[cur].add(prev)
y, x = loc
dy, dx = delta
nloc = (y+dy, x+dx)
if nloc not in walls:
heappush(heap, (cost+1, (nloc, delta), cur))
for ndelta in rot90s(delta):
heappush(heap, (cost+1000, (loc, ndelta), cur))
return best, backtrack(prevs, goal)
best, tiles = dijkstra(start, goal)
print(best)
print(len(tiles)) |
from heapq import *
from collections import defaultdict
data = open("input").read().strip()
grid = data.split('\n')
walls = set()
start, goal = None, None
moves = [(-1, 0), (0, 1), (1, 0), (0, -1)]
def rot90s(delta):
dy, dx = delta
return [(-dx, -dy), (dx, dy)] #?
for y, line in enumerate(grid):
for x, ch in enumerate(line):
if ch == '#':
walls.add((y,x))
if ch == 'S':
start =(y,x)
if ch == 'E':
goal = (y, x)
def backtrack(prevs, goal):
to_check = [(goal, delta) for delta in moves]
seen = set()
while to_check:
cur = to_check.pop()
if cur in seen:
continue
seen.add(cur)
to_check.extend(list(prevs[cur]))
locs = set(loc for loc, _ in seen)
return locs
def dijkstra(start, goal):
seen = defaultdict(lambda: 1e80)
prevs = defaultdict(set)
fst = (start, (0, 1))
heap = [(0, fst, None)]
best = float('Inf')
while heap:
cost, cur, prev = heappop(heap)
loc, delta = cur
if best < cost:
break
if seen[cur] < cost:
continue
if seen[cur] == cost and prev:
prevs[cur].add(prev)
continue
if loc == goal:
best = cost
prevs[cur].add(prev)
continue
seen[cur] = cost
if prev:
prevs[cur].add(prev)
y, x = loc
dy, dx = delta
nloc = (y+dy, x+dx)
if nloc not in walls:
heappush(heap, (cost+1, (nloc, delta), cur))
for ndelta in rot90s(delta):
heappush(heap, (cost+1000, (loc, ndelta), cur))
return best, backtrack(prevs, goal)
best, tiles = dijkstra(start, goal)
print(best)
print(len(tiles))
2024 Day 15 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
| data = open("input").read().strip()
gridd, actions = data.split('\n\n')
gridd = gridd.split('\n')
walls = set()
init_boxes = set()
robot = None
for y, line in enumerate(gridd):
for x, ch in enumerate(line):
if ch == '#':
walls.add((y,x))
if ch == 'O':
init_boxes.add((y,x))
if ch == '@':
robot = (y, x)
def step(boxes, robot, action):
dx, dy = 0, 0
if action == '<':
dx = -1
elif action == '>':
dx = 1
elif action == 'v':
dy = 1
elif action == '^':
dy = -1
else:
return robot
ry, rx = robot
t = (ry + dy, rx + dx)
if t in walls:
return robot
if not t in boxes:
return t
t2 = t
while t2 in boxes:
t2 = (t2[0] + dy, t2[1] + dx)
if t2 in walls:
return robot
boxes.remove(t)
boxes.add(t2)
return t
def part1():
rloc = robot
boxes = set(s for s in init_boxes)
for a in actions:
rloc = step(boxes, rloc, a)
return sum(100*y + x for (y, x) in boxes)
walls2 = set()
init_boxes2 = set()
robot2 = None
for y, line in enumerate(gridd):
line = line.replace('#', '##').replace('.', '..').replace('O', 'O.').replace('@', '@.')
for x, ch in enumerate(line):
if ch == '#':
walls2.add((y,x))
if ch == 'O':
init_boxes2.add((y,x))
if ch == '@':
robot2 = (y, x)
def has_box(boxes, loc):
y, x = loc
return loc in boxes or (y, x-1) in boxes
def box_origin(boxes, loc):
y, x = loc
if loc in boxes:
return loc
if (y, x-1) in boxes:
return (y, x-1)
def box_locs(boxes, loc):
assert(has_box(boxes, loc))
y, x = box_origin(boxes, loc)
return [(y, x), (y, x+1)]
def try_move(boxes, loc, dy, dx):
assert(has_box(boxes, loc))
y, x = loc
cur_borigs = [box_origin(boxes, loc)]
touched = set()
while cur_borigs:
nxt = []
for borig in cur_borigs:
touched.add(borig)
if dy != 0:
for (by, bx) in box_locs(boxes, borig):
nloc = (by+dy, bx+dx)
if nloc in walls2:
return False
if has_box(boxes, nloc):
nxt.append(box_origin(boxes, nloc))
if dx == -1:
y, x = borig
nloc = (y, x-1)
if nloc in walls2:
return False
if (y, x-2) in boxes:
nxt.append((y, x-2))
if dx == 1:
y, x = borig
nloc = (y, x+2)
if nloc in walls2:
return False
if (y, x+2) in boxes:
nxt.append((y, x+2))
cur_borigs = nxt
boxes -= touched
for (y, x) in touched:
boxes.add((y+dy, x+dx))
return True
def step2(boxes, robot, action):
dx, dy = 0, 0
if action == '<':
dx = -1
elif action == '>':
dx = 1
elif action == 'v':
dy = 1
elif action == '^':
dy = -1
else:
return robot
ry, rx = robot
t = (ry + dy, rx + dx)
if t in walls2:
return robot
if not has_box(boxes, t):
return t
if try_move(boxes, t, dy, dx):
return t
else:
return robot
def pp(boxes, robot):
lines = [['.']*len(gridd[0])*2 for _ in range(len(gridd))]
for (y, x) in walls2:
lines[y][x] = '#'
for (y, x) in boxes:
lines[y][x] = '['
lines[y][x+1] = ']'
lines[robot[0]][robot[1]] = '@'
for line in lines:
print(''.join(line))
print()
def part2():
rloc = robot2
boxes = set(s for s in init_boxes2)
for a in actions:
rloc = step2(boxes, rloc, a)
return sum(100*y + x for (y, x) in boxes)
print(part1())
print(part2()) |
data = open("input").read().strip()
gridd, actions = data.split('\n\n')
gridd = gridd.split('\n')
walls = set()
init_boxes = set()
robot = None
for y, line in enumerate(gridd):
for x, ch in enumerate(line):
if ch == '#':
walls.add((y,x))
if ch == 'O':
init_boxes.add((y,x))
if ch == '@':
robot = (y, x)
def step(boxes, robot, action):
dx, dy = 0, 0
if action == '<':
dx = -1
elif action == '>':
dx = 1
elif action == 'v':
dy = 1
elif action == '^':
dy = -1
else:
return robot
ry, rx = robot
t = (ry + dy, rx + dx)
if t in walls:
return robot
if not t in boxes:
return t
t2 = t
while t2 in boxes:
t2 = (t2[0] + dy, t2[1] + dx)
if t2 in walls:
return robot
boxes.remove(t)
boxes.add(t2)
return t
def part1():
rloc = robot
boxes = set(s for s in init_boxes)
for a in actions:
rloc = step(boxes, rloc, a)
return sum(100*y + x for (y, x) in boxes)
walls2 = set()
init_boxes2 = set()
robot2 = None
for y, line in enumerate(gridd):
line = line.replace('#', '##').replace('.', '..').replace('O', 'O.').replace('@', '@.')
for x, ch in enumerate(line):
if ch == '#':
walls2.add((y,x))
if ch == 'O':
init_boxes2.add((y,x))
if ch == '@':
robot2 = (y, x)
def has_box(boxes, loc):
y, x = loc
return loc in boxes or (y, x-1) in boxes
def box_origin(boxes, loc):
y, x = loc
if loc in boxes:
return loc
if (y, x-1) in boxes:
return (y, x-1)
def box_locs(boxes, loc):
assert(has_box(boxes, loc))
y, x = box_origin(boxes, loc)
return [(y, x), (y, x+1)]
def try_move(boxes, loc, dy, dx):
assert(has_box(boxes, loc))
y, x = loc
cur_borigs = [box_origin(boxes, loc)]
touched = set()
while cur_borigs:
nxt = []
for borig in cur_borigs:
touched.add(borig)
if dy != 0:
for (by, bx) in box_locs(boxes, borig):
nloc = (by+dy, bx+dx)
if nloc in walls2:
return False
if has_box(boxes, nloc):
nxt.append(box_origin(boxes, nloc))
if dx == -1:
y, x = borig
nloc = (y, x-1)
if nloc in walls2:
return False
if (y, x-2) in boxes:
nxt.append((y, x-2))
if dx == 1:
y, x = borig
nloc = (y, x+2)
if nloc in walls2:
return False
if (y, x+2) in boxes:
nxt.append((y, x+2))
cur_borigs = nxt
boxes -= touched
for (y, x) in touched:
boxes.add((y+dy, x+dx))
return True
def step2(boxes, robot, action):
dx, dy = 0, 0
if action == '<':
dx = -1
elif action == '>':
dx = 1
elif action == 'v':
dy = 1
elif action == '^':
dy = -1
else:
return robot
ry, rx = robot
t = (ry + dy, rx + dx)
if t in walls2:
return robot
if not has_box(boxes, t):
return t
if try_move(boxes, t, dy, dx):
return t
else:
return robot
def pp(boxes, robot):
lines = [['.']*len(gridd[0])*2 for _ in range(len(gridd))]
for (y, x) in walls2:
lines[y][x] = '#'
for (y, x) in boxes:
lines[y][x] = '['
lines[y][x+1] = ']'
lines[robot[0]][robot[1]] = '@'
for line in lines:
print(''.join(line))
print()
def part2():
rloc = robot2
boxes = set(s for s in init_boxes2)
for a in actions:
rloc = step2(boxes, rloc, a)
return sum(100*y + x for (y, x) in boxes)
print(part1())
print(part2())
2024 Day 14 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
| import re
from functools import reduce
from operator import mul
X, Y = 101, 103
lines = open("input").read().splitlines()
lines = [list(map(int, re.search(r"p=(-?\d+),(-?\d+) v=(-?\d+),(-?\d+)", line).groups())) for line in lines]
def simulate(robot, time):
x, y, vx, vy = robot
fx, fy = (x + time * vx) % X, (y + time * vy) % Y
return (fx, fy)
def quad(x, y):
if x < X // 2:
if y < Y // 2:
return 0
elif y > Y // 2:
return 1
elif x > X // 2:
if y < Y // 2:
return 2
elif y > Y // 2:
return 3
return -1
def display(robots):
for j in range(Y):
for i in range(X):
if (i, j) in robots:
print(".", end="")
else:
print(" ", end="")
print()
# Part 01
robots = [0] * 4
for robot in lines:
q = quad(*simulate(robot, time=100))
if q != -1:
robots[q] += 1
print(reduce(mul, robots))
# Part 02
i = 0
while True:
i += 1
positions = [simulate(robot, time=i) for robot in lines]
if len(positions) == len(set(positions)):
display(positions)
print(i) |
import re
from functools import reduce
from operator import mul
X, Y = 101, 103
lines = open("input").read().splitlines()
lines = [list(map(int, re.search(r"p=(-?\d+),(-?\d+) v=(-?\d+),(-?\d+)", line).groups())) for line in lines]
def simulate(robot, time):
x, y, vx, vy = robot
fx, fy = (x + time * vx) % X, (y + time * vy) % Y
return (fx, fy)
def quad(x, y):
if x < X // 2:
if y < Y // 2:
return 0
elif y > Y // 2:
return 1
elif x > X // 2:
if y < Y // 2:
return 2
elif y > Y // 2:
return 3
return -1
def display(robots):
for j in range(Y):
for i in range(X):
if (i, j) in robots:
print(".", end="")
else:
print(" ", end="")
print()
# Part 01
robots = [0] * 4
for robot in lines:
q = quad(*simulate(robot, time=100))
if q != -1:
robots[q] += 1
print(reduce(mul, robots))
# Part 02
i = 0
while True:
i += 1
positions = [simulate(robot, time=i) for robot in lines]
if len(positions) == len(set(positions)):
display(positions)
print(i)
2024 Day 13 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
| import re
machines = []
grps = open("input").read().strip().split('\n\n')
for grp in grps:
lines = grp.split('\n')
ax, ay = map(int, re.findall(r'(\d+)', lines[0]))
bx, by = map(int, re.findall(r'(\d+)', lines[1]))
tx, ty = map(int, re.findall(r'(\d+)', lines[2]))
machines.append([ax, bx, ay, by, tx, ty])
def solve_linear_system(a, b, c, d, e, f):
"""
Solves:
a*x + b*y = e
c*x + d*y = f
"""
# Determinant of the coefficient matrix
det = a * d - b * c
if det == 0:
raise ValueError("The system has no unique solution (determinant is zero).")
# Using Cramer's Rule to find x and y
x = (e * d - b * f) / det
y = (a * f - e * c) / det
return x, y
def solve(input, p2=False):
ans = 0
for machine in machines:
if p2:
machine[-1] += 10000000000000
machine[-2] += 10000000000000
x, y = solve_linear_system(*machine)
if int(x) == x and int(y) == y:
ans += x * 3 + y
return int(ans)
print(solve(input))
print(solve(input, p2=True)) |
import re
machines = []
grps = open("input").read().strip().split('\n\n')
for grp in grps:
lines = grp.split('\n')
ax, ay = map(int, re.findall(r'(\d+)', lines[0]))
bx, by = map(int, re.findall(r'(\d+)', lines[1]))
tx, ty = map(int, re.findall(r'(\d+)', lines[2]))
machines.append([ax, bx, ay, by, tx, ty])
def solve_linear_system(a, b, c, d, e, f):
"""
Solves:
a*x + b*y = e
c*x + d*y = f
"""
# Determinant of the coefficient matrix
det = a * d - b * c
if det == 0:
raise ValueError("The system has no unique solution (determinant is zero).")
# Using Cramer's Rule to find x and y
x = (e * d - b * f) / det
y = (a * f - e * c) / det
return x, y
def solve(input, p2=False):
ans = 0
for machine in machines:
if p2:
machine[-1] += 10000000000000
machine[-2] += 10000000000000
x, y = solve_linear_system(*machine)
if int(x) == x and int(y) == y:
ans += x * 3 + y
return int(ans)
print(solve(input))
print(solve(input, p2=True))
2024 Day 12 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
| grid = open("input").read().splitlines()
h, w = len(grid), len(grid[0])
moves = [(-1, 0), (0, 1), (1, 0), (0, -1)]
def loc(y, x):
if y < 0 or x < 0:
return None
try:
return grid[y][x]
except Exception:
return None
groups = []
def bfs(y, x):
grp = set([(y, x)])
val = grid[y][x]
cur = [(y, x)]
while cur:
nxt = []
for (y, x) in cur:
for (dy, dx) in moves:
ny, nx = y+dy, x+dx
if loc(ny, nx) == val and (ny, nx) not in seen:
seen.add((ny, nx))
grp.add((ny, nx))
nxt.append((ny, nx))
cur = nxt
return grp
def area(grp):
return len(grp)
def perim(grp):
tot = 0
for (y, x) in grp:
for (dy, dx) in moves:
ny, nx = y+dy, x+dx
if (ny, nx) not in grp:
tot += 1
return tot
plot_sides = moves
def sides(grp):
sseen = set()
ccs = 0
for (y, x) in grp:
for (dy, dx) in moves:
if (y+dy, x+dx) in grp:
continue
# n = outside, d = outside "side"
# find 'canonical' corner side
cy, cx = y, x
while (cy+dx, cx+dy) in grp and (cy+dy, cx+dx) not in grp:
cy += dx
cx += dy
if (cy, cx, dy, dx) not in sseen:
sseen.add((cy, cx, dy, dx))
ccs += 1
return ccs
seen = set()
part1 = 0
part2 = 0
for y in range(h):
for x in range(w):
if (y, x) in seen:
continue
grp = bfs(y, x)
a, p, s = area(grp), perim(grp), sides(grp)
part1 += a*p
part2 += a*s
print(part1)
print(part2) |
grid = open("input").read().splitlines()
h, w = len(grid), len(grid[0])
moves = [(-1, 0), (0, 1), (1, 0), (0, -1)]
def loc(y, x):
if y < 0 or x < 0:
return None
try:
return grid[y][x]
except Exception:
return None
groups = []
def bfs(y, x):
grp = set([(y, x)])
val = grid[y][x]
cur = [(y, x)]
while cur:
nxt = []
for (y, x) in cur:
for (dy, dx) in moves:
ny, nx = y+dy, x+dx
if loc(ny, nx) == val and (ny, nx) not in seen:
seen.add((ny, nx))
grp.add((ny, nx))
nxt.append((ny, nx))
cur = nxt
return grp
def area(grp):
return len(grp)
def perim(grp):
tot = 0
for (y, x) in grp:
for (dy, dx) in moves:
ny, nx = y+dy, x+dx
if (ny, nx) not in grp:
tot += 1
return tot
plot_sides = moves
def sides(grp):
sseen = set()
ccs = 0
for (y, x) in grp:
for (dy, dx) in moves:
if (y+dy, x+dx) in grp:
continue
# n = outside, d = outside "side"
# find 'canonical' corner side
cy, cx = y, x
while (cy+dx, cx+dy) in grp and (cy+dy, cx+dx) not in grp:
cy += dx
cx += dy
if (cy, cx, dy, dx) not in sseen:
sseen.add((cy, cx, dy, dx))
ccs += 1
return ccs
seen = set()
part1 = 0
part2 = 0
for y in range(h):
for x in range(w):
if (y, x) in seen:
continue
grp = bfs(y, x)
a, p, s = area(grp), perim(grp), sides(grp)
part1 += a*p
part2 += a*s
print(part1)
print(part2)
2024 Day 11 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
| line = open("input").read().strip().split()
data = [int(x) for x in line]
def update_stone(s):
if s == 0:
return (1,)
ss = str(s)
if len(ss) % 2 == 0:
sh = len(ss)//2
return (int(ss[:sh]), int(ss[sh:]))
return (s*2024,)
def dfs(mem, val, blinks):
# depth-first search
if blinks == 0:
return 1
if (val, blinks) in mem:
return mem[(val, blinks)]
sub = update_stone(val)
tot = 0
for el in sub:
tot += dfs(mem, el, blinks-1)
mem[(val, blinks)] = tot
return tot
def run(n):
mem = {}
tot = 0
for stone in data:
tot += dfs(mem, stone, n)
return tot
print(run(25))
print(run(75)) |
line = open("input").read().strip().split()
data = [int(x) for x in line]
def update_stone(s):
if s == 0:
return (1,)
ss = str(s)
if len(ss) % 2 == 0:
sh = len(ss)//2
return (int(ss[:sh]), int(ss[sh:]))
return (s*2024,)
def dfs(mem, val, blinks):
# depth-first search
if blinks == 0:
return 1
if (val, blinks) in mem:
return mem[(val, blinks)]
sub = update_stone(val)
tot = 0
for el in sub:
tot += dfs(mem, el, blinks-1)
mem[(val, blinks)] = tot
return tot
def run(n):
mem = {}
tot = 0
for stone in data:
tot += dfs(mem, stone, n)
return tot
print(run(25))
print(run(75))
2024 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
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
| lines = open("input").read().splitlines()
grid = []
for line in lines:
grid.append(list(map(int, line)))
h, w = len(grid), len(grid[0])
moves = [(-1, 0), (0, 1), (1, 0), (0, -1)]
h, w = len(grid), len(grid[0])
def loc(y, x):
if y < 0 or x < 0:
return None
try:
return grid[y][x]
except Exception:
return None
def bfs1(start):
# breadth-first search #1
cur = set([start])
for i in range(9):
nxt = set()
for y, x in list(cur):
if loc(y, x) != i:
continue
for ny, nx in list((y+dy, x+dx) for dy, dx in moves):
nxt.add((ny, nx))
cur = nxt
return sum(loc(y, x) == 9 for y, x in list(cur))
tot = 0
for y in range(h):
for x in range(w):
tot += bfs1((y, x))
print(tot)
def bfs2(start):
# breadth-first search #2
cur = [start]
for i in range(9):
nxt = []
for y, x in list(cur):
if loc(y, x) != i:
continue
for ny, nx in list((y+dy, x+dx) for dy, dx in moves):
nxt.append((ny, nx))
cur = nxt
return sum(loc(y, x) == 9 for y, x in cur)
tot = 0
for y in range(h):
for x in range(w):
tot += bfs2((y, x))
print(tot) |
lines = open("input").read().splitlines()
grid = []
for line in lines:
grid.append(list(map(int, line)))
h, w = len(grid), len(grid[0])
moves = [(-1, 0), (0, 1), (1, 0), (0, -1)]
h, w = len(grid), len(grid[0])
def loc(y, x):
if y < 0 or x < 0:
return None
try:
return grid[y][x]
except Exception:
return None
def bfs1(start):
# breadth-first search #1
cur = set([start])
for i in range(9):
nxt = set()
for y, x in list(cur):
if loc(y, x) != i:
continue
for ny, nx in list((y+dy, x+dx) for dy, dx in moves):
nxt.add((ny, nx))
cur = nxt
return sum(loc(y, x) == 9 for y, x in list(cur))
tot = 0
for y in range(h):
for x in range(w):
tot += bfs1((y, x))
print(tot)
def bfs2(start):
# breadth-first search #2
cur = [start]
for i in range(9):
nxt = []
for y, x in list(cur):
if loc(y, x) != i:
continue
for ny, nx in list((y+dy, x+dx) for dy, dx in moves):
nxt.append((ny, nx))
cur = nxt
return sum(loc(y, x) == 9 for y, x in cur)
tot = 0
for y in range(h):
for x in range(w):
tot += bfs2((y, x))
print(tot)
2024 Day 09 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
| data = open("input").read().strip()
used = []
p2 = []
for i, ch in enumerate(data):
if i % 2 == 0:
used.extend([i//2]*int(ch))
p2.append((i//2, int(ch)))
else:
used.extend([None]*int(ch))
p2.append((None, int(ch)))
def move_files():
disk = p2[:]
last_fid, _ = disk[-1]
for fid in range(last_fid, -1, -1):
for i in range(len(disk)):
t_fid, flen = disk[i]
if t_fid == fid:
break
# insert
for j in range(i):
jfid, empty_blocks = disk[j]
if jfid is not None:
continue
if flen <= empty_blocks:
remain = empty_blocks - flen
disk[j] = disk[i]
disk[i] = (None, flen)
if remain:
disk = disk[:j+1] + [(None, remain)] + disk[j+1:]
break
return disk
def expand_disk(disk):
full = []
for fid, flen in disk:
full.extend([fid]*flen)
return full
disk = expand_disk(move_files())
tot = 0
for i, fid in enumerate(disk):
if fid is not None:
tot += i * fid
print(tot) |
data = open("input").read().strip()
used = []
p2 = []
for i, ch in enumerate(data):
if i % 2 == 0:
used.extend([i//2]*int(ch))
p2.append((i//2, int(ch)))
else:
used.extend([None]*int(ch))
p2.append((None, int(ch)))
def move_files():
disk = p2[:]
last_fid, _ = disk[-1]
for fid in range(last_fid, -1, -1):
for i in range(len(disk)):
t_fid, flen = disk[i]
if t_fid == fid:
break
# insert
for j in range(i):
jfid, empty_blocks = disk[j]
if jfid is not None:
continue
if flen <= empty_blocks:
remain = empty_blocks - flen
disk[j] = disk[i]
disk[i] = (None, flen)
if remain:
disk = disk[:j+1] + [(None, remain)] + disk[j+1:]
break
return disk
def expand_disk(disk):
full = []
for fid, flen in disk:
full.extend([fid]*flen)
return full
disk = expand_disk(move_files())
tot = 0
for i, fid in enumerate(disk):
if fid is not None:
tot += i * fid
print(tot)
2024 Day 09 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
| data = open("input").read().strip()
used = []
p2 = []
for i, ch in enumerate(data):
if i % 2 == 0:
used.extend([i//2]*int(ch))
p2.append((i//2, int(ch)))
else:
used.extend([None]*int(ch))
p2.append((None, int(ch)))
def move_blks():
disk = used[:]
for i in range(len(disk)-1, -1, -1):
if disk[i] is None:
continue
for j in range(i):
if disk[j] is None:
disk[j], disk[i] = disk[i], None
break
return disk
disk = move_blks()
tot = 0
for i, fid in enumerate(disk):
if fid is not None:
tot += i * fid
print(tot) |
data = open("input").read().strip()
used = []
p2 = []
for i, ch in enumerate(data):
if i % 2 == 0:
used.extend([i//2]*int(ch))
p2.append((i//2, int(ch)))
else:
used.extend([None]*int(ch))
p2.append((None, int(ch)))
def move_blks():
disk = used[:]
for i in range(len(disk)-1, -1, -1):
if disk[i] is None:
continue
for j in range(i):
if disk[j] is None:
disk[j], disk[i] = disk[i], None
break
return disk
disk = move_blks()
tot = 0
for i, fid in enumerate(disk):
if fid is not None:
tot += i * fid
print(tot)
2024 Day 08 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
| from collections import defaultdict
import itertools
lines = open("input").read().splitlines()
h = len(lines)
w = len(lines[0])
def antinodes(pts):
s = set()
for (y1, x1), (y2, x2) in itertools.permutations(pts, 2):
y3, x3 = 2*y1-y2, 2*x1-x2
if 0 <= y3 < h and 0 <= x3 < w:
s.add((y3, x3))
return s
nodes = defaultdict(list)
for y, line in enumerate(lines):
for x, freq in enumerate(line):
if freq != '.':
nodes[freq].append((y, x))
s = set()
for _, locs in nodes.items():
s |= antinodes(locs)
print(len(s))
def harmonic_antinodes(pts):
s = set()
for (y1, x1), (y2, x2) in itertools.permutations(pts, 2):
dy, dx = y1-y2, x1-x2
i = 0
while True:
y3, x3 = y1+dy*i, x1+dx*i
if 0 <= y3 < h and 0 <= x3 < w:
s.add((y3, x3))
i += 1
else:
break
return s
s = set()
for _, locs in nodes.items():
s.update(harmonic_antinodes(locs))
print(len(s)) |
from collections import defaultdict
import itertools
lines = open("input").read().splitlines()
h = len(lines)
w = len(lines[0])
def antinodes(pts):
s = set()
for (y1, x1), (y2, x2) in itertools.permutations(pts, 2):
y3, x3 = 2*y1-y2, 2*x1-x2
if 0 <= y3 < h and 0 <= x3 < w:
s.add((y3, x3))
return s
nodes = defaultdict(list)
for y, line in enumerate(lines):
for x, freq in enumerate(line):
if freq != '.':
nodes[freq].append((y, x))
s = set()
for _, locs in nodes.items():
s |= antinodes(locs)
print(len(s))
def harmonic_antinodes(pts):
s = set()
for (y1, x1), (y2, x2) in itertools.permutations(pts, 2):
dy, dx = y1-y2, x1-x2
i = 0
while True:
y3, x3 = y1+dy*i, x1+dx*i
if 0 <= y3 < h and 0 <= x3 < w:
s.add((y3, x3))
i += 1
else:
break
return s
s = set()
for _, locs in nodes.items():
s.update(harmonic_antinodes(locs))
print(len(s))
2024 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
36
37
38
39
40
41
42
| from collections import defaultdict
grid = open("input").read().splitlines()
def on_grid(pos):
h = len(grid)
w = len(grid[0])
return pos[0] in range(h) and pos[1] in range(w)
def find_antinodes(n1, n2):
dy, dx = n1[1] - n2[1], n1[0] - n2[0]
nodes = []
k = 0
p = n1
while on_grid(p):
nodes.append(p)
k += 1
p = (n1[0] + k * dx, n1[1] + k * dy)
k = 0
p = n2
while on_grid(p):
nodes.append(p)
k += 1
p = (n2[0] - k * dx, n2[1] - k * dy)
return nodes
nodes = defaultdict(list)
for j, line in enumerate(grid):
for i, obj in enumerate(line.strip()):
if obj != '.':
nodes[obj].append((i, j))
antinodes = []
for _, positions in nodes.items():
for n1, n2 in ((p, q) for i, p in enumerate(positions[:-1])
for q in positions[i + 1:]):
antinodes.extend(find_antinodes(n1, n2))
antinodes = {pos for pos in antinodes if on_grid(pos)}
print(len(antinodes)) |
from collections import defaultdict
grid = open("input").read().splitlines()
def on_grid(pos):
h = len(grid)
w = len(grid[0])
return pos[0] in range(h) and pos[1] in range(w)
def find_antinodes(n1, n2):
dy, dx = n1[1] - n2[1], n1[0] - n2[0]
nodes = []
k = 0
p = n1
while on_grid(p):
nodes.append(p)
k += 1
p = (n1[0] + k * dx, n1[1] + k * dy)
k = 0
p = n2
while on_grid(p):
nodes.append(p)
k += 1
p = (n2[0] - k * dx, n2[1] - k * dy)
return nodes
nodes = defaultdict(list)
for j, line in enumerate(grid):
for i, obj in enumerate(line.strip()):
if obj != '.':
nodes[obj].append((i, j))
antinodes = []
for _, positions in nodes.items():
for n1, n2 in ((p, q) for i, p in enumerate(positions[:-1])
for q in positions[i + 1:]):
antinodes.extend(find_antinodes(n1, n2))
antinodes = {pos for pos in antinodes if on_grid(pos)}
print(len(antinodes))
2024 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
25
26
27
28
| from collections import defaultdict
def on_grid(pos, grid):
h = len(grid)
w = len(grid[0])
return pos[0] in range(h) and pos[1] in range(w)
def find_antinodes(n1, n2):
dy, dx = n1[1] - n2[1], n1[0] - n2[0]
return [(n1[0] + dx, n1[1] + dy), (n2[0] - dx, n2[1] - dy)]
nodes = defaultdict(list)
grid = open("input").read().splitlines()
for j, line in enumerate(grid):
for i, obj in enumerate(line.strip()):
if obj != '.':
nodes[obj].append((i, j))
antinodes = []
for _, positions in nodes.items():
for n1, n2 in ((p, q) for i, p in enumerate(positions[:-1])
for q in positions[i + 1:]):
antinodes.extend(find_antinodes(n1, n2))
antinodes = {pos for pos in antinodes if on_grid(pos, grid)}
print(len(antinodes)) |
from collections import defaultdict
def on_grid(pos, grid):
h = len(grid)
w = len(grid[0])
return pos[0] in range(h) and pos[1] in range(w)
def find_antinodes(n1, n2):
dy, dx = n1[1] - n2[1], n1[0] - n2[0]
return [(n1[0] + dx, n1[1] + dy), (n2[0] - dx, n2[1] - dy)]
nodes = defaultdict(list)
grid = open("input").read().splitlines()
for j, line in enumerate(grid):
for i, obj in enumerate(line.strip()):
if obj != '.':
nodes[obj].append((i, j))
antinodes = []
for _, positions in nodes.items():
for n1, n2 in ((p, q) for i, p in enumerate(positions[:-1])
for q in positions[i + 1:]):
antinodes.extend(find_antinodes(n1, n2))
antinodes = {pos for pos in antinodes if on_grid(pos, grid)}
print(len(antinodes))
2024 Day 07 Part 01 + 02
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| def can_combine_to(target, nums, ops, sum=0):
return target == sum if not nums else any(can_combine_to(target, nums[1:], ops, op(sum, nums[0])) for op in ops)
lines = (line.split(":") for line in open("input").read().strip().split("\n"))
pairs = [(int(target), list(map(int, nums.split()))) for target, nums in lines]
ops_one = [lambda a, b: a + b, lambda a, b: a * b]
ops_two = ops_one + [lambda a, b: int(str(a) + str(b))]
one = sum(target for target, nums in pairs if can_combine_to(target, nums, ops_one))
two = sum(target for target, nums in pairs if can_combine_to(target, nums, ops_two))
print(one)
print(two) |
def can_combine_to(target, nums, ops, sum=0):
return target == sum if not nums else any(can_combine_to(target, nums[1:], ops, op(sum, nums[0])) for op in ops)
lines = (line.split(":") for line in open("input").read().strip().split("\n"))
pairs = [(int(target), list(map(int, nums.split()))) for target, nums in lines]
ops_one = [lambda a, b: a + b, lambda a, b: a * b]
ops_two = ops_one + [lambda a, b: int(str(a) + str(b))]
one = sum(target for target, nums in pairs if can_combine_to(target, nums, ops_one))
two = sum(target for target, nums in pairs if can_combine_to(target, nums, ops_two))
print(one)
print(two)
2024 Day 06 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
| from collections import deque
def get_start(grid):
for i, row in enumerate(grid):
for j, c in enumerate(row):
if c == "^":
return i, j
return None
adj = [(-1, 0), (0, 1), (1, 0), (0, -1)]
grid = open("input").read().splitlines()
sx, sy = get_start(grid)
visited = set([])
idx = 0
q = deque([(sx, sy, idx)])
while q:
x, y, idx = q.popleft()
dx, dy = adj[idx]
visited.add((x, y))
# boundary
if not (0 <= x + dx < len(grid) and 0 <= y + dy < len(grid[0])):
break
# obstacle
if grid[x + dx][y + dy] == "#":
# turn right
idx = (idx + 1) % len(adj)
q.append((x, y, idx))
else:
# move
q.append((x + dx, y + dy, idx))
print(len(visited))
num_obstructions = 0
for i, j in visited:
if i == sx and j == sy:
continue
visited = set([])
idx = 0
q = deque([(sx, sy, idx)])
while q:
x, y, idx = q.popleft()
dx, dy = adj[idx]
if (x, y, idx) in visited:
num_obstructions += 1
break
visited.add((x, y, idx))
if not (0 <= x + dx < len(grid) and 0 <= y + dy < len(grid[0])):
break
if grid[x + dx][y + dy] == "#" or (x + dx == i and y + dy == j):
idx = (idx + 1) % len(adj)
q.append((x, y, idx))
else:
q.append((x + dx, y + dy, idx))
print(num_obstructions) |
from collections import deque
def get_start(grid):
for i, row in enumerate(grid):
for j, c in enumerate(row):
if c == "^":
return i, j
return None
adj = [(-1, 0), (0, 1), (1, 0), (0, -1)]
grid = open("input").read().splitlines()
sx, sy = get_start(grid)
visited = set([])
idx = 0
q = deque([(sx, sy, idx)])
while q:
x, y, idx = q.popleft()
dx, dy = adj[idx]
visited.add((x, y))
# boundary
if not (0 <= x + dx < len(grid) and 0 <= y + dy < len(grid[0])):
break
# obstacle
if grid[x + dx][y + dy] == "#":
# turn right
idx = (idx + 1) % len(adj)
q.append((x, y, idx))
else:
# move
q.append((x + dx, y + dy, idx))
print(len(visited))
num_obstructions = 0
for i, j in visited:
if i == sx and j == sy:
continue
visited = set([])
idx = 0
q = deque([(sx, sy, idx)])
while q:
x, y, idx = q.popleft()
dx, dy = adj[idx]
if (x, y, idx) in visited:
num_obstructions += 1
break
visited.add((x, y, idx))
if not (0 <= x + dx < len(grid) and 0 <= y + dy < len(grid[0])):
break
if grid[x + dx][y + dy] == "#" or (x + dx == i and y + dy == j):
idx = (idx + 1) % len(adj)
q.append((x, y, idx))
else:
q.append((x + dx, y + dy, idx))
print(num_obstructions)
2024 Day 05 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
| from collections import defaultdict
def reorder(elements, rules):
out = []
while len(out) != len(elements):
for e in elements:
if e not in out:
if all(x in out or x not in elements for x in rules[e]):
out.append(e)
break
return out
def mid(list):
return list[len(list) // 2]
lines = open("input").read().strip().split("\n\n")
rules = defaultdict(list)
for line in lines[0].split("\n"):
a,b = line.split("|")
rules[b].append (a)
# for a given page 'b', returns a list of pages 'a' that go before.
updates = lines[1].split("\n")
p1 = 0
p2 = 0
for update in updates:
pages = update.split(",")
if pages == reorder(pages, rules):
p1 += int(mid(pages))
else:
p2 += int(mid(reorder(pages, rules)))
print("Part 1: " + str(p1))
print("Part 2: " + str(p2)) |
from collections import defaultdict
def reorder(elements, rules):
out = []
while len(out) != len(elements):
for e in elements:
if e not in out:
if all(x in out or x not in elements for x in rules[e]):
out.append(e)
break
return out
def mid(list):
return list[len(list) // 2]
lines = open("input").read().strip().split("\n\n")
rules = defaultdict(list)
for line in lines[0].split("\n"):
a,b = line.split("|")
rules[b].append (a)
# for a given page 'b', returns a list of pages 'a' that go before.
updates = lines[1].split("\n")
p1 = 0
p2 = 0
for update in updates:
pages = update.split(",")
if pages == reorder(pages, rules):
p1 += int(mid(pages))
else:
p2 += int(mid(reorder(pages, rules)))
print("Part 1: " + str(p1))
print("Part 2: " + str(p2))
2024 Day 04 Part 02
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| grid = open("input").read().splitlines()
h = len(grid)
w = len(grid[0])
candidates = []
score = 0
# find all coords that contain letter "A"
# stay 1 character away from the boundary
for i in range(1,h-1):
for j in range(1,w-1):
if grid[i][j] == "A":
candidates.append((i,j))
print(candidates)
for i,j in candidates:
if (grid[i-1][j-1] == "S" and grid[i+1][j+1] == "M") or (grid[i-1][j-1] == "M" and grid[i+1][j+1] == "S"):
if (grid[i+1][j-1] == "S" and grid[i-1][j+1] == "M") or (grid[i+1][j-1] == "M" and grid[i-1][j+1] == "S"):
score+=1
print(score) |
grid = open("input").read().splitlines()
h = len(grid)
w = len(grid[0])
candidates = []
score = 0
# find all coords that contain letter "A"
# stay 1 character away from the boundary
for i in range(1,h-1):
for j in range(1,w-1):
if grid[i][j] == "A":
candidates.append((i,j))
print(candidates)
for i,j in candidates:
if (grid[i-1][j-1] == "S" and grid[i+1][j+1] == "M") or (grid[i-1][j-1] == "M" and grid[i+1][j+1] == "S"):
if (grid[i+1][j-1] == "S" and grid[i-1][j+1] == "M") or (grid[i+1][j-1] == "M" and grid[i-1][j+1] == "S"):
score+=1
print(score)
2024 Day 04 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
| # https://www.geeksforgeeks.org/search-a-word-in-a-2d-grid-of-characters/
# Python program to search word in 2D grid in 8 directions
# Modified to search for multiple occurances for each grid point
ans = []
# This function searches for the given word
# in all 8 directions from the coordinate.
def search2D(grid, row, col, word):
global ans
h = len(grid)
w = len(grid[0])
# return false if the given coordinate
# does not match with first index char.
if grid[row][col] != word[0]:
return False
lenWord = len(word)
# x and y are used to set the direction in which
# word needs to be searched.
x = [-1, -1, -1, 0, 0, 1, 1, 1]
y = [-1, 0, 1, -1, 1, -1, 0, 1]
# This loop will search in all the 8 directions
# one by one. It will return true if one of the
# directions contain the word.
for dir in range(8):
# Initialize starting point for current direction
currX, currY = row + x[dir], col + y[dir]
k = 1
while k < lenWord:
# break if out of bounds
if currX >= h or currX < 0 or currY >= w or currY < 0:
break
# break if characters dont match
if grid[currX][currY] != word[k]:
break
# Moving in particular direction
currX += x[dir]
currY += y[dir]
k += 1
# If all character matched, then value of must
# be equal to length of word
if k == lenWord:
ans.append((row, col))
grid = open("input").read().splitlines()
word = "XMAS"
h = len(grid)
w = len(grid[0])
for i in range(h):
for j in range(w):
search2D(grid, i, j, word)
#print(ans)
print(len(ans)) |
# https://www.geeksforgeeks.org/search-a-word-in-a-2d-grid-of-characters/
# Python program to search word in 2D grid in 8 directions
# Modified to search for multiple occurances for each grid point
ans = []
# This function searches for the given word
# in all 8 directions from the coordinate.
def search2D(grid, row, col, word):
global ans
h = len(grid)
w = len(grid[0])
# return false if the given coordinate
# does not match with first index char.
if grid[row][col] != word[0]:
return False
lenWord = len(word)
# x and y are used to set the direction in which
# word needs to be searched.
x = [-1, -1, -1, 0, 0, 1, 1, 1]
y = [-1, 0, 1, -1, 1, -1, 0, 1]
# This loop will search in all the 8 directions
# one by one. It will return true if one of the
# directions contain the word.
for dir in range(8):
# Initialize starting point for current direction
currX, currY = row + x[dir], col + y[dir]
k = 1
while k < lenWord:
# break if out of bounds
if currX >= h or currX < 0 or currY >= w or currY < 0:
break
# break if characters dont match
if grid[currX][currY] != word[k]:
break
# Moving in particular direction
currX += x[dir]
currY += y[dir]
k += 1
# If all character matched, then value of must
# be equal to length of word
if k == lenWord:
ans.append((row, col))
grid = open("input").read().splitlines()
word = "XMAS"
h = len(grid)
w = len(grid[0])
for i in range(h):
for j in range(w):
search2D(grid, i, j, word)
#print(ans)
print(len(ans))
2024 Day 03 Part 02
If there are any capturing groups in the regular expression e.g. (…) then re.findall returns only the values captured by the groups. If there are no groups the entire matched string is returned.
1
2
3
4
5
6
7
8
9
10
11
12
13
| import re
line = open("input").read().strip()
mulsenable = True
score = 0
for match in re.finditer(r"mul\((\d{1,3}),(\d{1,3})\)|do\(\)|don\'t\(\)", line):
if match.group() == "don't()":
mulsenable = False
elif match.group() == "do()":
mulsenable = True
else:
if mulsenable:
score += int(match.group(1)) * int(match.group(2))
print(score) |
import re
line = open("input").read().strip()
mulsenable = True
score = 0
for match in re.finditer(r"mul\((\d{1,3}),(\d{1,3})\)|do\(\)|don\'t\(\)", line):
if match.group() == "don't()":
mulsenable = False
elif match.group() == "do()":
mulsenable = True
else:
if mulsenable:
score += int(match.group(1)) * int(match.group(2))
print(score)
2024 Day 03 Part 01
1
2
3
4
| import re
line = open("input").read().strip()
muls = re.findall(r"mul\((\d{1,3}),(\d{1,3})\)", line)
print(sum(int(x) * int(y) for x,y in muls)) |
import re
line = open("input").read().strip()
muls = re.findall(r"mul\((\d{1,3}),(\d{1,3})\)", line)
print(sum(int(x) * int(y) for x,y in muls))
2024 Day 02 Part 02
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| lines = open("input").read().splitlines()
lines = [list(map(int, line.split())) for line in lines]
def is_safe(nums):
gaps = [abs(b-a) for a, b in zip(nums, nums[1:])]
if (nums == sorted(nums)) or (nums == sorted(nums,reverse = True)):
if min(gaps) >= 1 and max(gaps) <= 3:
return True
return False
safe = 0
nums = []
for line in lines:
for i in range (0, len(line)):
nums = line.copy()
nums.pop(i)
if is_safe(nums):
safe += 1
break
print(safe) |
lines = open("input").read().splitlines()
lines = [list(map(int, line.split())) for line in lines]
def is_safe(nums):
gaps = [abs(b-a) for a, b in zip(nums, nums[1:])]
if (nums == sorted(nums)) or (nums == sorted(nums,reverse = True)):
if min(gaps) >= 1 and max(gaps) <= 3:
return True
return False
safe = 0
nums = []
for line in lines:
for i in range (0, len(line)):
nums = line.copy()
nums.pop(i)
if is_safe(nums):
safe += 1
break
print(safe)
2024 Day 02 Part 01
1
2
3
4
5
6
7
8
9
| lines = open("input").read().splitlines()
lines = [list(map(int, line.split())) for line in lines]
safe = 0
for line in lines:
gaps = [abs(b-a) for a, b in zip(line, line[1:])]
if (line == sorted(line)) or (line == sorted(line,reverse = True)):
if min(gaps) >= 1 and max(gaps) <= 3:
safe += 1
print (safe) |
lines = open("input").read().splitlines()
lines = [list(map(int, line.split())) for line in lines]
safe = 0
for line in lines:
gaps = [abs(b-a) for a, b in zip(line, line[1:])]
if (line == sorted(line)) or (line == sorted(line,reverse = True)):
if min(gaps) >= 1 and max(gaps) <= 3:
safe += 1
print (safe)
2024 Day 01 Part 02
1
2
3
4
| lines = open("input").read().splitlines()
lines = [map(int, line.split()) for line in lines]
listx, listy = zip(*lines)
print(sum(x * listy.count(x) for x in listx)) |
lines = open("input").read().splitlines()
lines = [map(int, line.split()) for line in lines]
listx, listy = zip(*lines)
print(sum(x * listy.count(x) for x in listx))
2024 Day 01 Part 02
1
2
3
4
5
6
7
8
9
10
| lines = open("input").read().splitlines()
listx, listy = [], []
for line in lines:
x, y = line.split()
listx.append(int(x))
listy.append(int(y))
score = 0
for x in listx:
score += x * listy.count(x)
print(score) |
lines = open("input").read().splitlines()
listx, listy = [], []
for line in lines:
x, y = line.split()
listx.append(int(x))
listy.append(int(y))
score = 0
for x in listx:
score += x * listy.count(x)
print(score)
2024 Day 01 Part 01
1
2
3
4
5
6
7
8
9
10
11
12
| lines = open("input").read().splitlines()
listx, listy = [], []
for line in lines:
x, y = line.split()
listx.append(int(x))
listy.append(int(y))
listx = sorted(listx)
listy = sorted(listy)
dist = 0
for i, x in enumerate(listx):
dist += abs(x - listy[i])
print(dist) |
lines = open("input").read().splitlines()
listx, listy = [], []
for line in lines:
x, y = line.split()
listx.append(int(x))
listy.append(int(y))
listx = sorted(listx)
listy = sorted(listy)
dist = 0
for i, x in enumerate(listx):
dist += abs(x - listy[i])
print(dist)