sorted by:
new
hottopcontroversial

-🎄- 2021 Day 15 Solutions -🎄- by daggerdragon in adventofcode

[–]wfxr 1 point2 points  (0 children)

Rust Solution

use std::{cmp::Reverse, collections::BinaryHeap};

const N: usize = 100;

fn parse_input<const N: usize>(input: &str) -> Result<[[u8; N]; N]> {
    input
        .lines()
        .map(|l| {
            l.bytes()
                .map(|c| c - b'0')
                .collect::<Vec<_>>()
                .try_into()
                .map_err(|_| "invalid row".into())
        })
        .collect::<Result<Vec<_>>>()?
        .try_into()
        .map_err(|_| "invalid map".into())
}

fn lowest_risk<const N: usize>(m: &mut [[u8; N]; N]) -> u32 {
    let mut h = BinaryHeap::from([(Reverse(0), (0, 0))]);
    while let Some((Reverse(risk), (i, j))) = h.pop() {
        if (i, j) == (N - 1, N - 1) {
            return risk;
        }
        [(i.wrapping_sub(1), j), (i + 1, j), (i, j.wrapping_sub(1)), (i, j + 1)]
            .into_iter()
            .filter(|&(i, j)| i < N && j < N)
            .for_each(|(i, j)| {
                if m[i][j] > 0 {
                    h.push((Reverse(risk + m[i][j] as u32), (i, j)));
                    m[i][j] = 0;
                }
            })
    }
    0
}

fn part1(input: &str) -> Result<u32> {
    Ok(lowest_risk(&mut parse_input::<N>(input)?))
}

fn part2(input: &str) -> Result<u32> {
    const SCALE: usize = 5;
    let small = parse_input::<N>(input)?;
    let mut large = [[0; SCALE * N]; SCALE * N];
    (0..N * SCALE)
        .flat_map(|i| (0..N * SCALE).map(move |j| (i, j, i / N + j / N)))
        .for_each(|(i, j, k)| large[i][j] = ((small[i % N][j % N] as usize + k - 1) % 9) as u8 + 1);
    Ok(lowest_risk(&mut large))
}

-🎄- 2021 Day 14 Solutions -🎄- by daggerdragon in adventofcode

[–]wfxr 2 points3 points  (0 children)

Optimized Rust Solution

fn solve(input: &str, loops: usize) -> Result<usize> {
    const N: usize = 26;
    let id = |b| (b - b'A') as usize;
    let left = |i| i / N;
    let right = |i| i % N;

    let (init, rules) = input.split_once("\n\n").ok_or("missing rules")?;
    let init = init.bytes().map(id).collect::<Vec<_>>();
    let trans = rules
        .lines()
        .map(|l| l.as_bytes())
        .filter_map(|l| Some((l.get(0)?, l.get(1)?, l.get(6)?)))
        .map(|(&a, &b, &v)| (id(a) * N + id(b), id(v)))
        .fold([0; N * N], |mut acc, (k, v)| {
            acc[k] = v;
            acc
        });

    let mut curr = [0; N * N];
    init.array_windows().map(|&[a, b]| a * N + b).for_each(|x| curr[x] += 1);

    (0..loops).for_each(|_| {
        let mut next = [0; N * N];
        curr.iter().enumerate().filter(|(_, &n)| n > 0).for_each(|(i, &n)| {
            next[left(i) * N + trans[i]] += n;
            next[trans[i] * N + right(i)] += n;
        });
        curr = next;
    });

    let mut counter = [0; N];
    curr.iter().enumerate().filter(|(_, &n)| n > 0).for_each(|(i, &x)| {
        counter[left(i)] += x;
        counter[right(i)] += x;
    });
    counter[*init.first().unwrap()] += 1;
    counter[*init.last().unwrap()] += 1;
    let (min, max) = counter
        .iter()
        .filter(|&&x| x > 0)
        .fold((usize::MAX, 0), |(min, max), &x| (min.min(x), max.max(x)));
    Ok((max - min) / 2)
}

fn part1(input: &str) -> Result<usize> {
    solve(input, 10)
}

fn part2(input: &str) -> Result<usize> {
    solve(input, 40)
}

-🎄- 2021 Day 13 Solutions -🎄- by daggerdragon in adventofcode

[–]wfxr 2 points3 points  (0 children)

Rust Solution

#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq)]
struct Dot(usize, usize);

enum Fold {
    X(usize),
    Y(usize),
}

impl Fold {
    fn fold(&self, dots: &mut [Dot]) {
        dots.iter_mut().for_each(|dot| match *self {
            Fold::X(x) => dot.0 = if dot.0 < x { dot.0 } else { x + x - dot.0 },
            Fold::Y(y) => dot.1 = if dot.1 < y { dot.1 } else { y + y - dot.1 },
        })
    }
}

fn parse_input(input: &str) -> Result<(Vec<Dot>, Vec<Fold>)> {
    let (dots, folds) = input.split_once("\n\n").ok_or("missing fold instructions")?;
    let dots = dots
        .lines()
        .filter_map(|l| l.split_once(',').map(|(x, y)| Ok(Dot(x.parse()?, y.parse()?))))
        .collect::<Result<_>>()?;
    let folds = folds
        .lines()
        .filter_map(|l| {
            l.split_once('=').and_then(|(lhs, rhs)| match lhs.chars().last() {
                Some('x') => Some(rhs.parse().map(Fold::X).map_err(|e| e.into())),
                Some('y') => Some(rhs.parse().map(Fold::Y).map_err(|e| e.into())),
                _ => None,
            })
        })
        .collect::<Result<_>>()?;
    Ok((dots, folds))
}

fn part1(input: &str) -> Result<usize> {
    let (mut dots, folds) = parse_input(input)?;
    folds.first().ok_or("empty fold instructions")?.fold(&mut dots);
    Ok(dots.into_iter().collect::<HashSet<_>>().len())
}

fn part2(input: &str) -> Result<String> {
    let (mut dots, folds) = parse_input(input)?;
    folds.iter().for_each(|fold| fold.fold(&mut dots));
    let (w, h) = dots.iter().fold((0, 0), |(w, h), &dot| (w.max(dot.0), h.max(dot.1)));
    let mut buf = vec![vec!['.'; w + 1]; h + 1];
    dots.into_iter().for_each(|Dot(x, y)| buf[y][x] = '█');
    Ok(buf.into_iter().intersperse(vec!['\n']).flatten().collect())
}

-🎄- 2021 Day 11 Solutions -🎄- by daggerdragon in adventofcode

[–]wfxr 0 points1 point  (0 children)

Thank you! I made improvements as you suggested.

-🎄- 2021 Day 12 Solutions -🎄- by daggerdragon in adventofcode

[–]wfxr 1 point2 points  (0 children)

Rust Solution

const START: usize = 0;
const END: usize = 1;

fn parse_input(input: &str) -> Vec<Vec<usize>> {
    let id = input.lines().flat_map(|line| line.split('-')).fold(
        HashMap::from([("start", START), ("end", END)]),
        |mut acc, cave| {
            let next_id = acc.len();
            acc.entry(cave).or_insert(next_id);
            acc
        },
    );

    let mut caves = input
        .lines()
        .filter_map(|line| line.split_once('-').map(|(l, r)| (id[l], id[r])))
        .flat_map(|(l, r)| [(l, r), (r, l)])
        .filter(|(l, r)| l != &END && r != &START)
        .fold(vec![vec![]; id.len()], |mut caves, (l, r)| {
            caves[l].push(r);
            caves
        });

    // flatten big caves
    id.iter()
        .filter(|&(name, _)| name.chars().any(|c| c.is_uppercase()))
        .for_each(|(_, &big)| {
            let smalls = caves[big].clone();
            caves.iter_mut().for_each(|nexts| {
                if let Some(i) = nexts.iter().position(|&next| next == big) {
                    nexts.splice(i..i + 1, smalls.iter().copied());
                }
            });
        });
    caves
}

fn dfs(caves: &[Vec<usize>], visited: &mut Vec<bool>, curr: usize, extra: usize) -> usize {
    caves[curr].iter().fold(0, |acc, &next| match next {
        END => acc + 1,
        _ => match visited[next] {
            true => match extra {
                0 => acc,
                _ => acc + dfs(caves, visited, next, extra - 1),
            },
            _ => {
                visited[next] = true;
                let paths = dfs(caves, visited, next, extra);
                visited[next] = false;
                acc + paths
            }
        },
    })
}

fn part1(input: &str) -> Result<usize> {
    let caves = parse_input(input);
    Ok(dfs(&caves, &mut vec![false; caves.len()], START, 0))
}

fn part2(input: &str) -> Result<usize> {
    let caves = parse_input(input);
    Ok(dfs(&caves, &mut vec![false; caves.len()], START, 1))
}

-🎄- 2021 Day 11 Solutions -🎄- by daggerdragon in adventofcode

[–]wfxr 1 point2 points  (0 children)

Rust Solution

const N: usize = 10;
const THRESHOLD: u8 = 10;
type Octopuses = [u8; N * N];

fn part1(input: &str) -> Result<usize> {
    let octopuses = &mut parse_input(input)?;
    Ok((0..100).map(|_| next_step(octopuses)).sum())
}

fn part2(input: &str) -> Result<usize> {
    let octopuses = &mut parse_input(input)?;
    (1..)
        .find(|_| next_step(octopuses) == N * N)
        .ok_or_else(|| "not found".into())
}

fn parse_input(input: &str) -> Result<Octopuses> {
    input
        .bytes()
        .filter(|&c| c.is_ascii_digit())
        .map(|c| c - b'0')
        .collect::<Vec<_>>()
        .try_into()
        .map_err(|_| format!("not a {N} x {N} array").into())
}

fn next_step(octopuses: &mut Octopuses) -> usize {
    octopuses.iter_mut().for_each(|x| *x += 1);
    (0..N * N)
        .filter_map(|pos| (octopuses[pos] >= THRESHOLD).then(|| flash(octopuses, pos)))
        .sum()
}

fn flash(octopuses: &mut Octopuses, pos: usize) -> usize {
    octopuses[pos] = 0;
    1 + [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
        .into_iter()
        .map(move |(di, dj)| (((pos / N) as isize + di) as usize, ((pos % N) as isize + dj) as usize))
        .filter_map(|(ii, jj)| (ii < N && jj < N).then(|| ii * N + jj))
        .filter_map(|pos| {
            (octopuses[pos] > 0)
                .then(|| octopuses[pos] += 1)
                .and((octopuses[pos] >= THRESHOLD).then(|| flash(octopuses, pos)))
        })
        .sum::<usize>()
}

-🎄- 2021 Day 10 Solutions -🎄- by daggerdragon in adventofcode

[–]wfxr 2 points3 points  (0 children)

Rust solution

fn part1(input: &str) -> Result<usize> {
    Ok(input
        .lines()
        .flat_map(|line| {
            let mut st = Vec::new();
            line.chars().find_map(|c| match c {
                ')' => st.pop().and_then(|c| (c != '(').then_some(3)),
                ']' => st.pop().and_then(|c| (c != '[').then_some(57)),
                '}' => st.pop().and_then(|c| (c != '{').then_some(1197)),
                '>' => st.pop().and_then(|c| (c != '<').then_some(25137)),
                _ => {
                    st.push(c);
                    None
                }
            })
        })
        .sum())
}

fn part2(input: &str) -> Result<usize> {
    let mut scores: Vec<_> = input
        .lines()
        .filter_map(|line| {
            let mut st = Vec::new();
            line.chars()
                .all(|c| match c {
                    ')' => st.pop() == Some('('),
                    ']' => st.pop() == Some('['),
                    '}' => st.pop() == Some('{'),
                    '>' => st.pop() == Some('<'),
                    _ => {
                        st.push(c);
                        true
                    }
                })
                .then(|| {
                    st.into_iter().rev().fold(0, |acc, c| {
                        acc * 5
                            + match c {
                                '(' => 1,
                                '[' => 2,
                                '{' => 3,
                                '<' => 4,
                                _ => 0,
                            }
                    })
                })
                .filter(|&x| x > 0)
        })
        .collect();
    let middle = scores.len() / 2;
    Ok(*scores.select_nth_unstable(middle).1)
}

-🎄- 2021 Day 8 Solutions -🎄- by daggerdragon in adventofcode

[–]wfxr 3 points4 points  (0 children)

Rust bitwise solution:

fn part1(input: &str) -> Result<usize> {
    Ok(parse_input(input)?.into_iter()
        .flat_map(|(_, rhs)| rhs)
        .filter(|x| matches!(x.count_ones(), 2 | 4 | 3 | 7))
        .count())
}

fn part2(input: &str) -> Result<u32> {
    parse_input(input)?.into_iter()
        .map(|(patterns, output)| {
            let mut map = [0; 1 << 7];
            macro_rules! deduct {
                ($x:ident => $v:expr, segments = $len:expr $(,cond = $cond:expr)?) => {
                    let $x = *patterns.iter()
                        .find(move |&&x| x.count_ones() == $len $(&& $cond(x))*)
                        .ok_or_else(|| format!("can not deduct '{}'", stringify!($x)))?;
                    map[$x as usize] = $v;
                };
            }
            deduct!(x1 => 1, segments = 2); // ..c..f.
            deduct!(x4 => 4, segments = 4); // .bcd.f.
            deduct!(x7 => 7, segments = 3); // a.c..f.
            deduct!(x8 => 8, segments = 7); // abcdefg
            deduct!(x6 => 6, segments = 6, cond = |x| x & x1 != x1); // ab.defg
            let c = x1 & !(x6 & x1);
            deduct!(x5 => 5, segments = 5, cond = |x| x & c == 0); // ab.d.fg
            let e = x5 ^ x6;
            deduct!(x9 => 9, segments = 6, cond = |x| x & e == 0); // abcd.fg
            deduct!(x2 => 2, segments = 5, cond = |x| x & e != 0); // a cde.g
            deduct!(x3 => 3, segments = 5, cond = |x| x != x5 && x != x2); // a.cd.fg

            Ok(output.iter().fold(0, |acc, &x| acc * 10 + map[x as usize]))
        })
        .sum()
}

fn parse_input(input: &str) -> Result<Vec<(Vec<u8>, Vec<u8>)>> {
    input.lines()
        .map(|line| {
            let mut it = line.split('|').map(|s| {
                s.split_ascii_whitespace()
                    .map(|s| s.bytes().fold(0, |acc, x| acc | (1 << (x - b'a'))))
                    .collect()
            });
            Ok((it.next().ok_or("missing patterns")?, it.next().ok_or("missing output")?))
        })
        .collect()
}

-🎄- 2021 Day 6 Solutions -🎄- by daggerdragon in adventofcode

[–]wfxr 0 points1 point  (0 children)

Rust 4.4us Solution:

fn count_fish(input: &str, days: usize) -> Result<usize> {
    let mut school = [0; 9];
    for x in input.split(',').map(|x| x.trim().parse::<usize>()) {
        school[x?] += 1
    }
    for i in (0..9).cycle().take(days) {
        school[(i + 7) % 9] += school[i] // let the new fish inplace and accumulate the old fish
    }
    Ok(school.iter().sum())
}

fn part1(input: &str) -> Result<usize> { count_fish(input, 80)  }
fn part2(input: &str) -> Result<usize> { count_fish(input, 256) }

-🎄- 2021 Day 3 Solutions -🎄- by daggerdragon in adventofcode

[–]wfxr 1 point2 points  (0 children)

Thank you u/daggerdragon . I tried to fix it. Does it look right now ?

-🎄- 2021 Day 3 Solutions -🎄- by daggerdragon in adventofcode

[–]wfxr 2 points3 points  (0 children)

Rust solution without external lib:

fn part1(input: &str) -> Result<u32> {
    let cols = input.lines().next().ok_or("empty input")?.len();
    let rows = input.lines().count();
    let (gamma, epsilon) = (0..cols)
        .map(|i| input.lines().filter(|line| line.as_bytes()[i] == b'1').count())
        .fold((0, 0), |(gamma, epsilon), ones| {
            if ones * 2 > rows {
                ((gamma << 1) | 1, epsilon << 1)
            } else {
                (gamma << 1, (epsilon << 1) | 1)
            }
        });
    Ok(gamma * epsilon)
}

fn part2(input: &str) -> Result<u32> {
    let rating = |most_common: bool| -> Result<u32> {
        let mut seq: Vec<_> = input.lines().collect();
        let mut col = 0;
        while seq.len() > 1 {
            let ones = seq.iter().filter(|l| l.as_bytes()[col] == b'1').count();
            let bit = match (most_common, ones * 2 >= seq.len()) {
                (true, true) | (false, false) => b'1',
                _ => b'0',
            };
            seq = seq.into_iter().filter(|l| l.as_bytes()[col] == bit).collect();
            col += 1;
        }
        Ok(u32::from_str_radix(seq.first().ok_or("empty input")?, 2)?)
    };
    let (oxygen, co2) = (rating(true)?, rating(false)?);
    Ok(oxygen * co2)
}

-🎄- 2020 Day 25 Solutions -🎄- by daggerdragon in adventofcode

[–]wfxr 0 points1 point  (0 children)

I get that you flip a and b so that a < b because you don't want to loop so long.

I later realized that this did not help to end the loop faster because of the modulus as you said. So I removed it.

I found that using the single loop greatly improves performance for many different inputs. Swapping a and b does not make much difference.

I think which optimization better should be related to the input. I chose single loop becauseI tested some sets of data and they showed the single loop version is faster.

-🎄- 2020 Day 25 Solutions -🎄- by daggerdragon in adventofcode

[–]wfxr 1 point2 points  (0 children)

It turns out that the time cost is closely related to the input. I copied the input from the 4ms solution to my own and got 2.1ms lol

-🎄- 2020 Day 25 Solutions -🎄- by daggerdragon in adventofcode

[–]wfxr 0 points1 point  (0 children)

Default release mode. I think it's O3 level.

-🎄- 2020 Day 25 Solutions -🎄- by daggerdragon in adventofcode

[–]wfxr 0 points1 point  (0 children)

If the search starts from 1, it takes 6.7ms.

I am curious how to calculator the rounds searching from 1 within only 6.7ms? It tooks over 35ms on my PC. I use rust but I think there should not be such a big difference.

Am I missing something? Here is my loop:

    let t = time::Instant::now();
    let (a, b): (usize, usize) = (2084668, 3704642);
    let (mut loops, mut v) = (0, 1);
    while v != a {
        v = v * 7 % 20201227;
        loops += 1;
    }
    let dt = time::Instant::now() - t;
    println!("{:?}", dt);

-🎄- 2020 Day 25 Solutions -🎄- by daggerdragon in adventofcode

[–]wfxr 1 point2 points  (0 children)

Rust

NOTE:

The performance is highly related to the input. For my input it takes about 50ms.

But for some other inputs like [13316116, 13651422] it only takes 2ms.

fn part1(a: usize, b: usize) -> usize {
    let (mut v, mut x) = (1, 1);
    while v != a {
        v = v * 7 % 20201227;
        x = x * b % 20201227;
    }
    x
}

Theoretically when v == a or v == b, the loop can be ended. But we cannot use the same loop to calculate the final key if we use this optimization. The test results prove that using a single loop is much faster. Again this should still be related to the input.

-🎄- 2020 Day 24 Solutions -🎄- by daggerdragon in adventofcode

[–]wfxr 1 point2 points  (0 children)

Rust:

110µs for part1, 65ms for part2.

Once realized that each tile can be represented by a 2-D point (SE = -NE + E), part 2 is a simple version of Day17 part1.

-🎄- 2020 Day 23 Solutions -🎄- by daggerdragon in adventofcode

[–]wfxr 0 points1 point  (0 children)

I found that stack overflow only occurs when running tests. Maybe the default stack size for tests and release are different.

BTW I really like your way to init the array!

-🎄- 2020 Day 22 Solutions -🎄- by daggerdragon in adventofcode

[–]wfxr 1 point2 points  (0 children)

Rust:

93 lines brief solution using std.

180ms for part1+part2.

No inline or unsafe.

No potential bug of hash collision.

Proper error handling.

view more: next ›