dev-diary.txt

TODOs
    * try out proptest
    * read through https://github.com/Aidiakapi/advent_of_code_2019 for interesting rust tidbits


====

7/11/20

let's do this!
starting with day 1

alg was pretty straightforward

when i got to part b, i initially tried to use a loop {}
but i was having issues reassigning a var that lived outside of the loop
couldn't figure out the answer by googling
so i switched to recursion which made the problem go away :]

next up, i had this utility function

pub fn parse_ints_from_file(filename: &str) -> Vec<i32> {
    let contents = fs::read_to_string(filename).unwrap();

    contents
        .lines()
        .map(|x| x.parse::<i32>().unwrap())
        .collect()
}

and i wanted to figure out how to make it generic

i ended up trying this out

pub fn parse_ints_from_file<T: FromStr + Debug>(filename: &str) -> Vec<T> {
    let contents = fs::read_to_string(filename).unwrap();
    contents.lines().map(|x| x.parse::<T>().unwrap()).collect()
}

but it gives this error:

error[E0599]: no method named `unwrap` found for enum `std::result::Result<T, <T as std::str::FromStr>::Err>` in the current scope
 --> src/util.rs:8:45
  |
8 |     contents.lines().map(|x| x.parse::<T>().unwrap()).collect()
  |                                             ^^^^^^ method not found in `std::result::Result<T, <T as std::str::FromStr>::Err>`
  |
  = note: the method `unwrap` exists but the following trait bounds were not satisfied:
          `<T as std::str::FromStr>::Err: std::fmt::Debug`

error: aborting due to previous error

For more information about this error, try `rustc --explain E0599`.
error: could not compile `advent_2019`.

which i can't figure out what to make of.

made a rust playground link:
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=ffeee4b54d862e99387b644c9d03d19b
and sent it to smt asking for advice!

will sent back this:

pub fn parse_ints_from_file_generic<T: FromStr + Debug>(filename: &str) -> Vec<T> where <T as std::str::FromStr>::Err: std::fmt::Debug {
    let contents = fs::read_to_string(filename).unwrap();

    contents
        .lines()
        .map(|x| {
            let parsed = x.parse::<T>();
            parsed.unwrap()
        })
        .collect()
}

which he acknowledges is hideous

smt solved it!!

pub fn parse_lines_from_file<T: FromStr>(filename: &str) -> Vec<T> {
    let contents = fs::read_to_string(filename).unwrap();

    contents
        .lines()
        .map(|x| {
            x.parse::<T>()
                .map_err(|_| format!("unable to parse {:?}", x))
                .unwrap()
        })
        .collect()
}

he says:
    unwrap() expects to print the "Debug" of whatever the Error was from the Result type
    so it requires that the error implements Debug
    that's why mapping the error to a string fixed it, because String implements Debug

neat!

happened to open this article about docs

https://blog.guillaume-gomez.fr/articles/2020-03-12+Guide+on+how+to+write+documentation+for+a+Rust+crate
    this is very good!
    no_run is interesting
    so is the thing about putting # at the beginning of lines that you don't want to show up in the docs

    rustdoc lints are neat too! v good for libraries obviously

ok, so looking at day 2

you have a tape
you have instructions, groups of four ints (or one int for stop-program)

opcode 1 is add
1, idx_1, idx_2, dst

opcode 2 is mul
2, idx_1, idx_2, mul

opcode 99 is stop program

you process an instruction - a group of 4 integers on the tape - and then step forward 4 to the next one

so! we need a tape

it'll be a vec of i32s

===

7/12/20

ok day 2 was pretty ez and also pretty fun

looks like it's the setup for some future days

i'll definitely be extracting this run_program() stuff out into a separate file for reuse later
but for now let's just go right into day 3

ok so 3 is interesting
one particularly interesting thing about it is that the grid has no specified size

so i could just try to make a huge 2d vector but that would be dumb and gross
but like it would work, just be inefficient and slow

is there a more efficient way to represent this?

what if each wire is represented as a series of (x, y) positions?

that seems better to me

then we could just check to see which elements are in both vectors

DONE learn more about into_iter, https://stackoverflow.com/questions/34733811/what-is-the-difference-between-iter-and-into-iter

https://hermanradtke.com/2015/06/22/effectively-using-iterators-in-rust.html
    "I tend to use .iter() most. I try to be very concious and deliberate
    about when I move resources and default to borrowing (or referencing)
    first. The reference created by .iter() is short-lived, so we can move or
    use our original value afterwards. If you find yourself running into does
    not live long enough, move errors or using the .clone() function, this is
    a sign that you probably want to use .into_iter() instead."

done profile 3a, i'm expecting to see huge slowdown bc of tons of tiny allocations
    https://carol-nichols.com/2017/04/20/rust-profiling-with-dtrace-on-osx/ good tips

i think that it's gonna be bc i make so many tiny strings
i think that instead it would be a lot better to read each wire string in one pass
eg have a function that returns a slice of the string up until the next comma, then operate on that

looks like most of our time is actually spent initializing the hashset?

https://stackoverflow.com/questions/44575380/is-there-any-way-to-insert-multiple-entries-into-a-hashmap-at-once-in-rust

ok you know what
this is actually all fine
when built in release mode, the whole program so far runs in 0.04 seconds
so 3a is fine for now
let's see if it falls over when it comes time for 3b though!!

it didn't :)

ok, i've been reading chapters of the book here and there
just finished structs and enums
and made it to the modules chapter!
but i think a lot changed after the paper book was written, re: modules, 2018 edition, etc
so i'm going to read the online version of that chapter instead, hopefully it's more up to date

https://doc.rust-lang.org/book/ch07-00-managing-growing-projects-with-packages-crates-and-modules.html
    ya, in https://github.com/rust-lang/book/issues/1888 carol says ch 7 was "totally reworked"

    struct fields are private by default, but can be made public one by one
    by contrast, enums are also private by default, but if they're public then all of their variants are public
    which makes sense!

    oh, i figured out why i couldn't use `use` in this new project
    it was because i didn't have a `src/lib.rs` like i do in advent_2018

    "Using a semicolon after mod front_of_house rather than using a block
    tells Rust to load the contents of the module from another file with the
    same name as the module."

oooh https://doc.rust-lang.org/stable/edition-guide/ should be a good reread

ok cool

4a was easy to implement

kinda slow tho! nothing crazy, but not fast

for fun i flipped the conditionals around, checking nondecreasing first, and that made it about twice as fast
neat!

and then i changed it so that
instead of making a jillion tiny vectors from scratch
we just allocate a single vector that we use as a buffer
and that shaved the bulk of the rest of the time off :]
not my usual way of doing things, but there's a reason it's a common pattern!

ok let's look at day 5!

so it looks like it's time to revisit the opcodes/memory/program stuff

we're handling two more opcodes, with different lengths

so i think it's time to make opcodes a more first-class concept

or tbh maybe not, i think i can get away with a long match() for now

i'm not sure what the appropriate tool here would be - structs? enums?

i guess there could be an Opcode struct like this

struct Opcode {
    opcode: i32,
    num_args: usize,
}

but then so where does the code live that runs the operation for a particular opcode?

ugh yeah i'll just stick with a match for now
i'll figure out something better later

ok yeah so nvm i went with that struct idea

struct and a match

workin ok so far!

it was necessary+helpful bc the number of args is important to know so that we can
advance the instruction pointer appropriately

ok five is gonna be complicated :)

input+output
and modes
eek

===

7/13/20

ok let's take a look at 5a again

Parameter modes are stored in the same value as the instruction's opcode. The
opcode is a two-digit number based only on the ones and tens digit of the
value, that is, the opcode is the rightmost two digits of the first value in
an instruction. Parameter modes are single digits, one per parameter, read
right-to-left from the opcode: the first parameter's mode is in the hundreds
digit, the second parameter's mode is in the thousands digit, the third
parameter's mode is in the ten-thousands digit, and so on. Any missing modes
are 0.

maybe a parse_instruction() fn that returns (opcode: i32, mode: i32)

ahhh i see

took me a second to notice this:

Parameter modes are single digits, *****one per parameter******, read
right-to-left from the opcode: the first parameter's mode is in the hundreds
digit, the second parameter's mode is in the thousands digit, the third
parameter's mode is in the ten-thousands digit, and so on. Any missing modes
are 0.

ok wow this shit is interesting

definitely need a function just for this

but how to get it to not allocate a ton of tiny vecs when parsing/representing parameter modes?

i guess it could take as input a buffer vec<i32> that's initialized with zeroes

    Parameters that an instruction writes to will never be in immediate mode.

makes sense

    Integers can be negative: 1101,100,-1,4,0 is a valid program (find 100 + -1, store the result in position 4).

interesting!

ok so i hacked on 5a for a bit and i thought i had implemented it right
but the output commands are printing out 3
and they're supposed to be printing out 0
and also it crashes after a while
so clearly i've done something wrong

let's work this program out by hand

3,225

take an int (1) as input, store it to 225

1,225,6,6

add the value at 255 and the value at 6, and store the result to 6
the value at 255 is 1
the value at 6 is 1100
so the result is 1101, which we store to 6

1101,1,238,225

add 1 and 238 and store the result to 225
the result is 239, which we store to 225

104,0

print out the value at 0

which is 3!!!!!!
what gives????????

i must be interpreting this program incorrectly somehow

oh fuck wait nvm

104,0

that's "print in immediate mode: 0"
ie print the literal value 0
so why am i printing out 3?

oh, it's because i made a mistake in my print function

i had this:

    println!(">>> {}", memory[args[0] as usize]);

but it should have been this:

    println!(">>> {}", args[0]);

annnd that fixes it and makes my program no longer crash
lolll

ez!

ok i tidied up

still a few more done to resolve

===

7/15/20

finished up 5b!

DONE how can we associate operations' code more closely with their structs? will traits get involved here?

DONE try out a logging library
    https://fasterthanli.me/articles/getting-in-and-out-of-trouble-with-rust-futures has an example
    pretty_env_log it is

===

7/16/20

took a peek at 6a

idea so far:

* construct a tree from the input
* each node in the tree has a `depth` u32
* walk the tree, sum all the depths

constructing the tree will be interesting though

i think first we'll have to parse each line into a tuple of strings
into a hashmap actually imo!
yeah that's the way to go
and then build the tree based on that hashmap of directional relationships

maybe use a stack along the way while building the tree?

hrm hrm hrm
so a single body can have multiple satellites
but each body can only orbit one thing
so there's like a directionality there in the relationship

constructing a hashmap of {satellite: body} is straightforward enough
but how do you walk through that hashmap in order to construct a tree?

i think i want to make a hashmap of {body: vec_of_satellites}
it'll involve a lot of allocations but it'll work fine

ugh
ok so that's fine
but now making the tree is hard :)

do i even need a separate tree?
can i not just walk this hashmap?

i can walk it :)

===

7/18/20

ok, 6b

so we need to figure out how many "orbit transfers" between us and santa
my plan so far:

parse another map of orbits, keep both

so right now i have an outward-facing map of {body: satellites}
i also want an inward-facing map of {satellite: body}

let's come up with terms for these

lol how about BodyToSatellites and SatelliteToBody?
keep it simple

ok cool, done
so now what?

we use satellite_to_body["SAN"] to figure out where he is
and then so the idea i had the other day was

you have a function that's like

find_path_to(destination_body: &str, origin_body: &str, body_to_satellites: &BodyToSatellites) -> Option<u32>

which returns a number like 5 if it finds a path to origin starting from destination, or none if it doesn't

and so starting at san's current position, you call find_path_to("YOU")
and if it returns Some(u32) you have your answer
and if it doesn't, then you walk up the SatelliteToBody chain until you hit a body that has multiple satellites

maybe it'd be worth having `find_path_to()` also take a, like, "candidates" arg, because we'll know that
"YOU" _definitely isn't_ in the direction that we're _coming from_, and instead find_path_to() should only
be checking paths that involve the _other_ satellites of "origin"

anyway that's the rough idea

let's try to get some of this down into code and see how it looks

i'm gonna skip that "candidates" arg stuff for now
it's a perf optimization and kinda fiddly to get right
can reach for it later if we need it

it worked! didnt need candidates after all :)

ok, looking at 7a
to start, we need to come up with the permutations of [0, 1, 2, 3, 4]
gonna go with itertools .permutations()

ok cool that was pretty ez! just fun with iterators and .fold()

ok 7b is gonna be a lot more involved
looks fun!

===

7/19/20

ok let's get into 7b

i've been a bit nervous about it
i'm worried that these little computers are going to need to run in parallel and like have interconnected dependencies
on each other's inputs/outputs
but we'll see!!

"Eventually, the software on the amplifiers will halt after they have
processed the final loop. When this happens, the last output signal from
amplifier E is sent to the thrusters."

having trouble figuring out how to make sense of that

do i need to change the `computer` system so that each program halts temporarily whenever it produces output?
maybe i could have `run_program()` return an enum as part of its return value

right now it returns

(Memory, Output)

but maybe i could change it to return

enum ComputerState {
    Running,
    Halted
}

struct Computer {
    memory: Memory,
    output: Output,
    state: ComputerState
    // XXX ALSO INSTRUCTION POINTER
}

i think that would work.

let me reread the prompt a few more times to make sure i'm interpreting it correctly before i go through all this work

DONE also have `run_program` take some sort of, like, `halt_level` input
that defaults to `EXIT`
but that can also be set to `OUTPUT`

except rust doesn't have default values, o well

ok run_program() is going to need to take a Computer, and computer is going to have a few more fields
eg input and instruction_pointer

and i don't think i want ComputerState to be a part of Computer
instead i think i want `run_program()` to return a tuple of (Computer, halt_reason)

ok cool so
that was a lot of work in refactoring and fixing up preexisting callsites/tests
kind of a pain tbh
but i _think_ i did it right? we'll see

ok i think i have an infinite loop happening
yeah i definitely do
well dang!

how do i debug that??
do i have to read the 7.txt program and figure out why it's behaving this way?

it's kinda long!

ohhhh

ok i think i suspect what the problem is

so i stopped the program a bit early and looked at what the outputs were for each computer
and i noticed that they were repeating - computers 0, 1, 2, 3, 4  always gave the same outputs
and then i added a println() at the start of run_program() showing what the computer's instruction pointer was

and i see this

run_program starting with a computer at instruction_pointer 0
run_program starting with a computer at instruction_pointer 0
run_program starting with a computer at instruction_pointer 0
run_program starting with a computer at instruction_pointer 0
run_program starting with a computer at instruction_pointer 0
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16
run_program starting with a computer at instruction_pointer 16

so! i think the issue here is that i'm not incrementing the instruction pointer
before halting the program when i break early due to an output instruction being hit!!!!

let's try incrementing the instruction pointer and seeing if this infinite loop goes away
it did :)

ok cool so
i messed around with rayon a bit
and then i was like: hey, i wonder if this made a difference?
i had added rayon to days 3 and 7
and it looked initially like maybe there was some difference
but then i set up criterion
and it turned out that it made no difference!!!

so i was like, ok nvm let's look at a flamegraph
and according to the flamegraph, we actually spend the bulk of our time in day 4
specifically, four::write_password_to_buffer()
which, what gives?!

time to reread that function

ok it looks like this

fn write_password_to_buffer(number: i32, buffer: &mut Password) {
    for (i, digit) in number
        .to_string()
        .chars()
        .map(|x| x.to_digit(10).unwrap())
        .enumerate()
    {
        buffer[i] = digit;
    }
}

i'm sure that it's the `.to_string()` part that's the bad part
so, rather than generating numbers in a range, then converting them into strings, then parsing each char as a digit,
then writing that back into a buffer digit by digit

let's do something more direct!

ok so here's the measurements from benchmarking four by itself
[75.454 ms 76.239 ms 77.121 ms]

ok and i finally got my reimplementation working

four                    time:   [5.1523 ms 5.2919 ms 5.4431 ms]
                        change: [-93.248% -93.059% -92.848%] (p = 0.00 < 0.05)
                        Performance has improved.

:)))))))

ninety three percent improvement!!!

sick

so that was interesting
for a while there i was fighting the borrow checker
i originally had

struct PasswordRange<'a> {
    buffer: &'a mut Password,
    upper_bound: u32,
    current_number: u32,
}

and then i was trying to impl Iterator on it
and have .next() return a &Password

but that wasn't working and i couldn't figure it out
but then https://stackoverflow.com/questions/25702909/can-i-write-an-iterator-that-mutates-itself-and-then-yields-a-reference-into-its
was really helpful
basically the idea is that: if i'm returning references to this buffer,
but my calls to .next() are continuing to mutate the buffer,
then that's invalid behavior; .collect() is an interesting example to think about, for instance

so i changed it to

struct PasswordRange {
    upper_bound: u32,
    current_number: u32,
}

and wrote a separte, standalone function that takes a number and writes it to a buffer
so i pulled these two behaviors apart - starting at one number and counting up, vs writing a number to a buffer -
and i ended up with a system that works

incidentally

starting at one number and counting up is what ranges do already
i don't need to implement a separate standalone range struct from scratch
so let's delete that!!!!

okay awesome

all-solutions/all solutions
                        time:   [118.47 ms 122.96 ms 131.50 ms]
                        change: [-51.712% -45.625% -37.691%] (p = 0.00 < 0.05)
                        Performance has improved.

forty five percent of the all-solutions runtime has gone away!!!

super neat

let's play around with what's left

flamegraph shows me that the bulk of what's left is 3a, 3b, and 2b
so let's try rayon!

here's what 3 looks like on the rayon branch
individual              time:   [18.340 ms 18.598 ms 18.885 ms]

and here's master

three                   time:   [14.308 ms 14.395 ms 14.500 ms]

so, rayon didn't help for 3
because i'm a dummy and didn't look at the flame graph closely enough
the stuff i .par_iter()'d wasn't the stuff that was slow
it's wire_intersections() that's slow

so, i'm gonna back out my rayon change from 3

individual              time:   [14.029 ms 14.111 ms 14.215 ms]
                        change: [-25.383% -24.125% -22.950%] (p = 0.00 < 0.05)
                        Performance has improved.

yup!
ok cool

so, how do we speed up wire_intersections?
i'm actually not sure that we can!
i forgot the details of this problem
wire_1 and wire_2 are really long vectors with tons of (x, y) pairs
let's see how long they are

[src/three.rs:44] wire_1.len() = 153537
[src/three.rs:44] wire_2.len() = 149380

yeah, that's a lot of items!
so i think my current implementation is fine
i'm not sure how to solve this problem without representing these wires as super long vectors of (x, y) pairs

ok, so three can't easily be sped up
well then, what else is on the docket?
let's take a look at two

ok, here's two right now
time:   [25.520 ms 26.106 ms 26.768 ms]

let's see if there's a reasonable spot for rayon to fit in
there is :) :) :)

here's the result!

individual              time:   [696.42 us 718.97 us 745.37 us]
                        change: [-97.316% -97.210% -97.074%] (p = 0.00 < 0.05)
                        Performance has improved.

97%!!!!!!!!!!

ok cool sweet
let's merge

ok rad
now let's look at six
maybe make it a bit less recursive
here's six's measurements rn

individual              time:   [14.123 ms 14.231 ms 14.356 ms]

ok, i unrolled the recursion of the outer function, let's see what that did

individual              time:   [16.066 ms 16.829 ms 17.677 ms]
                        change: [+12.401% +18.257% +23.997%] (p = 0.00 < 0.05)
                        Performance has regressed.

hm, not helpful!
let's try unrolling the inner recursion

oh right, this is the problem where i was thinking about marking certain paths as not worth visiting
i think i could probably keep the recursion and just do that marking
bc the recursion is actually a good fit for the algorithm

so, let's do that

it helped a lot! :)

individual              time:   [1.6026 ms 1.6383 ms 1.6801 ms]
                        change: [-90.219% -89.601% -88.953%] (p = 0.00 < 0.05)
                        Performance has improved.

so where are we at on all_solutions rn?

all-solutions/all solutions
                        time:   [84.659 ms 89.329 ms 98.045 ms]
                        change: [-41.600% -29.692% -14.464%] (p = 0.00 < 0.05)
                        Performance has improved.

sick
it looks like i lost some lines in my dev diary from earlier
but i'm 99% positive that earlier i spent some time benchmarking all_solutions and got times
that were hovering right around 240ms

so this is a big improvement!

let's take a look at seven
time:   [8.3632 ms 8.4799 ms 8.6138 ms]

and now let's see it with rayon

individual              time:   [4.7613 ms 5.0371 ms 5.4016 ms]
                        change: [-43.492% -40.600% -35.971%] (p = 0.00 < 0.05)
                        Performance has improved.

3ms isn't much in the grand scheme of things, but 40% is nice!!!!!

===

7/20/20

ok cool

so i was poking around to see if people had suggestions for how to improve 3
and there aren't really any
except - instead of building two hashsets and intersecting them
you can just build one and do lookups on it while walking the other vector
interesting!
let's bench

before:
individual              time:   [15.972 ms 16.531 ms 17.253 ms]

after:
individual              time:   [9.4935 ms 9.8182 ms 10.174 ms]
                        change: [-43.695% -40.607% -37.473%] (p = 0.00 < 0.05)
                        Performance has improved.

all right, not bad!!!

cool, i think that's about as optimized as days 1-7 are gonna get for now
fun times!

DONE lol i don't think i realized that rust has while loops

===

7/22/20

ok cool so 8a was ez

there's a clippy lint firing, telling me i'm counting bytes "the naive way"
here's the timing from doing it the naive way

individual              time:   [46.515 us 46.840 us 47.268 us]

that is obviously plenty, plenty fast
let's try the bytecount crate now

and here's the bytecount version

individual              time:   [39.544 us 39.837 us 40.206 us]

very little difference
i'll still keep the bytecount code for funsies tho

ok nine looks interesting!
relative base is hopefully straightforward
DONE implement the write_arguments() portion of it

DONE:
    The computer's available memory should be much larger than the initial
    program. Memory beyond the initial program starts with the value 0 and can be
    read or written like any other memory.

DONE: (It is invalid to try to access memory at a negative address, though.)

DONE
    The computer should have support for large numbers. Some instructions
    near the beginning of the BOOST program will verify this capability.


let's figure this program out

109,1,204,-1,1001,100,1,100,1008,100,16,101,1006,101,0,99

109, 1
increment relative base by 1

204, -1
output 109

ok cool i ended up figuring out the issue - i hadn't fully implemented relative-base behavior in write_arguments()

DONE - still having an issue with the 9a program in test mode
DONE i think that the issue is my messed-up if-statement at the end of write_arguments
DONE augh revisit that

===

7/23/20

DONE figure out a way to refactor the big match expression in Computer.run()
    sick i did it :)
    really proud of how that worked out
    for a while i thought that i had made it a million times slower
    but it turned out i had forgotten to advance the instruction pointer when halting early after an output instruction
    which is the same mistake i had made when originally implementing that instruction!
    lol oh well anyway
    super cool!!! aaa i'm really pleased with how this worked out

i spent like an hour trying to set up codecov on travis but couldn't get it working
it kept saying "no coverage found"
oh well! who cares

eh screw it, let's try github actions
gave up on codecov there too
too complicated to set up

ok so i'm looking at 10a
interesting setup!

it looks like the idea is:
in a grid with width W and height H

for any given asteroidal point in the grid
cast rays from that asteroid in all directions until you find an intersection
not just along horizontal/vertical, not just on diagonal
but instead, loop through all the possible slopes

so let's say we have an 8x9 grid and we're at (4, 4)

........
........
........
........
....X..a
.......b
.......c
.......d
.......e


then we look at each outermost element in the grid, one by one
    DONE i'll want a vec of their coordinates
and for each one, we'll calculate its slope
    DONE how do we reduce slopes?
        eg we want (1, 0) instead of (3, 0)
        there's a gcd crate
        and the gcd of 0 and k is k

so for instance, a above would have a slope of (1, 0)
b would have a slope of (3, 1)
c would have a slope of (3, 2)
d woul dhave a slope of (3, 3) which gets reduced to (1, 1)
etc

and so we end up with an asteroid at position (x, y)
and a SET of slopes
    DONE: note - not a list!
    DONE figure out how to use the set as a reusable buffer

and for each slope,
    for i in 0..,
        let xx = x + (slope.0 * i);
        let yy = y + (slope.1 * i);
        if (xx, yy) is off the grid:
            break
        else:
            if grid.get(xx, yy) == Spot::ASTEROID:
                asteroids_seen += 1

we could probably turn the above into iterators by using takewhile or something

ok cool so i've made some progress
not quite there yet, but progress

so right now i'm running into this issue
on this map

.#..#
.....
#####
....#
...##

the top right asteroid, at (4, 0)
is only reporting 6 asteroids

it's reporting these:

found asteroid at 1, 0
found asteroid at 2, 2
found asteroid at 3, 2
found asteroid at 3, 4
found asteroid at 4, 2
found asteroid at 0, 2

so now, by hand, let's figure out which ones it should see

.#..X
.....
#####
.....
...#.

shit dude, fuck me
i don't think that my slope idea is actually going to work

how would i describe the algorithm that seems to be necessary here?
how do i implement this in less than n^n time???
hm hm hm

maybe this slope thing is salvageable

which asteroid isn't being found?
it's the one at (1, 2)

what's the (delta_x, delta_y) between (4, 0) and (1, 2)?
it's (-3, 2)

and so there's seriously no border position with that slope?
yeah there isn't
so how do we know to check for that slope?
    DONE figure this out

here's an idea
for each asteroid
    let mut num_seen = 0;

    make a sorted set of all of the other asteroids' (x, y) positions, sorted by distance from asteroid ascending
        DONE do we have those? or maybe a heap or something?
        NOTE - (clone a previous set and sort it, or something)
            update: actually just use a vec buffer
                clone it at the start of this cycle
                sort it by distance
                and then at each step of the way, use .retain() on it
    while the set is non-empty:
        let sub_asteroid = sorted_set.pop_smallest();
        num_seen += 1;
        calculate the (delta_x, delta_y) between asteroid and sub_asteroid
        for each point from asteroid, along (delta_x, delta_y), stopping at the end of the grid:
            remove that point from the sorted set (if it's in there)

ok i think that could work!!!!!

===

7/24/20

ok let's try it

ok i don't think retain is going to be helpful for the ray-casting part
i think i should just reuse my iterator approach from earlier

ok so i got the approach down into code
but it's reporting too many asteroids

DONE add prints showing what we see from (4, 0)

ok so from 4, 0 we see:

2, 0
2, 1
4, 3
2, 2
4, 4
0, 1
2, 3
3, 4
2, 4

cross-referencing that against the map:

.#..#
.....
#####
....#
...##

so here are the ones that i see in there that shouldn't be in there

4, 3
4, 4

ok i see why, calculated the slope's too coarse, i didn't shorten it to (0, -1)

DONE bring back gcd for slope simplification

ok, here's where we're at now

from 4, 0
found asteroid at 2, 0
using slope -1, 0
dropping asteroid at 2, 0
found asteroid at 2, 1
using slope -2, 1
dropping asteroid at 2, 1
found asteroid at 4, 3
using slope 0, 1
dropping asteroid at 4, 3
dropping asteroid at 4, 4
found asteroid at 2, 2
using slope -1, 1
dropping asteroid at 2, 2
dropping asteroid at 0, 4
found asteroid at 0, 1
using slope -4, 1
dropping asteroid at 0, 1
found asteroid at 2, 3
using slope -2, 3
dropping asteroid at 2, 3
found asteroid at 3, 4
using slope -1, 4
dropping asteroid at 3, 4
found asteroid at 2, 4
using slope -1, 2
dropping asteroid at 2, 4
8

why isn't there an asteroid at (4, 2) in there???

&grid.asteroid_positions = [ ( 0, 1,), ( 0, 4,), ( 2, 0,), ( 2, 1,), ( 2, 2,), ( 2, 3,), ( 2, 4,), ( 3, 4,), ( 4, 3,), ( 4, 4,), ]
lol fuck me
i got my x and y mixed up when making asteroid_positions

ok sweet, fixed
progress!

done!
and original running time was ~65ms
added rayon, running time is now ~35ms
nice! :)

ok
so part 2 looks interesting
going to be a bit tricky i think
maybe
maybe not?
maybe

so, we place a monitoring station at 20, 20, bc that's the location from part a

and then we assemble the list of asteroids
and then we... what?
we're definitely going to be doing rounds of sorting and iteration

and we're definitely going to be finding angles between two points
it looks like atan2 is what i want for that

here's some code from messing around on rust playground

    let y: f32 = 3.0;
    let x: f32 = 3.0;

    dbg!(y.atan2(x));
    dbg!(y.atan2(x).to_degrees());

[src/main.rs:5] y.atan2(x) = 0.7853982
[src/main.rs:6] y.atan2(x).to_degrees() = 45.0

"The laser starts by pointing up and always rotates clockwise"

    let y: f32 = 3.0;
    let x: f32 = 0.0;

[src/main.rs:5] y.atan2(x) = 1.5707964
[src/main.rs:6] y.atan2(x).to_degrees() = 90.0

    let y: f32 = 3.0;
    let x: f32 = 0.0;

[src/main.rs:5] y.atan2(x) = 1.8925469
[src/main.rs:6] y.atan2(x).to_degrees() = 108.43495

    let y: f32 = 0.0;
    let x: f32 = -1.0;

[src/main.rs:5] y.atan2(x) = 3.1415927
[src/main.rs:6] y.atan2(x).to_degrees() = 180.0

ok cool so
i messed around on my notepad
and with rust playground
and have found that this formula is what we want:

fn rotate(x: f64) -> f64 {
    PI / 2.0 - x
}

rotate(y.atan2(x)).to_degrees()

which we should be able to turn into a nice `angle()` fn very easily

ok here's what i came up with

fn angle(x: i32, y: i32) -> f64 {
    let base_angle = ((PI / 2.0) - (y as f64).atan2(x as f64)).to_degrees();

    if base_angle < 0.0 {
        base_angle + 360.0
    } else {
        base_angle
    }
}

had to transform negative angles
anywayyyyyy

now we can make a nice ordered vec of buckets (DONE vecdeques for buckets?)
and just visit them in order, popping off the first item from each bucket if it still exists

ok i think the way to do this is to first transform the vec of asteroids into a vec of ((x, y), angle) tuples

ok cool
so i did that and got some stuff running
it's not quite right though
i think that my main logic is functional
but that my angle functions are effed because i'm bad at unit circles

===

7/25/20

so i ended up finishing 10b! it was fun once i got past unit circles
got to learn about how to use group_by, neato

but so
i benchmarked 10b, and it's really fast
and i was like wow!
so then i was like, what if i rewrite 10a using the implementation of 10b?

so, here's 10a before

individual              time:   [57.191 ms 57.640 ms 58.136 ms]
and here it is after!!!

individual              time:   [11.160 ms 11.222 ms 11.299 ms]
                        change: [-74.311% -73.880% -73.505%] (p = 0.00 < 0.05)
                        Performance has improved.

and i got to delete some code too!!!
so that is awesome
hooray!

ok actually so i had a further idea - just reuse 10b but without actually allocating vecdeques for all the grouped chunks
instead just group asteroids by angle and then return the number of unique angles seen
messed around for a bit and got something working
again, here's before

individual              time:   [43.432 ms 44.244 ms 45.242 ms]

and here's after

individual              time:   [2.9618 ms 3.1129 ms 3.2753 ms]
                        change: [-93.331% -92.964% -92.580%] (p = 0.00 < 0.05)
                        Performance has improved.

93 percent is good!!!

ok cool
let's look at day 11

"You'll need to build a new emergency hull painting robot. The robot needs to:
    * be able to move around on the grid of square panels on the side of your ship,
    * detect the color of its current panel,
    * and paint its current panel black or white.
(All of the panels are currently black.)"

this sounds a whole lot like karel

"The Intcode program will serve as the brain of the robot. The program uses
input instructions to access the robot's camera: provide 0 if the robot is
over a black panel or 1 if the robot is over a white panel."

makes sense - at first i was expecting special instructions, but input/output makes a lot more sense
bc my computer is supposed to be general purpose after all!

"Then, the program will output two values:

    * First, it will output a value indicating the color to paint the panel the
    robot is over: 0 means to paint the panel black, and 1 means to paint the
    panel white.

    * Second, it will output a value indicating the direction the
    robot should turn: 0 means it should turn left 90 degrees, and 1 means it
    should turn right 90 degrees."

"After the robot turns, it should always move forward exactly one panel. The robot starts facing up."

ok cool, sounds fun so far
i don't see anything talking about how big the grid is
so i think that rather than having a 2d vec or a long 1d vec, i should just do the thing i usually do in this situation,
i.e. store a vec of visited (i32, i32) positions

ok so the robot has a Direction
and a Position

hm
i may actually want to store a hashmap of <(i32, i32), Color>

ok cool
this sounds easy+fun so far
let's get to it

ok cool, that was fun!
here's the timings from my initial implementation:

individual              time:   [31.314 ms 31.395 ms 31.484 ms]
let's flamegraph it

ok cool, interesting
so i spend the bulk of my time in computer::load_operations()
let's see if we can cache operations on Computer

that's kind of interesting
it's easy enough mechanically at first
but then i run into issues about ownership/borrowing
if i borrow self.operations[foo] immutably, i can't mutably borrow self afterward to do operation.run(self)

hm hm hm
what to do?

i think that putting `.operations` on Computer is a no-go
what if instead, Computer has a State sub-struct

ok that worked
computer's api is kinda gross rn, because all of my programs reach into its state to manipulate its input and output
DONE fix that up

but so anyway here's 11a's perf!

individual              time:   [8.0179 ms 8.0820 ms 8.1640 ms]
                        change: [-74.488% -74.257% -73.963%] (p = 0.00 < 0.05)
                        Performance has improved.

let's flamegraph it and see what's up

what if load_operations() returned a vec instead of a hashmap?
gives me about a 10% perf boost in Computer.run(), neat

===

7/26/20

ok so i was reading chapter 20 of the rust book
and i noticed that they were using arrays as buffers instead of using vecs as buffers
and i remembered that in my flamegraph for 11, i saw some mysterious allocations
and i remembered that i use vecs as my buffers for parameter modes and args
so i was like: let's switch em to arrays instead of vecs!

individual              time:   [2.0650 ms 2.0730 ms 2.0830 ms]
                        change: [-67.767% -67.487% -67.238%] (p = 0.00 < 0.05)
                        Performance has improved.

:)))))))

ok so then i sat down to try out lazy_static

it looked pretty easy:

lazy_static! {
    static ref OPERATIONS: Vec<Option<Operation>> = load_operations();
}

but it turns out that everything in a lazy_static needs to be sync:

5  | / lazy_static! {
6  | |     static ref OPERATIONS: Vec<Option<Operation>> = load_operations();
7  | | }
   | |_^ `(dyn for<'r, 's> std::ops::Fn(&'r mut computer::State, &'s [i64]) -> computer::operations::Outcome + 'static)` cannot be shared between threads safely

what about this?

https://docs.rs/once_cell/1.4.0/once_cell/

i poked around with it and found that it didn't help my perf

before:
all-solutions/all solutions
                        time:   [72.607 ms 73.619 ms 75.475 ms]

after:
all-solutions/all solutions
                        time:   [85.469 ms 86.728 ms 88.533 ms]
                        change: [+12.896% +16.331% +19.638%] (p = 0.00 < 0.05)

relevant diff:
-pub(crate) fn load_operations() -> Vec<Option<Operation>> {
+fn initialize_operations() -> Vec<Option<Operation>> {
     let mut operations = Vec::with_capacity(100);
     for _ in 0..100 {
         operations.push(None);
@@ -151,3 +152,8 @@ pub(crate) fn load_operations() -> Vec<Option<Operation>> {

     operations
 }
+
+#[allow(clippy::redundant_closure)]
+pub(crate) fn load_operations() -> Lazy<Vec<Option<Operation>>> {
+    Lazy::new(|| initialize_operations())
+}

i think that this once_cell thing could be useful in situations where:
* i have things that can actually be static vars (i.e. things that don't contain closures), or
* i have things that require tons of heavy computation and can then be cached

but it doesn't seem like it's a good fit for this particular situation, i.e. one where
i just want to cache a small vec in order to avoid allocating

oh well!

ok i read the rust book's macro chapter online
and also finished rereading the physical textbook :)
and i poked around to see future stuff - i was curious to see if there'll be a 2021 edition,
https://internals.rust-lang.org/t/2021-edition/12153/70 looks like the answer is no! which i think is prob correct
ok let's poke around with code coverage one more time

https://github.com/mun-lang/mun/pull/100

ok sick that was actually really easy
the only step i was missing last time i tried was that i didn't see there was a tarpaulin github action
and so all i needed to do was add it, and add the codecov action,
and now i have https://codecov.io/gh/jrheard/advent_2019

neat!

ok
day 12 looks interesting

the input looks like this

<x=-1, y=0, z=2>
<x=2, y=-10, z=-7>
<x=4, y=-8, z=8>
<x=3, y=5, z=-1>

let's parse it with a regex

gravity is interesting, it's basically
    for each moon:
        for each other moon:
            moon.velocity.x += if moon.x > other_moon.x {-1} else {1} // except 0 if they're the same, so match on cmp


ok cool
so, gravity done
DONE velocity
DONE wrapper function that applies gravity and then velocity

DONE calculate energy
and that's 12a down!

ok 12b is interesting
initial implementation was ez
but it's too slow - the problem takes a million steps to conclude
they say "Clearly, you might need to find a more efficient way to simulate the universe."

so uh
how?
???????

ok i looked up a hint for this one bc i just wasn't going to get it
people are talking about how you can compute x, y, and z separately
let's look at that i guess

ok ya that works - the idea is that you find out how long til x repeats, then y, then z, and get their lcm
i don't think i would have thought of that :[
o well!

12b is about 20ms, can't see any way to optimize it, nbd - the whole point of it was that it's slow

ok cool let's do 13a
13a was ez
hopefully b is more interesting!
it is :)

ok so
first, we initialize the whole screen
after that, it looks like it sends down instructions like:
(old_paddle_x, old_paddle_x) 0
(new_paddle_x, new_paddle_x) 3
(old_ball_x, old_ball_x) 0
(new_ball_x, new_ball_x) 4

ok cool done nice
i think i could improve its perf by speeding up the is-the-game-over check
maybe have a hashset of block positions

took a peek at 14a
initial intuition: i think the idea is going to be to work backward, recursively, one step at a time
what's the cheapest way to get 1 fuel?
    it's 7 LCSV, 1 LKPNB, 36 CMNH, 1 JZXPH, 20 DGJPN, 3 WDWB, 69 DXJKC, 3 WHJKH, 18 XSGP, 22 CGZL, 2 BNVB, 57 PNSD
and what's the cheapest way to get that?
    it's god knows what

recursive steps ad infinitum

so maybe some sort of hashmap of {chemical -> vec<chemical>}, mapping output to inputs

ok so i worked on 14a for a bit
and i'm having fun
but my initial approach isn't working

it's coming up with this:

&merged_leaf_costs = [
    RecipeComponent {
        chemical: "A",
        quantity: 4,
    },
    RecipeComponent {
        chemical: "B",
        quantity: 9,
    },
    RecipeComponent {
        chemical: "C",
        quantity: 11,
    },
]

when it should be this:

Consume 45 ORE to produce 10 A.
Consume 64 ORE to produce 24 B.
Consume 56 ORE to produce 40 C.
Consume 6 A, 8 B to produce 2 AB.
Consume 15 B, 21 C to produce 3 BC.
Consume 16 C, 4 A to produce 4 CA.
Consume 2 AB, 3 BC, 4 CA to produce 1 FUEL.

how do i investigate this?

i think i should start by adding more printing to stage 1

ok so i made some progress
but i think that i'm running into issues where i'm reacting a mid-level ingredient too soon
gotta think about this some more

also my names are bad, but i'll fix em later

===
7/28/20

ideas i've had so far:
* walk the tree as a first pass, to see which chemicals show up at which level
    * (not sure how this helps)
* do one entire pass on the recipe, record all the components that went into `component_costs()`,
    and then somehow coalesce them and do a second smarter+cheaper pass
        not sure how to avoid double-counting components tho - this is why i think i need to know about levels

gonna work out 14_sample_2 by hand first and compare it against what my program is doing
yeah the issue is definitely that i'm just not doing the most efficient possible bulk buys

i feel like those two ideas above could work together to get me through this
but i just don't have like a totally firm grasp on what i have in mind
think think think

i'm not sure if the levels thing is necessary
let's try the record-and-do-second-pass thing

ok so at this point i have a hashmap that's tracking the things that were inefficiently bulk-bought
but i'm not sure what to do with it

maybe directly representing recipes as individual components, and swapping out bigger ones for littler ones,
isn't quite the right way to do this

maybe instead i need to be representing recipes as trees
and merging nodes together
what would that look like?

a Node would be like

{
    chemical: String,
    quantity: u32,
    children: Vec<Node>
}

ok

so, the first thing we do is do a full pass where we naively fill the tree out
and then we do series of followup passes where we merge same-chemical nodes together, discarding their children
until there's no more merging to be done

i think that that recursion is gonna be kinda tricky to get right

the first part with the full pass should be easy though, so let's start there

ok cool, i got some code down that does the first pass really easy
but so now the merging pass, i think that's going to be tricky to figure out
it should be ok to express once i figure out how to do it
i just need to figure out how to do it!

i'm pleased with how the first pass came out tho, that was p ez

ok lol this is devolving rapidly
so i have another approach, and it solves 14_sample_2
but it's hideous, because i don't know how to do trees in rust
and it fails on the actual puzzle input

DONE try it on one of the other samples i haven't downloaded yet
DONE figure out how to clean it up
    it's so bad

DONE try out #[cfg(not(tarpaulin_include))] to hide 13's unused draw function from codecov

DONE also track depth first seen in the initial tree
and then walk the chemicals in that order

===

7/29/20

ok uh hm
what to do
i think i need to do two things:

1) implement IntoIter for fun
2) start this whole problem over again from scratch

let's do 1 first :)

ok holy cow after a lot of flailing i think i did it!
turned out the trick was to use a vecdeque, neat

ok cool
uh next up i wanna do 1.5:
track the depth in the tree at which bulk-buy chemicals first appear
ok that didn't help, oh well

okay, so, let's take a step back and look at the problem statement again from scratch
    DONE i think maybe i could salvage this by just tuning my sorting of bulk-buy chemicals
        yes indeed :))))))

ok! 14b is pretty interesting
it's a different approach
you need to "run" these recipes now

i need to make a struct that has a bank of chemicals and buys more as needed

so the interesting question is
do i give it the naive tree?
or my fancy collapsed tree?
i think i give it my fancy collapsed tree

no, never mind, bc my collapsed tree no longer resembles the input tree due to all my collapsing
i think i have to use the original recipes hashmap

ok i'm pretty stumped on 14b
i poked around online
one thing i saw was that peoples' 14a solutions tended to do a single pass and just keep track of leftover chemicals as you go
that seems like a good idea
let's play around with that and see if it simplifies things for 14a
lol whatever
i played around with it a bit but like
i already spent enough time on 14a
let's move on

oh, i see
it took me a while to understand what people were doing
so right now, i have a function that computes the amount of ore required for 1 fuel
what they're doing is, they're calling that function with different inputs
until they find the largest input whose output is less than one trillion

that's cool, that's cool
but so
i have no idea whether or not my solution will actually work in this scneario
guess we'll find out!!!!

i don't think my 14a solutoin is going to work here
i think i need to go with the shopping cart solution that everyone else did
ugh
i have enjoyed this problem less than i had hoped :(
at least i got to learn fun tree+iter things
it just sucks to try a ton of different solutions and have them all fail
oh well!!!!

===

7/30/20

ok i did 14a+b over from scratch with the shopping cart queue approach
and at long last it works!
so i will take it.

taking a peek at 15a
looks fun!

i expect that the general idea is going to be to go straight until you hit a wall,
then hug the wall, always turning left wherever possible (unless you reach a dead end and have to turn around)
and in this way you can map out all the walls (hopefully)
and once you've done that, perhaps you can do some sort of pathfinding + flood fill operation to explore the rest

so i think there are gonna be two passes here

1) explore the whole zone until you find the oxygen system
2) starting over from scratch, and armed with the filled-out map from step 1, what's the shortest path to the oxygen system

DONE i'm probably gonna want to make some sort of print_map() function

okay, so we make a robot
and we load the program and make a Computer

the program takes an input, a number between 1-4:
    "Only four movement commands are understood: north (1), south (2), west (3), and east (4)."

and then it returns a number as output:

    "The repair droid can reply with any of the following status codes:
    - 0: The repair droid hit a wall. Its position has not changed.
    - 1: The repair droid has moved one step in the requested direction.
    - 2: The repair droid has moved one step in the requested direction;
        its new position is the location of the oxygen system."

so, again, my plan is to just try to explore the whole level
and i was thinking about doing that in two phases
how do i know when phase one is over?
a naive answer would be that it's over if you return to the place where you started
i don't like that tho, bc what if you go down a dead end alley and then come right back

i think phase 1 is over if:
    * you return to where you started, AND
    * all of the spaces around the start position have been explored
        * cardinal directions for now, not diagonals

ok so here's something interesting
my robot immediately got stuck in this hallway

 . #
#R..#
 #

it paces back and forth between these two corners, because i'm just telling it to turn left every time it hits a wall
that turn-left strategy isn't about when you _hit_ a wall, it's about when you're able to _see_ and _hug_ a wall
let's come up with something better

ok cool so the alg is actually really easy
if you hit a wall: turn left
otherwise: turn right
ezpz
thankfully, there aren't any open spaces in this level, it's all just corridors
so my robot finds the goal!!!!

next up: pathfinding

i think that the right approach here would be:
give the robot a distance_from_origin map
with Position keys and u32 values
and maybe also give him a .last_position

hrm
hrm hrm hrm
i'm not sure if that's actually a thing
hrm
what if instead i just explore the whole level and _then_ do a flood fill _myself_, without the robot??
let's see if i can explore the whole level

ok yeah i totally can, it immediately exits in about 3100 steps

what if i modified print_map fn to use flood_fill numbers too?
hrm, nvm, that wouldn't work bc flood_fill numbers will obviously be larger than one tile!!

===

7/31/20

ok fft time
bit apprehensive

ok sick, i got 16a working, lots of fun with iterators
pretty slow tho!

is it possible to automatically skip the elements corresponding to zeroes in the pattern?

DONE rewrite inner part of one_pass fn to be a loop instead of an iterator

here's what perf looks like right now for 16a
individual              time:   [114.04 ms 116.19 ms 118.87 ms]

ok i rewrote it to skip zeroes and it made a perf difference!!

individual              time:   [73.766 ms 74.364 ms 74.955 ms]
                        change: [-37.507% -35.999% -34.663%] (p = 0.00 < 0.05)
                        Performance has improved.

also: i immediately discovered that the loop code was going to be super shitty, so i was able
to easily adapt the iterator code and it totally worked!
hooray iterators! hooray funcitonal programming!

===

8/1/20

ok so i'm watching https://www.youtube.com/watch?v=spUNpyF58BY
about the fft
and the main idea appears to be:
the transform of a summed list of frequencies
is equal to the sum of the individual transformed frequencies

i'm pretty cofident that there's gotta be a direct relation to this problem
i'm now realizing that the whole "pattern" thing - the -1, 0, 1, 0 - is directly analogous to frequencies

what i haven't figured out yet is, precisely how does this apply to the problem at hand?
maybe parallelism can happen here? seems kinda nutty to spin off ten million little rayon threadlets tho
i haven't gotten to the part of the video where he explains the fft itself yet tho, gonna keep watching

ok he didn't really, this is just the ft
fine
so i'm watching https://www.youtube.com/watch?v=nl9TZanwbBk , the dft
he's saying that the idea is
you take a bunch of samples of a function at times x1, x2, ...xn
and so those samples are called f1, f2, ...fn
and somehow you're going to be able to compute a series of values
f1^, f2^, ..fn^
where each of _those_ values indicates the extent to which the frequency corresponding
to that position - 1, 2, ...n - was present in your series of values

this sounds scary and is making my head hurt a little but i think that actually it's maybe not scary at all
ok cool let's keep going

ok so i'm in https://www.youtube.com/watch?v=E8HeD-MUrjY
he says that the dft is o(n^2), that's what i've got so far
and he says that the fft is o(nlogn)
which, cool! awesome!

ok whatever
i ended up getting hints via reddit
here's the initial runtime of 16b

individual         time:   [3.9024 s 3.9745 s 4.0650 s]

here's what happens if i chop off the first half of the string

time:   [1.7887 s 1.8765 s 1.9292 s]

50% speedup as expected, good!

omg i ran a flamegraph and half of our time is in vec extend allocation
let's put a with_capacity or two somewhere

ok nvm the easier thing to do is to just rewrite the fft-one-phase fn as something that mutates the vec in-place
just a manual forloop
that gives us:

individual/individual   time:   [337.67 ms 338.62 ms 339.63 ms]
                        change: [-82.455% -81.954% -81.066%] (p = 0.00 < 0.05)

not bad!!
let's look at the flamegraph now
ok i think that's about as good as it's gonna get
>10x speedup ain't bad!

ok cool so
started on 17a
straightforward so far
i've written a function that loads the ship map and robot
but i think there's something wrong with it, bc it has diagonal lines sometimes
i bet it has to do with the line that makes the robot
ok yeah i had forgotten to push a scaffold spot on when i encounter the robot, cool

ok so next up is gonna be detecting the locations of all of the intersections
a position is at an intersection if three or more of its cardinal-direction neighbors are scaffolds
eg

 #
###

 #
##
 #

#
##
#

etc

hrm
i could do this in a few different ways
at first i was gonna write a neighbors-for-position function
but - given that we're going to have a robot that points in different directions and walks across these scaffolds
i think that it might be appropriate to walk these scaffold lines in a directional way
that way my intersection-finding code will be somewhat "linear" :)

ok so the robot starts at the end of a scaffold and is facing in a correct direction
so let's just try implementing a robot.walk_forward() function

DONE how we know when we've reached the end?
i guess we could have an unvisited_scaffolds set of positions

ok also lol
we need to figure out how to keep the robot from just turning around back and forth forever
ok ez
17a done!

17b looks pretty nutty!!!!

DONE 1. accumulate a master vec of of (Turn, distance) tuples that describes the path from the start to the finish
DONE break it into a long chained iterator of windows of size 2..<something reasonable  like 6>
DONE build a hashmap of <path_window -> occurrences>
DONE turn that into a vec of (window, occurrences) tuples, sort by (occurrences * window_size) descending
DONE print out the top 5-10 or something

then after that i'll write tests to demonstrate that i have code that can find these commonly-occurring windowss

NOTE i can _only_ use a, b, and c in my main movement code!!!!!!!!
so DONE i think i'm gonna have to write a function that takes three path_windows
and tries to paint the whole path with them, returning true if it's possible, false otherwise

ok, let's start

DONE catch up

ok so i've gotten most of the above working

NOTE: there are only 34 (turn, distance) segments in the whole path

===

8/2/20

ok let's get back to it
so itertools .combinations() is going to be what i want here

ok cool so i worked for a while and got stuff working!
i figured out how to paint the path, and how to figure out which functions to choose for a, b, and c
but now i'm not getting the results i want from the computer
i've been poking and prodding at it
i'm hoping that the problem is just that my input-feeding code isn't quite right
and it sure looks like that's true

[src/seventeen.rs:401] str = "A,A,B,C,B,C,B,C,B,A\nR,:,L,<,R,6\nR,6,R,:,R,<,R,6\nR,:,L,<,L,<\nn\n"

those distances are obviously incorrect
oh, i see!!!!
if a distance is eg 12, it needs to be represented by two different ascii chars

ok sick it works :) :) :)

DONE clean 17b the heck up!!

ok 18a looks really fun :)

vague ideas:
* dependency graph
* flow field / precomputed distances

...hrm
maybe that's overcomplicating things
maybe not

they give this example:

########################
#f.D.E.e.............@.#
######################.#
#d.....................#
########################

you could pick up `e` because it's closer
but `d` will be faster in the long run!

ok so like
this is pretty interesting
how can my program know that d will be faster in the long run?

so, we know that we have to get to f
    and we know that doors D and E are in the way of f
    and right now, keys d and e are available to us

    it seems to me like we need to fully plan out the route in advance somehow
    like, recursively try both branches and compare them

    that might be the main idea here

so to recap
whenever we reach a decision point, i.e. a situation where we have multiple keys available to us
then we try each option, run the simulation from there, and go with the option that ends up in the cheapest overall result

some more detail:
    * at each step, we can do a flood fill to compute everything's distance from us
    * each recursive path keeps track of the distance traveled along it so far
    * each recursive path ends if keys is empty
    * DONE if a recursive path bails, we'll have to put the correpsonding key/door back where it was!!

enums:
    spot
        wall
        empty
        door
    direction
        north
        south
        east
        west

type Position = (usize, usize)

structs:
    vault
        keys: hashmap<char, Position>
        doors: hashmap<char, Position>
        map: Vec<spot>

whenever we pick up a key:
    * we remove it from keys
    * we remove the door from doors
    * we turn the coresponding `vault.map` entry from a `door` into an `empty`

ok cool
so, i got the basics working
right now my solution's too slow tho
also it was buggy for a bit but i fixed the bug - my mistake was that i forgot to put (player.position, 0)
in the flood-fill distances map before running the flood fill. whoops!

okay, so yeah my solution is definitely way too slow
bc in the worst case it's o(n!)
and 26! is 4.0329146e+26
so, not a chance :)

let's try some other stuff
i looked at reddit for hints

one random post i saw:
"My basic idea was to precompute the way from the start and all possible keys
to each other key and store the length and needed keys to pass doors in the way."

interesting idea!

DONE keep a mutable buffer of path_so_far, and print it out to the screen whenever we bottom out
so it prints stuff like `126: [('a', 25), ('e', 2), etc]`

ok so i have 18a somewhat working again
still way too slow though
DONE what can be cached??

find_shortest_path looks like this

fn find_shortest_path(
    key_distances: &HashMap<char, HashMap<char, (u32, HashSet<char>)>>,
    keys_left: &mut HashSet<char>,
    doors_opened: &mut HashSet<char>,
    key: char,
    distance_so_far: u32,
) -> u32 {

if keys_left and doors_opened were bitfields,
then we could add a cache arg like...
what exactly?

===

8/4/20

well, let's try the bitfield thing just for fun anyway

ok cool so i got bitfields working
now what can i cache, and where?

DONE i'm not automatically tracking keys that you get for free by walking _through_ stuff

ok now i'm tracking that
but it doesn't look like my tracking logic is getting used correctly
ok i think it is now


===

8/5/20


#################
#i.G..c...e..H.p#
########.########
#j.A..b...f..D.o#
########@########
#k.E..a...g..B.n#
########.########
#l.F..d...h..C.m#
#################

[('a', 3), ('g', 4), ('h', 6), ('d', 4), ('f', 8), ('b', 4), ('j', 5), ('c',
11), ('e', 4), ('p', 5), ('i', 14), ('o', 16), ('k', 16), ('n', 14), ('l',
16), ('m', 14)]

why c, e, p, i?
why not c, i, e, p?

hrm
i want to just toss my code and start over
i'll keep the outer stuff but nuke the inner stuff

seen on reddit:

    There is one very important way to prune nodes, by noticing that some of them
    are actually the same node. For example, if you collect a,b,c,d (and end up
    in location of key d), your state is exactly the same as if you collected
    b,c,a,d - so really, only the last key collected matters for the node; this
    makes the search space orders of magnitude smaller. This was actually the
    only optimization I needed to make my Dijkstra implementation in Python find
    the result in under 10 seconds.

        I think you mean the order of the previous collected keys doesn't matter.
        Because the a,c is the same as b,c which isn't actually true

hrggggggg

ok i did it :)

===

8/7/20

let's look at 18b

hopefully the main difference is just that:
* i'll need to parse the file into four different vaults
* i'll need to floodfill each vault separately
* i'll need to adapt the main search alg to use the four floodfill maps instead of a single one

let's start with the first
what's the sanest way to parse the file into four vaults

ok, looks like i got my four vaults
and my four floodfills
now, to adapt the search alg

DONE i'm partway through doing that but it's total trash atm
i need to sit down and actually think about it

ok so let's sit and think
at the start of the search, we seed the queue
which means - starting at each @,
we add a

    queue.push_back(SearchNode {
        distance: *distance,
        key: other_key,
        keys_acquired: Bitfield(keys_along_the_way.0 | other_key.0),
        keys_left: Bitfield(keys_to_find.0 - other_key.0 - keys_along_the_way.0),
    });

for each door that's reachable from @ without requiring any doors.
this seems sane so far.

then, the main search loop begins.
while the queue isn't empty, we pop the first item off.
we record a shortest path if we're out of keys to get.
we also do some continues to bail early if we're on a known-non-optimal path.

next, we loop over each of the four key-distance maps.
if the key-distance map doesn't contain the current key that we're at, we skip this map
if it _does_, then:
    for each other key reachable from the current search node's key:
        if we need that key and have all the necessary doors opened:
            we do
                queue.push_back(SearchNode {
                    distance: distance + distance_to_other_key,
                    key: other_key,
                    keys_acquired: Bitfield(
                        keys_acquired.0 | keys_along_the_way.0 | other_key.0,
                    ),
                    keys_left: Bitfield(
                        keys_left.0 - (keys_left.0 & keys_along_the_way.0) - other_key.0,
                    ),
                });

this seems reasonble to me.
but when i ran the alg, it bailed immediately without finding a path, so it must have one or more bugs!
let's add prints that show how far we make it in the search before bailing.

we actually make it decently far:
    let SearchNode {
        distance,
        key,
        keys_acquired,
        keys_left,
    } = queue.pop_front().expect("queue is non-empty");

    println!(
        "{}: {:?}, {:?}, {:?}",
        distance, key, keys_acquired, keys_left
    );

    yields

    16: Key(4), Bitfield(4), Bitfield(67108859)
    46: Key(2048), Bitfield(2048), Bitfield(67106815)
    32: Key(131072), Bitfield(131072), Bitfield(66977791)
    62: Key(4194304), Bitfield(4194304), Bitfield(62914559)
    142: Key(262144), Bitfield(4456448), Bitfield(62652415)
    164: Key(16777216), Bitfield(16777216), Bitfield(50331647)
    212: Key(256), Bitfield(16785664), Bitfield(50323199)
    192: Key(8192), Bitfield(16785408), Bitfield(50323455)
    82: Key(4194304), Bitfield(4325376), Bitfield(62783487)
    162: Key(262144), Bitfield(4587520), Bitfield(62521343)
    112: Key(131072), Bitfield(4325376), Bitfield(62783487)
    142: Key(262144), Bitfield(4456448), Bitfield(62652415)
    272: Key(131072), Bitfield(4587520), Bitfield(62521343)
    212: Key(256), Bitfield(16785664), Bitfield(50323199)
    192: Key(8192), Bitfield(16785408), Bitfield(50323455)
    212: Key(256), Bitfield(16785664), Bitfield(50323199)
    162: Key(262144), Bitfield(4587520), Bitfield(62521343)
    242: Key(262144), Bitfield(4587520), Bitfield(62521343)

i added some more prints

seed: pushing 'd'
seed: pushing 'm'
seed: pushing 'x'
seed: pushing 's'
seed: pushing 't'
seed: pushing 'j'
seed: pushing 'o'
seed: pushing 'z'
16: 'd', Bitfield(4), Bitfield(67108859)
46: 'm', Bitfield(2048), Bitfield(67106815)
62: 'x', Bitfield(4194304), Bitfield(62914559)
pushing 't'
pushing 's'
32: 's', Bitfield(131072), Bitfield(66977791)
pushing 'x'
pushing 't'
142: 't', Bitfield(4456448), Bitfield(62652415)
pushing 's'
212: 'j', Bitfield(16785664), Bitfield(50323199)
192: 'o', Bitfield(16785408), Bitfield(50323455)
pushing 'j'
164: 'z', Bitfield(16777216), Bitfield(50331647)
pushing 'j'
pushing 'o'
142: 't', Bitfield(4456448), Bitfield(62652415)
112: 's', Bitfield(4325376), Bitfield(62783487)
pushing 't'
82: 'x', Bitfield(4325376), Bitfield(62783487)
pushing 't'
162: 't', Bitfield(4587520), Bitfield(62521343)
272: 's', Bitfield(4587520), Bitfield(62521343)
212: 'j', Bitfield(16785664), Bitfield(50323199)
212: 'j', Bitfield(16785664), Bitfield(50323199)
192: 'o', Bitfield(16785408), Bitfield(50323455)
242: 't', Bitfield(4587520), Bitfield(62521343)
162: 't', Bitfield(4587520), Bitfield(62521343)

why isn't it working :)

hrm
we never seem to evaluate a node that isn't in the seeds

hrm hrm hrm
ok i think i see the issue
right now, my SearchNode looks like this

struct SearchNode {
    distance: u32,
    key: Key,
    keys_acquired: Bitfield,
    keys_left: Bitfield,
}

but i think instead it needs to look like this

struct SearchNode {
    distance: u32,
    current_keys: Vec<Key>,
    keys_acquired: Bitfield,
    keys_left: Bitfield,
}

i'm not in love with putting a vec there bc i think it'll cause lots of allocations
bc i'm gonna have to clone the vec a lot
that'll prob be ok for 18b, but i imagine it'll make 18a really bad
we'll see tho

ok it worked :))))
it definitely slowed 18a down
i can deal with that later if i care about it
hopefully i don't care!
anyway 18b down!!!

ok so 19b is interesting
at first i was like, can we just calculate the slopes of the two lines?
but i don't think it's going to be that easy

i think we need to basically walk the beam with two cursors, one on each side of the beam
the nice thing about this approach is that:
if the cursor moves away from the center of the beam and encounters empty space, it doesn't need to walk any farther in that direction
if the cursor moves toward the center of the beam and encounters beam, it doesn't need to walk any farther in that direction

interesting

ok so here's a sketch

#...........
.#..........
..##........
...###......
....###.....
.....####...
......#####.
......######

make two cursors
one hugs the left side of the beam, one hugs the right side of the beam
maybe each one has, like, an x-axis direction, -1 or 1?

and so in order to move one step away from the beam, you inc your y coordinate, and then

    if you're the left cursor:
        if you're now in empty space:
            move right until you're in the beam

    if you're the right cursor:
        if you're now in the beam:
            move right until you're in empty space, then move left one step

so, that algorithm seems pretty simple and like something that should work
how do we know when to stop?

i think i'm on to something here:
    you keep track of each point visited along the two lines in two vecs
    each vec maps y-coordinate to x-coordinate

    and so after stepping both cursors at least 100 (could tune this to be higher i'm sure) times, you could do:
        call the left cursor's position (l_x, l_y)
        let r_x = right_line[l_y - 100];
            if r_x - l_x >= 100 {
                ding ding ding you're done!!
            }

    DONE i don't think you even need to keep track of the left line's coordinates

ok so i got that down but immediately ran into issues - stepping the left cursor never terminated
a println in 19a shows why

0, 0
2, 5
3, 7
3, 8
4, 9
4, 10
4, 11
5, 11
5, 12
5, 13
6, 13
5, 14
6, 14
6, 15
7, 15
6, 16
7, 16
6, 17
7, 17
8, 17
7, 18

early on, the beam is so sparse that it skips some x, y positions!!

hr hrm hrm

ok so i think my cursor-stepping looks ok (haven't 100% confirmed tho)
so i suspect that the bug is in my calculation of when to break

===

8/8/20

ok i got 19b to work!
couple of off-by-ones, fun

it's pretty slow, gonna profile and benchmark
pretty sure it's bc i spend so much time making new computers

ok actually nvm it's reasonably fast in release mode
but even so let's take a quick look

individual/individual   time:   [52.312 ms 58.459 ms 62.067 ms]

yeah, profiling shows that we spend half our time in computer::new
can we instead do some sort of mem::set() shenanigans?

looks like you can just do copy_from_slice() and it does memcpy stuff under the hood

individual/individual   time:   [30.381 ms 30.583 ms 30.880 ms]
                        change: [-48.302% -45.351% -41.956%] (p = 0.00 < 0.05)
                        Performance has improved.

neat!

ok looking at day 20
looks like a straightforward bfs flood fill type approach
i don't think i'll even need to do any sort of precomputing for a, just `return distance` the first time we get to the exit i think?

but parsing this thing looks like it's gonna be a real pain
let's think about what parsing is going to look like

an input is split into lines() on line breaks
so it will have a logical num_lines concept
each line has the same width

so, this donut concept is what makes it tricky to parse

ok i think i'm getting there
so what does a DonutCave look like?

enum Cell {
    Empty, // '.'
    Wall, // '#'
    OffGrid  // ' '
}

while we're parsing the donut cave, we maintain a vec of PartialPortals
a PartialPortal is a tuple of (Position, char)

and whenever we encounter a letter:
    if `partial_portals` contains an element that's one position away from the letter's current position:
        we pop that element off of `partial_portals` and create a Portal
            a Portal looks like (label, position) - also maybe Direction?
            NOTE we'll have to keep track of directionality to make sure that we get labels and positions right
    else:
        we add (current_position, current_letter) to `partial_portals

so by doing this, we assemble a vec of Portals
there will be two Portals per label -
    so eg there'll be an "AB" portal at position (2, 5) and another "AB" portal at position (20, 10) or whatever

once we've gotten all of _that_, we'll end up with a Vec of Cells
and a Vec of Portals

we can then run that vec of Portals through some sort of `combine_portals()` function
that outputs a Dict of {Position -> Position}

struct DonutCave {
    cells: Vec<Cell>
    portals: HashMap<Position, Position>
}

ya i think something like that would do the trick!!

DONE NOTE: AA and ZZ are special cases
TODO use a binaryheap, sort by distance

ok urgh
the width thing was too simplistic
it's a donut

ok cool i came up with a match that i think should work
gonna take a break but i think that we've made some progress
i haven't tried to run any of this yet though :)

i _think_ that all i have left before implementing bfs is:
implement portal merging

===

9/9/20

ya, 20a implementation is looking good so far
i put some dbg!()s in my work-in-progress DonutCave::new() and the output looks good

done!

ok, 20b looks interesting
having a little trouble understanding the prompt though

    "When you enter the maze, you are at the outermost level; when at the
    outermost level, only the outer labels AA and ZZ function (as the start and
    end, respectively); all other outer labeled tiles are effectively walls.
    At any other level, AA and ZZ count as walls, but the other outer
    labeled tiles bring you one level outward."

that seems straightforward

ok i think i see

if we're at depth 0, AA and ZZ function but nothing else does
otherwise, AA and ZZ are off limits, portals work fine,
inner portals take you one depth lower, and outer portals take you one depth up

so i think i need to make these modifications:
    DONE * Portals need to have a .kind field whose value is Inner or Outer
    DONE * cave needs to have a .inner_portals field and a .outer_portals field
        DONE * i might need to rewrite/scrap merge_portals
    * i'll need to rewrite the bfs search
        * i'm thinking about just copy-pasting it into another module and modifying it from there

gonna start with those first bits bc they shouldn't interfere with 20a

ok i made some progress but i'm getting a really big answer
i'm not confident that my seen-set logic is totally great
gonna take a look at that next
also, lots of copy pasting :/

ok i'm no longer sure that having a vec of seen sets is the right approach
hrm
although similarly it's hard to imagine a situation where visiting the same position
twice at the same level would actually be helpful

ok sick i rewrote seen-tracking to use a nice little PositionTracker struct
and that cleaned the code up nicely
and in the process it fixed whatever bug existed! probably a -1 instead of a +1 or something
who knows
anyway radddd that feels good

runs kinda slow tho! let's try it in release mode to confirm
naw, runs fine in release mode, nice :)

let's try enabling lto for funsies
here's the current benchmark of run_all_solutions

individual/individual   time:   [831.95 ms 846.56 ms 861.37 ms]

enabling lto didn't make any difference at all! interesting!
well, i'm glad that my stuff is that fast already

looks like we spend most of our time in 16b
actually 20b has some room for optimization maybe
let's take a look

ok so we spend _tons_ of time in hashmap insert and hashmap make_hash

ok, here's the current 20b baseline

individual/individual   time:   [138.78 ms 139.41 ms 140.11 ms]

what if i get rid of these hashsets and instead have them be flat vecs of booleans

individual/individual   time:   [46.056 ms 46.578 ms 47.406 ms]
                        change: [-66.918% -66.469% -66.039%] (p = 0.00 < 0.05)
                        Performance has improved.

nice :))))))

still i'm seeing hashbrown map make_hash show up in profiles tho
oh, that'll be inner_portals and outer_portals

if i wanted to, i could replace them with a struct whose backing storage is a vec, similar strategy
but i'm comfortable with 46ms for now! 100ms win heck yes

===

8/10/20

ok let's look at 21a

so, first priority is getting a springdroid up and running
how do we interact with this thing?
we feed it a program
and we read an outcome
the outcome is either a Success(u32) or a Death(Vec<String>)

ok cool ez :)
now let's write the program
what characteristics do i want the program to have?

* if there's empty space 4 ahead, DON'T jump
* if there's empty space 1 ahead, DO jump
* if there's empty space 2 ahead, DO jump

so:

// jump if there's a hole in one or both of the next two spaces
NOT B J
NOT A T
OR T J
// let J stay true iff there's ground 4 ahead
AND D J

ok, that didn't work because it caused us to fall in this hole:

.................
.................
@................
#####.#..########

and a jump lets us skip the next three spots

so we need to jump if there's a hole in the next 3 spots
so how about

NOT B J
NOT A T
OR T J
NOT C T
OR T J
AND D J

ok that got us past 21a

now let's do 21b

we have access to registers e-i
here's what our current program does

.................
.................
@................
#####.#.##.######

.................
.................
.@...............
#####.#.##.######

.................
.................
..@..............
#####.#.##.######

.................
...@.............
.................
#####.#.##.######

....@............
.................
.................
#####.#.##.######

.................
.....@...........
.................
#####.#.##.######

.................
.................
......@..........
#####.#.##.######

.................
.................
.................
#####.#@##.######

note that we're capped at 15 lines of program!
ok let's work on it

NOT B J
NOT A T
OR T J
NOT C T
OR T J
AND D J
// new, don't jump if there's a hole 8 away
// [WIP] unless there's also ground 5 away
NOT E T
NOT T T
AND T J
OR H J

ok cool neat i win!

let's peek at 22b

"deal into new stack" sounds like "reverse"

"split at n" sounds like
    if n > 0 {
        let (left, deck) == deck.split_at_mut(n);
        deck.append(left);
    } else {
        let (left, deck) == deck.split_at_mut(deck.len() + n);
        deck.append(left);
    }

"deal with increment n" is interesting
    is it just an easy while loop?

ok so i put something together
it fails on sample 1

oh it was just bc i didn't see that the samples run on decks of 10 cards

ok cool neat

working on the full input now
falls over on this instruction

[src/twenty_two.rs:45] instruction = Cut(
    -7558,
)
thread 'twenty_two::tests::test_solutions' panicked at 'index 18446744073709545065 out of range for slice of length 1007',

overflow error, looks like
oh i didn't put enough zeroes in the deck size

ok 22a done
lol 22b

ok so clearly, realizing an entire deck of this size (119315717514047) and shuffling it this many times (101741582076661)
will be impossible

i'm supposed to keep track of the card in position 2020

so here's the plan
* figure out how to move _just one card_ per the list of shuffling instructions
* get 22a working with that new slimmer code
* run the shuffle 5 times, printing out the card-of-interest's new offset each time, and hope to god there's a pattern
* ideally then we can just do like
    (starting_position + offset_per_shuffle * num_shuffles) % deck.len()

we'll see tho!!

ok so reverse is ez
cut seems ok
dealwithincrement - done but maybe buggy

ok i'm seeing some failing tests, let's dig into em


hm i think this might be the issue

[src/twenty_two.rs:85] instruction = DealWithIncrement(
    7,
)
before: 3
after: 1
[src/twenty_two.rs:85] instruction = DealIntoNewStack
before: 1
after: 9

ok cool fixed it
off-by-one

so i'm trying to run a single shuffle and my deal-with-increment loop is taking forever
bc my 2020 index immediately gets placed at 119314191427817
and, like, looping that many times is too many

so i need to destroy this loop and replace it with multiplications and divisions and mods and stuff after all
oh well!!

===

8/12/20

ok we're looking at 22b
trying to find patterns in deal-with-increment
i think that deal-with-increment only works if the increment has no factors that are divisors of num_cards

let's try out some deals

deal 10 cards

increment 3
0 741 852 963

increment 7
0 369 258 147

increment 9
0 9 8 7 6 5 4 3 2 1

argh

eff this
https://github.com/mstksg/advent-of-code-2019/blob/master/reflections.md#day-22
https://work.njae.me.uk/2020/01/12/advent-of-code-2019-day-22/
https://github.com/Aidiakapi/advent_of_code_2019/blob/master/src/day22.rs

dude FUCK this

ok uh whoops so one thing is that
someone on reddit points out that 22b asks for the number _in position 2020_ at the end
as opposed to asking _what index the card 2020 ends up in_
whoopssssss

https://www.reddit.com/r/adventofcode/comments/ee0rqi/2019_day_22_solutions/

https://www.reddit.com/r/adventofcode/comments/ee0rqi/2019_day_22_solutions/fbnkaju/

    A key observation to make is that every possible deck can be encoded as a
    pair of (first number of the deck, or offset AND difference between two
    adjacent numbers, or increment). ALL numbers here are modulo (cards in
    deck), or MOD. Then, getting the nth number in the sequence can be done
    by calcuating offset + increment * n.

===

8/13/20

ugh
ok

so i'm on board with
    representing the deck as (offset, increment)
    deal into new stack as
        increment *= -1
        offset += increment
    cut n cards as
        offset += increment * n
    deal with offset as
        increment *= inv(n)
            where inv(n) = pow(n, MOD - 2, MOD)
                see https://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method for details on fast

ok and then he says
    Let (offset_diff, increment_mul) be the values of offset and increment
    after one shuffle pass starting from (0, 1). Then, for any (offset,
    increment), applying a single shuffle pass is equivalent to:
        offset += increment * offset_diff
        increment *= increment_mul

ok and so then the final equation is
    increment = pow(increment_mul, n, MOD)
    offset = offset_diff * (1 - pow(increment_mul, iterations, MOD)) * inv(1 - increment_mul)

dude fuck this problem

https://github.com/AxlLind/AdventOfCode2019/blob/master/src/bin/22.rs is the way to go
i'm going to move on with my life

===

8/14/20

ok, looking at 23
it looks potentially fun!

am i gonna be spinning up 50 threads and having them communicate via a shared mutex of some sort?

===

8/15/20

ok so yeah
i'm thinking about putting a vec of 256 vecdeques in a mutex of some kind
if a computer gets a message for computer 4, it does mutex.lock()[4].push(message) or something like that
and a message is a tuple of (x, y)

requiring threads is pretty unusual for aoc so i may be misunderstanding the prompt
but let's try it and see what happens

it'd be interesting to see if async/await is a better fit
i'd guess not tho, bc iirc async/await is good for io-bound situations and threads are fine for cpu-bound

ok so that went about as well as i expected, ie it didn't work

TODO i think i need a different thread whose job it is to directly manipulate the computers' memory
i'm not sure that that's actually possible though bc rust

but basically i think the issue is that each computer enters a
                computer.run(HaltReason::Output);
line without having received an input, and then its loop never circles back around to the start to actually give that input to it

hrm hrm hrm
this is interesting
gonna have to spend some time thinking about this

NO do i make some sort of, like, AsyncComputer
whose .state.input is an Arc<Mutex<Vec<i64>>>??

hrm
what about, like, two different state structs
SyncState and AsyncState
that both implement a shared State trait with a method like .get() or something?
no man i don't like that
i feel like it'll make me touch all the old computer code to turn it into using syncstate

one thing i'm seeing in the solutions thread is adding a NeedsInput halt level
that's def the way to go

ok cool done rad

individual/individual   time:   [23.927 ms 74.199 ms 110.02 ms]
i wonder if we even need threads for this

ok we did NOT need threads :)

individual/individual   time:   [2.1499 ms 2.2040 ms 2.2697 ms]
                        change: [-97.607% -95.749% -84.545%] (p = 0.01 < 0.05)
                        Performance has improved.

little refactor was fun
23b was ez
working on 24a

ok done :)

24b is hard to understand

so right now i have

struct Grid {
    cells: Vec<Cell>,
    width: usize,
    height: usize,
}

i think this is going to change to

struct Grid {
    levels: VecDeque<Level>,
    width: usize,
    height: usize,
}

struct Level {
    depth: i32,
    cells: Vec<Cell>
}

so like one main question is

how do i know when to add a new level, either above or below one of my current ones?

i think i'll keep my outermost levels - with negative depths - on the front of `level`s, and the inner ones on the back
just bc it's like the number line

ok but so right so
when do i add a new level?

if i'm on an outermost (farthest-negative) level and i have any alive cells on my border,
or if i'm on an innermost (farthest-postive) level and i have any alive cells bordering my center cell

ok so what are the main changes that need to happen for 24b
1. num_alive_neighbors() needs to take levels into account
2. when we tick, we need to make a new `levels` vec based on the old `levels` vec
3. during ticking, we need to make new levels as needed

ok that did not go well
gonna take some time off

ok i spent some more time on 24b
got some code down
it's not working atm

lol i was using the wrong sample input
let's try again

ok it's still failing but different this time
let's poke at it

done :)

ok 25a looks fun
it's not running the way i'd expect tho, it prints out a newline and then halts waiting for input

ok i wasn't checking the halt code

===

8/19/20

Items here:
- monolith
- antenna
- ornament
- asterisk
- fixed point
- dark matter


monolith - heavier
asterisk - lighter

screw it i'll just write a program to do this
found a bunch of other items while doing it, whoops+neat

A loud, robotic voice says "Alert! Droids on this ship are lighter than the
detected value!" and you are ejected back to the checkpoint.

ok so now i'm at the point where i want to bfs
how do i do that?

DONE the reason i'm getting infinite hangs is bc i'm running until needs input

A loud, robotic voice says "Analysis complete! You may proceed." and you enter the cockpit.
Santa notices your small droid, looks puzzled for a moment, realizes what has happened, and radios your ship directly.
"Oh, hello! You should be able to get in by typing 134227456 on the keypad at the main airlock."