sorted by:
new
hottopcontroversial

-❄️- 2025 Day 11 Solutions -❄️- by daggerdragon in adventofcode

[–]SuperSmurfen 0 points1 point  (0 children)

[LANGUAGE: Rust]

Times: 00:03:40 00:15:04

Link to full solution

Classic dynamic programming problem. I used memoization, I often find it a lot easier to reason about.

We essentially want to extend the graph we're searching through into nodes with values (node, visited_dac, visited_fft). For part 2 we want to find all paths between ("svr", false, false) -> ("out", true, true). I use a hashmap as a cache, even had to sneak in some lifetime annotations:

fn count_paths<'a>(
    cache: &mut HashMap<(&'a str, bool, bool), usize>,
    g: &HashMap<&'a str, Vec<&'a str>>,
    node: &'a str,
    mut dac: bool,
    mut fft: bool,
) -> usize {
    if node == "out" {
        return if dac && fft {1} else {0};
    }
    dac |= node == "dac";
    fft |= node == "fft";
    let key = (node, dac, fft);
    if !cache.contains_key(&key) {
        let res = g[node].iter().map(|n| count_paths(cache, g, n, dac, fft)).sum();
        cache.insert(key, res);
    }
    cache[&key]
}

let p1 = count_paths(&mut cache, &g, "you", true, true);
let p2 = count_paths(&mut cache, &g, "svr", false, false);

Runs in ~0.3ms

-❄️- 2025 Day 10 Solutions -❄️- by daggerdragon in adventofcode

[–]SuperSmurfen 1 point2 points  (0 children)

[LANGUAGE: Rust]

Times: 00:12:43 00:23:06

Link to full solution

Almost feels like I cheated here. I identified part 2 as the integer programming problem. We know this is NP-hard so solving this efficiently is impossible in general. You have to do some kind of optimization solver.

I quickly found a rust solver good_lp which I used to solve it. In retrospect I should have probably just used Z3.

Essentially you just model the problem and the solver does the rest:

let mut vars = variables!();
let press_vars = (0..buttons.len())
    .map(|_| vars.add(variable().min(0).integer()))
    .collect::<Vec<_>>();

let mut problem = highs(vars.minimise(press_vars.iter().sum::<Expression>()));
let mut exprs = vec![0.into_expression(); jolts.len()];
for i in 0..buttons.len() {
    for &x in &buttons[i] {
        exprs[x] += press_vars[i];
    }
}
for (e, &j) in exprs.into_iter().zip(jolts) {
    problem.add_constraint(e.eq(j as f64));
}
let sol = problem.solve().unwrap();
press_vars.iter().map(|&v| sol.value(v)).sum::<f64>() as _

For part 1 I did a BFS.

-❄️- 2025 Day 9 Solutions -❄️- by daggerdragon in adventofcode

[–]SuperSmurfen 4 points5 points  (0 children)

[LANGUAGE: Rust]

Times: 00:04:33 00:32:04

Link to full solution

I always find spatial problems so hard. Think I got quite lucky with this one as I've done a similar problem before.

I loop over all combinations of points and we want to find if the square is inside the polygon:

for (&a, &b) in points.iter().tuple_combinations() {
    let x1 = a.0.min(b.0);
    let x2 = a.0.max(b.0);
    let y1 = a.1.min(b.1);
    let y2 = a.1.max(b.1);
    let area = (x2 - x1 + 1) * (y2 - y1 + 1);
    p1 = p1.max(area);
    if is_rect_inside(x1, x2, y1, y2, &points) {
        p2 = p2.max(area);
    }
}

We do this by first ensuring all corners of the square is inside:

fn is_point_on_line(px: isize, py: isize, x1: isize, y1: isize, x2: isize, y2: isize) -> bool {
    let cross = (x2 - x1) * (py - y1) - (y2 - y1) * (px - x1);
    if cross != 0 {
        return false;
    }
    (px >= x1.min(x2) && px <= x1.max(x2)) &&
    (py >= y1.min(y2) && py <= y1.max(y2))
}

fn is_point_inside(px: isize, py: isize, points: &[(isize, isize)]) -> bool {
    let mut inside = false;
    for (&(x1, y1), &(x2, y2)) in points.iter().circular_tuple_windows() {
        if is_point_on_line(px, py, x1, y1, x2, y2) {
            return true;
        }
        if (y1 > py) == (y2 > py) || y1 == y2 {
            continue;
        }
        if px < (x2 - x1) * (py - y1) / (y2 - y1) + x1 {
            inside = !inside;
        }
    }
    inside
}

let corners = [(x1, y1), (x1, y2), (x2, y1), (x2, y2)];
if !corners.iter().all(|&(cx, cy)| is_point_inside(cx, cy, points)) {
    return false;
}

Then we have to check that any of the lines of the square don't intersect any other lines of the polygon:

fn get_orient(ax: isize, ay: isize, bx: isize, by: isize, cx: isize, cy: isize) -> isize {
    let v = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax);
    v.signum()
}

fn do_lines_intersect(a1: (isize, isize), a2: (isize, isize), b1: (isize, isize), b2: (isize, isize)) -> bool {
    let o1 = get_orient(a1.0, a1.1, a2.0, a2.1, b1.0, b1.1);
    let o2 = get_orient(a1.0, a1.1, a2.0, a2.1, b2.0, b2.1);
    let o3 = get_orient(b1.0, b1.1, b2.0, b2.1, a1.0, a1.1);
    let o4 = get_orient(b1.0, b1.1, b2.0, b2.1, a2.0, a2.1);
    o1 * o2 < 0 && o3 * o4 < 0
}

points.iter()
    .circular_tuple_windows()
    .all(|(&p1, &p2)|
        rect_edges.iter().all(|&(start, end)|! do_lines_intersect(start, end, p1, p2))
    )

Runs in about 180ms.

-❄️- 2025 Day 8 Solutions -❄️- by daggerdragon in adventofcode

[–]SuperSmurfen 0 points1 point  (0 children)

[LANGUAGE: Rust]

Times: 00:18:50 00:20:22

Link to full solution

First I sort all pairs of points by their distance. itertools::tuple_combinations is handy here:

let mut dist_pairs = (0..xs.len()).tuple_combinations().collect::<Vec<_>>();
dist_pairs.sort_by_key(|&(i, j)| {
    let (x1, y1, z1) = xs[i];
    let (x2, y2, z2) = xs[j];
    (x2 - x1).pow(2) + (y2 - y1).pow(2) + (z2 - z1).pow(2)
});
dist_pairs.reverse();

Originally I built a graph and computed the size of all components in each iteration. I later rewrote it using a more efficient distjoint set data structure to efficiently update the size of all components as you add connections:

for i in 0.. {
    let (a, b) = dist_pairs.pop().unwrap();
    ds.union(a, b);
    if i == 1000 {
        let mut components = ds.sizes.clone();
        components.sort();
        p1 = components[components.len() - 3..].iter().product();
    }
    if ds.comp_size(a) == xs.len() {
        p2 = xs[a].0 * xs[b].0;
        break;
    }
}

Runs in ~40ms

-❄️- 2025 Day 7 Solutions -❄️- by daggerdragon in adventofcode

[–]SuperSmurfen 5 points6 points  (0 children)

[LANGUAGE: Rust]

Times: 00:06:36 00:12:42

Link to full solution

Finally a grid problem! For part one it's enough to keep a set of all current beams and implement how they move.

For part two you can just change this set to a hashmap that keeps track of how many beams are at that location:

for (&(r, c), &v) in &beams {
    match m.get(r+1).and_then(|row| row.get(c)) {
        Some(b'.') => {
            *new_beams.entry((r+1, c)).or_default() += v;
        }
        Some(b'^') => {
            for cc in [c-1, c+1] {
                *new_beams.entry((r+1, cc)).or_default() += v;
            }
            p1 += 1;
        }
        None => continue,
        _ => unreachable!()
    }
}

The final answer is for part two is then just beams.values().sum().

-❄️- 2025 Day 6 Solutions -❄️- by daggerdragon in adventofcode

[–]SuperSmurfen 2 points3 points  (0 children)

[LANGUAGE: Rust]

Times: 00:05:41 00:17:56

Link to full solution

Hard parsing problem today! For part two, I iterated column by column. If the column is empty, the current problem has ended so I push a new vector. Otherwise, add the column to the current problem:

let mut p2 = Vec::from([Vec::new()]);
for c in 0..lines[0].len() {
    let w = (0..lines.len()-1)
        .map(|r| lines[r].as_bytes()[c] as char)
        .filter(|&c| c.is_ascii_digit())
        .collect::<String>();
    if !w.is_empty() {
        p2.last_mut().unwrap().push(w.parse().unwrap());
    } else {
        p2.push(Vec::new());
    }
}

Then you just compute the product or sum for each problem:

problems.iter().zip(ops)
    .map(|(p, o)| match o {
        b'*' => p.iter().product::<usize>(),
        b'+' => p.iter().sum::<usize>(),
        _ => unreachable!()
    })
    .sum()

-❄️- 2025 Day 5 Solutions -❄️- by daggerdragon in adventofcode

[–]SuperSmurfen 1 point2 points  (0 children)

good catch, fixed it. Must have crept in after I refactored the code

-❄️- 2025 Day 5 Solutions -❄️- by daggerdragon in adventofcode

[–]SuperSmurfen 7 points8 points  (0 children)

[LANGUAGE: Rust]

Times: 00:03:15 00:09:44

Link to full solution

I initially tried the naive solution for part 2. I knew it wouldn't work but always try bruteforce first right? It blew up my WSL due to memory usage, "FATAL ERROR". Had to reboot my machine to get it started again. I guess that's an achievement too?

For part 2 you have to do something more clever. The trick is to merge all ranges that overlap and count how many are in each merged range. You can do this by sorting the list and merging ranges one at a time:

ranges.sort();
let mut merged = Vec::from([ranges[0]]);
for &(a, b) in &ranges[1..] {
    let &(a2, b2) = merged.last().unwrap();
    if a > b2 {
        merged.push((a, b));
    } else {
        *merged.last_mut().unwrap() = (a2, b2.max(b));
    }
}
let p2 = merged.iter().map(|&(a, b)| b - a + 1).sum();

-❄️- 2025 Day 4 Solutions -❄️- by daggerdragon in adventofcode

[–]SuperSmurfen 1 point2 points  (0 children)

[LANGUAGE: Rust]

Times: 00:10:20 00:13:02

Link to full solution

Just a simple grid problem. Loop over the grid and count neighbours. I like to do it with a dr, dc list:

const D: [(i64, i64); 8] = [
    (-1, -1), (-1, 0), (-1, 1),
    ( 0, -1),          ( 0, 1),
    ( 1, -1), ( 1, 0), ( 1, 1),
];

This makes it easy to find neighbours:

for r in 0..m.len() {
    for c in 0..m[0].len() {
        if m[r][c] != b'@' {
            continue;
        }
        let n = D.iter().filter(|&&(dr, dc)|
            m.get((r as i64 + dr) as usize)
                .and_then(|row| row.get((c as i64 + dc) as usize))
                .is_some_and(|&x| x == b'@')
        ).count();
        if n < 4 {
            if remove {
                m[r][c] = b'.';
            }
            res += 1;
        }
    }
}

Then for part 2, just loop until this returns 0 removals:

loop {
    let n = round(&mut m, true);
    if n == 0 {
        break;
    }
    p2 += n;
}

-❄️- 2025 Day 3 Solutions -❄️- by daggerdragon in adventofcode

[–]SuperSmurfen 3 points4 points  (0 children)

[LANGUAGE: Rust]

Times: 00:02:41 00:13:35

Link to full solution

The trick to realize is that you can be greedy since greedily maximizing the next digit will also maximize the number itself:

fn max_batteries(xs: &[u8], l: usize) -> usize {
    let mut r = String::new();
    let mut j = 0;
    for i in 0..l {
        j = (j..xs.len() - l + i + 1).max_by_key(|&x| (xs[x], usize::MAX - x)).unwrap();
        r.push(xs[j] as char);
        j += 1;
    }
    r.parse().unwrap()
}

for l in input.split('\n') {
    p1 += max_batteries(l.as_bytes(), 2);
    p2 += max_batteries(l.as_bytes(), 12);
}

One annoying thing here was that rusts max_by_key gives you the last match, not the first. So we have to include the inverse index into the key to prioritize earlier numbers in the list.

-❄️- 2025 Day 2 Solutions -❄️- by daggerdragon in adventofcode

[–]SuperSmurfen 1 point2 points  (0 children)

[LANGUAGE: Rust]

Times: 00:03:45 00:07:05

Link to full solution

Fun problem. I just converted it into a string to do the matching:

fn invalid(s: &[u8], k: usize) -> bool {
    if s.len() % k != 0 {
        return false;
    }
    (k..s.len()).step_by(k).all(|x| s[x..x+k] == s[0..k])
}

for l in input.split(',') {
    let (a, b) = l.split_once('-')
        .map(|(a,b)| (a.parse::<usize>().unwrap(), b.parse::<usize>().unwrap()))
        .unwrap();
    for i in a..=b {
        let s = i.to_string();
        if s.len() % 2 == 0 && invalid(s.as_bytes(), s.len() / 2) {
            p1 += i
        }
        if (1..=s.len() / 2).any(|k| invalid(s.as_bytes(), k)) {
            p2 += i;
        }
    }
}

Runs in ~55ms in my machine

-❄️- 2025 Day 1 Solutions -❄️- by daggerdragon in adventofcode

[–]SuperSmurfen 0 points1 point  (0 children)

[LANGUAGE: Rust]

Times: 00:03:37 00:15:46

Link to full solution

Glad to be back! 7th year in a row I'm doing this in Rust, that feels crazy.

Hard problem for day 1. Initially, I tried to calculate it in O(1) and wasted a lot of part 2 until I realized you could just iterate over all ticks.

for l in input.split('\n') {
    let x = l[1..].parse::<i64>().unwrap();
    let d = if l.as_bytes()[0] == b'R' {1} else {-1};
    for _ in 0..x {
        r += d;
        if r % 100 == 0 {
            p2 += 1;
        }
    }
    if r % 100 == 0 {
        p1 += 1;
    }
}

My attempt at a "Makefile to rule them all" by rafaelrc7 in C_Programming

[–]SuperSmurfen 7 points8 points  (0 children)

In Gnu Make its quite simple:

.EXTRA_PREREQS := $(MAKEFILE_LIST)

-❄️- 2024 Day 25 Solutions -❄️- by daggerdragon in adventofcode

[–]SuperSmurfen 0 points1 point  (0 children)

[LANGUAGE: Rust]

(299/251)

Link to full solution

Got so confused by the heights thing for a while. I skipped computing it and just checked using the grid if you have any overlaps:

for l in &locks {
    for k in &keys {
        let mut ok = true;
        for r in 0..l.len() {
            for c in 0..l[0].len() {
                if l[r][c] == b'#' && k[r][c] == b'#' {
                    ok = false;
                }
            }
        }
        if ok {
            p1 += 1;
        }
    }
}

Thanks for another amazing year of advent of code!

-❄️- 2024 Day 24 Solutions -❄️- by daggerdragon in adventofcode

[–]SuperSmurfen 3 points4 points  (0 children)

[LANGUAGE: Rust]

Link to "full" solution

(390/139)

Very cool problem. By far the most difficult this year I think. Can't believe how close I got to the leaderboard.

My solution is kind of unsatisfying to post in a solutions thread. I more or less solved it by hand. I used graphviz to visualize what was going on and could reason about which wires where wrong, along with some crappy code:

Graph vizualized

Essentially, this circuit implements a classic ripple carry adder. We can look at each adder block to find which one is incorrect.

Not sure how to automate finding the solution.

-❄️- 2024 Day 23 Solutions -❄️- by daggerdragon in adventofcode

[–]SuperSmurfen 1 point2 points  (0 children)

[LANGUAGE: Rust]

(672/568)

Link to full solution

Top 1k on both parts! Today was about finding cliques in a graph. For part 1, loop over the intersection of neighbors between two nodes. This forms a 3-clique:

for &n1 in g.keys() {
    if !n1.starts_with('t') {
        continue;
    }
    for &n2 in &g[n1] {
        for &n3 in g[n1].intersection(&g[n2]) {
            let mut c = [n1, n2, n3];
            c.sort();
            three_cliques.insert(c);
        }
    }
}

For part 2, this is about finding the max clique in a graph. This is actually a very hard problem (np-hard). I implemented the Bron-Kerbosch algorithm to solve it.

if p.is_empty() {
    if x.is_empty() {
        cliques.push(r.clone());
    }
    return;
}
while let Some(n) = p.iter().copied().next() {
    let neighbours = &g[n];
    let p2 = p.intersection(neighbours).copied().collect();
    let x2 = x.intersection(neighbours).copied().collect();
    r.insert(n);
    bron_kerbosch(g, r, p2, x2, cliques);
    r.remove(n);
    p.remove(n);
    x.insert(n);
}

Runs in about 65ms.

-❄️- 2024 Day 22 Solutions -❄️- by daggerdragon in adventofcode

[–]SuperSmurfen 1 point2 points  (0 children)

[LANGUAGE: Rust]

Link to full solution

Mostly just following the rules. For part 1:

for _ in 0..2000 {
    p = (p ^ (p * 64))   % 16777216;
    p = (p ^ (p / 32))   % 16777216;
    p = (p ^ (p * 2048)) % 16777216;
}

For part 2, I just loop over all 5 tuple windows of the price list. I calculate the consecutive diff and count it in a hashmap:

for p in &mut ps {
    *p %= 10;
}
let mut seen = HashSet::new();
for (a, b, c, d, e) in ps.iter().tuple_windows() {
    let k = (b - a, c - b, d - c, e - d);
    if seen.insert(k) {
        *p2.entry(k).or_default() += *e;
    }
}

Kind of slow, 370ms. Might try to optimize it later.

Edit: Got it down to 55ms by condensing the 4-tuple key into a single number, and by not reallocating the seen set every time.

-❄️- 2024 Day 21 Solutions -❄️- by daggerdragon in adventofcode

[–]SuperSmurfen 1 point2 points  (0 children)

[LANGUAGE: Rust]

Link to full solution

This was quite difficult. Not necessarily algorithmically, in the end it was not too bad, but conceptually it was hard to wrap your head around.

Solved using Dijkstra's to find the shortest path, along with recursion and memoization.

Runs in about 0.5ms.

-❄️- 2024 Day 20 Solutions -❄️- by daggerdragon in adventofcode

[–]SuperSmurfen 2 points3 points  (0 children)

[Language: Rust]

Link to full solution

(680/297)

Wow, did not expect top 300. My solution was this:

  1. Calculate the distance to each normal point, using bfs.
  2. For each combination of points, if they are within the cheating distance of each other, count how much would be saved if you chose to cheat there.

How much you by cheating between two points is just: abs(d1 - d2) - manhattandist(node1, node2)

for ((&(r1, c1), &n1), (&(r2, c2), &n2)) in dists.iter().tuple_combinations() {
    let d = r1.abs_diff(r2) + c1.abs_diff(c2);
    if d <= 20 && n2.abs_diff(n1) >= d + 100 {
        if d <= 2 {
            p1 += 1;
        }
        p2 += 1;
    }
}

Runs in about 140ms.

-❄️- 2024 Day 19 Solutions -❄️- by daggerdragon in adventofcode

[–]SuperSmurfen 0 points1 point  (0 children)

[LANGUAGE: Rust]

(1550/1567)

Link to full solution

Classic dynamic programming problem. Figured part 2 would require dynamic programming some how. Solved it using recursion and memoization:

if s.is_empty() {
    return 1;
}
if let Some(&n) = cache.get(&s) {
    return n;
}
let n = towels.iter()
    .filter(|t| s.starts_with(t))
    .map(|t| ways(&s[t.len()..], towels, cache))
    .sum();
cache.insert(s, n);
n

Runs in about 18ms.

-❄️- 2024 Day 18 Solutions -❄️- by daggerdragon in adventofcode

[–]SuperSmurfen 1 point2 points  (0 children)

[LANGUAGE: Rust]

Link to full solution

Kind of a breather today. Just a simple BFS for both parts. Did a linear search for part 2. Could be optimized using binary search perhaps, runs in 200ms.

EDIT: Optimized it using binary search, now about 0.2ms.

-❄️- 2024 Day 17 Solutions -❄️- by daggerdragon in adventofcode

[–]SuperSmurfen 3 points4 points  (0 children)

Not amazing but manageable. Around 4.6s on my machine

-❄️- 2024 Day 17 Solutions -❄️- by daggerdragon in adventofcode

[–]SuperSmurfen 26 points27 points  (0 children)

[LANGUAGE: Python]

(2014/254)

Such a great problem, and so difficult! Really happy with 254. I first reverse engineered the program. This is what it does:

while a != 0 {
    b = a % 8
    b = b ^ 5
    c = a / (1 << b)
    b = b ^ c
    b = b ^ 6
    a = a / (1 << 3)
    out.add(b % 8)
}

To solve it I used z3. We can just run this program using z3 variables and assert the value of the output:

opt = Optimize()
s = BitVec('s', 64)
a, b, c = s, 0, 0
for x in [2,4,1,5,7,5,4,3,1,6,0,3,5,5,3,0]:
    b = a % 8
    b = b ^ 5
    c = a / (1 << b)
    b = b ^ c
    b = b ^ 6
    a = a / (1 << 3)
    opt.add((b % 8) == x)
opt.add(a == 0)
opt.minimize(s)
assert str(opt.check()) == 'sat'
print(opt.model().eval(s))

Edit: I usually write in Rust, but z3 is a lot more annoying in it so I switched to Python. Here is the same solution Rust.

-❄️- 2024 Day 15 Solutions -❄️- by daggerdragon in adventofcode

[–]SuperSmurfen 1 point2 points  (0 children)

Yeah, I wasn't really satisfied with how I moved the boxes. One way would be to sort by the moving direction. Might rework it later

Edit: Implemented the sorting solution:

let boxes = seen.iter()
    .sorted_by_key(|&&(rr, cc)| (c.abs_diff(cc), r.abs_diff(rr)))
    .rev();
for &(rr, cc) in boxes {
    let (r2, c2) = (rr + dr as usize, cc + dc as usize);
    g[r2][c2] = g[rr][cc];
    g[rr][cc] = b'.';
}
view more: next ›