Advent of Code 2020 - Day 10

1 Просмотры
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.

Our first dynamic programming problem! Very exciting. I previously made a playlist about DP:

The answer for part 2 is enormous (18 trillion for me), so we can't count the paths ( 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 ( 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.
Комментариев нет.