Man this one frustrated me because of a subtle difference in the wording of part 1 vs part 2. I had the correct logic from the start, but with an off-by-one error because of my interpretation of the wording. Part 1 says, “any rows or columns that contain no galaxies should all actually be twice as big” while part 2 says, “each empty column should be replaced with 1000000 empty columns”.

I added 1 column/row in part 1, and 1_000_000 in part 2. But if you’re replacing an empty column with 1_000_000, you’re actually adding 999_999 columns. It took me a good hour to discover where that off-by-one error was coming from.

Uiua

As promised, just a little later than planned. I do like this solution as it’s actually using arrays rather than just imperative programming in fancy dress. Run it here

Grid ← =@# [
  "...#......"
  ".......#.."
  "#........."
  ".........."
  "......#..."
  ".#........"
  ".........#"
  ".........."
  ".......#.."
  "#...#....."
]

GetDist! ← (
  # Build arrays of rows, cols of galaxies
  ⊙(⊃(◿)(⌊÷)⊃(⧻⊢)(⊚=1/⊂)).
  # check whether each row/col is just space
  # and so calculate its relative position
  ∩(\++1^1=0/+)⍉.
  # Map galaxy co-ords to these values
  ⊏:⊙(:⊏ :)
  # Map to [x, y] pairs, build cross product, 
  # and sum all topright values.
  /+≡(/+↘⊗0.)⊠(/+⌵-).⍉⊟
)
GetDist!(×1) Grid
GetDist!(×99) Grid

I saw that coming, but decided to do it the naive way for part 1, then fixed that up for part 2. Thanks to AoC I can also recognise a Manhattan distance written in a complex manner.

from __future__ import annotations

import re
import math
import argparse
import itertools

def print_sky(sky:list):
    for r in sky:
        print("".join(r))

class Point:
    def __init__(self,x:int,y:int) -> None:
        self.x = x
        self.y = y

    def __repr__(self) -> str:
        return f"Point({self.x},{self.y})"

    def distance(self,point:Point):
        # Manhattan dist
        x = abs(self.x - point.x)
        y = abs(self.y - point.y)
        return x + y

def expand_galaxies(galaxies:list,position:int,amount:int,index:str):
    for g in galaxies:
        if getattr(g,index) > position:
            c = getattr(g,index)
            setattr(g,index, c + amount)

def main(line_list:list,part:int):
    ## list of lists is the plan for init idea

    expand_value = 2 -1
    if part == 2:
        expand_value = 1e6 -1
    if part > 2:
        expand_value = part -1

    sky = list()
    for l in line_list:
        row_data = [*l]
        sky.append(row_data)
    
    print_sky(sky)
    
    # get galaxies
    gal_list = list()
    for r in range(0,len(sky)):
        for c in range(0,len(sky[r])):
            if sky[r][c] == '#':
                gal_list.append(Point(r,c))

    print(gal_list)

    col_indexes = list(reversed(range(0,len(sky))))
    # expand rows
    for i in col_indexes:
        if not '#' in sky[i]:
            expand_galaxies(gal_list,i,expand_value,'x')

    # check for expanding columns
    for i in reversed( range(0, len( sky[0] )) ):
        col = [sky[x][i] for x in col_indexes]
        if not '#' in col:
            expand_galaxies(gal_list,i,expand_value,'y')

    print(gal_list)

    # find all unique pair distance sum, part 1
    sum = 0
    for i in range(0,len(gal_list)):
        for j in range(i+1,len(gal_list)):
            sum += gal_list[i].distance(gal_list[j])

    print(f"Sum distances: {sum}")

if __name__ == "__main__":
    parser = argparse.ArgumentParser(description="template for aoc solver")
    parser.add_argument("-input",type=str)
    parser.add_argument("-part",type=int)
    args = parser.parse_args()
    filename = args.input
    if filename == None:
        parser.print_help()
        exit(1)
    part = args.part
    file = open(filename,'r')
    main([line.rstrip('\n') for line in file.readlines()],part)
    file.close()

Rust

I was unsure in Part 1 whether to actually expand the grid or just count the number of empty lanes in each ranges. I ended up doing the latter which was obviously the right choice for part 2, but I think it could have gone either way.

Raku

Today I’m thankful that I have the combinations() method available. It’s not hard to implement combinations(), but it’s not particularly interesting. This code is a bit anachronistic because I solved part 1 by expanding the universe instead of contracting it, but this way makes the calculations for part 1 and part 2 symmetric. I was worried for a bit there that I’d have to do some “here are all the places where expansion happens, check this list when calculating distances” bookkeeping, and I was quite relieved when I realized that I could just use arithmetic.

edit: Also, first time using the Slip class in Raku, which is mind bending, but very useful for expanding/contracting the universe and generating the lists of galaxy coordinates. And I learned a neat way to transpose 2D arrays using [Z].

View the code on Github

use v6;

sub MAIN($input) {
    my $file = open $input;

    my @map = $file.lines».comb».Array;
    my @galaxies-original = @map».grep("#", :k).grep(*.elems > 0, :kv).rotor(2).map({($_[0] X $_[1]).Slip});
    my $distances-original = @galaxies-original.List.combinations(2).map({($_[0] Z- $_[1])».abs.sum}).sum;

    # contract the universe
    @map = @map.map: {$_.all eq '.' ?? slip() !! $_};
    @map = [Z] @map;
    @map = @map.map: {$_.all eq '.' ?? slip() !! $_};
    @map = [Z] @map;

    my @galaxies = @map».grep("#", :k).grep(*.elems > 0, :kv).rotor(2).map({($_[0] X $_[1]).Slip});
    my $distances-contracted = @galaxies.List.combinations(2).map({($_[0] Z- $_[1])».abs.sum}).sum;

    my $distances-twice-expanded = ($distances-original - $distances-contracted) * 2 + $distances-contracted;
    say "part 1: $distances-twice-expanded";
    my $distances-many-expanded = ($distances-original - $distances-contracted) * 1000000 + $distances-contracted;
    say "part 2: $distances-many-expanded";
}

Python

from .solver import Solver


class Day11(Solver):

  def __init__(self):
    super().__init__(11)
    self.galaxies: list = []
    self.blank_x: set[int] = set()
    self.blank_y: set[int] = set()

  def presolve(self, input: str):
    lines = input.rstrip().split('\n')
    self.galaxies = []
    max_x = 0
    max_y = 0
    for y, line in enumerate(lines):
      for x, c in enumerate(line):
        if c == '#':
          self.galaxies.append((x, y))
        max_x = max(max_x, x)
      max_y = max(max_y, y)
    self.blank_x = set(range(max_x + 1)) - {x for x, _ in self.galaxies}
    self.blank_y = set(range(max_y + 1)) - {y for _, y in self.galaxies}

  def solve(self, expansion_factor: int) -> int:
    galaxies = list(self.galaxies)
    total = 0
    for i in range(len(galaxies)):
      for j in range(i + 1, len(galaxies)):
        sx, sy = galaxies[i]
        dx, dy = galaxies[j]
        if sx > dx:
          sx, dx = dx, sx
        if sy > dy:
          sy, dy = dy, sy
        dist = sum((dx - sx, dy - sy,
            max(0, expansion_factor - 1) * len([x for x in self.blank_x if sx < x < dx]),
            max(0, expansion_factor - 1) * len([y for y in self.blank_y if sy < y < dy])))
        total += dist
    return total

  def solve_first_star(self):
    return self.solve(2)

  def solve_second_star(self):
    return self.solve(1000000)

Nim

Approached part 1 in the expected way, by expanding the grid. For part 2, I left the grid alone and just adjusted the galaxy location vectors based on how many empty rows and columns there were above and to the left of them. I divided my final totals by 2 instead of bothering with any fancy combinatoric iterators.

• Day 11, part 1
• Day 11, part 2

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

Kotlin

Github

Was lazy at the beginning, so I started to do actual expansion in memory, then decided to do it properly. And it paid off in the second part.

• find galaxy coordinates + hold few bit masks to find unused rows and columns → convert to indexes
• transform original galaxies coordinates considering number of previous empty lines (time for simple binary search)
• use the Manhattan distance

Crystal

!crystal_lang@lemmy.ml

wording in part 2 threw me off too

I could have done this in 2 loops, but this method is way easier to do
And it’s gorgeous code imo
(except for the fact that lemmy’s huge tab sizes make it look weird)

E = ARGV[0].to_i

input = File.read("input.txt")

sky = input.lines.map &.chars

# find galaxies
galaxies = Array(Tuple(Int32, Int32)).new
sky.size.times do |y| 
	sky[0].size.times do |x|
		if sky[y][x] == '#'
			galaxies << {y, x}
end     end     end
# puts galaxies

# vertical expansion locations
expandsy = Array(Int32).new
sky.size.times do |i|
	unless galaxies.any? {|gal| gal[0] == i}
		expandsy << i
end     end

# horizontal expansion locations
expandsx = Array(Int32).new
sky[0].size.times do |i|
	unless galaxies.any? {|gal| gal[1] == i}
		expandsx << i
end     end

# calculate expansion for each galaxy
adds = Array.new(galaxies.size) { [0, 0] }
expandsy.each do |y|
	galaxies.each_with_index do |gal, i|
		if gal[0] > y
			adds[i][0] += 1
end     end     end

# calculate expansion for each galaxy
expandsx.each do |x|
	galaxies.each_with_index do |gal, i|
		if gal[1] > x
			adds[i][1] += 1
end     end     end

# expaaaaaaaand
galaxies.map_with_index! {|gal, i| {gal[0] + adds[i][0]*E, gal[1] + adds[i][1]*E} }

# distances
sum = 0_u64
galaxies.each do |gal|
	galaxies.each do |gal2|
		if gal2 != gal
			sum += (gal2[0] - gal[0]).abs + (gal2[1] - gal[1]).abs
end     end     end
puts sum/2

That was a fun one. Especially after yesterday. As soon as I saw that star 1 was expanding each gap by 1, I just had a feeling that star 2 would be doing the same calculation with a larger expansion, so I wrote my code in a way that would make that quite simple to modify. When I saw the factor of 1,000,000 I was scared that it was going to be one of those processor-destroying AoC challenges where you either wait for 2 hours to get an answer, or have to come up with a fancy mathematical way of solving things, but after changing my i32 distance to an i64, it calculated just fine and instantly. I guess only storing the locations of galaxies and not dealing with the entire grid was good enough to keep the performance down.

https://github.com/capitalpb/advent_of_code_2023/blob/main/src/solvers/day11.rs

use crate::Solver;
use itertools::Itertools;
use num::abs;

#[derive(Debug)]
struct Point {
    x: usize,
    y: usize,
}

struct GalaxyMap {
    locations: Vec,
}

impl GalaxyMap {
    fn from(input: &str) -> GalaxyMap {
        let locations = input
            .lines()
            .rev()
            .enumerate()
            .map(|(x, row)| {
                row.chars()
                    .enumerate()
                    .filter_map(|(y, digit)| {
                        if digit == '#' {
                            Some(Point { x, y })
                        } else {
                            None
                        }
                    })
                    .collect::>()
            })
            .flatten()
            .collect::>();

        GalaxyMap { locations }
    }

    fn empty_rows(&self) -> Vec {
        let occupied_rows = self
            .locations
            .iter()
            .map(|point| point.y)
            .unique()
            .collect::>();
        let max_y = *occupied_rows.iter().max().unwrap();

        (0..max_y)
            .filter(move |y| !occupied_rows.contains(&y))
            .collect()
    }

    fn empty_cols(&self) -> Vec {
        let occupied_cols = self
            .locations
            .iter()
            .map(|point| point.x)
            .unique()
            .collect::>();
        let max_x = *occupied_cols.iter().max().unwrap();

        (0..max_x)
            .filter(move |x| !occupied_cols.contains(&x))
            .collect()
    }

    fn expand(&mut self, factor: usize) {
        let delta = factor - 1;

        for y in self.empty_rows().iter().rev() {
            for galaxy in &mut self.locations {
                if galaxy.y > *y {
                    galaxy.y += delta;
                }
            }
        }

        for x in self.empty_cols().iter().rev() {
            for galaxy in &mut self.locations {
                if galaxy.x > *x {
                    galaxy.x += delta;
                }
            }
        }
    }

    fn galactic_distance(&self) -> i64 {
        self.locations
            .iter()
            .combinations(2)
            .map(|pair| {
                abs(pair[0].x as i64 - pair[1].x as i64) + abs(pair[0].y as i64 - pair[1].y as i64)
            })
            .sum::()
    }
}

pub struct Day11;

impl Solver for Day11 {
    fn star_one(&self, input: &str) -> String {
        let mut galaxy = GalaxyMap::from(input);
        galaxy.expand(2);
        galaxy.galactic_distance().to_string()
    }

    fn star_two(&self, input: &str) -> String {
        let mut galaxy = GalaxyMap::from(input);
        galaxy.expand(1_000_000);
        galaxy.galactic_distance().to_string()
    }
}

Nim

Happy I decided to not actually expand anything. Manhattan distance and counting the number of empty rows and columns was plenty. Also made part 2 an added oneliner :) It’s still pretty inefficient iterating over the grid multiple times to gather the galaxies and empty rows, runtime is about 17ms

I could also extract and re-use my 2D Coord and Grid classes from day 10, and learned more about Nim in the process ^^

Part 1 and 2 combined

Rust solution

Multiplied the manhattan distance by the number of empty space lines crossed.

Dart

Nothing interesting here, just did it all explicitly. I might try something different in Uiua later.

solve(List lines, {int age = 2}) {
  var grid = lines.map((e) => e.split('')).toList();
  var gals = [
    for (var r in grid.indices())
      for (var c in grid[r].indices().where((c) => grid[r][c] == '#')) (r, c)
  ];
  for (var row in grid.indices(step: -1)) {
    if (!grid[row].contains('#')) {
      gals = gals
          .map((e) => ((e.$1 > row) ? e.$1 + age - 1 : e.$1, e.$2))
          .toList();
    }
  }
  for (var col in grid.first.indices(step: -1)) {
    if (grid.every((r) => r[col] == '.')) {
      gals = gals
          .map((e) => (e.$1, (e.$2 > col) ? e.$2 + age - 1 : e.$2))
          .toList();
    }
  }
  var dists = [
    for (var ix1 in gals.indices())
      for (var ix2 in (ix1 + 1).to(gals.length))
        (gals[ix1].$1 - gals[ix2].$1).abs() +
            (gals[ix1].$2 - gals[ix2].$2).abs()
  ];
  return dists.sum;
}

part1(List lines) => solve(lines);
part2(List lines) => solve(lines, age: 1000000);