this post was submitted on 11 Dec 2023
12 points (80.0% liked)

Advent Of Code

763 readers
1 users here now

An unofficial home for the advent of code community on programming.dev!

Advent of Code is an annual Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.

AoC 2023

Solution Threads

M T W T F S S
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25

Rules/Guidelines

Relevant Communities

Relevant Links

Credits

Icon base by Lorc under CC BY 3.0 with modifications to add a gradient

console.log('Hello World')

founded 1 year ago
MODERATORS
12
submitted 11 months ago* (last edited 11 months ago) by Ategon to c/advent_of_code
 

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


🔒 Thread is locked until there's at least 100 2 star entries on the global leaderboard

🔓 Unlocked after 9 mins

top 20 comments
sorted by: hot top controversial new old
[–] [email protected] 13 points 11 months ago* (last edited 11 months ago) (1 children)

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.

[–] [email protected] 4 points 11 months ago (1 children)

Yepp, this one got me as well! I found the discrepancy when testing against the sample through, which showed the result for a factor 100 (which needed to be 99). Knowing the correct outcome made debugging a lot easier.

I always make sure my solution passes all the samples before trying the full input.

[–] [email protected] 4 points 11 months ago (1 children)

Me too. I ran all the samples, and I was still banging my head. I can usually see the mistake if it's an off-by-one error in a calculation, but this was a mistake in reading the problem description, so I couldn't see it at first.

[–] [email protected] 2 points 11 months ago

Yeah the descriptions contain a lot of story fluff, but also critical bits of information.

[–] [email protected] 4 points 11 months ago

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
[–] [email protected] 3 points 11 months ago* (last edited 11 months ago)

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

Code

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";
}

[–] purplemonkeymad 3 points 11 months ago* (last edited 11 months ago)

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.

Pythonfrom 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()

[–] [email protected] 3 points 11 months ago

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.

[–] [email protected] 2 points 11 months ago* (last edited 2 months ago)

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)
[–] [email protected] 2 points 11 months ago

Crystal

[email protected]

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

[–] capitalpb 2 points 11 months ago

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()
    }
}
[–] [email protected] 2 points 11 months ago (1 children)

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.

[–] [email protected] 2 points 11 months ago

I divided my final totals by 2 instead of bothering with any fancy combinatoric iterators.

same lmao, it's only double the calculations. If x2 is mucking your code up, it's too slow anyway.

[–] [email protected] 2 points 11 months ago* (last edited 11 months ago)

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
[–] [email protected] 2 points 11 months ago

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
[–] cvttsd2si 1 points 11 months ago

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)
[–] [email protected] 1 points 11 months ago* (last edited 11 months ago)

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);
[–] [email protected] 1 points 11 months ago

Rust

use std::fs;
use std::path::PathBuf;

use clap::Parser;

use itertools::Itertools;
use std::ops::Range;

#[derive(Parser)]
#[command(author, version, about, long_about = None)]
struct Cli {
    input_file: PathBuf,
}

fn main() {
    // Parse CLI arguments
    let cli = Cli::parse();

    // Read file
    let input_text = fs::read_to_string(&cli.input_file)
        .expect(format!("File \"{}\" not found", cli.input_file.display()).as_str());

    let map: Vec> = input_text.lines().map(|r| r.chars().collect()).collect();

    let mut expanding_rows = vec![];
    // Expand rows
    map.iter().enumerate().for_each(|(row_num, r)| {
        if r.iter().filter(|c| **c == '.').count() == r.len() {
            expanding_rows.push(row_num);
        }
    });

    let mut expanding_cols = vec![];

    // Find expanding cols
    for col in 0..map[0].len() {
        // Determine if all '.'
        let expand = map.iter().filter(|row| row[col] == '.').count() == map.len();

        if expand {
            expanding_cols.push(col);
        }
    }

    // Find galaxies
    let mut galaxies: Vec<(usize, usize)> = vec![];
    for (row_num, row) in map.iter().enumerate() {
        for (col_num, char) in row.iter().enumerate() {
            if *char == '#' {
                galaxies.push((row_num.try_into().unwrap(), col_num.try_into().unwrap()));
            }
        }
    }

    println!("Num Galaxies: ({})", galaxies.len());

    println!(
        "Expanding rows: {:?}\tExpanding cols: {:?}",
        expanding_rows, expanding_cols
    );

    // Distance between each pair
    let expansion_1 = 2;
    let expansion_2 = 1_000_000;
    let mut sum_distances_1 = 0;
    let mut sum_distances_2 = 0;
    println!(
        "Total combinations: {}",
        galaxies.iter().tuple_combinations::<(_, _)>().count()
    );
    for (g1, g2) in galaxies.iter().tuple_combinations() {
        let vert_range: Range = if g1.0 < g2.0 {
            (g1.0)..(g2.0)
        } else {
            (g2.0)..(g1.0)
        };
        let horr_range: Range = if g1.1 < g2.1 {
            (g1.1)..(g2.1)
        } else {
            (g2.1)..(g1.1)
        };

        let vert_expansions = expanding_rows
            .iter()
            .filter(|r| vert_range.contains(*r))
            .count();
        let horr_expansions = expanding_cols
            .iter()
            .filter(|r| horr_range.contains(*r))
            .count();
        let expansions = vert_expansions + horr_expansions;

        let distance = vert_range.len() + horr_range.len();

        sum_distances_1 += distance + (expansions * (expansion_1 - 1));
        sum_distances_2 += distance + (expansions * (expansion_2 - 1));
    }

    println!("Total distance: {}", sum_distances_1);
    println!("Part 2 distance: {}", sum_distances_2);
}

[–] [email protected] 1 points 11 months ago

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

[–] [email protected] 1 points 11 months ago

Rust solution

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