cosmic expansion

approach

the grid is never expanded. the code counts galaxies per row and per column and records every galaxy's position.

for every pair of galaxies the distance is the manhattan distance plus an extra expansion for each empty row and empty column between them. part 1 uses an extra of 1 and part 2 an extra of 999999, so each empty line counts as a million.

the trick

add the expansion per empty row or column crossed instead of growing the grid.

res = 0
for g1, g2 in combinations(galaxies, 2):
    r1, c1 = g1
    r2, c2 = g2
    mnr, mxr = sorted([r1, r2])
    mnc, mxc = sorted([c1, c2])
    total = mxr - mnr + mxc - mnc
    total += sum(expansion for i in range(mnr, mxr) if rows[i] == 0)
    total += sum(expansion for i in range(mnc, mxc) if cols[i] == 0)
    res += total
return res