Nim

Part 1 and 2: I solved today's puzzle without expanding the universe. Path in expanded universe is just a path in the original grid + expansion rate times the number of crossed completely-empty lines (both horizontal and vertical). For example, if a single tile after expansion become 5 tiles (rate = +4), original path was 12 and it crosses 7 lines, new path will be: 12 + 4 * 7 = 40.
The shortest path is easy to calculate in O(1) time: abs(start.x - finish.x) + abs(start.y - finish.y).
And to count crossed lines I just check if line is between the start and finish indexes.

Total runtime: 2.5 ms
Puzzle rating: 7/10 Code: day_11/solution.nim
Snippet:

proc solve(lines: seq[string]): AOCSolution[int] =
  let
    galaxies = lines.getGalaxies()
    emptyLines = lines.emptyLines()
    emptyColumns = lines.emptyColumns()

  for gi, g1 in galaxies:
    for g2 in galaxies[gi+1..^1]:
      let path = shortestPathLength(g1, g2)
      let crossedLines = countCrossedLines(g1, g2, emptyColumns, emptyLines)
      block p1:
        result.part1 += path + crossedLines * 1
      block p2:
        result.part2 += path + crossedLines * 999_999