# # Advent of Code 2021

This year I solved the problems in notebooks (Jupyter, Pluto.jl), and integrated the capabilities of fetching inputs and submitting answers. The code can be found in the following directories of the repo lucifer1004/AoC (opens new window).

• Simulation.

• Simulation.

• Simulation.

## # Day04

• Brute force, check each matrix iteratively.
• Precalculate the index of every number to determine the winning index of each matrix.

• Simulation.

## # Day06

• Dynamic programming. Can be further optimized via matrix exponentiation.

## # Day07

• Enumerate all integers within the range of $[\min,\max]$ to find the minimum of the total cost function.
• Better
• Part 1: The minimum can be obtained at the median.
• Part 2: The total cost function is a quadratic function within each segment. The coefficients of the quadratic function can be recalculated in $\mathcal{O}(1)$ time when moving from one segment to the next.

## # Day08

• Analysis. 1, 4, 7 and 8 can be determined easily. The rest digits can be determined from the intersection of each digit with the known digits.

## # Day09

• Part 1: enumeration.
• Part 2: BFS/DFS.

• Stack.

• BFS.

• DFS.

• Simulation.

## # Day14

• Dynamic programming on word pairs, regardless of the sequence. The beginning and ending positions should be handled with care.

## # Day15

• Shortest path via Dijkstra.