Day 11: Cosmic Expansion
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as https://topaz.github.io/paste/ , pastebin, or github (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
🔒 Thread is locked until there's at least 100 2 star entries on the global leaderboard
🔓 Unlocked after 9 mins
Crystal
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)code
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 ani64
, 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() } }
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.
Python
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()
Scala3
def compute(a: List[String], growth: Long): Long = val gaps = Seq(a.map(_.toList), a.transpose).map(_.zipWithIndex.filter((d, i) => d.forall(_ == '.')).map(_._2).toSet) val stars = for y <- a.indices; x <- a(y).indices if a(y)(x) == '#' yield List(x, y) def dist(gaps: Set[Int], a: Int, b: Int): Long = val i = math.min(a, b) until math.max(a, b) i.size.toLong + (growth - 1)*i.toSet.intersect(gaps).size.toLong (for Seq(p, q) <- stars.combinations(2); m <- gaps.lazyZip(p).lazyZip(q).map(dist) yield m).sum def task1(a: List[String]): Long = compute(a, 2) def task2(a: List[String]): Long = compute(a, 1_000_000)
Python
Also on Github.
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)