69 lines
1.8 KiB
Python
69 lines
1.8 KiB
Python
|
#!/usr/bin/env python
|
||
|
|
# 2023 - Advent Of Code 11 - part 2
|
||
|
|
|
||
|
|
# file = 'input_example.txt'
|
||
|
|
file = 'input.txt'
|
||
|
|
EXPANSION = 1000000
|
||
|
|
|
||
|
|
# pylint: disable=consider-using-with
|
||
|
|
input_lines = [line.strip('\n') for line in open(file, encoding="utf-8")]
|
||
|
|
print(f'map: ({len(input_lines[0])}, {len(input_lines)})')
|
||
|
|
|
||
|
|
stars = []
|
||
|
|
for y, _ in enumerate(input_lines):
|
||
|
|
for x in range(0, len(_)):
|
||
|
|
# pylint: disable=unnecessary-list-index-lookup
|
||
|
|
if input_lines[y][x] == '#':
|
||
|
|
stars.append((x, y))
|
||
|
|
print(f'stars: {len(stars)}, map: ({len(input_lines[0])}, {len(input_lines)})')
|
||
|
|
|
||
|
|
# find empty lines
|
||
|
|
empty_lines = []
|
||
|
|
for y, _ in enumerate(input_lines):
|
||
|
|
if '#' not in input_lines[y]:
|
||
|
|
empty_lines.append(y)
|
||
|
|
print(f'empty lines: {empty_lines}')
|
||
|
|
|
||
|
|
# find empty columns
|
||
|
|
empty_columns = []
|
||
|
|
for x in range(0, len(input_lines[0])):
|
||
|
|
empty = True
|
||
|
|
for y, _ in enumerate(input_lines):
|
||
|
|
if input_lines[y][x] == '#':
|
||
|
|
empty = False
|
||
|
|
break
|
||
|
|
if empty:
|
||
|
|
empty_columns.append(x)
|
||
|
|
print(f'empty columns: {empty_columns}')
|
||
|
|
|
||
|
|
paths = []
|
||
|
|
for s1 in stars:
|
||
|
|
for s2 in stars:
|
||
|
|
if s1 != s2 and {s1, s2} not in paths:
|
||
|
|
paths.append({s1, s2})
|
||
|
|
print(f'number of paths: {len(paths)}')
|
||
|
|
|
||
|
|
|
||
|
|
# instead of extending the map, offset star coordinates
|
||
|
|
def expand_coord(num, compare_list):
|
||
|
|
i = 0
|
||
|
|
for i, star in enumerate(compare_list):
|
||
|
|
if num < star:
|
||
|
|
return i * (EXPANSION-1) + num
|
||
|
|
return (i+1) * (EXPANSION-1) + num
|
||
|
|
|
||
|
|
|
||
|
|
# dist = math.abs(x2-x1) + math.abs(y2-y1)
|
||
|
|
sum_path = 0
|
||
|
|
for path in paths:
|
||
|
|
p = list(path)
|
||
|
|
x1 = expand_coord(p[0][0], empty_columns)
|
||
|
|
x2 = expand_coord(p[1][0], empty_columns)
|
||
|
|
y1 = expand_coord(p[0][1], empty_lines)
|
||
|
|
y2 = expand_coord(p[1][1], empty_lines)
|
||
|
|
dist = abs(x1 - x2) + abs(y1 - y2)
|
||
|
|
sum_path += dist
|
||
|
|
print(f'{path} dist: {dist}')
|
||
|
|
|
||
|
|
print(f'{sum_path=}')
|