Advent of Code 2020 - Day 10

Placed 25/9. Submitted a wrong answer to part 1 because I didn't read carefully enough; I'm very happy with my score considering that.

The answer for part 2 is enormous (18 trillion for me), so we can't count the paths (i.e. which adpaters we use) one-by-one. So how do we do it? Dynamic programming.

The idea is that once we have reached, say, adapter 10, the number of ways to finish our path (i.e. to plug in our device) is always the same. It doesn't matter how we got to adapter 10. This is the wastefulness of the brute force solution; every time it gets to adapter 10, it recomputes all the possible ways to get to the end. We can speed it up by eliminating this wastefulness; just compute the number of ways to finish the path from adapter 10 once, and then reuse that information every time you need it.

We can implement this idea with memoization. Write a recursive function dp() that implements the brute force solution by computing the number of ways to finish the path based on the current adapter. Our idea above translates to the observation that if you call dp with the same input, you always get the same output. So keep a global dict that remembers which outputs go with which inputs. If you get an input you haven't seen before, compute the output and add it to the dict. If you get it an input you have seen before, return the output you previously saved in the dict.

This speeds up the solution from exponential-time to quadratic-time. There are only 100 possible inputs to dp(), so we will only need to compute 100 different outputs. Computing each output requires an O(n) loop (it is easy to optimize this part to O(1)), not including the recursive work (including it would be double-counting, since we are considered that we will have to compute all 100 outputs). So the total running time is O(n^2).

This idea is very general. Many problems have brute-force exponential time solutions that repeat the same work over and over and can be memoized for dramatic speedups. The trickiness in solving DP problems is figuring out what you can "forget"; you need to have as few function inputs as possible so you can reuse work as much as possible. In this problem, we had to realize we only cared about the current adapter, not the whole path.

[TheFrogfather]

Thanks for a very detailed explanation of what's happening and why. I'd got most of the way there, but realised it was going to take several thousand million years to execute!

[gandhiisback]

Thanks for making these great explanations! Please do keep making them, I look forward to learning how to solve some of the harder problems from the later days from you.

[harmonicposting]

this was randomly recommended to me as someone who barely even understands the basics of programming but these kinds of videos are always a satisfying watch

[thomastatum]

Thanks for the explanation on pt 2. I come here in December when I'm stuck to help get perspective.

[Ma-wosk]

Aaaand you got a new subscriber. Thanks for sharing your wisdom, you great Aoc master

[flwi]

Holy smokes - 4:40 to solve this beast. First time this year I look for a video before trying to solve it myself, because I had no idea what he wants from me - and I'm 5mins into reading the description. 😂
I only measure the time myself, because I don't want to get up super early). I'm usually 5-10x slower than you, but have some evil outliers.

Mad respect! And everything with blank vim - but at least some syntax highlighting 🤯

[vader]

All the flavor text confused me so much today for part 1. I kept on searching for the actual problem until I realized it really was just a basic sort and the only thing to solve was the last question.

[rainbowvein]

Thank you so much for taking the time to explain the dynamic programming solution. I'd got as far as the recursive function and calculating the pathways which for the test input worked fine but as you said - in the main file it takes forever! Makes so much sense what you explained, so thank you.

[CAG]

So you basically did what I did but 2x more concisely and 12 times faster. Guess it's time to die <_<

[sgeisenh]

While I prefer the combinatorial approach to part 2, the simplicity of the memoized approach is striking.

[neanderthal]

Thanks! Great videos, I usually watch them when I'm finished the problem or I'm stuck ;P

[Racrdude]

I keep seeing memoization pop up in people's solutions. I should definitely start using this! My original solution would have worked if I just added memoization (I did the O(e^n) you showed), but I spent another 15 minutes writing a new algorithm

[ugabbel]

Really great job, I've get the same solution but after an hour of thinking ahah

[hjdeheer]

This can also actually be done in a O(n log n) solution where you use a memorization list but then with an iterative dynamic programming solution (O(n)). But then the complexity is still bound by the sorting of the list so O(n log n) complexity

[wurschtbrot]

You got a new subscriber! 🙂 Btw, what’s your keyboard? Sounds great

[sumnerevans]

I used an lru_cache from functools, instead of the explicit DP dictionary:

from functools import lru_cache
@lru_cache(maxsize=None)
def dp(i):

That being said, I was *much* slower than you, so apparently what you did is better :)

[wislord]

Second part could be solved with simple formula solution. 7^A x 2^B. I wish I could read that fast as you.. well and think as well ;)

[sgc]

Any way of your publishing the python code for each day's solution? Thank you.
If I recall you used to do these in C++, why Python?

[rastislavsvoboda]

checking just up to next 3 numbers, is it ok?
// j and i look very similar when in brackets :-(

def dp(i):
if i == len(xs) - 1:
return 1
if i in DP:
return DP[i]
ans = 0
for j in range(i + 1, i + 4):
if j < len(xs) and xs[j] - xs[i] <= 3:
ans += dp(j)
DP[i] = ans
return ans

[prakash_]

Great explanation. I found the pattern in part 2. And solved it without dp. My C++ Code:

vector<int> v;
unordered_set<int> st;
int m;
while (cin >> m) {
v.push_back(m);
st.insert(m);
}
sort(v.begin(), v.end());

long int ans = 1, n = v.size();
v.insert(v.begin(), 0);

for (int i = 0; i < n;) {

if (st.count(v[i] + 1) && st.count(v[i] + 2) && st.count(v[i] + 3) && st.count(v[i] + 4)) {
ans *= 7;
i += 4;
}
else if (st.count(v[i] + 1) && st.count(v[i] + 2) && st.count(v[i] + 3) )
{
ans *= 4;
i += 4;
}
else if ( (st.count(v[i] + 1) && !st.count(v[i] + 2) && st.count(v[i] + 3)) ||
(!st.count(v[i] + 1) && st.count(v[i] + 2) && st.count(v[i] + 3)) ||
(st.count(v[i] + 1) && st.count(v[i] + 2) && !st.count(v[i] + 3))) {
ans *= 2;
i += 3;
}
else {
i++;
}
}

I think some of the conditions in the if/elses might be redundant.