i said this in a reply but now i'm going to say it here

part 2 is a genuine programming challenge where you have to understand why the naive solution is slow and what you can do about it

part 1 is a challenge where you have to not get confused while you read the spec

so this is probably what was intended for part 2

but i did make it completely unreadable

https://github.com/undergroundmonorail/advent-of-code-2020/blob/main/day%2010/part2_alternate.py

unfortunately, as clever as the idea behind this solution is (i didn't come up with it lmao), i just threw a cache on the recursive function and it worked just as quickly

this one works without a cache though

coming along nicely

tested it with regular life because i know how it works but it should work with whatever rule

the reason this is nice is that each cell doesn't necessarily expect the cells around it to operate by the same rule

so i can have B0/S0123 chairs and B/S floor just magically work together

part 2 is going to be weird, thought at first the same approach wouldn't work but i think i can just modify `get_neighbours()'

bleh, part 2 solution worked first try but it takes 20 seconds and i would like to get it under 15 like the about page says

bahh i just realized that my technique for speeding up my solution would have worked on part 1 if i needed it, but exactly the thing that was changed in part 2 makes it not work

"what thing did you try that didn't work?"

here, have a diagram that probably only makes sense to me

wow you can actually see me get lazy about the arrows

okay with that actual clever idea ruled out, i have solved the problem by just hardcoding "if the rule never causes this cell to be born, don't even look at your neighbours, just stay dead"

here it is https://github.com/undergroundmonorail/advent-of-code-2020/tree/main/day%2011

extremely simple day. only thing that gave me trouble was just forgetting that the waypoint starts at (10, 1) for part 2

i didn't get to reuse any of the actual computation code though, just input parsing

https://github.com/undergroundmonorail/advent-of-code-2020/tree/main/day%2012

part 1 was easy

i have verified that i understand part 2 by writing a function to determine if an answer is correct, but i have no idea where to start actually finding an answer

it's related to finding the least common multiple, which is what i'm currently thinking about, but it's not the same

currently in my head i'm trying to figure out if there's anything i can do to cancel out the offsets but...

i want to say something like

maybe you only have to check "near" multiples of the LCM? for whatever "near" means. but that doesn't seem right

maybe something like subtracting out the offsets, finding the LCM, then adding the offsets back in somehow? no, that doesn't make sense either

maybe find a number for each bus such that bus % n equals the offset it needs and then find the LCM of those numbers?

this doesn't actually sound right to me either but i don't have enough intuition about this kind of stuff to trust it so let me try that

no that doesn't makes sense either

the first timestamp for the example 67, 7, 59, 61 that works is many digits long and the numbers that modulo to the offsets are 1, 2, 3, 19

i'm watching a youtube video about the chinese remainder theorem and there's a comment from 11 hours ago that references aoc 2020 day 13 part 2

so i'm on the right track

it seems so close to what i need but not the same as what i need

actually wait let me rearrange some numbers in my head, it might literally just be what i need

no it's too hard to do it in my head, i'm going to do it here

the chinese remainder theorem lets you find x for a system like

x = n_1 % a_1
x = n_2 % a_2
x = n_3 % a_3

etc

let's say i have an input of something like `5,x,7`. that means i have to find a timestamp where timestamp % 5 = 0 and timestamp % 7 = 5 (i.e. -2)

but if timestamp % 7 = 5, that means (timestamp + 2) % 7 = 0

so in this case i'm looking for numbers that satisfy

0 = (x + 0) % 5
0 = (x + 2) % 7

which is *so close*

for each bus_n (where i skip over any n that was an x, i just don't worry about it) i need

0 = (x + n) % bus_n

but i don't

have

the experience working with modulo

to know which algebraic moves i have here to try to extract x

if i can just get x on the left i'm golden, i finish this video on the chinese remainder theorem and i'm done

i want to just like

do it

like can i just...

0 = (x + n) % bus_n
-x = n % bus_n

...no that doesn't make sense. n % bus_n is just going to be n pretty much all the time, and -x means something completely different when it's congruent to something modulo whatever so when you resolve that they'll all be different again

yeah yeah i haven't finished day 13 yet, shut up i'll get to it

https://github.com/undergroundmonorail/advent-of-code-2020/tree/main/day%2014

easy day, i put in more effort than was actually required but it was fun. while solving part 2 i got an idea in my head like "could i write a recursive function that handles the floating bits at the same time as the conversion from binary to decimal" and sure enough, here we are. took a couple swings at it even after i got one working and i'm proud of how it came out

going back to this

after talking to emi it turns out i was extremely close to what i wanted

for a bunch of busses with offsets and ids, i had

0 = (x + bus_offset) % bus_id

and was struggling to get x on its own

the problem was that i was thinking of modular arithmetic from the way it's used as an operation in programming, not the way it's used in math: a fact about the entire congruence

so the way i get x on its own is just...

x = -bus_offset % bus_id

oops

like i was thinking of it as

(0) = ((x + bus_offset) % (bus_id))

but really it was

((0) = (x + bus_offset)) % (bus_id)

...this helps me but idk if it makes sense to anyone else

i probably shouldn't even be using "%" here, it would be clearer what's going on having it written out as "mod"

but whatever

okay i solved it

it involved an algorithm that i understand the broad strokes about why it works but don't really get the details of exactly, and it's a very naive implementation of that algorithm (i'm sure there are nicer ways to do it in python but... you'd need to understand the details exactly)

but it's done https://github.com/undergroundmonorail/advent-of-code-2020/blob/main/day%2013/part2.py

there must be a clever math thing for this, too

i can't do anything 30000000 times without the runtime being massive

so this last thing was incorrect, i accidentally was measuring the runtime of an infinite loop, not a 30000000 iteration loop

here's the day 15 code https://github.com/undergroundmonorail/advent-of-code-2020/tree/main/day%2015

part 2 is a mess because i didn't feel like doing any actual thinking to get rid of the off-by-one errors, i just kind of massaged it until it spat out the right answers for the example data on 10 and 2020 and then gave it the real data on 3*10^7

oof

i figured i'd experiment with closures for this one and found some behaviour i actually really don't like

wrote a function like:

def parse_rules(field_rules):
    for rule in field_rules:
        a, b, c, d = map(int, re.findall(r'(\d+)-(\d+) or (\d+)-(\d+)', rule)[0])

        yield lambda n, a, b, c, d: a <= n <= b or c <= n <= d

it extracts the four numbers out of all the rules and then yields a function with behaviour defined by those numbers

but

the closure doesn't remember the value of the numbers being returned, it only remembers what value it was pointing at. so as a, b, c and d were changing, it changed how all the lambda functions behaved. every single one was verifying that a number matched the last rule

and the way you fix that is: abuse default arguments. the lambas i'm yielding now look like this:

yield lambda n, a=a, b=b, c=c, d=d: a <= n <= b or c <= n <= d

why am i getting the wrong aaaaansweeeeer

it works for the example data but not for my input

it's because i can't fucking reaaaaad

maybe next time i'll read the instruction before i bitch about it

but probably nooooooot

so

i had a dictionary called rule_possibilities and my goal was to empty it out following some rules

i thought i was going to have to do an expensive operation to do that, but i could make it less expensive by removing the easy ones from the dictionary first, so i wrote the code to remove all the easy ones

and then it turned out that as i did that, they all became "easy", so when i was done with the easy ones there was nothing left

which is why my part 2 code has this block in it:

if rule_possibilities:
    # i thought i was going to have to write code for this case but i guess i don't
    pass

as for why the rest of the code sucks: i don't really have an excuse

https://github.com/undergroundmonorail/advent-of-code-2020/tree/main/day%2016

day 17 actually doesn't seem too bad, i can repurpose my LifeLikeCell from the other day to be 3d

the hard part is the "infinite 3-dimensional grid" in the pocket dimension, my current solution assumes a finite grid

but i think i have a hack for that

my hack worked fine for part 1 but i don't think it'll scale to part 2

actually you know what

it worked

it takes 50 seconds and i could speed it up significantly but i don't fuckin want to. not an interesting challenge, just tedious

here is my extremely hacky code for extending my LIfeLikeCell class into new dimensions https://github.com/undergroundmonorail/advent-of-code-2020/tree/main/day%2017

@monorail oh dang

I just had a lot of nested loops