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

Advent Of Code

770 readers
75 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
 

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

you are viewing a single comment's thread
view the rest of the comments
[–] capitalpb@programming.dev 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()
    }
}