dev-diary.txt

running recap

useful libraries:
* serde_scan

useful data structures i hadn't touched in a while:
* deque

TODOs:
* read through std lib docs
* watch all of jon gjengest's videos
* read rust by example
* read nomicon
* read source code for a rust web server
* read https://github.com/bheisler/Corrosion
* implement a doubly linked list that lets you insert in the middle and pop off the middle (with unsafe?)
* really experiment with debugging

ideas for a program to write after this:
* port quinto to rust and compare perf? (might require a react-like rust lib to replace reagent, does one exist?)
* look at the `battery` program and figure out how it generates its terminal graphs, come up with something to graph on the pi
* irc bot (good excuse to try out tokio)
* profiler (????)
* flocking simulator (?)

===

2/4/19

at long last, chapter 13 is behind me and i'm about ready to start

reading through https://doc.rust-lang.org/std/iter/trait.Iterator.html before i begin

the bit about using collect() to collect a list of Results into a Result of lists is interesting

btw here are the vim keybinds i've set up that i need to remember

gd - go to definition
gs - go to definition in a split
,gd - look up documentation
C-x C-o - completion (could this work with C-p instead?)

useful-looking methods aside from the usual FP ones:
* partition
* inspect
* filter_map
* by_ref
* all, any
* find
* find_map
* position, rposition
* max_by_key, max_by, min_by_key, min_by
* rev
* cloned

things i know by different names:
* `flat_map` is clj `mapcat`
* `scan` is clj `reductions`
* `skip` is clj `drop`
* `fold` is clj `reduce`
* `partition` is yelp_lib.iteration `winnow`

things to watch out for:
some of these methods (particularly map, filter, take_while, skip_while, etc)
have this in their documentation (copy-pasting follows):

Because the closure passed to filter() takes a reference, and many iterators iterate over
references, this leads to a possibly confusing situation, where the type of the closure is a double reference.

```
let a = [0, 1, 2];

let mut iter = a.into_iter().filter(|x| **x > 1); // need two *s!

assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), None);
```

so let's just keep an eye out for that.

TODO read through https://doc.rust-lang.org/std/index.html

ok here goes

1a: sum all the numbers

pretty straightforward

1b is straightforward too but i'm confused about this:

let set: HashSet<_> = [1, 2, 3].iter().cloned().collect();
assert_eq!(set.contains(&1), true);
assert_eq!(set.contains(&4), false);

why does set.contains(&1) have to have the &?

https://www.forrestthewoods.com/blog/learning-rust-via-advent-of-code/
has a good list of iterator methods and useful crates

mentions https://crates.io/crates/nom and https://crates.io/crates/pest as being
possibly useful for day24

recommends https://github.com/Amanieu/hashbrown

let's try it out!
2x speedup!!

oh wow nice i hadn't tried building in release mode - 0.01 seconds for the whole thing atm

ok so i went through a few rounds of changes for 2b

originally i had this

fn two_b() -> String {
    let contents = fs::read_to_string("src/inputs/2.txt").unwrap();
    let lines: Vec<&str> = contents.lines().collect();

    for (i, line) in lines.iter().enumerate() {
        for other_line in lines.iter().skip(i) {
            let diff_positions = differing_character_positions(line, other_line);
            if diff_positions.iter().count() == 1 {
                let mut ret = String::new();
                for (i, character) in line.chars().enumerate() {
                    if i != diff_positions[0] {
                        ret.push(character);
                    }
                }

                return ret;
            }
        }
    }

    "unreachable".to_string()
}

then i went crazy with iterator methods for fun and got this

fn two_b() -> String {
    let contents = fs::read_to_string("src/inputs/2.txt").unwrap();
    let lines: Vec<&str> = contents.lines().collect();

    let (box_a, box_b) = lines
        .iter()
        .enumerate()
        .flat_map(|(i, line)| {
            lines
                .iter()
                .skip(i)
                .map(move |other_line| (line, other_line))
        })
        .find(|(line, other_line)| {
            differing_character_positions(line, other_line)
                .iter()
                .count()
                == 1
        })
        .unwrap();

    let differing_index = differing_character_positions(box_a, box_b)[0];

    let mut ret = String::new();
    for (i, character) in box_a.chars().enumerate() {
        if i != differing_index {
            ret.push(character);
        }
    }

    return ret;
}

but i was sure that there must be some way to improve that - in particular, the bit where
i was like trying to zip lines against itself (or get, like, a one-way cartesian product?)
felt like it must be implemented in itertools somewhere
and lo and behold, .combinations(2) does exactly what i wanted
except that it puts things in a Vec, so i have to put the two strings into a tuple
so i can destructure them later
and then we get this

fn two_b() -> String {
    let contents = fs::read_to_string("src/inputs/2.txt").unwrap();
    let lines: Vec<&str> = contents.lines().collect();

    let (box_a, box_b) = lines
        .iter()
        .combinations(2)
        .map(|pair| (pair[0], pair[1]))
        .find(|(box_a, box_b)| {
            differing_character_positions(box_a, box_b)
                .iter()
                .count()
                == 1
        })
        .unwrap();

    let differing_index = differing_character_positions(box_a, box_b)[0];

    let mut ret = String::new();
    for (i, character) in box_a.chars().enumerate() {
        if i != differing_index {
            ret.push(character);
        }
    }

    return ret;
}

i still feel like the bit at the end where we make a string that's got all the chars
except for one at a particular index must be improvable somehow, but it's not obvious to me how

eh, it turns out this does the trick:

    box_a
        .chars()
        .enumerate()
        .filter(|(i, _)| *i != differing_index)
        .map(|(_, character)| character)
        .collect::<String>()

but the forloop approach is simpler so i'll stick with that.

======

2/5/19

3a+3b were easy

starting 4a - first challenge is to sort the log entries chronologically

https://crates.io/crates/chrono is apparently a good crate for time stuff

also, HN says:

`
For sorting sequential fields you can chain comparisons with .then():
    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,
    }

`
`
Or you can use sort_by_key and extract the relevant sorting key as a tuple (or any other Ord structure) e.g.
    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.
`

starting off with chrono

====

2/6/19

trying out vs code
seems reasonable so far
had to turn off intellisense (autocomplete) in text files just now,
https://stackoverflow.com/questions/38832753/how-to-disable-intellisense-in-vs-code-for-markdown was really useful for that

USEFUL KEYBOARD SHORTCUTS I WILL NEED TO MEMORIZE
gd - go to definition
gh - "equivalent to hovering your mouse over wherever the cursor is. Handy for seeing types and error messages without reaching for the mouse!"
Cmd-shift-, - go one tab to the left
Cmd-shift-. - go one tab to the right
Cmd-t - open terminal pane
Cmd-shift-up - toggle maximized/regular pane size

less often:
Cmd-shift-X - show extensions
Cmd-shift-F - show search
Cmd-shift-e - show explorer
Cmd-shift-U - show output pane
Cmd-shift-m - show problems pane
Cmd-b - show/hide sidebar

full list at https://code.visualstudio.com/shortcuts/keyboard-shortcuts-macos.pdf

TODO consider learning about vim-easymotion, https://github.com/easymotion/vim-easymotion
vs code vim bindings plugin has support for it

DONE use dbg!() instead of println for inspecting data

DONE read the edition guide after the book: https://rust-lang-nursery.github.io/edition-guide/introduction.html

DONE read https://blog.burntsushi.net/rust-error-handling/

https://www.ragona.com/posts/learning_rust_2019 talks about Box, i'm sure i'll understand this more
once i've gotten to that part of the book

====

2/7/19

spent some time with flamer trying to improve the speed of 5, didn't make much progress, just gonna skip it for now

ok so i've been having a slight amount of trouble with chapter 15, let's write down my understanding of these things

* Box<T> is for storing data on the heap instead of the stack; one common reason you might want to do that
is when storing a piece of data whose size can't be known at compile time.
* Rc<T> is for storing data that can have multiple owners. it's used to make sure that the data is correctly
and automatically dropped once its owners have all gone away.
* RefCell<T> is for situations where you want to mutate data in ways/places that you're sure are safe,
but which the compiler can't tell are safe via static analysis. the compiler enforces ownership/borrowing rules
at compile time, which is good for a bunch of reasons that are obvious to me (catch errors earlier, less overhead, etc).
RefCell<T> enforces ownership/borrowing rules at runtime, which is bad because you catch errors later (or not at all,
a user might find them instead) and there's more overhead, but good because it lets you do things that
you wouldn't be able to do otherwise. the book talks a lot about the "interior mutability pattern" in relation to this.

you can combine Rc and RefCell to have multiple owners of mutable data. careful though because
this can lead to reference cycles.

to avoid this, you can use Rc::downgrade instead of Rc::clone
this gives you a Weak<T>
"the difference is the weak_count doesn't need to be 0 for the Rc<T> instance to be cleaned up."

so i think it's the case that if i see RefCell, i should think: "this field gets mutated
in ways that the compiler can't check the safety of statically."

the book puts it this way: "The RefCell<T> type with its interior mutability gives us a type
that we can use when we need an immutable type but need to change an inner value of that type;
it also enforces the borrowing rules at runtime instead of compile time."

====

2/8/19

so i'm noticing something in implementing 6

i want to use the name "location" here, because it's short but clear

but i'm worried about polluting the global namespace with a vague name, and so
i'm calling it DangerLocation, and having functions with names like `initialize_danger_location_grid()`
instead of `initialize_grid()`, etc.

i think that this is a smell that means that i should be using modules!

DONE after 6b: consider splitting each solution out into its own module + file,
and having a "utils" module for now with shared functions like frequencies

yeah that's definitely the right thing to do

have a binary crate and a lib crate

DONE rename DangerLocation and LocationGrid and etc back to less-specific names once we have that six namespace

====

2/9/19

where's my snowpocalypse?

so the concurrency chapter is talking about channels and mutexes

it's not obvious to me which is the right approach for parallelizing 5b,
they seem pretty equivalent in this case, and channels seem to have a nicer api for what i'm imagining

the section on RefCell<T>/Rc<t> vs Mutex<T>/Arc<T> is interesting
"In the same way we used RefCell<T> to allow us to mutate contents inside an Rc<T>,
we use Mutex<T> to mutate contents inside an Arc<T>."

i think i'll start with channels for 5b, then google to see what rayon is, i've heard it's relevant

ok cool chapter 16 done, let's do this

ok initial naive channel-based implementation gets us from 7.6 seconds to 4.2!
still lots of room for improvement and i'm sure i did this in a clumsy way, but that's cool!

next up i'm going to dig into rayon, starting by watching https://www.youtube.com/watch?v=gof_OEv71Aw
this rust belt youtube channel looks promising, i'm sure i'm going to spend all day watching rust videos now

around 6:20 - "and another problem is that some of the iterator combinators actually just don't make sense
in parallel at all, like fold as we'll see" - eep - "and so we have to do different combinators that work
a bit differently" - phew

more about fold around 14:00

with rayon, use .reduce() instead; it basically does several folds at once and then folds the results together
hm, this doesn't sound like a good fit for 5b

with rayon's .reduce(), the types of acc and x have to be the same, whereas with .fold() you can have acc be different
(i'd want acc to be of a different type, eg (string last_char) or something)

ok yeah just gonna watch vids all day and then come back to rayon once i've closed all these youtube tabs

NVM for 5b: maybe split the string up into two sets of pairs (so we don't miss should-react letters on the pair boundary), like

"aBbAcdeaFf" gets turned into
"aB", "bA", "cd", "ea", "Ff" and
"a", "Bb", "Ac", "de", "aF", f"
and also each pair is marked with its associated indices in the string
and then you check each pair to see if it should react, and record the indices if so
and then sort the list of marked indices
and if an index shows up twice, then you know that [index-1 index] is the right pair to react,
and [index index+1] should be ignored, and you can handle that somehow

https://www.youtube.com/watch?v=Fe6_LFGiqP0 - systems programming in rust
"systems programming is when you spend more time looking at man pages than at stack overflow" - nice
not much actual substance in this talk, this is all just stuff that's apparent if you read the book, oh well

https://www.youtube.com/watch?v=Wz2oFEDwiOk - documentation talk
this way of framing docs is useful:
* the meet cute (what is this, why should i care)
* the black triangle (hello world but with a focus on exercising the library's full pipeline)
* the walkthrough
* the reference

https://www.youtube.com/watch?v=C4jQbc1RJPY - nov 2018 core rust devs talk
interesting bit about "momentum" around the 16 minute mark
"most RFCs never survive the first comment", meaning that the first comment
sets the tone for the discussion that follows (particularly in open-source)
she suggests that a tactic you can use is to ping someone you know and ask them
to be the one to make the first comment, to ensure the discussion doesn't
immediately go off the rails
that all makes tons of sense!

ok taking a break from vids

so i snuck a peek at forrest's day5 solution (only that one tho!) and it looks like
his is really similar to mine but doesn't have any perf issues
i think that's because my `polymer_chars_react_one_way_check()` function happens
in a tight loop and calls .to_uppercase() a million times and that's probably slow
let's try having two arrays of letters a-z and A-Z

nvm, chars have methods like .to_ascii_uppercase() and they're way way faster, that
solved the problem! i tried an approach with explicit hand-coded math and it wasn't
faster than .to_ascii_uppercase() and friends

also rayon rules

====

2/10/19

https://www.youtube.com/watch?v=grU-4u0Okto - traits in rust
trait objects bit in the third segment seems to mainly be about Box?
i need to learn more about what trait objects are, this is a good intro tho

DONE: took another peek at forrest's day5 - instead of having his buffer be a string,
he does:
let mut new_polymer = Vec::<u8>::with_capacity(source_polymer.len());

i should try this!
also check out char.eq_ignore_ascii_case(other_char)

oh, i see - the thing forrest does makes sense.
instead of having a recursive series of react_one_step() calls,
he just realizes that the polymer being worked on is itself a stack
that's clever.

so the reason that that took so long was that i came up with the multi-pass solution
and immediately tunnel-visioned on it and didn't allow myself to think of other solutions.

instead of trying over and over to optimize the multi-pass solution, i should have
taken the opportunity to think: ok, putting that aside for a moment,
what are some other ways that i might solve this problem from scratch?

i'd like to think that i'd have come up with the single-pass solution if i'd done that,
but even if i didn't come up with it, looking for fresh solutions still would have been the correct thing to do.

https://www.youtube.com/watch?v=Dbytx0ivH7Q - concurrency in rust
i'm familiar with everything in the first 30 mins, but then he talks about crossbeam and futures
tokio lets you do async i/o with futures
gives an implementation of an event loop
around 44:00 he talks about how instead of doing `struct Future`, `trait Future` makes a lot more sense
allows for different implementations of the same concept
there's a bit around 48:00 i didn't quite follow about Box and virtual dispatch and type erasure (?)

doodled around to see how to have a list of functions, got this:


let x: Vec<Box<Fn() -> ()>> = vec![
    Box::new(|| println!("1a: {}", one::one_a())),
    Box::new(|| println!("1b: {}", one::one_b())),
];

x.iter().for_each(|y| y());

might end up using that with rayon to execute all of our solutions at once once all 25 are done

ok i'm done with youtube videos!

http://smallcultfollowing.com/babysteps/blog/2015/12/18/rayon-data-parallelism-in-rust/ - old rayon article
"one of the main points of this post is to advocate for _potential parallelism_ as the basis for Rust
data parallelism libraries, in contrast to the _guaranteed concurrency_ that we have seen thus far."

post is pretty similar to the brief rayon talk the creator gave in 2017 i think

interesting note about how he has a sequential fallback for his quicksort algo

"I think the reason that the code does as well as it does is because it gets the “big things” right
– that is, Rayon avoids memory allocation and virtual dispatch"

"Previously I thought that “dangling pointers” in sequential programs and “data races” were
sort of distinct bugs: but now I see them as two heads of the same Hydra. Basically both are caused
by having rampant aliasing and mutation, and both can be solved by the ownership and borrowing."

https://blog.faraday.io/saved-by-the-compiler-parallelizing-a-loop-with-rust-and-rayon/

https://github.com/rayon-rs/rayon/blob/master/FAQ.md
has a good bit on usage guidelines for refcells
"using very small borrow sections like this is an anti-pattern: you ought to be enclosing the entire transaction together"
re: usage of .borrow()

also an interesting example about how when doing a multi-thread search, you want to keep a `lowest_cost` variable
around (or similar) and let all threads have access to it so that they can bail early if they're evaluating
a result that costs more than the cheapest one already found, etc.

https://docs.rs/rayon/*/rayon/iter/index.html
`Strings (&str) offer methods like par_split and par_lines.`
`Slices (&[T], &mut [T]) offer methods like par_split and par_windows, as well as various parallel sorting operations.`
`Various collections offer par_extend, which grows a collection given a parallel iterator.
(If you don't have a collection to extend, you can use collect() to create a new one from scratch.)`

par_chunks for slices looks useful

for the full list of parallel iterator methods, see
https://docs.rs/rayon/*/rayon/iter/trait.ParallelIterator.html
https://docs.rs/rayon/*/rayon/iter/trait.IndexedParallelIterator.html

====

2/11/19

neat, rust game engine https://github.com/amethyst/amethyst
parallel and uses entity component system

having a lottttt of trouble with graphs in 7a.

my Nodes look like this

#[derive(Clone, Debug)]
struct Node {
    step: char,
    children: RefCell<Vec<Rc<Node>>>,
}

and i'm trying to write a function that returns a Node if it's in the graph
or None otherwise
and this is what i have so far:

fn find_step_in_graph(root_node: &Rc<Node>, step: char) -> Option<Rc<Node>> {
    if root_node.step == step {
        return Some(Rc::clone(root_node));
    } else {
        for node in *root_node.children.borrow() {
            if let Some(ret) = find_step_in_graph(&node, step) {
                return Some(Rc::clone(&ret));
            }
        }
    }

    None
}

and i'm getting errors about how i can't move out of borrowed content, ie root_node.children.borrow()

which makes sense i guess but i don't really fully understand the ramifications and what i should do
just need to give it a little bit of time to let it simmer in my brain

also i found https://www.reddit.com/r/rust/comments/5ux4uq/rusts_poor_support_for_pointerbased_graphs/
and several other links to this "petgraph" thing - TODO look that up after i get a graph working on my own

things i'm confused about include: passing an Rc vs passing an &Rc

https://stackoverflow.com/questions/29401626/how-do-i-return-a-reference-to-something-inside-a-refcell-without-breaking-encap ?

ok i made a lot of progress thanks to smt - he says you never want to do an &Rc, instead you do a Rc::clone(thing)

that fixed everything

except so it turns out that in the actual puzzle input, there isn't a single root node, there are instead four
and that breaks an assumption i made when writing this solution
so i need to return to the drawing board and figure out how to adapt this solution to handle four top-level nodes
(i did)

====

2/12/19

https://tratt.net/laurie/blog/entries/a_quick_look_at_trait_objects_in_rust.html
"static dispatch leads to faster performance" ->
"Static dispatch makes inlining trivial. In my opinion, inlining is the mother of all optimisations:
the more of it you can do, the faster your program will run. Note that inlining doesn’t have to be done statically
(though it’s easier that way), but doing it dynamically tends to cause noticeable warmup."
"the type parameter means that monomorphisation kicks in: a specialised version of f is generated for every
distinct type we pass to X, allowing Rust to make everything statically dispatched."

apparently this:

fn f(x: &T) {
  println!("{}", x.m())
}

gives you dynamic dispatch - i thought Box<T> was required, but &T apparently works too

"That such an implicit coercion is possible is, in my experience, very surprising to those new to Rust.
If it’s any consolation, even experienced Rust programmers can fail to spot these coercions:
nothing in f's signature tells you that such a coercion will happen, unless you happen
to know that T is a trait, and not a struct. To that end, recent versions of Rust let you
add a syntactic signpost to make it clear:"

__interesting!!!__


fn f(x: &dyn T) {
  println!("{}", x.m())
}

"The extra dyn keyword has no semantic effect, but you might feel it makes it a little more obvious
that a coercion to a trait object is about to happen. Unfortunately, because the use of that keyword
is currently a bit haphazard, one can never take its absence as a guarantee that dynamic dispatch won’t occur."

"while it's true that all references to an object of our trait type T are of the same size,
it's not necessarily true that references to objects of different types are the same size."

====

2/13/19

(cont'd)

the article goes on to explain fat pointers and vtables
"that object’s vtable (which, itself, is a list of pointers to a struct’s dynamically dispatched functions)."

in the comment thread on reddit, steveklabnik says that there's an idiom lint you can turn on
to enforce adding &dyn notation for trait objects - another user says that it's #![warn(bare_trait_objects)]

so: i finished the book!
time to read a bunch of other stuff!
for starters, steve says that the macros appendix has been moved to be part of a chapter, so let's read that:
https://doc.rust-lang.org/book/ch19-06-macros.html

it refers to "the little book of macros",
https://danielkeep.github.io/tlborm/book/index.html
which i will not read for now

"There are some strange corners with macro_rules!. In the future, there will be a second kind of
declarative macro with the macro keyword that will work in a similar fashion but fix some of these edge cases.
After that is done, macro_rules! will be effectively deprecated. With this in mind, as well as the fact that
most Rust programmers will use macros more than write macros, we won’t discuss macro_rules! any further."

interesting!

procedural macros "must reside in their own crate with a special crate type.
This is for complex technical reasons that we hope to eliminate in the future."

main differences in proc macros since the book:
derive macros have a lot less boilerplate
and there are two other kinds of proc macros:

attribute-like macros, which let you decorate functions as well as structs/enums
the example they give is:

```
#[route(GET, "/")]
fn index() {
```

and function-like macros, which look a lot like an alternative version of declarative macros

followup piece: https://blog.rust-lang.org/2018/12/21/Procedural-Macros-in-Rust-2018.html
"macros are now integrated with the module system in Rust. This mainly means that
you no longer need the clunky #[macro_use] attribute when importing macros!"

hm, is that true?
it is!!!!

"The syn crate not only comes with the ability to parse built-in syntax but you can also
easily write a recursive descent parser for your own syntax.
The syn::parse module has more information about this capability."

interesting bit about spans + error messages

the article also mentions that the serde crate has a crazy amount of configuration;
someday i should spend more time reading through that crate's docs and trying to figure out applications for it.
apparently it's really useful!

https://rocket.rs/ web framework to look into later

ok steve also said that https://doc.rust-lang.org/book/ch07-00-packages-crates-and-modules.html was reworked

"A package has a Cargo.toml that describes how to build one or more crates. 
A package can contain zero or one library crates and as many binary crates as you’d like.
There must be at least one crate (either a library or a binary) in a package."

"If a package contains both src/main.rs and src/lib.rs, then it has two crates:
a library and a binary, both with the same name. If we only had one of the two, the package
would have either a single library or binary crate. A package can have multiple binary crates by
placing files in the src/bin directory: each file will be a separate binary crate."

looks like you can specify an absolute path by using the `crate` keyword
at the start of your path, like `crate::foo::bar()` - i think that's new

"If you want to bring an item into scope with use and a relative path, there’s a small difference
from directly calling the item using a relative path: instead of starting from a name in the current scope,
you must start the path given to use with self."

"Starting relative paths with self when specified after use might not be neccesary in the future;
it’s an inconsistency in the language that people are working on eliminating."

"your authors tend to specify absolute paths starting with crate"

"For functions, it’s considered idiomatic to specify the function’s parent module with use, and then
specify the parent module when calling the function. Doing so rather than specifying the path to the
function with use, as Listing 7-16 does, makes it clear that the function isn’t locally defined,
while still minimizing repetition of the full path."

you can also rename your imports with the `as` keyword

nested path imports is neat, you can do

use std::{cmp::Ordering, io};

instead of

use std::cmp::Ordering;
use std::io;

also you can do

use std::io::{self, Write};

instead of

use std::io;
use std::io::Write;

hm, this new version of the chapter doesn't mention mod.rs!
https://github.com/rust-lang-nursery/edition-guide/issues/104

ok now let's read the edition guide

TODO read https://doc.rust-lang.org/std/

"In Rust 2018, it's considered idiomatic to use the dyn keyword for trait objects."

man there's a lotta stuff in the edition guide

`loop` can now break with a value! that's interesting
associated constants are interesting, i guess that's how std::i32::MAX works
you can match on slices, neat

https://rust-lang-nursery.github.io/edition-guide/rust-2018/rustup-for-managing-rust-versions.html
talks about how you can specify version toolchain per-command or per-directory, neat!

====

2/14/19

https://hacks.mozilla.org/2018/03/making-webassembly-better-for-rust-for-all-languages/
seems like the main push (at least at the time?) is to have the ability to drop into rust
for the most perf-sensitive parts of your js app

https://rustwasm.github.io/2018/06/25/vision-for-rust-and-wasm.html

"Surgically inserting Rust compiled to WebAssembly should be the best choice for speeding
up the most performance-sensitive JavaScript code paths. Do not throw away your existing code base,
because Rust plays well with others. Regardless of whether you are a Rust or Web developer,
your natural workflow shouldn’t change because Rust compiled to wasm integrates seamlessly into your preferred tools."

"We can publish .wasm packages to npm, and you can depend on them in package.json
just like you normally would any other JavaScript library."

"If you are a Rust hacker and want to compile your crate to .wasm and share it on npm,
you shouldn’t have to change your workflow either. In fact, you shouldn’t even need to install npm,
Node.js, and a whole JavaScript development environment. wasm-pack will compile, optimize,
and generate JavaScript bindings for your crate. And then it will publish it to npm for you too!"

cool stuff!

looks like in the interim, several crates have been published that give you all the necessary
extern bindings so you can access eg window.requestAnimationFrame etc without having to define their
signature in rust, which is super rad (js-sys and web-sys)

https://rustwasm.github.io/2018/12/06/reflecting-on-rust-and-wasm-in-2018.html

note the bit where they have these four different application templates, looks useful
```
wasm-pack-template for creating NPM libraries with Rust and Wasm.
create-wasm-app for creating Web applications built on top of Rust-generated wasm NPM libraries.
rust-webpack-template for creating whole Web applications with Rust, WebAssembly, and the Webpack bundler.
rust-parcel-template for creating whole Web applications with Rust, WebAssembly, and the Parcel bundler.
```

https://doc.rust-lang.org/std/convert/trait.From.html

https://blog.burntsushi.net/rust-error-handling/

"the key to ergonomic error handling is reducing the amount of explicit
case analysis the programmer has to do while keeping code composable."

this is way too long.

https://speice.io/2019/02/understanding-allocations-in-rust.html

unrelated DONE: been thinking about what program i want to write post-aoc.
so far main contenders are an irc bot and a profiling library.
irc bot would be easy, profiling library would be hard.
evan's written some stuff about sampling profilers, not sure if it applies to rust,
i have the vague idea that since rust doesn't have reflection it's a lot harder to profile,
could be super wrong!

ok let's figure out how to use vs code debug mode on a rust program

it works ok but not great, you can't really see values in the sidebar
details: https://github.com/vadimcn/vscode-lldb/blob/master/MANUAL.md#rust-language-support
https://code.visualstudio.com/docs/editor/debugging

ok let's try day 8

ok so 8 is tricky

at first it seems like it'd be perfect for a recursive solution,
but you can't know the length of the vec of numbers to pass to the recursive call
without having processed the whole input first

so anyway this has to be done in one pass

right now i'm mulling over some sort of, like, stack of stacks
where each sub-stack represents the children of the rightmost entry in the parent stack
so like

2 3 0 3 10 11 12 1 1 0 1 99 2 1 1 2

becomes

[ 
    Node {num_c: 2 num_m: 3}
    [
        Node {num_c 0 num_m 3}
        // at this point we see we're not processing any children
        // so we push the next 3 entries into the most recent node's metadata vec

        // at this point we see that the current substack has 1 item in it,
        // and the parent node has num_c 2, so we still have more children to process

        Node {num_c: 1 num_m: 1}
        // so basically if we instantiate a new node and its num_c is > 0,
        // then it becomes the new parent node and we start a new substack
        [
            Node {num_c: 0 num_m: 1}
            // we're not processing any children
            // so we push the next 1 entry as metadata

            // at this point we see that the current substack has 1 item in it,
            // and the parent node has num_c 1,
            // so we set the parent's children to the current substack

        ]

        // at this point we see that the current node has 1 metadata to process, so we add that

        // at this point we see that the current substack has 2 items in it,
        // and the parent node (DONE: how do we get back tot he parent node? separate stack of parent nodes?)
        // has num_c 2, so we set the parent's children to the current substack
    ]

    // and now we process the next 3 entries as metadata
]

so it's looking to me like actually we have two stacks:
one stack of parent nodes,
one stack of child vectors
that doesn't make sense when written downb ut let's look at the example done that way

input:
2 3 0 3 10 11 12 1 1 0 1 99 2 1 1 2

original state:
parent_stack []
children_vec_stack []

read 2 entries to make node:
A {num_c: 2, num_m 3}

set it as parent
num_c is > 0, so start a new children_vec

parent_stack []
children_vec_stack []
parent A {num_c: 2, num_m 3}
children_vec []

read 2 entries to make node:
B {num_c: 0, num_m: 3}

num_c is 0, so:
    read 3 entires, put them in B's metadata vec
    add B to children_vec

parent_stack []
children_vec_stack []
parent A {num_c: 2, num_m 3}
children_vec [B {num_c: 0, num_m: 3, metadata: [10, 11, 12]}]

read 2 entries to make node:
C {num_c: 1, num_m: 1}

num_c is > 0, so
    push parent on parent_stack
    set parent to C
    push children_vec on children_vec stack
    start a new children_vec

parent_stack [A {num_c: 2, num_m 3}]
children_vec_stack [[B {num_c: 0, num_m: 3, metadata: [10, 11, 12]}]]
parent C {num_c: 1, num_m: 1}
children_vec []

read 2 entries to make node:
D {num_c: 0, num_m: 1}

num_c is 0, so:
    read 1 entry, put it in D's metadata vec
    add D to children_vec

parent_stack [A {num_c: 2, num_m 3}]
children_vec_stack [[B {num_c: 0, num_m: 3, metadata: [10, 11, 12]}]]
parent C {num_c: 1, num_m: 1}
children_vec [D {num_c: 0, num_m: 1, metadata: [99]}]

children_vec has len 1 and parent has num_c 1, so we're done with parent's children
    read parent.num_m entries and put them in parent.metadata
    set parent.children to children_vec
    set children_vec to children_vec_stack.pop()
    add parent to children_vec
    set parent to parent_stack.pop()

parent_stack []
children_vec_stack []
parent A {num_c: 2, num_m 3}
children_vec [
    B {num_c: 0, num_m: 3, metadata: [10, 11, 12]}
    C {num_c: 1, num_m: 1, children: [D {num_c: 0, num_m: 1, metadata: [99]}], metadata: [2]}
]

children_vec has len 2 and parent has num_c 2, so we're done with parent's children
    read parent.num_m entries and put them in parent.metadata
    set parent.children to children_vec
    children_vec_stack is empty, so we're done! return parent

so i think that algorithm makes sense, and the two-stack approach makes sense!
DONE: how do we actually program that?

ok nvm i think we can use recursion after all
just with a mutable buffer input

ok yeah it was recursion after all lol
i'm just so used to having recursive functions be pure

the idea of having a recursive function that operates on a mutable buffer input
and only consumes some small number of items off of its front just never occurred to me!
totally worked first try tho once i banged the code out!

DONE profiling links at https://www.reddit.com/r/rust/comments/aqqr0z/what_are_best_resources_on_profiling_and/

===

2/15/19

starting 9
seems pretty straightforward?

ok so the thing about 9b is that my naive 9a implementation is about
a bajllion times too slow for 9b.
so there must be something smarter we can do here!

my initial reaction is that .insert() and .remove() are probably really slow
when the vector is like 8mb large!
what can we do instead?
have a bitmask of valid vector indices?

alternatively, keeping with the theme of solutions so far - do we have a buffer of
[0..max_marble] integers,
and we somehow consume it in one pass?

let's try thinking about a version of this game except where scoring happens every 5 marbles
and you move 2 to the left instead of 7 to to the left.


plan so far: (this is several plans at once mixed together, DONE distill)
{
allocate a bitfield of max_marble bits, all set to 0, representing whether or not an index into the list is valid
    this bitfield only gains valid indexes from left to right -
    once an index has become invalid midway between the first bit and the currently rightmost bit, it never becomes re-valid

allocate a vector of max_marble ints, initialized to 0 although that shouldn't matter
DONE: hide the vector behind a struct that uses the bitfield in order to ensure that you never
access an invalid index?
the struct should also keep track of the length
DONE: MarbleGame struct. what is its api? add_marble() returns an Option<(player, turn_score)> maybe?

whenever we put a new marble into the vector, flip the index's corresponding bit to 1

DONE but how do we handle looping back from the end of the vector to the start of the vector?
DONE what's the relationship between the list of indexes and the vector of marble ids?
DONE how do we handle putting a new marble in midway through the circle of marbles?

DONE what if the vector is a vec that maps {marble_id: current_index} ?
and every time we do a midway-through-the-vector insertion, we update the index of all of the marbles to the right of that insertion?
still sounds like a whole lot of work!
DONE this is the best idea i've had so far, but it still seems suboptimal! in fact i think it might be way worse
    than the naive approach! in particular, getting "all the marbles to the right of that insertion" is a lot of work!

iterate i from 0 to max_marble
keep track of length in a variable
generate a list of insertion indexes like [1, 1, 3, 1, 3, 5, 7, 1], etc // DONE IT'S NOT why though? how is this useful?
if i % 23 is 0, do scoring somehow
and i really do think a bitmask of 
}

ok so on the walk into downtown i had an idea
so what if we have two deques, left and right
what other values would we need to track?
let's sketch out this struct

struct MarbleGame {
    left: VecDeque<u32>,
    right: VecDeque<u32>,
    current_position: usize,
    next_marble_id: usize,
    current_marble: usize,
}

and sketch out some implementation

impl MarbleaGame {
    pub fn new(last_marble) -> MarbleGame;

    pub fn add_marble(&mut self) -> Option<(player_index, points)> {
        if next_marble_id % 23 != 0 {
            // place marble at this position
            self.left.push_back(self.current_marble);
            self.move_right();
            self.current_marble = self.next_marble_id;

        } else {
            // DONE what does scoring look like?
        }

        self.next_marble_id += 1;
    }

    fn move_right(&mut self, num_spaces: usize) {
        if self.right.is_empty() {
            let tmp = self.right;
            self.right = self.left;
            self.left = tmp;
        }

        self.left.push_back(self.right.pop_front());
    }

    fn move_left(&mut self, num_spaces: usize) {
        if self.left.is_empty() {
            let tmp = self.right;
            self.right = self.left;
            self.left = tmp;
        } 
        
        self.right.push_front(self.left.pop_back());
    }
}

what does it look like when you move all the way left?

say we have
0 (4) 2  1  3 
and we move left one
then we get
(4) 0 2 1 3
fine.
when happens if you move left again?

well, you should get
0 2 1 3 (4)
how do we get that?
we just swap left and right and that's it

so hm let's take another look at moving right
say we have
0 2 1 (4) 3 
and we move right one
then we get
0 2 1 3 (4)
fine.
what happens if you move right again?

well, you should get
0 2 1 3 (4)
which you get just by swapping left and right.

hm let's take a look at what it would look like to actually place a marble in an at-the-end position vs an in-the-middle position
let's place this marble:
0 2 1 (4) 3 
then we get:
0 2 1 4 3 (5)
so we placed the marble and then moved right one.

instead let's place this marble:
0 2 1 3 (4)
then we get:
0 2 1 3 4

oh i think i get it
so you _always_ have to move left one or right one
and if you're wrapping around, you _also_ swap left and right
you don't just do one or the other, you have to do _both_ in a wraparound case
k!

ok cool i think i'm on the right track, going afk, hopefully i remember my state of mind

ok i think that having a current_marble field is confusing things.
i think that we should just say that the marble that's at the far back end of self.left is the current marble.

done!
looks like forrest implemented it using a linked list - that actually makes way more sense
DONE NO THANKS let's try that
way way way way way more sense
like so much sense that i'm ashamed of not having thought of it but oh well

====

2/16/19

https://cglab.ca/~abeinges/blah/too-many-lists/book/

ok well on the bright side https://cglab.ca/~abeinges/blah/too-many-lists/book/#an-obligatory-public-service-announcement
kind of exonerates me re: not having thought of using a linked list here
i remember learning linked lists in college and being told that you'd never actually use them in real life

https://cglab.ca/~abeinges/blah/too-many-lists/book/first-push.html
he uses std::mem::replace(), neat

ok uh
i'm not super into this book because it seems out of date
and i tried using the techniques in https://play.rust-lang.org/?gist=71c6bc45ff92452d5a4397ddb2dbb3de&version=stable
but did not find them easy to adapt to this program
so i think having two deques is fine.

10a looks interesting
the first part looks relatively straightforward
but detecting when letters have been spelled out? how do you do that?
DONE heuristic: look for straight lines!!!!
have a function that looks at the grid and counts the number of straight lines with length >5
and if it's high (unclear atm what "high" means), that's the one!

====

2/17/19

11a was easy
11b is also easy but runs slow
there's clearly a way to speed it up

first approach that jumps out at me:

for larger size lenses, you can save a lot of lookups by just doing math around the edges

like let's say we have this grid (i'll be using regular coordinates for this example, not their weird (1,1) origin coordinates)

-3   4   2   2   2
-4   4   3   3   4
-5   3   3   4  -4
 4   3   3   4  -3
 3   3   3  -5  -1

and let's say we're looking at 4x4 sizes
so we start in the bottom right
which means that the lowest-right 4x4 square we can look at starts at [1, 1] with the number 4 in its top left

and that square has a power of 27.
now we move left one position to look at the 4x4 square whose top-left point is [0, 1], the -4
and to find its power we take 27, subtract (4 - 4 - 3 -1), and add (-4 -5 + 4 +3)
or i mean i guess conversely we could start in the top left and move down right, that doesn't change anything
cool

DONE put a print_grid() function in util, DONE optional min/max x/y args

DONE forrest suggests a https://en.wikipedia.org/wiki/Summed-area_table for 11b, take a look

starting 12a
reading through itertools docs

group_by looks useful:

```
// group data into runs of larger than zero or not.
let data = vec![1, 3, -2, -2, 1, 0, 1, 2];
// groups:     |---->|------>|--------->|

// Note: The `&` is significant here, `GroupBy` is iterable
// only by reference. You can also call `.into_iter()` explicitly.
for (key, group) in &data.into_iter().group_by(|elt| *elt >= 0) {
    // Check that the sum of each group is +/- 4.
    assert_eq!(4, group.sum::<i32>().abs());
}
```

tuple_windows seems relevant, is there some non-tuple version?

into_group_map also looks really useful
and sorted!
and minmax!

ok 12a done
12b looks pretty nuts, definitely going to need to adjust my approach to get this to work

ok so wow
state of mind
so we can't just immediately make the vector of pots 1MB wide because checking all those overlapping chunks would be a pain
although actually we could just track min_index and max_index and update them each generation
to slowly widen the area that we look through

ok so something's definitely going wrong with my translating back and forth between indexes
that's because i wrote this index stuff in a really brittle fiddly way that i was hoping wouldn't come crashing down
but it has
soooo

so i looked around on the subreddit and people say that after a bit you end up gaining exactly X plants every generation
so let's write code to detect that

ok cool done
so the code right now is just totally atrocious
DONE: tomorrow go back and tidy up
and write a test for 12b, answer was 3750000001113

===

2/18/19

ok, day 13 looks fun!
initial state of mind:
store the grid as a 2d vector of MineSpace enums

the enum has these variants:

StraightVertical // |
StraightHorizontal // -
CurveRight // \
CurveLeft // /
Intersection // +
Empty

also need to parse out carts' starting points (and detect what the space underneath them looks like?)
<
>
^
v

"On your initial map, the track under each cart is a straight path matching the direction the cart is facing."

carts have these fields:
x: usize
y: usize
direction: Direction

Direction is an enum with variants North, East, South, West

ok, getting 13a working on the sample input was fun
but i come up with the answer (63, 31) , which is apparently wrong :(
oh right it was because cart_positions wasn't being cleared of old positions mid-turn

looking at 14a

how much d'you want to bet that 14b involves drastically bumping up the number of elves?

found the bug in 14a, i was dropping recipes on the ground if they were exactly equal to 0

ok 14b done! runs kinda slow, about 3 seconds, DONE optimize

ok so yeah the trick is going to be to remove the allocations
the original solution allocated two vectors every tick, let's kill them one at a time
that fixed it :)

===

2/20/19

day 15

"For instance, the order in which units take their turns within a round is the reading
order of their starting positions in that round, regardless of the type of unit or
whether other units have moved after the round started."

reading order being (y, x) position tuples - compute these at the start of the round to make
an ordered list of turns

unit turn:
1. identify all enemy units; if none exist, turn is over (and so is the game?)
2. attack an enemy if you're adjacent to one
3. otherwise identify all open squares adjacent to a target
    * if none exist and the unit isn't already adjacent to a target, end turn
4. figure out which open space is closest and make one step toward it.
    * if there's no open path to any target, end turn
    * if multiple open spaces are closest, pick the first by key (y, x)
    * DONE: how to represent this?
        * each path is a list of positions, you pick the path with the shortest length, if there are multiple you sort by the (y, x) of the last space in each path
    * DONE note that a space can have multiple paths to it! so once a space is chosen, you choose the path whose _first_ space is first in (y, x) order

writeup strongly hints that you should start with movement and only move on to attacking once you've gotten movement solidly down

DONE print_grid() function (one in utils already, right?)

=====

2/22/19

implemented bfs per avi's great tutorial

having trouble figuring out the best way to iterate over the list of monsters while mutating it
like, that's usually a bad thing
so, what to do instead?

https://www.reddit.com/r/rust/comments/7xl0o9/iterating_over_a_vec_mutably_while_already/ has some tips

DONE would things be simpler if each monster had an id? probably yes, right? like, definitely majorly yes?
and game.monsters is a hashmap of id to monster?

https://www.youtube.com/watch?v=aKLntZcp27M
generational index allocator is interesting
she says that vecs and indexes are the way to go and that this approach helps avoid dangling indexes
there's a crate called slotmap, TODO investigate

====

2/23/19

so right now we're pretty close to having correct results,
except sometimes our number-of-full-turns-completed is off by 1,
and we often have surviving monsters whose health total is incorrect by 3hp.
which tells me that there's something wrong either with attacking or with removing dead monsters

oops!
"After moving (or if the unit began its turn in range of a target), the unit attacks."
so it can move _and_ attack!

ok, implementing that fixed the first two extended combat examples, but when i tried to run
the full input i got 227744, which the checker says is too low.
so let's try the rest of the examples!

DONE run clippy again

====

2/24/19

15b done
runs kinda slow!
let's do another pass on profiling, yeah?
https://www.reddit.com/r/rust/comments/aqqr0z/what_are_best_resources_on_profiling_and/

https://blog.anp.lol/rust/2016/07/24/profiling-rust-perf-flamegraph/

"Once you’ve fully excised calls to clone(), are doing everything conceivable in parallel,
have trimmed any non-essential checks and calculations, what to do?"

TODO: excise calls to clone and do things in parallel!

ok most of the tutorials assume you're on linux and don't work on os x -
valgrind and perf don't work on os x
but carol's guide in http://carol-nichols.com/2017/04/20/rust-profiling-with-dtrace-on-osx/ works like a charm

so we spend all of our time in fifteen
and of that time, it's all spent in malloc
i think this is probably because of all of my hashsets

actually it had more to do with the fact that .filtered_neighbors() and .all_neighbors() returned Vecs!
forrest solved this problem by returning a struct that implements Iterator, which makes sense.
i did that and my runtime went from 5s down to 2s!

-
BTW the commands i'm using for profiling:

(from cargo project)
rm out.stacks
sudo dtrace -c './target/debug/advent_2018' -o out.stacks -n 'profile-3000 /execname == "advent_2018"/ { @[ustack(100)] = count(); }'

(from flamegraph clone)
./stackcollapse.pl ~/dev/advent_2018/out.stacks | ./flamegraph.pl > advent.svg
-

from carol's writeup. super helpful!

now that we've gotten rid of the main source of allocations, the remaining bottleneck appears to be in the bfs function
we spend all our time manipulating this `came_from` map
i can't see an obvious way to optimize this though

====

2/25/19

well, we could reduce the number of times that we call bfs
what if the game stored these additional fields:
tick_number
someone_last_moved_on

and so that way we don't have to bfs a million times if nobody's changed positions in a few ticks?

it doesn't look like that buys us much

BUT
it _does_ look like the puzzle input we've been given divides pretty cleanly into multiple _regions_
so what if at the start of each combat round, we do a flood fill to find the number of distinct blocked-off regions
and if the current monster is in region A but all of its destinations are in region B, we know that it can't possibly get to any of them
so we know we can safely skip bfs for it?

and perhaps we could send that region information along to bfs if we find out that we _do_ have to bfs?
so compute_came_from also gets a `region` input, and when it's expanding the frontier it skips candidates that aren't in `region`?

hm but no, never mind, compute_came_from already does this after all, so there's no need for a separate flood fill step
because it takes `unoccupied_positions` as an input, and so it can't expand its search into other regions

hm but even so - if we had this precomputed region information, we could use it to _skip_ bfs for the affected monsters
if i'm in region A but my destinations are all in region B, don't bfs
that seems worth investigating!

=====

2/26/19

so i finally finished https://www.youtube.com/watch?v=9_3krAQtD2k
it was really good! lots of meaty narrative context

reading through https://github.com/aturon/rfcs/blob/future/text/0000-futures.md now
the "runtime characteristics" comment is really good
the sections toward the bottom are very good, lots of good context

http://aturon.github.io/2016/08/11/futures/

"Early on, Rust had a “green threading” model, not unlike Go’s...
The problem is that green threads were at odds with Rust’s ambitions to be a true C replacement,
with no imposed runtime system or FFI costs: we were unable to find an implementation strategy
that didn’t impose serious global costs."
interesting!

http://aturon.github.io/2016/09/07/futures-design/
^^^^^^^ this is very good

"By eliminating all the intermediate callbacks, we’ve addressed some of the key problems
of the previous version of the trait. But we’ve introduced a new one: after NotReady is returned,
who polls the future, and when do they do so?"

this whole .poll()-driven architecture is v interesting

https://github.com/rust-lang/rfcs/blob/master/text/2394-async_await.md

one thing i hadn't really appreciated was that it's a major design decision re:
how to annotate the return value of an async fn. rust has gone with annotating it with the inner type,
eg u8, which is the type of the value that's eventually returned from the function;
they could have instead had async fn return types be annotated with Future<foo, bar, whatever> syntax
i'm fine with the inner type, sg2m

"Rustdoc can handle async functions using the inner return type in a couple of ways
to make them easier to understand. At minimum we should make sure to include the async annotation
in the documentation, so that users who understand async notation know that the function will
return a future. We can also perform other transformations, possibly optionally, to display the
outer signature of the function."

"A fundamental difference between Rust's futures and those from other languages
is that Rust's futures do not do anything unless polled. The whole system is built
around this: for example, cancellation is dropping the future for precisely this reason.
In contrast, in other languages, calling an async fn spins up a future that starts
executing immediately."

looks like i'm reading and watching vids all day
still planning on implementing that regions change for day15 though
really looking forward to seeing what it does to perf / how it affects the flamegraph

https://doc.rust-lang.org/std/mem/fn.discriminant.html interesting
"This can be used to compare enums that carry data, while disregarding the actual data"
assert!(mem::discriminant(&Foo::A("bar")) == mem::discriminant(&Foo::A("baz")));
assert!(mem::discriminant(&Foo::B(1))     == mem::discriminant(&Foo::B(2)));
assert!(mem::discriminant(&Foo::B(3))     != mem::discriminant(&Foo::C(3)));

https://doc.rust-lang.org/rust-by-example/conversion/from_into.html

"The Into trait is simply the reciprocal of the From trait. That is, if you have
implemented the From trait for your type you get the Into implementation for free."

DONE try out https://github.com/bheisler/criterion.rs for measuring optimizations to day15

====

2/27/19

been spending some time reading through the criterion docs
https://bheisler.github.io/criterion.rs/book/user_guide/timing_loops.html has a good summary of
all the different methods available on a Bencher, eg b.iter() etc, and when you'd want to use them

criterion results for 15b at the moment:
15b                     time:   [881.40 ms 900.86 ms 922.18 ms]     

so now we have a good well-measured baseline that we can be confident about!

DONE see if it would be reasonable to run benchmarks nightly on ci or something;
don't really need to, just curious

"Note that cloud CI providers like Travis-CI and Appveyor introduce a great deal of noise
into the benchmarking process. For example, unpredictable load on the physical hosts of
their build VM's. Benchmarks measured on such services tend to be unreliable, so you should
be skeptical of the results. In particular, benchmarks that detect performance regressions
should not cause the build to fail, and apparent performance regressions should be verified
manually before rejecting a pull request."

criterion seems really good btw!

https://www.youtube.com/watch?v=4QZ0-vIIFug *** good stuff

gives _tons_ of narrative context around how they got to the .poll()-based system we see today, nice
although this talk is from the era where they had this task::current() thread local variable thing
and hadn't yet come up with Pin etc

https://boats.gitlab.io/blog/post/2018-01-04-unsafe-abstractions/

****
"The unsafe keyword is required to apply the abstraction because the abstraction introduces
some invariant which cannot be type checked and which the rest of the program is allowed
to assume is maintained in order to assume type safety."
****

v v v well expressed

so i started implementing regions
and the bfs was pretty straightforward
until i realized that this is a little more complicated than i thought, or anyway more subtle to express
my intiial implementation just dealt with self.unoccupied_spaces
but at the same time, i want each monster to be in a region
but regions are defined by the borders created by # spaces _and_ by monsters
so it's like, i need to be in looking-at-monsters mode but also in not-looking-at-monsters mode
hm. i guess it's just not the case that monsters can be in regions, i can think of a lot of edge cases there

oh

so i got this mostly working, except:
regions _can't_ just be computed one time at the start of each tick, because they can
be invalidated whenever a monster moves or attacks.
so you have to basically compute regions for each monster in every tick and that's not great perfwise
so this optimization doesn't really work! oh well!
gonna run criterion on it just for grins:

DONE this could still work
only update regions on attack if a monster _DIED_!

here's the benchmark with my initial buggy implementation that recomputes on every move AND attack:
15b                     time:   [1.1716 s 1.1974 s 1.2250 s]

benchmark after making it still recompute on all moves but only recompute on attack if the target died:
15b                     time:   [988.00 ms 990.34 ms 995.06 ms]               
                        change: [-16.588% -13.451% -9.9169%] (p = 0.00 < 0.05)
                        Performance has improved.

which is still worse than where we started
gonna profile just for grins

so now we spend 11% of our time in hashset.contains and 14% of our time in find_regions
not a super huge amount of time doing allocations interestingly

changed from using contains to intersection when computing region+destination combo, no change:

15b                     time:   [1.0324 s 1.0362 s 1.0409 s]                  
                        change: [-1.3267% +2.7950% +6.7726%] (p = 0.18 > 0.05)
                        No change in performance detected.

so anyway i'm gonna revert to the pre-region code, but still this was a fun exercise!

====

2/28/19

https://boats.gitlab.io/blog/post/shifgrethor-iv/

"The tracing algorithm works like this: starting at a root, visit every Gc object it references
and mark that object so that it will not be collected. This algorithm is an instance of
the visitor pattern, which Rust has a well-known manner of encoding: a trait and a derive
for that trait which calls the trait’s method recursively on all fields. serde’s traits,
for example, are an instance of this pattern."

https://boats.gitlab.io/blog/post/rust-2019/
boats organizational debt post
this one is super duper good, i hope something comes of it this year

http://fitzgeraldnick.com/2018/12/14/rust-and-webassembly-in-2019.html
sounds like we won't be rewriting quinto into rust+wasm in 2019, maybe 2020
although it might be fun to do an original laborious rewrite and then incrementally improve it
as the landscape improves
for certain values of "fun" :)

ok i've processed all my tabs let's do another day
day 16

====

3/1/16

so i had this one function with this signature

fn find_mapping(
    commitments: &mut HashMap<usize, usize>,
    possibilities: &mut HashMap<usize, HashSet<usize>>,
) -> bool {

and in there i wanted to modify `possibilities` in a loop, but i got a compiler error complaining that
the first iteration of the loop borrowed possibilities mutably and then the second iteration
couldn't get a mutable borrow because the first one still existed
and this was really confusing because i was like, didn't the first one go out of scope at the end of the first loop iteration?
and i googled around and none of the answers were super helpful

but i *think* that this answer https://stackoverflow.com/questions/46393890/mutable-borrow-in-loop is talking about my specific problem
i think that having two mutable references in this function signature causes the compiler to give them lifetimes 'a and 'b
and apparently, if a mutable reference has a lifetime, then that reference has to live as long as the lifetime(?)

so i'm going to try to counteract this by making a struct that bundles these two mutable hashmaps together

struct MappingComputationData {
    commitments: HashMap<usize, usize>,
    possibilities: HashMap<usize, HashSet<usize>>,
}

not a great name but maybe i'll come up with a better one later if this works

...lol fuck me the algorithm ran successfully on the first try but when i added printlns to see how it behaved
it never backs out!
so this actually could have been solved iteratively / without this nutso recursion
so DONE next up let's rewrite this thing to be simpler
i was pretty convinced that this would need a recursive implementation because the possibilities were too vague,
but i've been really really sick all week so i guess my brain was just wrong

=====

3/3/19

https://www.youtube.com/watch?v=ycMiMDHopNc - jonhoo's setup *****
https://github.com/livioribeiro/cargo-readme looks useful
also maaaaybe cargo tree -i, i can see it being useful in specific investigations but don't expect i'd use it on the regular
cargo benchcmp looks useful if you've got a ton of benchmarks defined

====

3/4/19

thoughts on 17
don't store the whole 2d grid, no need to represent the empty spaces
store the grid as a list of Points in y, x order
have a queue of Streams (is there a better name?)
a Stream has fields position and mode; mode is either Falling or Filling
a stream falls until it reaches something solid, then fills until its container is full, then is destroyed
AND is then replaced by either one or two streams, depending on if the vessel it just filled has equally tall walls
TODO one edge case that might come up - what if we have a vessel like this

 |
# # 
# # #
#   #
#####

it will end up looking like this

|~~~|
 #~# 
 #~# #
 #~~~#
 #####

note the new stream on the right. we'll need to make sure we handle falling onto water correctly

====

3/5/19

gonna put this on pause for now, gettin kinda tired of puzzles. this was a good way to learn rust
but i'm ready to take a break! might still use this repo for note-taking when watching rust vids /
reading rust blogs/books; would like my next rust project to be some sort of small application
where _i_ get to choose the rules :)

===

4/28/19

not doing any advent stuff atm, just using this doc as a scratchpad
someday i'll formalize my dev diary process a little bit better

https://www.youtube.com/watch?v=0zOg8_B71gE
around 12:30, he says: avoid having lots of booleans in your api surface, instead you should feel totally fine
about using 2-variant enums, like

enum DisplayStyle {Color, Monochrome}

i _love_ this, this is super super smart. i've known for a long time (since code complete iirc) that having tons of
booleans in your api surface is an antipattern, but i haven't had a good sense of what to do instead -
this totally answers that question. it's great because it's way more self-documenting.

around 20 minute mark: implement all std traits on your types, especially iterator