Intro
I'm Taneli Kaivola / Dist. My code is available in Gitlab.
I wanted to learn to use Rust better so I tackled all Adventure of Code 2020 problems with it. I don't do these to be high on the score board, I'd use Python if I wanted to do that (and likely wouldn't still be very high up there)..
These are my stories. They're mostly written for myself though. =D
Spoilers!
Yeah. So. There's all kinds of code snippets all around. Sometimes something that will just solve they puzzle completely.
You have been warned.
Day 1
Learning parsers
Wanted to parse stuff. Tried:
All of these kinda work, but for text parsing parse-display has been the best for me, easiest to use.
Parsing with pest is very complete but getting objects out seems horrible.
Kinda the same with pom, not as bad. It's still pretty bad. + - * | >> operators creates a confusing syntax.
Day 5
Learning to hate cargo bench
Tried cargo bench. Hated most of it. Mainly that trying to run nightly and stable in the same workspace messes up Visual Studio Code completely.
Took until day 9 to stabilise the benchmarking to criterion.
Day 9
Learnings
Searched for all kinds of ways to do benchmarking. On day 5 I tried cargo +nightly and cargo bench, but wanted to stay in stable. So found: criterion. Been using it since for (almost?) every day.
Learned benchmarking in stable.
Day 16: Ticket Translation
Feelings
Felt that I knew exactly what I was doing. Though making objects out of everything is kinda heavy, it's makes processing the data so much easier. Wrote the parser in plain Rust too.
Learnings
- Found out about mdbook
- Started writing this book
- Learned cargo-edit:
cargo install cargo-edit,cargo add package,cargo upgrade(which tried messing with my ^1.0.0 versions)
Task
Part 1
Using the rules, figure out how many tickets are valid. All values of tickets should match some rule.
Part 2
Figure out which field matches which rule.
Input example
class: 1-3 or 5-7
row: 6-11 or 33-44
seat: 13-40 or 45-50
your ticket:
7,1,14
nearby tickets:
7,3,47
40,4,50
55,2,20
38,6,12
Day 17
Feelings
Well.. Part 2 ended up being a complete copy-paste of part 1, but with adding one more dimension. Should generalise neighbor searches somehow.
Learnings
- Learned itertools.multi_cartesian_product
- And implemented my very first actually useful macro (see below)
- Maybe I'll be able to convert this to generic type instead some day, but that day is not today
.. later same day
pub trait VecNeighbors<T> {
fn neighbors(&self) -> Vec<Vec<T>>;
}
macro_rules! VecNeighbor_for {
($vectype:ty) => {
impl VecNeighbors<$vectype> for Vec<$vectype> {
fn neighbors(&self) -> Vec<Vec<$vectype>> {
self
.iter()
.map(|v|(v-1 ..= v+1).into_iter())
.multi_cartesian_product()
.filter(|x| x != self)
.collect::<Vec<_>>()
}
}
};
}
Implement it:
VecNeighbor_for!(i32);
.. and then just use it:
fn test_vecneighbor() {
let _coord:Vec<i32> = vec![0,0];
for x in _coord.neighbors().into_iter() {
println!("{:?}", &x);
}
}
Which gives you this:
[-1, -1]
[-1, 0]
[-1, 1]
[0, -1]
[0, 1]
[1, -1]
[1, 0]
[1, 1]
Day 18
Feelings
Weeeell. There's no algorith, just go and parse.
Pest doesn't suck as much as I thought on day 1. Especially for a task like this it's pretty damn good.
Learnings
Learned to use pest parser a little better.
Unfortunately the first sample in A thoughtful introduction to the pest parser happens to almost completely cover this day.
Parser
In pest syntax (see Pest Grammar):
num = @{ ASCII_DIGIT+ }
operation = _{ add | multiply }
add = { "+" }
multiply = { "*" }
expr = { term ~ (operation ~ term)* }
term = _{ num | "(" ~ expr ~ ")" }
calculation = _{ SOI ~ expr ~ EOI }
WHITESPACE = _{ " "+ }
As an example, 2*3+(4 * 5) can be parsed using:
Calculation::parse(Rule::calculation, "2*3+(4 * 5)").unwrap()
and it results to returning Pair structs
[
Pair {
rule: expr,
span: Span {
str: "2*3+(4 * 5)",
start: 0,
end: 11,
},
inner: [
Pair {
rule: num,
span: Span {
str: "2",
start: 0,
end: 1,
},
inner: [],
},
Pair {
rule: multiply,
span: Span {
str: "*",
start: 1,
end: 2,
},
inner: [],
},
Pair {
rule: num,
span: Span {
str: "3",
start: 2,
end: 3,
},
inner: [],
},
Pair {
rule: add,
span: Span {
str: "+",
start: 3,
end: 4,
},
inner: [],
},
Pair {
rule: expr,
span: Span {
str: "4 * 5",
start: 5,
end: 10,
},
inner: [
Pair {
rule: num,
span: Span {
str: "4",
start: 5,
end: 6,
},
inner: [],
},
Pair {
rule: multiply,
span: Span {
str: "*",
start: 7,
end: 8,
},
inner: [],
},
Pair {
rule: num,
span: Span {
str: "5",
start: 9,
end: 10,
},
inner: [],
},
],
},
],
},
Pair {
rule: EOI,
span: Span {
str: "",
start: 11,
end: 11,
},
inner: [],
},
]
Or more compact, evaluated by pest editor
- expr
- num: "2"
- multiply: "*"
- num: "3"
- add: "+"
- expr
- num: "4"
- multiply: "*"
- num: "5"
- EOI: ""
This can be parsed using:
fn eval(expression: Pairs<Rule>) -> i64 {
PREC_CLIMBER.climb(
expression,
|pair: Pair<Rule>| match pair.as_rule() {
Rule::num => pair.as_str().parse::<i64>().unwrap(),
Rule::expr => eval(pair.into_inner()),
_ => unreachable!(),
},
|lhs: i64, op: Pair<Rule>, rhs: i64| match op.as_rule() {
Rule::add => lhs + rhs,
Rule::multiply => lhs * rhs,
_ => unreachable!(),
},
)
}
That in turn uses PrecClimber:
lazy_static! {
static ref PREC_CLIMBER: PrecClimber<Rule> = {
use Rule::*;
use Assoc::*;
PrecClimber::new(vec![
Operator::new(multiply, Left),
Operator::new(add, Left),
])
};
}
Then the difference between part 1 and part 2 becomes just defining the evaluation order.
Part1:
PrecClimber::new(vec![
Operator::new(multiply, Left)|
Operator::new(add, Left),
])
Part2:
PrecClimber::new(vec![
Operator::new(multiply, Left),
Operator::new(add, Left),
])
Which is more or less one char difference between part1 and part2.
Day 19
Feelings
Well. Tried to do this in Rust. Ended up learning Python.
Learnings
Found out about regex-module for Python. It supports much more versatile regexes than I've been using.
Solution (both parts)
import regex
def defs(rules_s):
for rule in rules_s.split('\n'):
n, s = rule.split(': ', 1)
s = regex.sub(r'\s*(\d+)\s*', r'(?&r\1)', s)
s = regex.sub(r'"(\w+)"', r'\1', s)
yield "(?P<r{}>{})".format(n, s)
rules_s, messages_s = open('./input').read().split("\n\n", 1)
r = regex.compile(r'(?(DEFINE){})^(?&r0)$'.format(''.join(defs(rules_s))))
print("part1:", sum(1 if r.match(msg) else 0 for msg in messages_s.split('\n')))
rules_s, messages_s = open('./input').read().split("\n\n", 1)
rules_s = regex.sub(r'8: 42', '8: 42 | 42 8', rules_s)
rules_s = regex.sub(r'11: 42 31', '11: 42 31 | 42 11 31', rules_s)
# .. or replace with what you had in the instructions page
r = regex.compile(r'(?(DEFINE){})^(?&r0)$'.format(''.join(defs(rules_s))))
print("part2:", sum(1 if r.match(msg) else 0 for msg in messages_s.split('\n')))
This whole solution bases on using regex group definitions. What are they?
Regex group definitions
>>> regex.search(
r'(?(DEFINE)(?P<quant>\d+)(?P<item>\w+))(?&quant) (?&item)',
'5 elephants')
<regex.Match object; span=(0, 11), match='5 elephants'>
And they can be recursive so even this works:
>>> regex.search(
r'(?(DEFINE)(?P<quant>\d+)(?P<ele>ele(?&ele)?)(?P<item>(?&ele)\w+))(?&quant) (?&item)',
'5 eleeleelephants')
<regex.Match object; span=(0, 17), match='5 eleeleelephants'>
This allow the conversion from rules to regex with group definitions. Every rule is a single definition and references other rules.
Day 20
Feelings
That was absolutely horrible.
Day 22
Feelings
Part 1 ➟ easy and the code came out quite nice.
Part 2 ➟ what the hell am I trying to implement?
The rules in part 2 were quite confusing and explained a few times to increase the confusion even more.
And then there's this:
To play a sub-game of Recursive Combat, each player creates a new deck by making a copy of the next cards in their deck (the quantity of cards copied is equal to the number on the card they drew to trigger the sub-game).
I completely missed the part in bold for quite some time. Also the examples pass very well even if that functionality is missing.
Improvements for the future
Do some magic to run multiple games in parallel. For example in subgames, you could run three games in parallel: one that decides the winner, and two to precalculate next round for both winners.
Learnings
VecDeque
std::collections::VecDeque is just a double-ended queue, no biggies there. Just tried it out here the first.
iter_mut
I guess I may have used iter_mut actually successfully the first time here. Have tried a few times and it hasn't gone so well. But this time it did. So I've got that going for me. \o/
This gets a card from every player from the top of their decks.
fn pop_top(&mut self) -> Vec<u8> {
self.players.iter_mut().map(|p|p.deck.pop_front().unwrap()).collect()
}
Code that is enabled based on selected features
Cargo.toml:
[features]
vag_emissions = []
Cheat code somewhere in the .rs:
#[cfg(feature = "vag_emissions")]
if self.depth > 1 {
And the build with:
cargo build --release --features=vag_emissions
Implementing Debug-trait
#[derive(Default)]
pub struct Game {
pub game_id: usize,
pub depth: usize,
pub players: Vec<Player>,
pub round: usize,
pub winner: Option<usize>,
round_states: DeckStates,
}
Since my Game struct can grow quite large (particularly round_states: DeckStates), default derived Debug-trait doesn't make sense at all.
This one implements it without making it too verbose.
impl std::fmt::Debug for Game {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("Game")
.field("id", &self.game_id)
.field("depth", &self.depth)
.field("winner", &self.winner)
.field("round", &self.round)
.field("players", &self.players)
.finish()
}
}
Implementing Clone-trait
Game is cloned by cloning only the player data.
impl Clone for Game {
fn clone(&self) -> Self {
Self {
players: self.players.clone(),
game_id: 0,
depth: self.depth + 1,
// clone just the players and their decks
.. Default::default()
}
}
}
Using Default-trait in new
Default just makes new so much nicer to write. and Game::new() just looks good elsewhere.
pub fn new() -> Self {
Self { ..Default::default() }
}
AtomicUsize
To make sure every simulated game gets unique ID, AtomicUsize is pretty nice choice.
To start using it:
use std::sync::atomic::{AtomicUsize, Ordering};
static GAME_ID: AtomicUsize = AtomicUsize::new(1);
To increment:
pub fn play(&mut self) {
let game_id = GAME_ID.fetch_add(1, Ordering::SeqCst);
self.game_id = game_id;
And to return current value:
pub fn game_id() -> usize {
GAME_ID.load(Ordering::SeqCst)
}
Day 23
Feelings
Part 1 ➟ Yay, let's do VecDeque again!
Part 2 ➟ Why did I make this with VecDeque? FUUUUU~~
VecDeque is absolutely useless in part 2, way too slow to do it like that. Damnit.
So for part 2 I ported the whole thing to HashMap. Thought that if you need to look up a value and find next value you could do this kinda single linked list-ish way, but with good speed for lookups.
Well yeah. It manages to find the solution in about 5 seconds so I guess there's much improvement to do.
Improvement ideas
Good old perf and look at that
I still haven't got cargo flamegraph working for me at all, it just doesn't produce correct results (shows only the module). Maybe it's because of my workspace build?
perf record -g --call-graph dwarf or perf record -g --call-graph fp and then perf report | rustfilt | less work pretty well and I've been using those to figure out performance issues.
Lazy create
Should the whole structure be created before starting to run through it or would it be ok to just lazily populate it?
All of the values above 10 (to 1_000_000) are initially same as the position and the next value is +1 of it. Maybe that can be used as optimization of some kind?
What's the real access pattern anyway?
Try out flat memory structure
First thing is to is to try what happens if, instead of having HashMap, there would just be a vec or just mutable slice. As numbers are unique it should be quite simple to port hashmap version to this very simple flat memory structure with pointers. (even more like a linked list. uhh.)
Something like let mut v: Vec<u32> and having something like v[value] = next_value would be exactly as I have with HashMap, but without hashing. Facepalmed a bit too hard when I understood that. :|
This + compile time constant initializer should be pretty damn fast. Maybe.
Compile time constants
Try to set up some structures beforehand (at compile time). For example array of u32 from 1..1_000_000 that would just get loaded when the binary is loaded could be kinda nice maybe.
This might be nice to try out: compile time static arrays - dev.to
Day 24
Feelings
Part 1 ➟ Yay, let's 2d grid again! Except this time it has 6 neighbors instead of 4.
I thought that this is a good opportunity to build really nice classes. While at the same time I was really REALLY hoping part 2 didn't turn into some 4D hex tiled mess.
Part 2 ➟ Phew! Got lucky and this is just cellular automaton. Just with twist of having that 6 neighbors.
So this is the "whole code", except everything is hidden behind HexMap (and even more hidden behind HexPath):
#[allow(clippy::unnecessary_wraps)]
pub fn parse_input(input: &str) -> AnyhowResult<Input> {
Ok(input
.lines()
.map(|l| l.parse().unwrap())
.collect())
}
pub fn part1(_input: &Input) -> usize {
let mut map: HexMap = HexMap::new();
_input.into_iter()
.for_each(|path| map.flip(path.into()));
map.count_black()
}
pub fn part2(_input: &Input) -> usize {
let mut map: HexMap = HexMap::new();
_input.into_iter()
.for_each(|path| map.flip(path.into()));
(1 ..= 100).for_each(|_| {
map.next().unwrap();
});
map.count_black()
}
Learnings
as _
Instead of this:
let mut cups: VecDeque<u32> = _input.into_iter().map(|n|*n as u32).collect();
You can just do this:
let mut cups: VecDeque<u32> = _input.into_iter().map(|n|*n as _).collect();
Only works when the type is known naturally. But it's awesome for those times when you need to use as.
lazy_static! macro
I haven't used it much so I wanted to build static HashMap with it. NEIGHBOR_DIRECTIONS was a perfect candidate. (Though it could be made simpler and without HashMap and without static and without lazy_static!.. But I wanted to make it like this today. =D)
Laying out the classes
This was kinda fun. It's nice to see quite clear code when you set it up like this.
HexMap
The main game processor. The iterator of HexMap advances game of hex one step.
HexTile
A structure representing an address in the map in absolute coordinates.
This can be used as an iterator to get all the neighbors. HexTileIter is returned by HexTile.iter().
There are quite many ways to convert from other types to HexTile.
You can also add two hextiles together. Since coordinates can be negative, there can be a "relative" HexTile that represents a neighbor tile. Adding those two together will get you absolute position of a neighbor tile.
HexPath
Can be converted from a line in the input. Results in a Vec of HexDirection (which is a enum of directions).
HexPath can be converted always to HexTile which represents the end of the HexPath.
Improvements
Likely could be faster
Currently part2 takes about 77ms. Maybe it could be improved.
Replace HashMap with HashSet
Currently HashMap contains information about the color of the tile. It just only contains black tiles though.
Should be converted to HashSet, but I assume not much improvement will be made by that change.
Day 25
Feelings
Part 1 ➟ Looks like modular exponent, I hope part 2 isn't too bad. Part 2 ➟ Thank you Eric! \o/
It's been awesome journey through all these 25 days. I've learned a whole lot about Rust (and written tiny fraction about it here).
I'm hoping to do this again next year, but since the previous years are running there also.. Maybe.. Just maybe. =D
I also just donated to Advent of Code. I hope you will too.
Learnings
Cell
I haven't really wanted to touch many things (Rc, Arc, Box, Cell, RefCell, etc..) in Rust if I can manage without. This time I did want to take something extra. Today was easy. =)
So to Key calculates the secret loop count and I wanted it only calculated once. Without mutable internals every call to any method would result into mutable borrow like this.
struct Key {
public: usize,
loop_size: Option<usize>
}
impl Key {
// some details hidden here
fn get_secret(&mut self) -> usize {
if self.loop_size.is_none() {
// calculate s
self.loop_size = Some(s);
}
self.loop_size.unwrap()
}
}
And every time you'd want to use that:
let mut key = Key::new(5764801);
dbg!(
key.get_secret()
// ^^^^^^^^^^ and this now makes a mutable borrow
// even if it doesn't exactly look like it
);
So, it's dangerous to go alone - Take this: Cell.
Changing the struct is easy:
struct Key {
public: usize,
loop_size: Cell<Option<usize>>
}
And having that makes this pretty easy too:
fn get_secret(&self) -> usize {
if self.loop_size.get().is_none() {
// calculate s
self.loop_size.set(Some(s));
}
self.loop_size.get().unwrap()
}
After that, this is fine now:
// look mom, no mut
let key = Key::new(5764801);
dbg!(
key.get_secret()
);
dbg!
fn main() { let awesomeness = vec!["isn't", "this", "great", "!"]; // You could do this, but it's tedious: println!("{:#?}", &awesomeness); // Instead, do this: dbg!(&awesomeness); // which doesn't work in the playground of the book, but works in real life =D }
Benchmarking in stable Rust
Create bench/bench.rs:
use std::time::Duration;
use criterion::{black_box, criterion_group, criterion_main, Criterion};
use aoctemplate::*;
const INPUT: &str = include_str!("../input");
fn criterion_benchmark(c: &mut Criterion) {
c.bench_function("parse_input", |b| b.iter(|| parse_input(black_box(INPUT))));
let input = parse_input(INPUT).unwrap();
c.bench_function("part1", |b| b.iter(|| part1(black_box(&input))));
c.bench_function("part2", |b| b.iter(|| part2(black_box(&input))));
}
// criterion_group!(benches, criterion_benchmark);
criterion_group!{
name = benches;
config = Criterion::default().measurement_time(Duration::from_secs(10));
targets = criterion_benchmark
}
criterion_main!(benches);
And add this to Cargo.toml:
[[bench]]
name = "bench"
harness = false
Cargo-edit
Cargo-edit makes it easy to add dependencies to your Cargo.toml.
Just install, add some package and later update every dependencys.
cargo install cargo-edit
cargo add package
cargo upgrade
itertools.multi_cartesian_product
Running this:
use itertools::Itertools;
let v:Vec<Vec<_>> = vec![vec![1,2],vec![3,4],vec![5,6]];
let vp:Vec<Vec<_>> = v.into_iter()
.multi_cartesian_product()
.collect();
println!("{:?}", &vp);
Gives you this:
[[1, 3, 5], [1, 3, 6], [1, 4, 5], [1, 4, 6], [2, 3, 5], [2, 3, 6], [2, 4, 5], [2, 4, 6]]
And it's glorious.
Day 17 has actual implementation example of it.
Cell - Mutating internally
See Day 25.