Advent of Code 2021 - Day 21
Placed 18th on part 1; 1st on part 2!
Problem: https://adventofcode.com/2021/day/21
Code: https://github.com/jonathanpaulson/Ad...
I kind of garbled the explanation. Here's a hopefully clearer text explanation for part 2:
Brute force is way too slow here, as we can tell from the example. However, recursive brute force + memoization (dynamic programming) is fast!
Let's start with the recursive brute force. We want to compute how many ways each player can win. Let's generalize a bit and write a function that computes how many ways each player can win *starting from any position of the game*, not just the starting position. (That's my "count_win" function).
We can implement this recursively; the base case is that someone already won, in which case there's one way they can win and zero ways the other player can win. Otherwise, try all possible moves/die rolls for the current player, which produces a new game state/position, which we can solve recursively. The answer for our state is the sum of the answers for each recursive/child position.
Now that we have a recursive brute force, we can memoize it. Let's write down the answers for each position as we compute them (That's what my "DP" dict is for). If we want the answer for a position we've already computed, we don't need to do any work; just return it.
How much time does this actually save? A lot! Brute force explores trillions of possible sequences of die rolls. But there are only ~40,000 possible game positions (10 possible positions for each player * 21 possible scores for each player). So brute force must be looking at each position billions of times. Memoization only looks at each position once, so it runs literally a billion times faster.