[Day 11] Cosmic Expansion // Advent of Code 2023 (Python)
Part One
You continue following signs for “Hot Springs” and eventually come across an observatory. The Elf within turns out to be a researcher studying cosmic expansion using the giant telescope here.
He doesn’t know anything about the missing machine parts; he’s only visiting for this research project. However, he confirms that the hot springs are the next-closest area likely to have people; he’ll even take you straight there once he’s done with today’s observation analysis.
Maybe you can help him with the analysis to speed things up?
The researcher has collected a bunch of data and compiled the data into a single giant image (your puzzle input). The image includes empty space (
.) and galaxies (#). For example:...#......
.......#..
#.........
..........
......#...
.#........
.........#
..........
.......#..
#...#.....The researcher is trying to figure out the sum of the lengths of the shortest path between every pair of galaxies. However, there’s a catch: the universe expanded in the time it took the light from those galaxies to reach the observatory.
Due to something involving gravitational effects, only some space expands. In fact, the result is that any rows or columns that contain no galaxiesshould all actually be twice as big.
In the above example, three columns and two rows contain no galaxies:
v v v
...#......
.......#..
#.........
>..........<
......#...
.#........
.........#
>..........<
.......#..
#...#.....
^ ^ ^These rows and columns need to be twice as big; the result of cosmic expansion therefore looks like this:
....#........
.........#...
#............
.............
.............
........#....
.#...........
............#
.............
.............
.........#...
#....#.......Equipped with this expanded universe, the shortest path between every pair of galaxies can be found. It can help to assign every galaxy a unique number:
....1........
.........2...
3............
.............
.............
........4....
.5...........
............6
.............
.............
.........7...
8....9.......In these 9 galaxies, there are 36 pairs. Only count each pair once; order within the pair doesn’t matter. For each pair, find any shortest path between the two galaxies using only steps that move up, down, left, or right exactly one
.or#at a time. (The shortest path between two galaxies is allowed to pass through another galaxy.)For example, here is one of the shortest paths between galaxies
5and9:....1........
.........2...
3............
.............
.............
........4....
.5...........
.##.........6
..##.........
...##........
....##...7...
8....9.......This path has length
9because it takes a minimum of nine steps to get from galaxy5to galaxy9(the eight locations marked#plus the step onto galaxy9itself). Here are some other example shortest path lengths:Between galaxy
1and galaxy7: 15Between galaxy
3and galaxy6: 17Between galaxy
8and galaxy9: 5In this example, after expanding the universe, the sum of the shortest path between all 36 pairs of galaxies is
374.Expand the universe, then find the length of the shortest path between every pair of galaxies. What is the sum of these lengths?
Finally! A space exploration problem. I am a sucker for those!
So, let’s look at the problem, we have an image of space from the observatory and it looks something like this:
...#......
.......#..
#.........
..........
......#...
.#........
.........#
..........
.......#..
#...#.....And we need to compute the sum of the lengths of the shortest path between every pair of galaxies!
❗️The catch being, that by the time light reaches to us, the space expands due to ever expanding universe, but only some part, resulting in any rows or columns that contain no galaxies should all actually be twice as big.
Let’s visualise this?
Once we have the final image! We can just number the galaxies like:
And then we can just find the shortest distance from each pair of galaxies!
Seems pretty straight forward right? Let’s code!
As usual, I will begin with writing our base case as the ultimate validator!
And now let’s start expanding! It’s clear we first need to expand space by finding empty rows and columns and doubling it. So, let’s first just do that.
Here’s a simple function expand_space that just does that:
💡 Caught a bug, as if we modify the
space_mapwhile iterating through it, theempty_rowselements start to point to an incorrect index. To fix that, we can just introduce something like amod_countwhich can help us keep a track of originalindexin modifiedspace_map.
Now we can find all the galaxies locations in the expanded_space_map with a simple function:
💭 The last step is to now take 1 galaxy and find its shortest distance from all other galaxies and then repeat this process for all galaxies!
Well, before even touching the code, I can already see a lot of steps to optimise this one! For example: If we have found the shortest distance from Galaxy_1 to Galaxy_2 , it will be same other way around, so we can save extra compute by just refering to a cache.
....1........
.........2...
3............
.............
.............
........4....
.5...........
............6
.............
.............
.........7...
8....9.......So, in case of this example, where we have 9 galaxies can could have 81 combinations, since we can’t repeat a pair, the formula becomes:
Number of combinations= n! / r!(n−r)!
Solving for our case:
9C2 = 9! / 2!(9−2)! = 36
36 combinations!
Let’s write some code? I will be using good’ol BFS (breadth first search) to find the shortest path for each pair of galaxies. We may come back and optimise this to a more greedy approach for faster computation!
We can always hash a tupple though! ;)
Finally after a lot of iterations:
Let’s check our test case now?
Here’s our MVP code till now:
# Day 11: Cosmic Expansion
from enum import Enum
EMPTY_SPACE = "."
GALAXY = "#"
DISTANCE_MAP = {}
class Direction(Enum):
RIGHT = (0, 1)
LEFT = (0, -1)
DOWN = (1, 0)
UP = (-1, 0)
def expand_space_map(space_map):
empty_rows, empty_cols = [], []
for i, row in enumerate(space_map):
if GALAXY not in row:
empty_rows.append(i)
for i, col in enumerate(space_map[0]):
if GALAXY not in [row[i] for row in space_map]:
empty_cols.append(i)
mod_count = 0
for i in empty_rows:
space_map.insert(i + mod_count, EMPTY_SPACE * len(space_map[i]))
mod_count += 1
mod_count = 0
for i in empty_cols:
for j, row in enumerate(space_map):
space_map[j] = row[: i + mod_count] + EMPTY_SPACE + row[i + mod_count :]
mod_count += 1
return space_map
def find_shortest_distance(galaxy1, galaxy2, space_map):
print(f"Finding shortest distance between {galaxy1} and {galaxy2}")
# check if the distance between the two galaxies is already calculated
distance = DISTANCE_MAP.get(galaxy1, {}).get(galaxy2) or DISTANCE_MAP.get(
galaxy2, {}
).get(galaxy1)
if distance:
return distance
# using BFS to find the shortest path between two galaxies
queue = [galaxy1] # initialize the queue with the starting galaxy
visited = set() # set to keep track of visited galaxies
distance = 0 # initialize the distance to 0
while queue:
for _ in range(len(queue)):
current = queue.pop(0) # get the next galaxy from the queue
if current == galaxy2: # if we reach the destination galaxy
if galaxy1 not in DISTANCE_MAP:
DISTANCE_MAP[galaxy1] = {}
DISTANCE_MAP[galaxy1][galaxy2] = distance # store the distance between the galaxies
return distance
visited.add(current) # mark the current galaxy as visited
for direction in Direction: # explore all possible directions
i, j = current[0] + direction.value[0], current[1] + direction.value[1]
if (
0 <= i < len(space_map)
and 0 <= j < len(space_map[0])
and (i, j) not in visited
):
queue.append((i, j)) # add the neighboring galaxy to the queue
distance += 1 # increment the distance after exploring all galaxies at the current level
raise Exception("No path found between the two galaxies")
def find_all_galaxies(space_map):
galaxies = []
for i, row in enumerate(space_map):
for j, col in enumerate(row):
if col == GALAXY:
galaxies.append((i, j))
return galaxies
def analyze_space(space_map):
expanded_space_map = expand_space_map(space_map)
print(f"Expanded space map is {len(expanded_space_map)} x {len(expanded_space_map[0])}")
galaxies_locations = find_all_galaxies(expanded_space_map)
print(f"Number of galaxies: {len(galaxies_locations)}")
for galaxy1 in galaxies_locations:
for galaxy2 in galaxies_locations:
if galaxy1 != galaxy2:
find_shortest_distance(galaxy1, galaxy2, expanded_space_map)
sum = 0
for k,v in DISTANCE_MAP.items():
for k1,v1 in v.items():
sum += v1
return sum
def part_one():
with open("day_11/input.txt") as f:
space_map = f.read().splitlines()
sum = analyze_space(space_map)
print(f"❗️ Sum of the lengths of the shortest path between every pair of galaxies: {sum}")
def test_analyze_space():
space_map = """...#......
.......#..
#.........
..........
......#...
.#........
.........#
..........
.......#..
#...#....."""
sum = analyze_space(space_map.splitlines())
assert sum == 374, f"Expected 374, got {sum}"
print("✅ Passed test_analyze_observation()")
if __name__ == "__main__":
test_analyze_space()
# part_one()[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_11/cosmic_expansion.py"
✅ Passed test_analyze_observation()
[Done] exited with code=0 in 7.131 secondsWell, it did took 7.131 seconds to compute for a simple testcase, let’s see if it can do it for puzzle input?
And compute!!
Let’s add some logging to understand the scale of the problem?
We have 426 Galaxies in a map of size 151 x 147 which gives us 426C2 combinations, equaling 90525 possible pairs! We need to make it more efficient!
While, I can take the easy path of just doings the Bi-directional BFS where I can look up from both Galaxy 1 and Galaxy 2, I feels it’s better to take a peak into A* or Dijkstra’s Algorithm for our shortest path finding to be more efficient!
I am bit rusty don’t remember A* algo exactly but I do remember that A* is a type of greedy approch which does a smart search through a maze, where at each step it makes an informed guess about the best next step based on how far it has already traveled and how far it still has to go, according to the map. It’s a blend of exploring and using what you know to make good guesses, which makes it efficient and effective for finding paths.
Let’s use Github Copilot to quickly generate a A* method for searching and then refactor it to suit our galaxy and space_map problem:
Now, let’s run for the base test case with our logging enabled?
[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_11/cosmic_expansion.py"
Expanded space map is 12 x 13
Number of galaxies: 9
Finding shortest distance between (0, 4) and (1, 9)
Finding shortest distance between (0, 4) and (2, 0)
Finding shortest distance between (0, 4) and (5, 8)
Finding shortest distance between (0, 4) and (6, 1)
Finding shortest distance between (0, 4) and (7, 12)
Finding shortest distance between (0, 4) and (10, 9)
Finding shortest distance between (0, 4) and (11, 0)
Finding shortest distance between (0, 4) and (11, 5)
Finding shortest distance between (1, 9) and (0, 4)
Finding shortest distance between (1, 9) and (2, 0)
Finding shortest distance between (1, 9) and (5, 8)
Finding shortest distance between (1, 9) and (6, 1)
Finding shortest distance between (1, 9) and (7, 12)
Finding shortest distance between (1, 9) and (10, 9)
Finding shortest distance between (1, 9) and (11, 0)
Finding shortest distance between (1, 9) and (11, 5)
Finding shortest distance between (2, 0) and (0, 4)
Finding shortest distance between (2, 0) and (1, 9)
Finding shortest distance between (2, 0) and (5, 8)
Finding shortest distance between (2, 0) and (6, 1)
Finding shortest distance between (2, 0) and (7, 12)
Finding shortest distance between (2, 0) and (10, 9)
Finding shortest distance between (2, 0) and (11, 0)
Finding shortest distance between (2, 0) and (11, 5)
Finding shortest distance between (5, 8) and (0, 4)
Finding shortest distance between (5, 8) and (1, 9)
Finding shortest distance between (5, 8) and (2, 0)
Finding shortest distance between (5, 8) and (6, 1)
Finding shortest distance between (5, 8) and (7, 12)
Finding shortest distance between (5, 8) and (10, 9)
Finding shortest distance between (5, 8) and (11, 0)
Finding shortest distance between (5, 8) and (11, 5)
Finding shortest distance between (6, 1) and (0, 4)
Finding shortest distance between (6, 1) and (1, 9)
Finding shortest distance between (6, 1) and (2, 0)
Finding shortest distance between (6, 1) and (5, 8)
Finding shortest distance between (6, 1) and (7, 12)
Finding shortest distance between (6, 1) and (10, 9)
Finding shortest distance between (6, 1) and (11, 0)
Finding shortest distance between (6, 1) and (11, 5)
Finding shortest distance between (7, 12) and (0, 4)
Finding shortest distance between (7, 12) and (1, 9)
Finding shortest distance between (7, 12) and (2, 0)
Finding shortest distance between (7, 12) and (5, 8)
Finding shortest distance between (7, 12) and (6, 1)
Finding shortest distance between (7, 12) and (10, 9)
Finding shortest distance between (7, 12) and (11, 0)
Finding shortest distance between (7, 12) and (11, 5)
Finding shortest distance between (10, 9) and (0, 4)
Finding shortest distance between (10, 9) and (1, 9)
Finding shortest distance between (10, 9) and (2, 0)
Finding shortest distance between (10, 9) and (5, 8)
Finding shortest distance between (10, 9) and (6, 1)
Finding shortest distance between (10, 9) and (7, 12)
Finding shortest distance between (10, 9) and (11, 0)
Finding shortest distance between (10, 9) and (11, 5)
Finding shortest distance between (11, 0) and (0, 4)
Finding shortest distance between (11, 0) and (1, 9)
Finding shortest distance between (11, 0) and (2, 0)
Finding shortest distance between (11, 0) and (5, 8)
Finding shortest distance between (11, 0) and (6, 1)
Finding shortest distance between (11, 0) and (7, 12)
Finding shortest distance between (11, 0) and (10, 9)
Finding shortest distance between (11, 0) and (11, 5)
Finding shortest distance between (11, 5) and (0, 4)
Finding shortest distance between (11, 5) and (1, 9)
Finding shortest distance between (11, 5) and (2, 0)
Finding shortest distance between (11, 5) and (5, 8)
Finding shortest distance between (11, 5) and (6, 1)
Finding shortest distance between (11, 5) and (7, 12)
Finding shortest distance between (11, 5) and (10, 9)
Finding shortest distance between (11, 5) and (11, 0)
✅ Passed test_analyze_observation()
[Done] exited with code=0 in 0.121 secondsWoah! 0.121 seconds for the base test case. Comparing this to our previous BFS approach that took 7.131 seconds to churn out the answers, A* approach is almost ~59x faster! 🚀
Let’s run for our puzzle input and go make a coffee! ☕️
.
.
.
[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_11/cosmic_expansion.py"
❗️ Sum of the lengths of the shortest path between every pair of galaxies: XXXXX
[Done] exited with code=0 in 982.651 secondsWell, this took only 982.651 seconds ~ 16.377 minutes to run! And this happened because I just ran it and went to make coffee and when I came back, I was it was somewhere around 148th row. Since, I knew we have a total 151 rows only, I just let it run!
Finding shortest distance between (148, 104) and (119, 66)
Finding shortest distance between (148, 104) and (119, 105)
Finding shortest distance between (148, 104) and (119, 116)So, let’s input our answer into the box and…
Here’s our unpythonic code till now, I will optimise it in Part 2:
# Day 11: Cosmic Expansion
from enum import Enum
import heapq
EMPTY_SPACE = "."
GALAXY = "#"
DISTANCE_MAP = {}
class Direction(Enum):
RIGHT = (0, 1)
LEFT = (0, -1)
DOWN = (1, 0)
UP = (-1, 0)
def calculate_distance(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1]) # Manhattan distance
def get_adjacent_galaxies(space_map, galaxy):
adjacent_galaxies = []
for direction in Direction:
i, j = galaxy[0] + direction.value[0], galaxy[1] + direction.value[1]
if 0 <= i < len(space_map) and 0 <= j < len(space_map[0]):
adjacent_galaxies.append((i, j))
return adjacent_galaxies
def find_shortest_path(space_map, start_galaxy, end_galaxy):
galaxies_to_visit = []
heapq.heappush(galaxies_to_visit, (0, start_galaxy))
previous_galaxy = {}
cost_to_reach = {start_galaxy: 0}
estimated_total_cost = {start_galaxy: calculate_distance(start_galaxy, end_galaxy)}
while galaxies_to_visit:
current_galaxy = heapq.heappop(galaxies_to_visit)[1]
if current_galaxy == end_galaxy:
return cost_to_reach[
current_galaxy
] # Return the cost to reach the end galaxy
for adjacent_galaxy in get_adjacent_galaxies(space_map, current_galaxy):
tentative_cost = cost_to_reach[current_galaxy] + 1 # assuming uniform cost
if (
adjacent_galaxy not in cost_to_reach
or tentative_cost < cost_to_reach[adjacent_galaxy]
):
previous_galaxy[adjacent_galaxy] = current_galaxy
cost_to_reach[adjacent_galaxy] = tentative_cost
estimated_total_cost[
adjacent_galaxy
] = tentative_cost + calculate_distance(adjacent_galaxy, end_galaxy)
heapq.heappush(
galaxies_to_visit,
(estimated_total_cost[adjacent_galaxy], adjacent_galaxy),
)
raise Exception("No path found between the two galaxies")
def expand_space_map(space_map):
empty_rows, empty_cols = [], []
for i, row in enumerate(space_map):
if GALAXY not in row:
empty_rows.append(i)
for i, col in enumerate(space_map[0]):
if GALAXY not in [row[i] for row in space_map]:
empty_cols.append(i)
mod_count = 0
for i in empty_rows:
space_map.insert(i + mod_count, EMPTY_SPACE * len(space_map[i]))
mod_count += 1
mod_count = 0
for i in empty_cols:
for j, row in enumerate(space_map):
space_map[j] = row[: i + mod_count] + EMPTY_SPACE + row[i + mod_count :]
mod_count += 1
return space_map
def find_shortest_distance(galaxy1, galaxy2, space_map):
print(f"Finding shortest distance between {galaxy1} and {galaxy2}")
distance = DISTANCE_MAP.get(galaxy1, {}).get(galaxy2) or DISTANCE_MAP.get(
galaxy2, {}
).get(galaxy1)
if distance:
return distance
distance = find_shortest_path(space_map, galaxy1, galaxy2) # Use A* for pathfinding
if galaxy1 not in DISTANCE_MAP:
DISTANCE_MAP[galaxy1] = {}
DISTANCE_MAP[galaxy1][galaxy2] = distance
return distance
def find_all_galaxies(space_map):
galaxies = []
for i, row in enumerate(space_map):
for j, col in enumerate(row):
if col == GALAXY:
galaxies.append((i, j))
return galaxies
def analyze_space(space_map):
expanded_space_map = expand_space_map(space_map)
print(
f"Expanded space map is {len(expanded_space_map)} x {len(expanded_space_map[0])}"
)
galaxies_locations = find_all_galaxies(expanded_space_map)
print(f"Number of galaxies: {len(galaxies_locations)}")
for galaxy1 in galaxies_locations:
for galaxy2 in galaxies_locations:
if galaxy1 != galaxy2:
find_shortest_distance(galaxy1, galaxy2, expanded_space_map)
sum = 0
for k, v in DISTANCE_MAP.items():
for k1, v1 in v.items():
sum += v1
return sum
def part_one():
with open("day_11/input.txt") as f:
space_map = f.read().splitlines()
sum = analyze_space(space_map)
print(
f"❗️ Sum of the lengths of the shortest path between every pair of galaxies: {sum}"
)
def test_analyze_space():
space_map = """...#......
.......#..
#.........
..........
......#...
.#........
.........#
..........
.......#..
#...#....."""
sum = analyze_space(space_map.splitlines())
assert sum == 374, f"Expected 374, got {sum}"
print("✅ Passed test_analyze_observation()")
if __name__ == "__main__":
# test_analyze_space()
part_one()Part Two
The galaxies are much older (and thus much farther apart) than the researcher initially estimated.
Now, instead of the expansion you did before, make each empty row or column one million times larger. That is, each empty row should be replaced with
1000000empty rows, and each empty column should be replaced with1000000empty columns.(In the example above, if each empty row or column were merely
10times larger, the sum of the shortest paths between every pair of galaxies would be1030. If each empty row or column were merely100times larger, the sum of the shortest paths between every pair of galaxies would be8410. However, your universe will need to expand far beyond these values.)Starting with the same initial image, expand the universe according to these new rules, then find the length of the shortest path between every pair of galaxies. What is the sum of these lengths?
Well, of course, the galaxies are much older!
So, looks like we need to update how we expand our space map buy a factor of one million times, that is, 1000000x, for each empty row and column!
Yep! Our current code will not scale at all. Probably our solar system sun will collapse into itself before our single threaded Python will be able to compute anything!
So…let’s rethink this!
.
.
Well shit! Why do I even need any path finding algo here? Isn’t this just simple matrix manipulation? I think I ended up doing over-engineering here! This is classic trap of being Principal Engineer, making problems look more complex than they actually are!
Revisting Part 1
This problem required solving just Manhattan distance between 2 nodes. Here’s an example to get distance between (Galaxy 1, Galaxy 4) and (Galaxy 5, Galaxy 8):
The formula to get this is absurdly simple as well:
Manhattan Distance = |x1 — y1| + |x2 — y2|
Which makes my code as simple as:
Solving for part 1, testing with base test case and puzzle input:
[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_11/cosmic_expansion.py"
Expanded space map is 12 x 13
Number of galaxies: 9
Number of possible pairs of galaxies: 36
✅ Passed test_analyze_observation()
Expanded space map is 151 x 147
Number of galaxies: 426
Number of possible pairs of galaxies: 90525
❗️ Sum of the lengths of the shortest path between every pair of galaxies: xxxxxx
[Done] exited with code=0 in 0.199 secondsYep, correct answer! 🥲
Back to Part 2
Now, all that is changing is, the expansion distance between pairs of galaxies.
💭 If we can somehow just find the number of rows + cols to be modified compared to initial galaxy, we can just do the computation on original space_map and then just increase the distance by a factor of 1000000
💡 We can further simplify our code by not having to do the expansion at all as per part 1
We can introduce a new param — expansion_factor which we can pass as 2 for the part one, and 1000000 for part two to keep our code modular.
Let’s update our base test case:
And let’s run this:
[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_11/cosmic_expansion.py"
✅ Passed test_analyze_observation() for expansion_factor=2
✅ Passed test_analyze_observation() for expansion_factor=10
✅ Passed test_analyze_observation() for expansion_factor=100Phew! We can now just load up our puzzle input and call for our 10⁶ expansion_factor :
Let’s run this up!
[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_11/cosmic_expansion.py"
✅ Passed test_analyze_observation() for expansion_factor=2
✅ Passed test_analyze_observation() for expansion_factor=10
✅ Passed test_analyze_observation() for expansion_factor=100
❗️ Sum of the lengths of the shortest path between every pair of galaxies for expansion_factor=2: xxxx
‼️ Sum of the lengths of the shortest path between every pair of galaxies for expansion_factor=1000000: xxxxxxxxxx
[Done] exited with code=0 in 0.843 secondsWe get the answer in 0.843 seconds….for BOTH the parts + 3 test cases! 😹
This is why I absolutely love coding!
Let’s put this answer in the input box and….profit!
Here’s our final pythonic yet highly performant code:
# Day 11: Cosmic Expansion
class CosmicGrid:
def __init__(self, space_grid):
# Initialize the cosmic grid with the provided space grid
self.space_grid = space_grid
self.grid_height = len(space_grid)
self.grid_width = len(space_grid[0])
# Find rows and columns that are entirely empty
self.empty_rows = self._find_empty_rows()
self.empty_columns = self._find_empty_columns()
# Locate all galaxies within the grid
self.galaxy_positions = self._find_galaxy_positions()
def _find_empty_rows(self):
# Identify rows that contain only empty space
empty_rows = set()
for row in range(self.grid_height):
if all(cell == '.' for cell in self.space_grid[row]):
empty_rows.add(row)
return empty_rows
def _find_empty_columns(self):
# Identify columns that contain only empty space
empty_columns = set()
for col in range(self.grid_width):
if all(self.space_grid[row][col] == '.' for row in range(self.grid_height)):
empty_columns.add(col)
return empty_columns
def _find_galaxy_positions(self):
# Record the positions of all galaxies in the grid
galaxy_positions = []
for row in range(self.grid_height):
for col in range(self.grid_width):
if self.space_grid[row][col] == '#':
galaxy_positions.append((row, col))
return galaxy_positions
def find_shortest_distance(self, galaxy1, galaxy2, expansion_factor):
# Calculate the shortest distance between two galaxies, factoring in cosmic expansion
row_distance = 0
for r in range(min(galaxy1[0], galaxy2[0]), max(galaxy1[0], galaxy2[0]) + 1):
if r in self.empty_rows:
row_distance += 1
col_distance = 0
for c in range(min(galaxy1[1], galaxy2[1]), max(galaxy1[1], galaxy2[1]) + 1):
if c in self.empty_columns:
col_distance += 1
# Expanded distance is calculated by multiplying empty distances by the expansion factor
# Direct distance is the straight line distance, not through empty space
expanded_row_distance = row_distance * expansion_factor
expanded_col_distance = col_distance * expansion_factor
direct_distance = abs(galaxy1[0] - galaxy2[0]) + abs(galaxy1[1] - galaxy2[1])
return expanded_row_distance + expanded_col_distance + direct_distance - row_distance - col_distance
def sum_of_shortest_paths(self, expansion_factor):
# Sum the shortest paths between all pairs of galaxies
total_distance = 0
for i, galaxy1 in enumerate(self.galaxy_positions):
for galaxy2 in self.galaxy_positions[i + 1:]:
total_distance += self.find_shortest_distance(galaxy1, galaxy2, expansion_factor)
return total_distance
def part_one():
with open("day_11/input.txt") as f:
space_map = f.read().splitlines()
cosmic_grid = CosmicGrid(space_map)
sum = cosmic_grid.sum_of_shortest_paths(expansion_factor=2)
print(
f"❗️ Sum of the lengths of the shortest path between every pair of galaxies for expansion_factor=2: {sum}"
)
def part_two():
with open("day_11/input.txt") as f:
space_map = f.read().splitlines()
cosmic_grid = CosmicGrid(space_map)
sum = cosmic_grid.sum_of_shortest_paths(expansion_factor=1000000)
print(
f"‼️ Sum of the lengths of the shortest path between every pair of galaxies for expansion_factor=1000000: {sum}"
)
def test_analyze_space():
space_map = """...#......
.......#..
#.........
..........
......#...
.#........
.........#
..........
.......#..
#...#....."""
cosmic_grid = CosmicGrid(space_map.splitlines())
# part one
sum = cosmic_grid.sum_of_shortest_paths(expansion_factor=2)
assert sum == 374, f"Expected 374, got {sum}"
print("✅ Passed test_analyze_observation() for expansion_factor=2")
# part two
sum = cosmic_grid.sum_of_shortest_paths(expansion_factor=10)
assert sum == 1030, f"Expected 1030, got {sum}"
print("✅ Passed test_analyze_observation() for expansion_factor=10")
sum = cosmic_grid.sum_of_shortest_paths(expansion_factor=100)
assert sum == 8410, f"Expected 8410, got {sum}"
print("✅ Passed test_analyze_observation() for expansion_factor=100")
if __name__ == "__main__":
test_analyze_space()
part_one()
part_two()☘️ Moral of the story? As a Principal Engineer, I’m wired to navigate complex problems, often defaulting to intricate solutions like BFS, DFS, Dijkstra, and A*.
Here, I overcomplicated a straightforward task that simply needed the Manhattan distance formula. This experience was a humbling reminder that sometimes, simplicity is key. It’s easy to overlook the obvious when your mind is tuned to complexity. It’s crucial to step back and reassess, as the simplest path often leads to the most elegant solution.
This was a lesson in the beauty of simplicity in problem-solving.
p.s: I am deliberating not adding answers here so you can actually spend some time trying to understand how we solved the problem!
Feel free to checkout code on my Github repo and try to set it up and run on your machine 👇
