Advent of Code 2020

The 1st day, 2020.12.4

Day 1

I was kept busy by my work until today.

Of course, your expense report is much larger.

And when I opened the input I was like really? You call this "much larger"? Being from a competitive programming background I was expecting something like `N=2*10^5`; the input is just 200 lines long. Actually kinda makes sense, it's the first day, you normally wouldn't want to be intimidate on the first day.

And then I saw part 2 which is 3 numbers. Again due to the small N one can just brute force it (even with very bad brute force with big constants).

Day 2

Okay this is more like it, the input is 1000 lines long. Requires text manipulation... working with strings feels really similar to duct tapes when stuck to your fingers.

(After solving part 1)

Does the input get like 2*10^5 lines long on the 20-something-th day?

Day 3

Ahh yes... it begins.

Or not. For a moment I thought it's some kind of searching problem that requires a DFS or BFS.

So for part 1 you can have a little twist here: the whole "repeat to the right" thing means the horizontal movement can safely collapses into a `(x+3)%width`. Part 2 is similar.

Day 4

More text manipulation?! Oh Lord.

The 2nd day, 2020.12.5

Day 5

Okay, this is more like it. I alread had enough of text manipulation in my day job.

The FBLR thing is just a distraction; it's just a binary number that you didn't even have to split in half.

Part 2 is more interesting. "Completely full flight" means every seat ID except the protagonist's shall be in the list; this is the important bit. "The seats at the very front and back of the plane don't exists on this aircraft" part is merely a distraction.

The 3rd day, 2020.12.6

Day 6

I'm actually amazed at how good python can handle these sort of things, it almost feels like these problems are written with a very simple python answer in mind.

The 4th day, 2020.12.7

Day 7

It seems like I just can't escape from these pesky parsing stuff ain't I? But the probelm itself is more like it. Basically the whole rule thing forms an acyclic directed graph (with paths pointing from containee to container) and you can simply traverse the thing.

...I can't believe I'm actually having trouble at part 2. I messed up the counting part 4 times. The main idea is the same, but the direction of the paths are opposite (container points to containee).

The 5th day, 2020.12.8

Day 8

I start to question myself if this log is even necessary, up to now every part 1 has been trivial, like *very* trivial. Part 2 can be brute forced: generate every solution by replacing jmp with nop / nop with jmp. It's like 250+ different solutions, really not that much.

The 6th day, 2020.12.9

Day 9

Ah yes, prefix sum. Basic technique in competitive programming. When you (1) have a sequence of number, and (2) have to sum different parts of it many times, you don't just go sum the parts every time (which is O(nm)), you do a prefix sum and subtract one prefix sum with another, i.e. for `Sum(seq, i, j)` you can first have `PrefixSum[i] = Sum(seq, 0, i)` (which is O(n)) and have `PrefixSum[j]-PrefixSum[i]`, which is overall O(n+m).

As for part 1, if you really have to care about memory usage (e.g. you're doing competitive programming & the input can have 2\*10^5 lines long) you can have a buffer with a length of 25 and process the file line by line instead of reading the whole stuff at once. As for finding the number that doesn't have the property, one can probably do O(nlogn) by sorting + binary search, I did not bother to do that because the N is small enough (1000 lines) to just brute force.

The 7th day, 2020.12.10

Day 10

It really scares me for a bit here. I did not read carefully and thought "Really?? Are you gonna make me count all the possible combinations of power adapters to charge the protagonist's thing?" That'll probably require some form of dynamic programming and I was never good at it even in my competitive programming heyday.

Glad that it wasn't asking for that or else I might have to spend the rest of December on this single problem...

(After solving part 1)


Let's do this...

Of course I would not enumerate every single combination, that'll be stupid... DP it is.

One thing that's so annoying about DP is that it takes a heck ton of luck and math instinct to get the correct fricking formula for calculating. For simple problems it's fine, but for the more advanced it's a nightmare.

...I'm surprised. This is actually one of the simple problem. Easy to have this observation:

0  1  4  5  6  7  10  11  12  15  16  19
0  1  1  1  2  4   4   4   8   8   8   8

F(x): number of combination that can support x joltage

F(x) = 0   (x not in input)
F(x) = F(a1) + F(a2) + F(a3) + C
     where a1 = x - 1
           a2 = x - 2
           a3 = x - 3
           C = 1   (x <= 3)
               0   (x > 3)

`C` is necessary: if 0 can directly support `x` joltage it should be counted as well.

The 8th day, 2020.12.11

Day 11

So it's Game of Life but with a twist... nothing too serious.

The 9th day, 2020.12.12

Day 12

Nothing too serious today...

The left & right turns does not include any angle other than multiples of 90, so related shortcuts can be taken...

The 9th day, 2020.12.13

Day 13

Is the story gonna end like "oh you finally arrived at the vacation island but there's already no time left for your vacation"? Like wtf.

I'm getting tired of this. I'm not sure if I will participate in AoC2021.

Part 2 is way trickier than I thought. We can start doing brute force using the biggest id number, but it was hinted that the result will be way too big to brute force, so maybe I have to use a different method...

Yep. Tried out brute force. Definitely not fast enough.

It's Chinese Remainder Theorem.

This problem went from easy walk in the park to fucking free climbing real quick like what the fuck.

Okay fuck this. I have more important stuff to do, I don't have hours to spend on this stuff. I'm out.

(15:45) Okay I solved it. Have to refer to the Chinese version[1] of Wikipedia page for Chinese Remainder Theorem because I only need to know how to construct the stuff and the English version is fucking bullshit for that. Seriously who the fuck wrote that English Wikipedia page? For us pleibeian programmers this is as useless as uselessness can get.

[1]: 中国剩余定理 - 维基百科