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 To be uploaded still.
2024 Day 25 Part 01 + 02
2024 Day 24 Part 01 + 02
2024 Day 23 Part 01 + 02
2024 Day 22 Part 01 + 02
2024 Day 21 Part 01 + 02
2024 Day 20 Part 01 + 02
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)
