Learning Rust via Advent of Code
forrestthewoods.com
forrestthewoods.com
> parse!("#{} @ {},{}: {}x{}", id, x, y, w, h);
> This would be a clean inverse of println!.
The text_io crate does this exactly.
https://crates.io/crates/text_io
#[macro_use]
extern crate text_io;
fn main() {
let id: u32;
let x: u32;
let y: u32;
let w: u32;
let h: u32;
scan!("#{} @ {},{}: {}x{}", id, x, y, w, h);
} let line = "#1 @ 555,891: 18x12";
let parsed = scan!("#{} @ {},{}: {}x{}" <- line)?;
[1] https://docs.rs/serde_scan/0.3.2/serde_scan/macro.scan.htmlWith a healthy crate ecosystem, std should be as small as possible (without being too small).
It makes sense for std to contain:
- Types that can't easily be put in a module (eg the `Fn` trait)
- Types needed for cross-project interoperability (like `TcpStream` or `Future`). Having these in std helps prevent ecosystem fragmentation.
- Stuff that gets used in most non-trivial projects (eg `Box`, `Vec`, `println!`)
Everything else belongs in a crate, where it won't bloat up the size of rust's standard library for everyone in perpetuity. `scan!` looks great; but I expect it'll be used in less than 1% of projects. There's no shame in keeping it in a crate - thats what they're for!
https://github.com/BurntSushi/advent-of-code
You develop Rust skills by writing your own and then hone your skills by learning from idiomatic Rust.
struct Date {
year: u32,
month: u32,
day: u32,
}
let mut vec: Vec<Date> = Vec::new();
vec.sort_by(|a,b| {
a.year.cmp(&b.year)
.then(a.month.cmp(&b.month))
.then(a.day.cmp(&b.day))
});
Alternatively you can derive PartialEq, PartialOrd, Eq and Ord for your struct, which will produce a lexicographic ordering based on the top-to-bottom declaration order of the struct's members: #[derive(PartialEq, PartialOrd, Eq, Ord)]
struct Date {
year: u32,
month: u32,
day: u32,
} vec.sort_by_key(|d| (d.year, d.month, d.day))
sort_by is more flexible as it works fine with borrows, but when sorting on a series of integer values or references sort_by_key is great.> Alternatively you can derive PartialCmp for your struct, which will produce a lexicographic ordering based on the top-to-bottom declaration order of the struct's members:
Do you mean PartialOrd? partial_cmp is the method. And `sort` requires absolute ordering (Ord) not just partial.
And yeah, I meant Ord (and the required other Traits), I edited my post. Thanks for pointing this out.
I'll second this: Using a set of progressive problems is an excellent way to get used to actually writing code in a language.
"My first stumbling block was parsing. Almost every AoC problem starts with parsing lines of text from an input file."
Scheme. Guile. The PEG parsing module. (There's no kill like overkill.)
IME AoC isn't really progressive though, the problems ramp up and down pretty dramatically.
> Scheme. Guile. The PEG parsing module. (There's no kill like overkill.)
Rust has several pretty good parsing libraries e.g. nom, lalrpop, pest, …
I keep thinking that Rust has gone a little too far on the "keep it minimal" front. It also really disturbs me just how often with rust I'm having to rely on third party hosted crates. That's one huge amount of trust going on there.
Besides the impact of not being in stdlib is very low except for discovery.
More importantly, due to Rust's backwards compatibility guarantees, you can never remove something once it has been added.
I vaguely wave towards Python's 3-5 built-in "get data from a URL" libraries as an example of a bad route that this can take.
The regex crate can release a backwards-incompatible version 2 without destroying the entire ecosystem since multiple versions of a crate can co-exist in the final graph of dependencies.
How often do you see that actually being a problem? Rust releases new versions on a regular cadence. Just how often do you imagine the regex crate actually needs to be updated? Or how about the random number generator crate?
> Besides the impact of not being in stdlib is very low except for discovery.
I always find this an interesting argument. We've seen node.js etc. packages be compromised many times, or even completely vanish (left-pad)? How much confidence can I have that any individual package hasn't been compromised somehow? How much confidence can I have that random dependencies aren't suddenly going to enter my build chain. That left-pad situation was classic. So many things got broken, not because they'd picked up left-pad, but because dependencies of dependencies of dependencies relied on it (and so on down the line...)
There was that situation just a month or so ago where a developer just didn't want to maintain their package any more, had someone volunteer, who then compromised it with a crypto-miner.
Now on top of that licensing gets to be a whole bunch of fun as soon as you step outside the stdlib. For every crate you add, you need to do a licence audit, and for each and every one of its dependents, and its dependents dependents. Amazon, for example, has a black list of licenses. You can't use any software licensed under one of them, for whatever reason the lawyers have about each one.
See my sibling comment about backwards compatibility
> Just how often do you imagine the regex crate actually needs to be updated?
You can see the frequency of updates to the regex crate if you are interested: https://crates.io/crates/regex/versions.
Sometimes a release in a few days, or a few a month.
> Or how about the random number generator crate?
Even more interesting, because `rand` hasn't even reached 1.0 yet! https://crates.io/crates/rand/versions
Specifically, the authors are still deciding the right way to architect the library for the myriad of uses that Rust has.
> or even completely vanish (left-pad)
In 99.99% of the cases, you cannot remove a crate from crates.io; you can only prevent new projects from adding the crate as a dependency. The other 0.01% is because of legal reasons, and there's not much to be done about that.
> For every crate you add, you need to do a licence audit
https://github.com/onur/cargo-license claims to show you the licenses of every dependency. It's required to have a license to publish to crates.io.
With Rust, the package manager is very good. So it's not a problem in practice.
> Helper Lambdas
> I like lambdas in C++11. I use them regularly for small helpers that exist solely within a function.
`move` lambdas might work better? The default tries to infer based on usage but often fails. A `move` lambda lets you do something similar to C++'s capture lists (though more verbose / cumbersome).
> BinaryHeap
> The standard library provides a max-heap. I regularly needed a min-heap. I got one by making a custom struct with custom compare function.
std::cmp::Reverse
> I wonder if there is a nice macro crate to help with this? I'd love to write: compare!(a, b, year, month, day, hour, minute);
sort_by_key?
> I wish there was an f16 half-precision float. There's a good internals thread on minifloats that makes me think f16 will happen eventually.
A problem's there is there are at least two "standard" f16 (IEEE and ML)
> There is NonZeroU32. It's similar-ish, but only works for zero. There isn't a Non255U8 or, thankfully, Non4294967296U32.
They're built from the unstable `NonZero` (and the unstable and unsafe ZeroAble).
You could build a struct on top of NonZero which swaps zero and your sentinel value.
#[rustc_layout_scalar_valid_range_end(254)] struct Non255U8(u8);
Are there any good resources for progressively learning Python by doing something like AOC but starting from nothing and as a tutorial and explaining the basics of what a string is etc as it goes?
// #1 @ 916,616: 21x29
let parts: Vec<&str> = l.split(['@', ',', ':', 'x'].as_ref()).collect();
let x = parts[1].trim().parse::<i32>().expect("x as i32");
let y = parts[2].trim().parse::<i32>().expect("y as i32");
let w = parts[3].trim().parse::<i32>().expect("width as i32");
let h = parts[4].trim().parse::<i32>().expect("height as i32");
[0] https://doc.rust-lang.org/std/primitive.str.html#method.spli... let mut parts = l.split(&['@', ',', ':', 'x'][..])
.flat_map(|s| s.trim().parse::<i32>().ok());
let x = parts.next().expect("x as i32");
let y = parts.next().expect("y as i32");
let w = parts.next().expect("width as i32");
let h = parts.next().expect("height as i32");Why not? cargo makes it extremely easy to add new crates. The hardest part is figuring out what dependency you want, but once you know what it is, adding it is really easy.
$ cargo search regex
regex = "1.1.0" # An implementation of regular expressions for Rust. This implementation uses finite automata and gua…
regex-automata = "0.1.5" # Automata construction and matching using regular expressions.
…"The pattern can be a &str, char, or a closure that determines the split."
But in your case it is an array of chars and it splits for each of them. I don't see this documented at all.
[0] https://doc.rust-lang.org/std/str/pattern/trait.Pattern.html...
It’s possible that it used to be only those types, but was expanded. We should fix this!
The operator for this is for eg l[1..10]. It can also happen automatically.
&str is the same type as &[char] - just a renaming.
Still learning Rust myself, apologies if this leads you astray. Just do some reading on slices.
https://doc.rust-lang.org/book/ch04-03-slices.html#string-sl...
Suprisingly I found it very constructive to work on "two puzzles at once" -- how to use the new language, and solving the AoC itself.
It would be cool if there was some resource that linked well-written, idiomatic solutions for other languages as well. Anyone know if this has been done?
Not all repos are idiomatic, there’s at least one that isn’t (mine).
I found some of the repos useful for bettering my rust skills.
https://www.forrestthewoods.com/blog/learning-rust-via-advent-of-code/(https://adventofcode.com/
It should just be https://adventofcode.com/Regarding parsing, a lot of times the input format is unnecessarily complex. In "real-life", wouldn't you start by sanitizing your input? For me, search/replace and column-edits have been enough to avoid regexps entirely.
input
.lines()
.map(|s| s.trim())
.filter(|l| l.len() > 0)
.map(CustomType::from)
.collect::<Vec<_>>();
or for grid-like puzzels input
.lines()
.map(|s| s.trim())
.filter(|l| l.len() > 0)
.map(|l| l
.chars()
.map(CustomType::from)
.collect::<Vec<_>>()
)
.collect::<Vec<_>>();
0: https://github.com/k0nserv/advent-of-rust-2018It seems like we ran into a lot of the same pain points like parsing, lack of a min-heap, etc.
Regarding HashMap initialization the best way I'm aware of to do what you are looking for is with lazy_static[0]. Maybe not very clean or idiomatic though.
For sorting I found the best solution to that problem was using sort_by_key with a tuple like (a.year, a.month, a.day, a.hour, a.minute).
[0]: https://github.com/rust-lang-nursery/lazy-static.rs#example
Often, this has more to do with the environment, runtime, etc., and the features of the language merely exist to serve that purpose. If that were not true, someone probably would have used an existing language and changed the runtime.
For rust, it seems to exist to bring modern, safe language features to a minimal C-like runtime existence by doing all of the work in the compiler. C has continued to thrive all of this time because it has a minimal runtime and a stable ABI defined on nearly every platform. Rust has a minimal runtime and supports the C ABI very well, so it has a great chance to have a big impact in areas where C/C++ might otherwise be used less safely and less productively. So my focus when learning rust is how to use the C FFI while still writing idiomatic rust.
It's harder to learn that way, but I find it more satisfying, especially in cases where I don't have an immediate project that's going to use the language. The fact is, no matter how many programming puzzles I solve in rust, it's not going to make it any more likely that I will rely on it for anything but a toy or hobby project. But learning the rust FFI does make it more likely I will rely on it in the future. Puzzles can be solved in any language; weird corner cases in the FFI cannot.
Regarding input parsing, I pretty quickly converged to using regexes and never looked back. I guess it's an acquired taste, but rubular.com is my best friend when it comes to it.
You're right that Rust doesn't make doubly-linked lists easy. For that problem I somewhat skirted the issue. For a later problem I built an Octree. I used an Rc<RefCell<OctreeNode>>. That feels pretty gross, but I'm still not sure what the idiomatic pattern is. :(
I actually considered Rust given its popularity. I program C++ for a living, but I'd love to find some use for Rust.
Rust will probably my language of choice for this year's challenge.
I currently don't have the time to sink into something that could end up being a gimmick only, while there is some hardcore optimization needed in one of our services that could be approached through a better parallelization using Rust.
While from my point of view Nim is only interesting, Rust on the other hand seems promising. (I don't mean to compare different purpose languages, the problem stands on my spare time to study and the company needs, if that makes sense.)
This kind of thing does really worry me though, it's almost like a self-fulfilling prophecy, you aren't going to use Nim because you think there isn't enough people using it :(
Do you have any ideas of how we can make you and people like you change their mind?
From a end user point of view, I thought the official website and documentation felt a bit lackluster, not because it was bad or anything (the Nim tutorials part I & II are a godsend), but I instinctively compared it to languages like Python. Again, this is not a fair comparison, more like a impression. I'd love to see more blog posts like this one [0] or maybe the occasional roadmap.
Ah I understand where the 'self-fulfilling prophecy' is coming, but if anything I talked about Nim to dozens of people already, even if I can't currently find utility for it on my day job (I do ML, Embedded and Image processing, so it is actually really hard to use anything other than c++)
Again, commenting from the outside, it seems it is a hard position because today upcoming languages such as rust and go have some solid enterprise backing.
If anything, I don't think you need to change my mind! The Nim development is something I keep a close eye on and I hope I will progressively incorporate it on my daily tasks. The mentioned regret on the first post has really more to do on how little spare time I have.
[0]: https://nim-lang.org/blog/2018/06/07/create-a-simple-macro.h...
• Rust requires more rigor around ownership and borrowing. You can't juggle pointers as freely as you'd in C, or reference everything everywhere like in GC languages.
• Rust doesn't have inheritance, so many design patterns common in C++ or Java need rethinking in Rust.
If you really insist on doing things exactly the C way, or exactly the OOP way, then some things may work, some can be fudged, but it's going to be awkward.
However, if you adopt Rust's style, which is mostly functional, with clearly thought out ownership, without too many cyclic dependencies, then everything nicely falls into place, and Rust becomes easy and productive.
This is most notable immediately around the Result and Option types with their many modifiers (map, map_err, and_then, ...) and how strings work.
This can feel pretty awkward and cumbersome compared to other languages and that could be what you are describing.
It's not that way just for fun though: Most languages hide the underlying complexity from you and 'punish' you at runtime if you violate invariants by eg throwing exceptions. Rust forces you to deal with the invariants at compile time.
This makes you write safer code and prevents many errors, even "business logic" type errors if the API is right.
This is why "move fast and break things" aka prototyping is hard with Rust. (Note you can also circumvent many of these restrictions by using "unwrap()" et al a lot)
On the other hand, it gives you a high degree of confidence for writing and refactoring code: if it compiles, it probably works. (Assuming you were writing idiomatic code)
Rust is certainly not a good fit for every domain: the manual memory management is often overkill, and in very business logic heavy code like your typical CRUD apps, where most errors happen in logic that can't really be encoded in the type system, the value is limited.
This has been so true in my experience. I find that it does take longer overall to write something in Rust, but I almost never have to root out strange errors from my code. In shorter files, I almost never have to use ‘cargo run --debug’ twice.
Like many things, it's a tradeoff: is the cost of getting up to speed worth the benefits Rust gives? Like any tradeoff, some will say yes, some will say no.
Is it limiting?
Should this be used as a complement to a larger toy project?
On the other hand, the author of that post seems to have used a lot of more complex language features, did profiling, debugging, made use of many libraries etc - a lot of extra stuff that wasn't necessary to give correct answers but is crucial in 'real world' programming.
I strongly recommend it.
My first "app" in Golang was a discord bot. I have to do maintenance on it occasionally and it's been a great learning experience.
These types of problems will give you a good intro to a language, but won't introduce you to the more advanced libraries which you'll likely need in a professional context (e.g. threading/mutexs, tcp/udp, etc).
Building larger projects is of course also a great way to learn!
https://doc.rust-lang.org/book/ch04-02-references-and-borrow... https://doc.rust-lang.org/book/ch10-03-lifetime-syntax.html
In general AoC is just great for exploring new langs or brushing up on ones you haven't used for some time.