[–] 3 points 11 months ago (3 children)

Rust

Only took four days, but I made it, and without any maths libraries. I tried lots of unsuccessful searches (including A*) before realizing part 2 is a linear equation system. Then I tried to find all solutions by just going row by row, guessing all but one unknown variable and finding the smallest solution, but this was still way too slow due to the high amount of variables guessed.

By looking around on Wikipedia I found that the problem could be simplified by turning the matrix into Smith Normal Form or Hermitian Normal Form, but couldn't find any Rust library implementing these. Their algorithms looked just a bit too complicated to implement myself. Maybe I would have used Python, because sagemath has everything, but the problem of ultimately finding the smallest integer solution still remained, and I already had the search code in Rust without simplifying the matrix.

So put the matrix into echelon form by implementing Gaussian elimination, which wasn't too bad, and it significantly reduced the number of variables to guess. Now part 2 runs in 70ms.

View code on github

  • source
  • [–] 2 points 11 months ago

    Rust

    This one broke me, I couldn't do it without looking at some of the solutions in this thread. In the end, basically all that was necessary for part 2 is to check for every candidate rectangle if:

    1. No corners (red tiles) are inside the rectangle, and
    2. No lines intersect the rectangle.

    Plus a bunch shifting numbers around by 1. The code is not pretty at all, but at least it turned very efficient, solving part 2 in just 4.3ms. I have no idea how generalized the solution is. It definitely assumes that any larger rectangle is spanned inside the area and that the path doesn't cross over itself. Also of course that there are no two corners next to each other forming a 180 degree turn.

    View on github

    Code

    use std::ops::{Range, RangeInclusive};
    
    fn parse_input(input: &str) -> Vec<(u32, u32)> {
        input
            .lines()
            .map(|l| {
                let (a, b) = l.split_once(',').unwrap();
                (a.parse::<u32>().unwrap(), b.parse::<u32>().unwrap())
            })
            .collect()
    }
    
    #[inline]
    fn area(a: (u32, u32), b: (u32, u32)) -> u64 {
        (a.0.abs_diff(b.0) as u64 + 1) * (a.1.abs_diff(b.1) as u64 + 1)
    }
    
    fn part1(input: String) {
        let tiles = parse_input(&input);
        let mut largest = 0;
        for t1 in &tiles {
            for t2 in &tiles {
                let a = area(*t1, *t2);
                if a > largest {
                    largest = a;
                }
            }
        }
        println!("{largest}");
    }
    
    // Returns true only if t is not inside of the rectangle
    #[inline]
    fn red_allowed(t: (u32, u32), x_range: Range<u32>, y_range: Range<u32>) -> bool {
        !(t.0 > x_range.start && t.0 + 1 < x_range.end && t.1 > y_range.start && t.1 + 1 < y_range.end)
    }
    
    fn is_contained(
        a: (u32, u32),
        b: (u32, u32),
        tiles_x: &[(u32, u32)],
        tiles_y: &[(u32, u32)],
        vert_lines: &[(u32, RangeInclusive<u32>)],
        hori_lines: &[(u32, RangeInclusive<u32>)],
    ) -> bool {
        let x_range = a.0.min(b.0)..(a.0.max(b.0) + 1);
        let y_range = a.1.min(b.1)..(a.1.max(b.1) + 1);
    
        // Check that no corners (red tiles) are inside the rectangle
        let corners_ok = if x_range.end - x_range.start <= y_range.end - y_range.start {
            // Use tiles_x
            let start = match tiles_x.binary_search(&(x_range.start, 0)) {
                Ok(e) => e,
                Err(e) => e,
            };
            tiles_x
                .iter()
                .skip(start)
                .take_while(|t| t.0 < x_range.end)
                .filter(|&&t| t != a && t != b)
                .all(|t| red_allowed(*t, x_range.clone(), y_range.clone()))
        } else {
            // Use tiles_y
            let start = match tiles_y.binary_search_by_key(&(y_range.start, 0), |(x, y)| (*y, *x)) {
                Ok(e) => e,
                Err(e) => e,
            };
            tiles_y
                .iter()
                .skip(start)
                .take_while(|t| t.1 < y_range.end)
                .filter(|&&t| t != a && t != b)
                .all(|t| red_allowed(*t, x_range.clone(), y_range.clone()))
        };
        if !corners_ok {
            return false;
        }
    
        // Check that no line intersects the inside of the rectangle
        let start = match vert_lines.binary_search_by_key(&x_range.start, |(x, _)| *x) {
            Ok(e) => e,
            Err(e) => e,
        };
        for (x, line) in vert_lines
            .iter()
            .skip(start)
            .take_while(|(x, _)| *x < x_range.end)
        {
            if x_range.start < *x
                && x_range.end > *x + 1
                && (y_range.start + 1).max(*line.start()) < (y_range.end - 1).min(line.end() + 1)
            {
                return false;
            }
        }
        let start = match hori_lines.binary_search_by_key(&y_range.start, |(y, _)| *y) {
            Ok(e) => e,
            Err(e) => e,
        };
        for (y, line) in hori_lines
            .iter()
            .skip(start)
            .take_while(|(y, _)| *y < y_range.end)
        {
            if y_range.start < *y
                && y_range.end > *y + 1
                && (x_range.start + 1).max(*line.start()) < (x_range.end - 1).min(line.end() + 1)
            {
                return false;
            }
        }
        true
    }
    
    fn part2(input: String) {
        let tiles = parse_input(&input);
    
        let mut vert_lines = Vec::new();
        let mut hori_lines = Vec::new();
        let mut prev = *tiles.last().unwrap();
        for &t in &tiles {
            if t.0 == prev.0 {
                vert_lines.push((t.0, t.1.min(prev.1)..=t.1.max(prev.1)));
            } else {
                debug_assert_eq!(t.1, prev.1);
                hori_lines.push((t.1, t.0.min(prev.0)..=t.0.max(prev.0)));
            }
            prev = t;
        }
        vert_lines.sort_by_key(|(x, _)| *x);
        hori_lines.sort_by_key(|(y, _)| *y);
    
        let mut tiles_x = tiles.clone();
        tiles_x.sort();
        let mut tiles_y = tiles.clone();
        tiles_y.sort_by_key(|(x, y)| (*y, *x));
        let mut largest = 0;
        for (idx, t1) in tiles.iter().enumerate() {
            for t2 in tiles.iter().take(idx) {
                let a = area(*t1, *t2);
                if a > largest && is_contained(*t1, *t2, &tiles_x, &tiles_y, &vert_lines, &hori_lines) {
                    largest = a;
                }
            }
        }
        println!("{largest}");
    }
    
    util::aoc_main!();
    

  • source
  • [–] 3 points 11 months ago

    Rust

    It's getting spicier, luckily part 2 wasn't really much additional complexity this time. There exists a pretty fancy union-find data structure which would have made representing the subcircuits much faster, but I went with a lazy approach.

    View on github

    Code

    use euclid::default::Point3D;
    use euclid::point3;
    
    fn parse_input(input: &str) -> Vec<Point3D<i64>> {
        input
            .lines()
            .map(|l| {
                let mut parts = l.split(',').map(|p| p.parse::<i64>().unwrap());
                let (x, y, z) = (
                    parts.next().unwrap(),
                    parts.next().unwrap(),
                    parts.next().unwrap(),
                );
                point3(x, y, z)
            })
            .collect()
    }
    
    // Distances between all points. Reflexive and symmetric pairs are skipped,
    // so the Vec's have increasing size, starting at 0.
    fn dists(points: &[Point3D<i64>]) -> Vec<Vec<i64>> {
        points
            .iter()
            .enumerate()
            .map(|(idx, &p1)| {
                points
                    .iter()
                    .take(idx)
                    .map(|&p2| (p2 - p1).square_length())
                    .collect::<Vec<i64>>()
            })
            .collect()
    }
    
    fn sorted_distances(dists: &[Vec<i64>]) -> Vec<(usize, usize, i64)> {
        let mut sorted: Vec<(usize, usize, i64)> = dists
            .iter()
            .enumerate()
            .flat_map(|(i, row)| row.iter().enumerate().map(move |(j, d)| (i, j, *d)))
            .collect();
        sorted.sort_by_key(|(_, _, d)| *d);
        sorted
    }
    
    fn part1(input: String) {
        let points = parse_input(&input);
        let d = dists(&points);
        let sorted = sorted_distances(&d);
    
        let mut circuits: Vec<u32> = (0..points.len() as u32).collect();
        for (i, j, _) in sorted.into_iter().take(1000) {
            let new_circuit = circuits[i];
            let old_circuit = circuits[j];
            if new_circuit != old_circuit {
                for c in circuits.iter_mut() {
                    if *c == old_circuit {
                        *c = new_circuit;
                    }
                }
            }
        }
        let mut sizes: Vec<u32> = vec![0; points.len()];
        for c in circuits {
            sizes[c as usize] += 1
        }
        sizes.sort_unstable();
        let result = sizes.iter().rev().take(3).product::<u32>();
        println!("{result}");
    }
    
    fn part2(input: String) {
        let points = parse_input(&input);
        let d = dists(&points);
        let sorted = sorted_distances(&d);
    
        let mut circuits: Vec<u32> = (0..points.len() as u32).collect();
        for (i, j, _) in sorted.into_iter() {
            let new_circuit = circuits[i];
            let old_circuit = circuits[j];
            if new_circuit != old_circuit {
                let mut all_connected = true;
                for c in circuits.iter_mut() {
                    if *c == old_circuit {
                        *c = new_circuit;
                    }
                    if *c != new_circuit {
                        all_connected = false;
                    }
                }
                if all_connected {
                    let result = points[i].x * points[j].x;
                    println!("{result}");
                    return;
                }
            }
        }
    }
    
    util::aoc_main!();
    

  • source
  • [–] 4 points 11 months ago

    The gaps on the bottom and the top serve the important purpose of ventilation. It's a really effective design allowing vertical airflow. So yes, I do prefer air gaps over stinky boxes, and I have personally never seen a creep sticking their head under the gap.

  • source
  • parent
  • context
  • [–] 4 points 11 months ago (1 child)

    Rust

    Dynamic programming? Nah, just keep track of the number of overlapping beams and part 2 becomes no different to part 1.

    View on github

    use std::collections::VecDeque;
    
    fn parse_input(input: &str) -> (Vec<Vec<bool>>, (usize, usize)) {
        let splits = input
            .lines()
            .map(|l| l.chars().map(|c| c == '^').collect())
            .collect();
        // Assume start is on first row
        let start = (input.chars().position(|c| c == 'S').unwrap(), 0);
        (splits, start)
    }
    
    fn solve(input: String) {
        let (splits, start) = parse_input(&input);
        let mut nsplits = 0u32;
        let mut timelines = 1u64;
        let mut frontier = VecDeque::from([(start, 1)]);
        while let Some((pos, multiplicity)) = frontier.pop_front() {
            let (x, y) = (pos.0, pos.1 + 1);
            if y == splits.len() {
                // Falls out of bottom
                continue;
            }
            if splits[y][x] {
                nsplits += 1;
                timelines += multiplicity;
                if let Some((b, m2)) = frontier.back_mut()
                    && *b == (x - 1, y)
                {
                    *m2 += multiplicity;
                } else {
                    frontier.push_back(((x - 1, y), multiplicity));
                }
                frontier.push_back(((x + 1, y), multiplicity));
            } else if let Some((b, m2)) = frontier.back_mut()
                && *b == (x, y)
            {
                *m2 += multiplicity;
            } else {
                frontier.push_back(((x, y), multiplicity));
            }
        }
        println!("Part 1: {nsplits}");
        println!("Part 2: {timelines}");
    }
    
    fn main() -> std::io::Result<()> {
        let (input, _) = util::get_input("day7.txt")?;
        solve(input);
        Ok(())
    }
    
  • source
  • [–] 2 points 11 months ago

    Rust

    Mainly difficult parsing today.

    View on github

    fn part1(input: String) {
        let mut nums: Vec<Vec<u64>> = Vec::new();
        let mut mul: Vec<bool> = Vec::new();
        for l in input.lines() {
            if l.chars().next().unwrap().is_ascii_digit() {
                let row = l
                    .split_ascii_whitespace()
                    .map(|s| s.parse::<u64>().unwrap())
                    .collect();
                nums.push(row);
            } else {
                mul = l.split_ascii_whitespace().map(|s| s == "*").collect();
            }
        }
        let mut sum = 0;
        for (idx, op_mul) in mul.iter().enumerate() {
            let col = nums.iter().map(|row| row[idx]);
            sum += if *op_mul {
                col.reduce(|acc, n| acc * n)
            } else {
                col.reduce(|acc, n| acc + n)
            }
            .unwrap();
        }
        println!("{sum}");
    }
    
    fn part2(input: String) {
        let grid: Vec<&[u8]> = input.lines().map(|l| l.as_bytes()).collect();
        let n_rows = grid.len() - 1; // Not counting operator row
        let mut op_mul = grid[n_rows][0] == b'*';
        let mut cur = if op_mul { 1 } else { 0 };
        let mut sum = 0;
        for x in 0..grid[0].len() {
            let digits: Vec<u8> = (0..n_rows).map(|y| grid[y][x]).collect();
            if digits.iter().all(|d| *d == b' ') {
                sum += cur;
                op_mul = grid[n_rows][x + 1] == b'*';
                cur = if op_mul { 1 } else { 0 };
                continue;
            }
            let n = String::from_utf8(digits)
                .unwrap()
                .trim()
                .parse::<u64>()
                .unwrap();
            if op_mul {
                cur *= n;
            } else {
                cur += n;
            }
        }
        sum += cur;
        println!("{sum}");
    }
    
    util::aoc_main!();
    
  • source
  • [–] 2 points 11 months ago

    Rust

    Tried to outsmart part 2 by not merging ranges but just subtracting overlapping ranges from the current range's size, but then overlapping overlaps are subtracted more than once. So I ended up merging the ranges. They are kept in a list that is sorted by their starting position. Also, transforming the inclusive ranges in the input into exclusive ranges made things quite a bit easier.

    View on github

    use std::ops::Range;
    
    fn parse_input(input: &str) -> (Vec<Range<u64>>, Vec<u64>) {
        let ranges: Vec<_> = input
            .lines()
            .take_while(|l| !l.is_empty())
            .map(|l| {
                let (a, b) = l.split_once('-').unwrap();
                a.parse().unwrap()..b.parse::<u64>().unwrap() + 1
            })
            .collect();
        let nums = input
            .lines()
            .skip(ranges.len() + 1)
            .map(|n| n.parse().unwrap())
            .collect();
        (ranges, nums)
    }
    
    fn part1(input: String) {
        let (ranges, nums) = parse_input(&input);
        let count = nums
            .iter()
            .filter(|n| ranges.iter().any(|r| r.contains(n)))
            .count();
        println!("{count}");
    }
    
    fn part2(input: String) {
        let (ranges, _) = parse_input(&input);
        // Ranges are added to this Vec always sorted by start and non-overlapping
        let mut merged: Vec<Range<u64>> = Vec::with_capacity(ranges.len());
        for r in ranges {
            // Find index of first intersecting range
            let first_int_o = merged.iter().position(|m| {
                // Intersection range (if any)
                let int_start = r.start.max(m.start);
                let int_end = r.end.min(m.end);
                int_start < int_end
            });
            if let Some(first_int) = first_int_o {
                // Exclusive
                let last_int = merged.len()
                    - merged
                        .iter()
                        .rev()
                        .position(|m| {
                            let int_start = r.start.max(m.start);
                            let int_end = r.end.min(m.end);
                            int_start < int_end
                        })
                        .unwrap();
                // New range replacing all intersecting ranges
                let new = r.start.min(merged[first_int].start)..r.end.max(merged[last_int - 1].end);
                merged[first_int] = new;
                for i in (first_int + 1)..last_int {
                    merged.remove(i);
                }
            } else {
                // Does not overlap with anything. Find index that keeps sorting
                let idx = merged
                    .iter()
                    .position(|m| m.start > r.start)
                    .unwrap_or(merged.len());
                merged.insert(idx, r);
            }
        }
        let count = merged.iter().map(|r| r.end - r.start).sum::<u64>();
        println!("{count}");
    }
    
    util::aoc_main!();
    
  • source
  • [–] 2 points 11 months ago

    Rust

    View on github

    fn parse_input(input: &str) -> Vec<Vec<bool>> {
        input
            .lines()
            .map(|l| l.chars().map(|c| c == '@').collect())
            .collect()
    }
    
    fn count_adj(grid: &[Vec<bool>], (x, y): (usize, usize)) -> usize {
        let width = grid[0].len();
        let height = grid.len();
        grid.iter()
            .take((y + 2).min(height))
            .skip(y.saturating_sub(1))
            .map(|r| {
                r.iter()
                    .take((x + 2).min(width))
                    .skip(x.saturating_sub(1))
                    .take(3)
                    .filter(|e| **e)
                    .count()
            })
            .sum::<usize>()
    }
    
    fn part1(input: String) {
        let grid = parse_input(&input);
        let mut count = 0u32;
        for (y, row) in grid.iter().enumerate() {
            for (x, _) in row.iter().enumerate().filter(|(_, r)| **r) {
                let n_adj = count_adj(&grid, (x, y));
                // Center roll is counted too
                if n_adj < 5 {
                    count += 1;
                }
            }
        }
        println!("{count}");
    }
    
    fn part2(input: String) {
        let mut grid = parse_input(&input);
        let mut removed = 0u32;
        loop {
            let mut next_grid = grid.clone();
            let prev_removed = removed;
            for (y, row) in grid.iter().enumerate() {
                for (x, _) in row.iter().enumerate().filter(|(_, r)| **r) {
                    let n_adj = count_adj(&grid, (x, y));
                    // Center roll is counted too
                    if n_adj < 5 {
                        next_grid[y][x] = false;
                        removed += 1;
                    }
                }
            }
            if removed == prev_removed {
                break;
            }
            grid = next_grid;
        }
        println!("{}", removed);
    }
    
    util::aoc_main!();
    
  • source
  • view more: ‹ prev next ›