I loved this! I’m doing AoC in rust this year to learn/get better with rust. So being able to watch your process for solving a problem I just solved myself, in detail like this is a huge help! I was able to pick up on a bunch of rust idioms just by you talking through your approach to the problem and considering your options, so I really hope you keep doing these, and keep the detailed talking through the problem in!
I, too, really like seeing how other people approach a problem. I almost always learn something new. And I really appreciate Chris talking through the problem and the solution rather than just presenting a solution (it's often that talking through it part where I learn something).
Plus one to this! as a noob to rust, I can get a basic program written jogging my C++ memories, but it is hard to know how “good” that solution is without exploring all the tools available in rust :)
Yeah, same--I'm coming from Python and don't often use map-apply programming patterns, so seeing how a Rust programmer solves these problems after I've done it in my hacky way is great for learning the style differences between the languages :)
The reason you can't sort an iterator is because it wouldn't have anywhere to store it. An iterator only has access to the current value, not past or future ones. Thus sorting requires collecting all of the elements into some sort of new container, which can then be sorted in place. This is what itertools does.
If that's what itertools does then there's no technical restriction to it being implemented. Yes, you can't sort an Iterator in-place because it requires all of the values, but terminating functions like collect have to create a new Vec anyway. The Iterator trait itself doesn't preclude this behavior from existing in the stdlib. Also, I was able to find the reason after the recording! Basically nobody seems to have RFC'd the functionality into the stdlib: github.com/rust-lang/rust/issues/38882
@@chrisbiscardi I think the reason for a sort method on iterators not being implemented is to avoid confusion about allocation. Iterators are also lazy, and sorting them completely defeats that. The trait is also defined in `core::iter::Iterator`, where an allocator isn't available.
But what about making an index array? The Sort iterator would have a [u32] array that specifies the sorted order, e.g. for vec![2,3,1] it would be [2,0,1] Or with another approach, each next invocation for the iterator would find the n-th lowest element. That would be less optimal though, but didn't require memory
I ended up solving this one almost the same way you did, and then experimented with other ideas just for the sake of learning. A few observations: There are also sort_unstable, sort_unstable_by, etc. They can be more efficient if it is OK to rearrange values that compare equal. On a problem of this size, the performance difference would be tiny; but it's good to know about for those cases when you have much larger inputs. For parsing the numbers, you can do: .map(str::parse::) (with no closure). I find that just a little easier to read. To sort in reverse, you can do: .sort_by(|a, b| a.cmp(b).reverse()) I think that more obviously conveys that you want it sorted in reverse. It's easy to overlook that `a` and `b` were swapped in the closure. There is also sort_by_key() combined with std::cmp::Reverse, which I find a little harder to read (and remember). I really hope you will post more Advent of Code videos. I enjoy seeing how other people approach problems, including going back and refining a solution.
this is awesome thank you. I just tackled problem 1 in Python and am starting to learn Rust, so will be following along with this series to try and learn :)
Thx for sharing your solution. I'm currently learning rust and use advent of code to play around with the language, and it's very helpful to have you explain certain aspects. Tomorrow, I will have to change my repository to your setup. That looks way more reasonable than mine 😅
Good suggestion. I ended up sorting, then calling .reverse(), then .iter().take(3).sum(). I forgot about reverse iterators. The .rev() method to turn a forward iterator into a reverse iterator just feels weird to me, an so I tend to forget about it. I would expect something like .iter_rev() or similar to directly construct a reverse iterator. (I get why they did it that way. That one method can be applied to iterators producing owned values, shared references, or exclusive references.)
Nice, love comparing solutions and not just blatantly copying yours because I'm stuck! I was thinking if it was possible to extend the Iterator trait such that you could pick the "top_3()" items or something. Digging through the Iterator file, it was a little too intimidating to start anything
you could start with using scan, using a 3 element sorted array as the state and then write an extension trait that uses scan behind the scenes doc.rust-lang.org/std/iter/trait.Iterator.html#method.scan
I probably would've ended up using coalesce like this: play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=a8f94ea0b82ce025dfe198aab4ee4784 The coalesce uses the outer Result to do the iteration, while the inner Result is the result from our parse. Otherwise the answer is mostly the same docs.rs/itertools/latest/itertools/trait.Itertools.html#method.coalesce
Funny challenge, though the questions are released in the middle of the night so I'm not even paying attention to the indicated delay to solve them. The delay should count from the instant the question is shown. +1 point for the TDD approach! I used itertools and coalesce so that I don't have to load the whole file in memory. I know it's not that big, it's just for the sake of trying.
This video is missing how you developed the code step by step :(. The whole using closures part is elegant, when it is ready, but when I want to add a simple println in the closure without the rest of them, I get errors, because I need to assign the typed correctly. This feels like a "write everything at once" solution and not something you can develop organically. I went for two for loops instead, which looks awful, but as I am new to Rust i could develop it step by step. However thank you for your video and the provided insights.
How are you adding the println? and what do you mean by "without the rest of them"? Do you mean that you want to have a println at an arbitrary location in the chain? If so there's a function for that: inspect. Here's a link to the documentation for it: doc.rust-lang.org/std/iter/trait.Iterator.html#method.inspect and I would also suggest using the dbg! macro instead of println! for debugging purposes. Personally, my step-by-step *was* write the code from top to bottom so I edited out the typing and covered the result. I wasn't doing any sort of debugging or whatnot. What sort of additional explanation are you looking for? Is it the existence of the iterator functions and where to find them?
@@chrisbiscardi Thank you very much for your time to answer. I dive deeper into Rust every day and it gets a bit clearer. I cannot answer anymore, what exactly I did wrong, but ownership issues after the collect is something I keep running into. I could do the day 3 solution kinda slow but it worked out thanks to your tutorials :). dbg! seems to have some problems with claiming ownership and destroys code I had after it, so I switched back to println and the real debugger. I might skip a day to do some more basic Rust tutorials. Thanks again for all your videos.
I chose --lib because I knew I was going to set up my binaries in the bin folder, so instead of generating a main.rs, --lib generates a lib.rs with a test that my bin folder can use
Nushell has been my primary shell for over a year now. I still have some bash/zsh isms in my fingers but it's been really solid for me and I really enjoy the data features
@@chrisbiscardi I was reminded to participate today by your video, and just seeing the parse function in the glance at the thumbnail felt like too much of a hint, especially since all of the code is in the thumbnail, I think the title was subtle enough though
You can do Part 2 in one pass and without a heap allocation by using `fold()`: ``` pub fn sum_top_3(input: &str) -> u32 { input .split("
") .map(|food_items_per_elf| { food_items_per_elf .lines() .map(|calories_per_item| calories_per_item.parse::().unwrap()) .sum::() }) .fold([0, 0, 0], |mut top_3, calories_per_elf| { // The `unwrap()` could be avoided by writing `if let Some(min)`, // but I believe it's better to be explicit. `if let` would fail silently. let min = top_3.iter_mut().min().unwrap(); *min = u32::max(calories_per_elf, *min); top_3 }) .into_iter() .sum() } ``` This gives you a time complexity of O(n) and a space complexity of O(1).
i came up with something like this 💀 let file = fs::read_to_string("input.txt").expect("Error reading input file"); let mut vec: Vec = Vec::new(); let mut sum = 0; let mut largest = 0; for i in file.split("
") { for j in i.split(" ") { sum += match j.parse::() { Ok(val) => val, Err(..) => 0, }; } vec.push(sum); if sum > largest { largest = sum; } sum = 0; } vec.sort_by(|a, b| b.cmp(a)); for i in 0..=2 { sum += vec[i]; }
I loved this! I’m doing AoC in rust this year to learn/get better with rust. So being able to watch your process for solving a problem I just solved myself, in detail like this is a huge help! I was able to pick up on a bunch of rust idioms just by you talking through your approach to the problem and considering your options, so I really hope you keep doing these, and keep the detailed talking through the problem in!
I, too, really like seeing how other people approach a problem. I almost always learn something new. And I really appreciate Chris talking through the problem and the solution rather than just presenting a solution (it's often that talking through it part where I learn something).
Plus one to this! as a noob to rust, I can get a basic program written jogging my C++ memories, but it is hard to know how “good” that solution is without exploring all the tools available in rust :)
Yeah, same--I'm coming from Python and don't often use map-apply programming patterns, so seeing how a Rust programmer solves these problems after I've done it in my hacky way is great for learning the style differences between the languages :)
The reason you can't sort an iterator is because it wouldn't have anywhere to store it. An iterator only has access to the current value, not past or future ones.
Thus sorting requires collecting all of the elements into some sort of new container, which can then be sorted in place. This is what itertools does.
If that's what itertools does then there's no technical restriction to it being implemented. Yes, you can't sort an Iterator in-place because it requires all of the values, but terminating functions like collect have to create a new Vec anyway. The Iterator trait itself doesn't preclude this behavior from existing in the stdlib.
Also, I was able to find the reason after the recording! Basically nobody seems to have RFC'd the functionality into the stdlib: github.com/rust-lang/rust/issues/38882
@@chrisbiscardi I think the reason for a sort method on iterators not being implemented is to avoid confusion about allocation. Iterators are also lazy, and sorting them completely defeats that. The trait is also defined in `core::iter::Iterator`, where an allocator isn't available.
Doesn't seem so hard to collect into a Vec first then sort. And that makes it clear what the memory implications are!
But what about making an index array? The Sort iterator would have a [u32] array that specifies the sorted order, e.g. for vec![2,3,1] it would be [2,0,1]
Or with another approach, each next invocation for the iterator would find the n-th lowest element. That would be less optimal though, but didn't require memory
@@mzg147 A generic iterator can't be traversed multiple times; it might mutate or consume state, for example.
I ended up solving this one almost the same way you did, and then experimented with other ideas just for the sake of learning. A few observations:
There are also sort_unstable, sort_unstable_by, etc. They can be more efficient if it is OK to rearrange values that compare equal. On a problem of this size, the performance difference would be tiny; but it's good to know about for those cases when you have much larger inputs.
For parsing the numbers, you can do:
.map(str::parse::)
(with no closure). I find that just a little easier to read.
To sort in reverse, you can do:
.sort_by(|a, b| a.cmp(b).reverse())
I think that more obviously conveys that you want it sorted in reverse. It's easy to overlook that `a` and `b` were swapped in the closure. There is also sort_by_key() combined with std::cmp::Reverse, which I find a little harder to read (and remember).
I really hope you will post more Advent of Code videos. I enjoy seeing how other people approach problems, including going back and refining a solution.
Thoroughly explained, and thoroughly enjoying learning rust.
As someone trying to use AOC to learn Rust this is great! Learning so much! Thank You!
this is awesome thank you. I just tackled problem 1 in Python and am starting to learn Rust, so will be following along with this series to try and learn :)
Thx for sharing your solution.
I'm currently learning rust and use advent of code to play around with the language, and it's very helpful to have you explain certain aspects.
Tomorrow, I will have to change my repository to your setup. That looks way more reasonable than mine 😅
Looking forward to this! I am also planning to do this myself. Interested in your solutions😁 Keep it up!
I'm mindblown by the FP usage here
Everything here is helpful, but gosh thanks for the project setup notes! Exactly what will be helpful when I get around to day 3 tonight.
I've been meaning to start learning Rust. I mainly work with C#, so this will be very useful!
Great video! Looking forward to learning rust with this version of AoC
Same here. Good luck!
Since the sums are stored in a Vector, I would have sorted normally and then used iter().rev().take(3)
Good suggestion. I ended up sorting, then calling .reverse(), then .iter().take(3).sum(). I forgot about reverse iterators.
The .rev() method to turn a forward iterator into a reverse iterator just feels weird to me, an so I tend to forget about it. I would expect something like .iter_rev() or similar to directly construct a reverse iterator. (I get why they did it that way. That one method can be applied to iterators producing owned values, shared references, or exclusive references.)
If anyone is doing this on windows, you will encounter an error while you are splitting because in Windows, the line seperators are
instead of
Like you said, parse returns a result but max returns an Option. While you want to unwrap them both in this case, they are quite different.
Nice, love comparing solutions and not just blatantly copying yours because I'm stuck!
I was thinking if it was possible to extend the Iterator trait such that you could pick the "top_3()" items or something. Digging through the Iterator file, it was a little too intimidating to start anything
you could start with using scan, using a 3 element sorted array as the state and then write an extension trait that uses scan behind the scenes doc.rust-lang.org/std/iter/trait.Iterator.html#method.scan
How would you "group the values using itertools"? Would love to see that!
I probably would've ended up using coalesce like this: play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=a8f94ea0b82ce025dfe198aab4ee4784
The coalesce uses the outer Result to do the iteration, while the inner Result is the result from our parse. Otherwise the answer is mostly the same docs.rs/itertools/latest/itertools/trait.Itertools.html#method.coalesce
Also trying to do this year‘s AoC with Rust again! My goal is to reach the top 100 once. But it’s not looking very realistic after day 1. 😂
Funny challenge, though the questions are released in the middle of the night so I'm not even paying attention to the indicated delay to solve them. The delay should count from the instant the question is shown. +1 point for the TDD approach!
I used itertools and coalesce so that I don't have to load the whole file in memory. I know it's not that big, it's just for the sake of trying.
Probably wouldn't work for global ranking, but for personal scores I'd absolutely love to have a "time since opening the challenge".
@@erifetim True, that wouldn't work for global ranking.
I’m writing every puzzle in a different language this year. I did the first day in shell script
hey i don't get why sum need a type, won't rust know the type from parse?
This video is missing how you developed the code step by step :(.
The whole using closures part is elegant, when it is ready, but when I want to add a simple println in the closure without the rest of them, I get errors, because I need to assign the typed correctly. This feels like a "write everything at once" solution and not something you can develop organically. I went for two for loops instead, which looks awful, but as I am new to Rust i could develop it step by step.
However thank you for your video and the provided insights.
How are you adding the println? and what do you mean by "without the rest of them"? Do you mean that you want to have a println at an arbitrary location in the chain? If so there's a function for that: inspect. Here's a link to the documentation for it: doc.rust-lang.org/std/iter/trait.Iterator.html#method.inspect and I would also suggest using the dbg! macro instead of println! for debugging purposes.
Personally, my step-by-step *was* write the code from top to bottom so I edited out the typing and covered the result. I wasn't doing any sort of debugging or whatnot. What sort of additional explanation are you looking for? Is it the existence of the iterator functions and where to find them?
@@chrisbiscardi Thank you very much for your time to answer. I dive deeper into Rust every day and it gets a bit clearer. I cannot answer anymore, what exactly I did wrong, but ownership issues after the collect is something I keep running into. I could do the day 3 solution kinda slow but it worked out thanks to your tutorials :).
dbg! seems to have some problems with claiming ownership and destroys code I had after it, so I switched back to println and the real debugger. I might skip a day to do some more basic Rust tutorials.
Thanks again for all your videos.
1:45 Why did choose to use --lib?
I chose --lib because I knew I was going to set up my binaries in the bin folder, so instead of generating a main.rs, --lib generates a lib.rs with a test that my bin folder can use
Why not binaryheap
Dude I tray to get the code with git clone ........ but maybe something ist wrong with your repo
I solved this challenge in almost the exact same way about an hour ago. Love to see people thinking in a similar way to myself
1:38 ... you don't need because you are using what?
www.nushell.sh/
If you don't want to panic on bad input value, you can do '.filter_map(|item| item.parse::().ok())' instead which will just skip bad value.
In this case I think it would be better to panic or return an error than just silently ignore parsing issues.
Collecting and sorting is nlogn and memory inefficient. It should be possible to get the top 3 without collecting or sorting and also being o(n)
You cannot use sort to iter because iter have access to next element like linkedlist, but when you sorting array you need access to an entire array
Wow people actually use nushell. I mean I think it's cool, but I've been using bash/zsh too long.
Nushell has been my primary shell for over a year now. I still have some bash/zsh isms in my fingers but it's been really solid for me and I really enjoy the data features
Hi. Request: could you not provide hints in the title of AoC videos? :)
hey! I'm happy to try. Did you feel like today's title was too much of a hint? I felt like the question asked us to sum numbers pretty directly.
@@chrisbiscardi I don't know, I haven't yet looked at today's problem; so now you've already biased me in some way. :D
@@chrisbiscardi I was reminded to participate today by your video, and just seeing the parse function in the glance at the thumbnail felt like too much of a hint, especially since all of the code is in the thumbnail, I think the title was subtle enough though
kinda spoiling it by putting the code for the solution in the thumbnail, esp for people who haven't had the chance to do it yet
Im impressed how can you talk so much without saying anything and do so much without doing anything
And still be a pleasure to listen to!
You can do Part 2 in one pass and without a heap allocation by using `fold()`:
```
pub fn sum_top_3(input: &str) -> u32 {
input
.split("
")
.map(|food_items_per_elf| {
food_items_per_elf
.lines()
.map(|calories_per_item| calories_per_item.parse::().unwrap())
.sum::()
})
.fold([0, 0, 0], |mut top_3, calories_per_elf| {
// The `unwrap()` could be avoided by writing `if let Some(min)`,
// but I believe it's better to be explicit. `if let` would fail silently.
let min = top_3.iter_mut().min().unwrap();
*min = u32::max(calories_per_elf, *min);
top_3
})
.into_iter()
.sum()
}
```
This gives you a time complexity of O(n) and a space complexity of O(1).
i came up with something like this 💀
let file = fs::read_to_string("input.txt").expect("Error reading input file");
let mut vec: Vec = Vec::new();
let mut sum = 0;
let mut largest = 0;
for i in file.split("
") {
for j in i.split("
") {
sum += match j.parse::() {
Ok(val) => val,
Err(..) => 0,
};
}
vec.push(sum);
if sum > largest {
largest = sum;
}
sum = 0;
}
vec.sort_by(|a, b| b.cmp(a));
for i in 0..=2 {
sum += vec[i];
}