Part 1
This seems easier than the last one. The shortest path might sound tricky — my first impression was that some path-finding algorithm would be needed — but since this is all on a 2-dimensional grid, the shortest-path is equal to taking the x-step difference and the y-step difference between two points. In the example,
.5...........
.##.........6
..##.........
...##........
....##...7...
8....9.......this looks weird, but in fact it corresponds to
.5####.......
.....#......6
.....#.......
.....#.......
.....#...7...
8....9.......which makes it much easier! The distance between any two points is equal to the sum of the absolute value of the differences between their coordinates.
There's another detail, however, regarding the lines and columns without galaxies. I'd like to avoid unnecessarily expanding the input data, which is already quite big. I suppose one could just take the indices of those lines and columns, and put them in an ordered list. And then, when calculating the difference between any coordinates, one could count the amount of indices that are contained in the range of differences.
Tests
class Test202311_01(unittest.TestCase):
def test_can_get_data_from_input(self):
self.assertEqual(
get_data_from_input(TEST_DATA),
['...#......',
'.......#..',
'#.........',
'..........',
'......#...',
'.#........',
'.........#',
'..........',
'.......#..',
'#...#.....']
)
def test_can_get_indices_of_galaxyless_lines(self):
galaxymap = get_data_from_input(TEST_DATA)
self.assertEqual(
get_galaxyless_lines(galaxymap),
[3, 7]
)
def test_can_get_indices_of_galaxyless_columns(self):
galaxymap = get_data_from_input(TEST_DATA)
self.assertEqual(
get_galaxyless_columns(galaxymap),
[2, 5, 8]
)
def test_collecting_of_galaxy_coordinates(self):
galaxymap = get_data_from_input(TEST_DATA)
self.assertEqual(
collect_galaxy_coordinates(
galaxymap, 0, []),
[(0, 3), (1, 7), (2, 0), (4, 6),
(5, 1), (6, 9), (8, 7), (9, 0), (9, 4)]
)
def test_all_possible_combinations_of_two_galaxies(self):
galaxymap = get_data_from_input(TEST_DATA)
galaxies = collect_galaxy_coordinates(galaxymap, 0, [])
self.assertEqual(
len(get_all_possible_combinations_of_two_galaxies(galaxies)),
sum(range(1, 9))
)
def test_distance_between_galaxies(self):
galaxymap = get_data_from_input(TEST_DATA)
pair_of_galaxies = [(1, 7), (2, 0)]
self.assertEqual(
get_distance_between_two_galaxies(
*pair_of_galaxies,
[get_galaxyless_columns(galaxymap),
get_galaxyless_lines(galaxymap)]),
10
)
pair_of_galaxies = [(0, 3), (2, 0)]
self.assertEqual(
get_distance_between_two_galaxies(
*pair_of_galaxies,
[get_galaxyless_columns(galaxymap),
get_galaxyless_lines(galaxymap)]),
6
)
def test_solve_part_one(self):
self.assertEqual(
solve_part_one(TEST_DATA),
374
)
if __name__ == '__main__':
unittest.main()
What most troubles me in my approach is the innefficiency in looking up the lines or columns that are between any two points whose distance is being calculated. I'm not taking advantage of the array being ordered. It runs quickly, though, so maybe that's not an issue at all.
Code
from itertools import combinations
def get_data_from_input(data: str) -> list[str]:
return data.strip().split("\n")
def get_galaxyless_lines(galaxymap: list[str]) -> list[int]:
return [i for i, line in enumerate(galaxymap)
if "#" not in line]
def get_galaxyless_columns(galaxymap: list[str]) -> list[int]:
return [i for i, column in enumerate(zip(*galaxymap))
if "#" not in column]
# recursively iterates over the galaxymap
# and collects the coordinates
def collect_galaxy_coordinates(
galaxymap: list[str],
index: int,
coordinates) -> list[tuple[int, int]]:
if not galaxymap:
return coordinates
return collect_galaxy_coordinates(
galaxymap[1:],
index + 1,
coordinates + [(index, i) for i, _ in enumerate(galaxymap[0])
if galaxymap[0][i] == '#']
)
def get_all_possible_combinations_of_two_galaxies(
galaxies: list[tuple[int, int]]
) -> list[tuple[tuple[int, int], tuple[int, int]]]:
return list(combinations(galaxies, 2))
def get_distance_between_two_galaxies(
first: tuple[int, int],
second: tuple[int, int],
indices_of_galaxy_expansions: list[list[int]]) -> int:
vertical, horizontal = indices_of_galaxy_expansions
# galaxies are ordered by their x coordinate;
# the first galaxy of the pair is necessarily above
count_horizontal_expansion = len([i for i in horizontal
if first[0] < i < second[0]])
# on the vertical case, there's no such ordering;
# thus we figure which galaxy is to the left
left, right = ([first[1], second[1]] if first[1] < second[1]
else [second[1], first[1]])
count_vertical_expansion = len([i for i in vertical
if left < i < right])
return (abs(first[0] - second[0]) + count_horizontal_expansion * 999999 +
abs(first[1] - second[1]) + count_vertical_expansion * 999999)
def solve_part_one(data: str) -> int:
galaxymap = get_data_from_input(data)
coordinates = collect_galaxy_coordinates(galaxymap, 0, [])
all_pairs = get_all_possible_combinations_of_two_galaxies(coordinates)
galaxyless_info = [
get_galaxyless_columns(galaxymap),
get_galaxyless_lines(galaxymap),
]
return sum(map(lambda pair: get_distance_between_two_galaxies(
*pair, galaxyless_info
),
all_pairs
))
if __name__ == "__main__":
print(solve_part_one(open("input").read()))Part 2
It's nice that Part 2 completely validated my approach. In fact, I think I'd solve it in leaderboard time, had I not made the mistake of substituting 1 for 1000000 - it should be 999999...
I did not do any tests at all. In fact, I just changed the Part 1 code.
Code
def get_distance_between_two_galaxies(
first: tuple[int, int],
second: tuple[int, int],
indices_of_galaxy_expansions: list[list[int]]) -> int:
vertical, horizontal = indices_of_galaxy_expansions
# galaxies are ordered by their x coordinate;
# the first galaxy of the pair is necessarily above
count_horizontal_expansion = len([i for i in horizontal
if first[0] < i < second[0]])
# on the vertical case, there's no such ordering;
# thus we figure which galaxy is to the left
left, right = ([first[1], second[1]] if first[1] < second[1]
else [second[1], first[1]])
count_vertical_expansion = len([i for i in vertical
if left < i < right])
return (abs(first[0] - second[0]) + count_horizontal_expansion * 999999 +
abs(first[1] - second[1]) + count_vertical_expansion * 999999)