aoc/2023/original_solutions/day11.py at master · mebeim/aoc · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#!/usr/bin/env python3

from utils.all import *

advent.setup(2023, 11)
fin = advent.get_input()

grid = read_char_matrix(fin)
newgrid = []
insert = []
original = deepcopy(grid)

for c in range(len(grid[0])):
	if all(grid[r][c] == '.' for r in range(len(grid))):
		insert.append(c + len(insert))

for c in insert:
	for row in grid:
		row.insert(c, '.')

for r, row in enumerate(grid):
	newgrid.append(row[:])
	if set(row) == {'.'}:
		newgrid.append(row[:])

grid = newgrid

g = graph_from_grid(newgrid, '#', '.', True)
ks = list(g.keys())
ans = 0

for i, src in enumerate(ks):
	for dst in ks[i+1:]:
		a = Vec(*src[:2])
		b = Vec(*dst[:2])
		d = a - b
		ans += abs(d.r) + abs(d.c)

advent.print_answer(1, ans)


vertical = []
horizontal = []
expansion = 1000000 - 1
grid = original

for c in range(len(grid[0])):
	if all(grid[r][c] == '.' for r in range(len(grid))):
		vertical.append(c)

for r, row in enumerate(grid):
	if set(row) == {'.'}:
		horizontal.append(r)

ans = 0
g = graph_from_grid(original, '#', '.', True)
ks = list(g.keys())

for i, src in enumerate(ks):
	for dst in ks[i+1:]:
		a = Vec(*src[:2])
		b = Vec(*dst[:2])

		rfrom, rto = min(a.r, b.r), max(a.r, b.r)
		cfrom, cto = min(a.c, b.c), max(a.c, b.c)
		d = rto - rfrom + cto - cfrom

		for h in horizontal:
			if h >= rto:
				break
			if rfrom < h < rto:
				d += expansion

		for v in vertical:
			if v >= cto:
				break
			if cfrom < v < cto:
				d += expansion

		ans += d

advent.print_answer(2, ans)