aoc2023/d11.py

112 lines
2.5 KiB
Python

import lib
EXAMPLE = """
...#......
.......#..
#.........
..........
......#...
.#........
.........#
..........
.......#..
#...#.....
"""
def mdist(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def solve(lines: list[str]):
res = 0
g = list(map(list, lines))
er = []
for (i, r) in enumerate(g):
if "#" not in r:
er.append(i)
ec = []
for j in range(len(g[0])):
for row in g:
if "#" == row[j]:
break
else:
ec.append(j)
for r in reversed(er):
g.insert(r, ["." for _ in range(len(g[0]))])
for row in g:
for c in reversed(ec):
row.insert(c, ".")
# for row in g:
# print("".join(row))
gxs = []
for (row, line) in enumerate(g):
for (col, c) in enumerate(line):
if c == '#':
gxs.append((row, col))
for i in range(len(gxs)):
for j in range(i, len(gxs)):
a, b = gxs[i], gxs[j]
d = mdist(a, b)
# print(a, b, d)
res += d
# 16:00
return res
def solve2(lines: list[str], factor):
res = 0
g = list(map(list, lines))
gxs = []
for (row, line) in enumerate(g):
for (col, c) in enumerate(line):
if c == '#':
gxs.append((row, col, row, col))
for (row_i, row) in enumerate(g):
if "#" not in row:
for i in range(len(gxs)):
row, col, orig_row, orig_col = gxs[i]
if orig_row > row_i:
gxs[i] = (row + factor, col, orig_row, orig_col)
for col_j in range(len(g[0])):
for row in g:
if "#" == row[col_j]:
break
else:
for i in range(len(gxs)):
row, col, orig_row, orig_col = gxs[i]
if orig_col > col_j:
gxs[i] = (row, col + factor, orig_row, orig_col)
for i in range(len(gxs)):
for j in range(i, len(gxs)):
a, b = gxs[i], gxs[j]
d = mdist(a, b)
# print(a, b, d)
res += d
# 16:00
return res
def main():
lines = lib.str_to_lines_no_empty(EXAMPLE)
print("Example 1:", solve(lines))
lines = lib.str_to_lines_no_empty(open("i11.txt").read())
print("Solution 1:", solve(lines))
lines = lib.str_to_lines_no_empty(EXAMPLE)
print("Example 2:", solve2(lines, 99))
lines = lib.str_to_lines_no_empty(open("i11.txt").read())
print("Solution 2:", solve2(lines, 10**6 - 1))
if __name__ == "__main__":
main()