Gobbel2000

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

I think this is a very useful license to require in new software procurements commissioned by public entities in the EU. The FSFE calls this "public money – public code" (publiccode.eu). Having a specific EUPL over just the GPL might make this look more proper, even if there aren't many technical differences. However for personal use I would prefer using good old GPLv3.

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

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!();

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

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!();

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.

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

That's absolutely hilarious! Can somebody from the UK confirm if this is actually true?

Nope, can't ruin it for me because I have left this cursed place.

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!();

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!();

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!();

Rust

Seeing some of the other solutions in this thread, there are definitely simpler (and probably still faster) solutions possible, but I first sorted the bank by the highest batteries (keeping the index information) and then used a recursive greedy algorithm to find the largest battery that still follows the index order.

View on github

fn part1(input: String) {
    let mut sum = 0;
    'banks: for l in input.lines() {
        let mut sorted: Vec<(usize, u32)> = l
            .chars()
            .map(|c| c.to_digit(10).unwrap())
            .enumerate()
            .collect();
        sorted.sort_by(|(_, a), (_, b)| a.cmp(b).reverse());
        for (idx, first) in &sorted {
            for (id2, second) in &sorted {
                if id2 > idx {
                    sum += first * 10 + second;
                    continue 'banks;
                }
            }
        }
    }
    println!("{sum}");
}

// Recursive implementation of greedy algorithm.
// Returns Vec of length 12 if a result was found, guaranteed to be optimal.
// If there is no solution with the input, a shorter Vec is returned.
fn recursive(bank: &[(usize, u32)], mut cur: Vec<(usize, u32)>) -> Vec<(usize, u32)> {
    let pos = cur.last().unwrap().0;
    for &(idx, e) in bank.iter().filter(|(idx, _)| *idx > pos) {
        cur.push((idx, e));
        if cur.len() == 12 {
            // Recursion anchor: We have filled all 12 spots and therefore found
            // the best solution
            return cur;
        }
        // Recurse
        cur = recursive(bank, cur);
        if cur.len() == 12 {
            // Result found
            return cur;
        }
        // Nothing found, try next in this position
        cur.pop();
    }
    // Unsuccessful search with given inputs
    cur
}

fn part2(input: String) {
    let mut sum = 0;
    'banks: for l in input.lines() {
        let mut sorted: Vec<(usize, u32)> = l
            .chars()
            .map(|c| c.to_digit(10).unwrap())
            .enumerate()
            .collect();
        sorted.sort_by(|(_, a), (_, b)| a.cmp(b).reverse());
        let mut cur: Vec<(usize, u32)> = Vec::with_capacity(12);
        for &(idx, first) in &sorted {
            cur.push((idx, first));
            cur = recursive(&sorted, cur);
            if cur.len() == 12 {
                let num = cur.iter().fold(0u64, |acc, e| acc * 10 + e.1 as u64);
                sum += num;
                continue 'banks;
            }
            cur.pop();
        }
    }
    println!("{sum}");
}

util::aoc_main!();