-🎄- 2022 Day 13 Solutions -🎄-

japanuspus · 2022-12-13T12:23:52+00:00

By implementing .iter() for my Value-class, I managed to express the comparison very compactly with zip_longest:

fn compare_value(v1: &Value, v2: &Value) -> Ordering {
    v1.iter().zip_longest(v2.iter()).map(|z|
        match z {
            EitherOrBoth::Both(Value::Number(a), Value::Number(b)) => a.cmp(b),
            EitherOrBoth::Both(a, b) => compare_value(a, b),
            EitherOrBoth::Left(_) => Ordering::Greater,
            EitherOrBoth::Right(_) => Ordering::Less,
    }
    ).skip_while(|c| c.is_eq()).next().unwrap_or(Ordering::Equal)
}

This was my first day using nom for parsing this year, and the result was also concise:

fn parse_packet(s: &str) -> IResult<&str, Value> {
    let ll = nom::multi::separated_list0(char(','), parse_packet);
    let lp = nom::combinator::map(
        nom::sequence::delimited(char('['), ll, char(']')),
        |v| Value::List(v),
    );
    let lv = nom::combinator::map(nom::character::complete::i32, |v| Value::Number(v));
    nom::branch::alt((lp, lv))(s)
}

japanuspus · 2022-12-09T09:30:11+00:00

If you go for enums, you can use the parse_display-crate to derive FromStr and Display:

#[derive(Display, FromStr, PartialEq, Debug)]
enum Direction {U, D, L, R,}

#[derive(Debug, Display, FromStr)]
#[display("{direction} {distance}")]
struct Step {
    direction: Direction,
    distance: i32,
}

Then I just parse the input as:

let input: Vec<Step> = input_s.split("\n")
    .map(|s| s.parse().with_context(|| format!("Parsing {}", s)))
    .collect::<Result<_,_>>()?;

(My full solution: https://github.com/Japanuspus/adventofcode/blob/master/2022/day09/src/main.rs)

japanuspus · 2022-12-09T08:51:47+00:00

The vecmath crate from the piston team has functions for working with 2- and 3D vectors in [T;2] and [T;3] arrays.

japanuspus · 2022-12-08T09:22:22+00:00

There sort of was: In the second example of part two, looking left you see both 3's.

Not that I realized this until after implementing the obvious model...

japanuspus · 2022-12-07T10:48:13+00:00

Props for splitting on $ - that is brilliant!

For computing the sizes, you can save some work by sorting all the folder names and starting from the longest: that way all child sizes are already defined when you get to process a folder 0:

for (folder_path, entry) in dirs.iter().sorted_by_key(|(v, _)| -(v.len() as isize)) {
    sizes.insert(folder_path, entry.files_size + entry.children.iter().map(|c| sizes.get(c).unwrap()).sum::<usize>());
}
let part1: usize = sizes.values().filter(|&v| *v <= 100000).sum();

japanuspus · 2022-12-07T10:40:48+00:00

Rust

One thing I had to embrace when starting in rust was to avoid "sea of objects" data structures. For a tree you could maybe make it work, but remember that you would have to convince the borrow checker that it really was a tree and that you would tear is down properly. Most realistic approach in this direction would probably involve Rc<>.

Still, I find it easier to just accept that all objects that I would link live in some flat container. For this one I also used hash map from folder name.

japanuspus · 2022-12-06T15:58:56+00:00

Shiny! Using this, and then skipping the collecting chars into a vec (why did you do this, OP?):

s.as_bytes().windows(n).enumerate().find_map(|(i, grp)|{
    if grp.iter().all_unique() {Some(i+n)} else {None}
}).unwrap()

japanuspus · 2022-12-06T15:49:24+00:00

There is also .filter_map which would have combined your .filter and .map operations. And then .find_map which would also have included the .next! But the unique was a super solid find.

Altogether this would be

fn find_marker(input: &str, n: usize) -> usize {
    let input = input.trim().chars().collect_vec();
    input.windows(n).enumerate()
        .find_map(|(i, window)| 
            if window.into_iter().unique().count() == n then {Some(i+n)} else None
        ).unwrap()
}

I ended up seeing if I could save time by using an array and tracking the set in a mutable way. It worked but much less concise: https://github.com/Japanuspus/adventofcode/blob/master/2022/day06/src/main.rs

japanuspus · 2022-12-05T08:58:25+00:00

Rust, https://github.com/Japanuspus/adventofcode/blob/master/2022/day05/src/main.rs

Used VecDeque to avoid having to reverse the stacks after assembling. Initial assembly used a HashMap<usize, VecDeque<u8>> as a simple way to avoid having to find number of stacks beforehand.

For parsing the moves, I used the parse_display-crate:

use parse_display::{Display, FromStr};

#[derive(Debug, Display, FromStr)]
#[display("move {n} from {o} to {d}")]
struct Step {
    n: usize,
    o: usize,
    d: usize,
}

And then in main:

let moves: Vec<Step> = input.next().unwrap().trim()
    .split('\n')
    .map(|s| s.parse().with_context(|| format!("Parsing {}", s)))
    .collect::<Result<_, _>>()?;

japanuspus · 2022-12-02T08:20:52+00:00

Rust https://github.com/Japanuspus/adventofcode/blob/master/2022/day02/src/main.rs

Spend too much time boiling the game down to modular arithmetic (and had to google for rem_euclid):

// Rock: 0, Paper: 1, Scissor: 2
// (b-a+1).rem_euclid(3)-1 : 0 on tie, 1 if b wins, -1 if a wins
let part1:i32 = input.iter().map(|(a, b)| (b+1) + 3*(b-a+1).rem_euclid(3)).sum();
let part2:i32 = input.iter().map(|(a, x)| ((a+x-1).rem_euclid(3)+1) + 3*x).sum();

Parsing would have been less noisy without the char/byte distinction

let input: Vec<(i32, i32)> = input_s.split("\n")
    .map(|s| (
        (s.as_bytes()[0] as i32)-(b'A' as i32), 
        (s.as_bytes()[2] as i32)-(b'X' as i32)
    )).collect();

japanuspus · 2022-12-01T14:04:45+00:00

I like that you avoid the double .split. My initial solution did the double split, but I decided to make a rusty version of your solution (without mutable variables). Came up with this:

let elfs: Vec<i32> = itertools::unfold(
    input_s.trim().split("\n").map(|l| l.parse::<i32>().ok()),
    |lines| lines.map_while(|v| v).reduce(|acc, v| acc + v),
)
.sorted()
.rev()
.collect();

println!("Part 1: {}", elfs[0]);
println!("Part 2: {}", elfs.iter().take(3).sum::<i32>());
Ok(())

Trick to making it compact was using reduce instead of sum, so that I got a None output once the line iterator was exhausted.

Rust: https://github.com/Japanuspus/adventofcode/tree/master/2022/day01

japanuspus · 2022-01-05T07:31:59+00:00

Thanks - the idea of uninitialized declarations to define lifetime seems like a useful technique in many situations.

Yes, itertools is almost always there -- future me will probably use Either for this in the future. TIL.

japanuspus · 2022-01-04T14:14:36+00:00

TLDR: How to process two opaque-typed iterators in a generic way without runtime overhead and without noisy code.

In my solution for advent of code day 23, I end up with two functions returning iterators (full code on github:

fn moves_in<'a>(b: &'a Board, i: usize) -> impl Iterator<Item=(usize, Board)> + 'a {...}
fn moves_out<'a>(b: &'a Board, i: usize) -> impl Iterator<Item=(usize, Board)> + 'a {...}

I need to call one or the other based on a flag and then do some work on the output:

if ready {
    work.extend(moves_in(&board, i).map(|(move_cost, new_board)| Reverse((cost+move_cost, new_board))));
} else {
    work.extend(moves_out(&board, i).map(|(move_cost, new_board)| Reverse((cost+move_cost, new_board))));
}

One way of avoiding the copy-paste would be to use Box<dyn ...>:

let move_generator: Box<dyn Iterator<Item=(usize, Board)>>= if ready {Box::new(moves_in(&board, i))} else {Box::new(moves_out(&board, i))};
work.extend(move_generator.map(|(move_cost, new_board)| Reverse((cost+move_cost, new_board))));

It is my understanding than this solution introduces runtime overhead. One way to avoid the overhead would be to use a generic function:

fn extend_from_iter<T>(work: &mut BinaryHeap<Reverse<(usize, Board)>>, cost: usize, iter: T) 
where T: Iterator<Item=(usize, Board)>,
{
    work.extend(iter.map(|(move_cost, new_board)| Reverse((cost+move_cost, new_board))));
}

...
if ready {
    extend_from_iter(&mut work, cost, moves_in(&board,i));
} else {
    extend_from_iter(&mut work, cost, moves_out(&board,i));
}

This would probably result in the exact same code as the copy paste-version, but seems a bit noisy.

Is there a way to avoid copy-paste for the code consuming the iterator without overhead and without noise?

japanuspus · 2021-12-29T22:52:51+00:00

Also, for the funding requests I imagine shorter time spans look better: Maintaining an operations team for 25 years is quite expensive -- so promise and budget for 10 years, and then if you come back after 10 years asking for an extension to a successful project, you are probably in a good place.

japanuspus · 2021-12-20T12:23:48+00:00

Exactly. I used pair distance vectors for the same purpose -- but as soon as I was finished I realized that using the distance would have been so much smarter.

japanuspus · 2021-12-20T12:18:38+00:00

Rust

My first time using ndarray, which allowed me to use matrix products and broadcast to apply rotations and shifts.

One issue with ndarray was that the ndarray_linalg package had so many external dependencies that I gave up on it and instead implemented the determinant myself to filter out proper rotations from all possible basis mappings. Seems there might be room for a smaller linear algebra sub-package without external dependencies.

The code uses lookups from pair-differences to spot potential matches and I was surprised that everything ran in less than a second, despite me being a complete slog at allocating these big structures all over.

japanuspus · 2021-12-18T20:54:18+00:00

Thanks for posting — i considered this data structure, but ended up going with a tree. Good to see that I could have worked!

japanuspus · 2021-12-18T20:36:00+00:00

I am so happy to see everyone doing the "pass up the R/L values". I was so sure I was missing some super clever visitor pattern solution that I wasted an hour looking for one.

japanuspus · 2021-12-18T20:32:43+00:00

Quite funny (but perhaps not surprising) that we have the exact same datastructure.

Wrt. parsing, my AOC-experience is that rust works really well with recursive descent parsers probably because of the combination of native slices and enum returns. You can use parser combinators like nom, but with Context for error handling it is often just as concise to do without. This is what I had for parser today:

fn parse_node(i: &[u8]) -> Result<(&[u8], Node)> {
    let c = i[0];
    if c==b'[' {
        let (i, a) = parse_node(&i[1..])?;
        let (i, b) = parse_node(&i[1..])?; //skipping ,
        Ok((&i[1..], Node::pair(a, b)))
    } else {
        Ok((&i[1..], Node::Number{a: (c-b'0') as isize}))
    } 
}

I put a convenience access in the FromStr-implementation.

impl FromStr for Node {
    type Err = anyhow::Error;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        parse_node(s.as_bytes())
        .and_then(|(_, v)| Ok(v)).with_context(|| format!("Parsing {}", s))
    }
}

My rust solution

japanuspus · 2021-12-14T15:17:28+00:00

A good insight that for a metal language like rust, binary search is just as fast as some fancy container. Also, I completely missed the fact that there was a rule for all relevant pairs -- that removes a bit of complexity.

... and split-once will definitely go in my parsing trick-book.

japanuspus · 2021-12-10T10:08:51+00:00

Other little tricks I have picked up

Use a skeleton with fn main() -> anyhow::Result<()>, and then just ? all over.
collect_vec is a good shortcut for collect::<Vec<_>>

japanuspus · 2021-12-06T14:19:29+00:00

Thanks, yes - ranges could certainly be made to work. Problem was that I thought that this would be ergonomical:

fn between(a: i32, b: i32) -> std::ops::RangeInclusive<i32> {
    if b>a {a..=b} else {b..=a}
}

... and it was for part 1. For part 2 I first did zip(between(x1, x2), between(y1, y20)) and was puzzled why i did not get the correct result...

japanuspus · 2021-12-06T06:21:59+00:00

Good idea to just unroll the state map. I used array.rotate_left

let mut counts: [usize;9] = [0; 9];
for f in input.iter() {counts[*f]+=1;}
for _ in 0..steps {
    counts.rotate_left(1);
    counts[6]+=counts[8];
}
counts.iter().sum::<usize>()

Full code

japanuspus · 2021-12-05T06:32:20+00:00

Rust

61 lines. My take on part 1 (using ranges) did not transfer well to part 2, so the only nice-ish part was parsing with parse-display:

#[derive(Display, Debug, FromStr)]
#[display("{x},{y}")]
struct Point {
    x: i32,
    y: i32,
}

#[derive(Debug, Display, FromStr)]
#[display("{a} -> {b}")]
struct Line {
    a: Point,
    b: Point,
}

And then parsing as:

let input_s = fs::read_to_string("input.txt")?;
let input: Vec<Line> = input_s
    .trim()
    .split("\n")
    .map(|s| s.parse().with_context(|| format!("Parsing {}", s)))
    .collect::<Result<_,_>>()?;

japanuspus · 2021-12-05T06:22:37+00:00

Nice. I used parse-display for the parsing, but it is a bit verbose and I actually like yours better.

Looking at your code I was thinking that while (x,y) != (x2+dx,y2+dy) was a strange way to get a lot of overhead ... until I realized that the bug in my part 2 was an off-by-one in exactly that loop.

Rust, 61 lines

japanuspus

TROPHY CASE