Advent of Code Solutions

My solutions to Advent of Code problems.

Quick Start

NodeJS

1. Install dependencies via yarn install.
2. Two options:
   1. Run and watch a single file via yarn watch-single, or
   2. Run and watch the last file changed under a specific year via yarn start.

Python

1. Change directory cd python.
2. Install virtualenv via pip3 install virtualenv.
3. Run virtualenv ./env.
4. Run source ./env/bin/activate.
5. Run pip install -r py-requirements.txt.
6. Run nodemon --exec python 2022/19.py.

2022

1. Day 7 - No Space Left On Device
   • Iterator pattern
2. Day 11 - Monkey in the Middle
   • How to a keep a number small without impacting its divisibility by a specific number
   • LCM
3. Day 12 - Hill Climbing Algorithm
   • Dijkstra's algorithm and tips on it
4. Day 15 - Beacon Exclusion Zone
   • Merge intervals/ranges
   • Complement of intervals/ranges
5. Day 16 - Proboscidea Volcanium
   • Floyd–Warshall algorithm
   • DFS with backtracking one option but not others
6. Day 19 - Not Enough Minerals
   • Constraint satisfaction problem (CSP)
   • Python to solve the linear programming problem
   • Typescript - Depth-first branch and bound relaxation
7. Day 21 - Monkey Math
   • TODO
   • Plot it out and use linear regression

2021

Not advent of code, but just a fun problem I found on MorningBrew:

1. MorningBrew - Minimum plus/minus to get sum of 100

2020

Work in progress.

• Day 4b - Rules Design Pattern
• Day 5a - Binary Everywhere
• Day 6b - Custom Customs
  • Intersection of N arrays with unique values
• Day 7 - Recursive Hand Bags
  • DFS on weighted graphs
• Day 9b - Encoding Error
  • Efficient continguous sum
  • 1D version of Summed Area Tables
• Day 10b - Adapter Array
  • DP problem
  • Pigeonhole principle / counting
• Day 11 - Seating System
  • Immutable object
  • 2D Convolution
• Day 13 - Shuttle Search
  • Fun with prime numbers.
• Day 16 - Ticket Translation
  • Constraint satisfaction problem (CSP)
  • PriorityQueue to solve CSPs
• Day 17 - Conway Cube
  • ArrayDeques
  • InfiniteGrid
  • getPermutations and getSpace backtracking solutions.
• Day 18 - Math Expressions
  • Infix and postfix math expressions
• Day 19 - Grammar
  • Rules design
  • Regex subroutines
  • CYK algorithm
• Day 20 - Rotating Images
  • Rotation/reflection of 2D arrays in O(1).
  • Finding sub-image inside image.
• Day 21 - Allergen Assessment
  • Constraint satisfaction problem (CSP)
    • Uses Python to formulate and solve integer programming problem!
  • PriorityQueue to solve CSPs

2019

All problems are complete, but only some are worthy of notes:

• Day 2b - System of Equations
• Day 12b - N-Body Problem
  • Least Common Multiple (LCM)
• Day 14 - Stoichiometry
  • Fun DFS traversal problem
  • Linear regression solution for part 2
• Day 18a - Robots Unlocking Keys and Doors
  • Dijkstra's algorithm
• Day 18b - Multiple Robots Unlocking Keys and Doors
  • Combinatorics with Dijkstra.
• Day 20a - Donut Maze
• Day 20b - Recursive Donut Maze
• Day 22b - Slam Shuffle
  • Modular Inverse
  • Linear Congruence Equations
  • Modular Exponentiation
  • Fermats's Little Theorem
  • Extended Euclidian Algorithm
• Day 24a - Bit manipulation
  • Why you can't assume first one will repeat first.
• Day 24b - More bit manipulation

2018

• Day 2b - Find Similar Words
  • Used the same idea as Word Ladder I.
• Day 5 - Polymer Reactions
  • Good example of a Stack
• Day 6 - Coordinate Proximity
  • First use of BFS in 2018.
• Day 7 - The Sum of Its Parts
  • Lexicographical topological sort
  • Priority queue
• Day 7b
  • Coordinated lexicographical toplogical sort
• Day 8 - Tree
  • N-ary Tree
  • Tree toString() explained
• Day 8b - Tree
  • N-ary Tree class
• Day 10a - N-body Problem with Letters
  • Linearity of N-body problems
• Day 11 - Summed Area Table
  • Summed Area Table
  • Largest divisor of a number
• Day 12
  • Linear Regression
• Day 13
  • Rotation and Reflection Matrices

General problem solving tips

1. Try reducing the problem space down. If there's 10 valves, or 8 monkeys, or 30 doors, etc. Imagine if there was just 1 or 2 valves or monkeys or doors. Solve that smaller problem space first.
2. Look at the input, make sure there isn't any shortcut you can take. Maybe some monkeys you'll never visit, or some doors that don't ever have to be opened, or some valves you don't have to release pressure on because flow is 0, etc.
3. Transform the problem space. This came in handy for 2019 day 18a and 2022 day 16. Convert the problem into a graph, or an adjacency matrix, etc. that is much easier to work on because of fewer variables.