day 8 was pretty easy

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

you can tell i like functional stuff more than the average python user because i had to write this:

def first_true(it):
    for e in it:
        if e:
            return e

i thought i could use any() for that, since it's basically just applying or over an iterable and or short circuits when it gets a truthy value, but any() returns a literal True or False while i actually needed the truthy object

everything in the iterable that function gets is a number, most of which are 0 and one of which is the solution to the problem

so i could have just used sum() but i didn't want to keep calculating when i already had the answer

okay i just tried it with sum() and the difference in execution time is completely indistinguishable so maybe it was a waste of time

catching up on aoc

day 9 solutions kinda suck but here they are. they do work i just feel like they're very naive

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

so this was a weird one

i read part 1 over and over again because i was like "i must be missing something, there's no problem here. where is the programming challenge" but no it's just... nothing. it kinda tries to confuse you with stuff like your adapters being rated for a difference of 3 jolts but since you know every adapter has to be used, that's completely irrelevant to you. the jolts can never go down so you just sort the list.

i still managed to overcomplicate my part 1 solution but you could write it in a much simpler way. i just chose not to

my part 1 and 2 answers are almost nothing alike

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

in part 2 i didn't bother to stick around and see if a naive recursive solution would ever finish. i let it go for a couple seconds to see and after that it wouldn't even respond to ^C, i had to close the whole powershell window

luckily it runs instantly when you just put the functools.cache decorator on the naive recursive solution

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

@monorail no

@noiob oh

...oh you know what i did

i just replaced "2020" in the loop in my part 1 solution with "30000000" and then replaced the body with a = 'test', just to see

but it completely escaped me that my loop was while len(spoken) < [my number]:

whoops

@monorail lol