2019/

README

Advent of Code 2019

Language: Go

https://adventofcode.com/2019

---

Summary

Day	Name	Type of Algo & Notes
1	The Tyranny of the Rocket Equation	- Simple math problem
2	Program Alarm	- Intro to the crazy Intcode problems that are half the AoC days... - Array (slice...) manipulation - I used recursion
3	Crossed Wires	- Geometry kind of algo, finding intersections of lines on a grid
4	Secure Container	- May appear math-y, but it's really a string manipulation problem
5	Sunny with a Chance of Asteroids	- Yay more Intcode!........ - This gave me fits... - Good application for recursion (in my opinion)
6	Universal Orbit Map	- Tree traversal and depth calculations. It's not quite a Graph, but it has a directed graph algo feel too
7	Amplification Circuit	- More Intcode... Piping together multiple Intcode computers 😳😳😳 - Refactored Intcode computer to an OOP approach so a single computer maintains its data - Also requires making permutations generator - Some gymnastics to make this circular, but its easier with this OOP approach and the "objects"/instances of a struct maintaining their own data - Concurrency could be used to sync these Amps together...
8	Space Image Format	3D Array manipulation, pretty straight forward
9	Sensor Boost	MORE INTCODE. YAYY 🙃 - A new parameter mode and opcode. - Really feeling the (tech) debt of some earlier design choices here, went back to refactor day07 before jumping into this one, then it was a small bit of code for the relative param/opcode & resizing computer memory if necessary
10	Monitoring Station	- This (part2) is my favorite algo... Yes I have a favorite algo Fundamentally it's a geometry problem, angles and trig - Part 1: Calculated via slopes - Part 2: Using Arctangent to find angles an asteroid makes against a vertical line from the home base asteroid. Then those angles can be used to determine if Asteroids are covering each other, AND iterating through all of them can find the next angle Asteroid to vaporize
11	Space Police	- More Intcode stuff... - 2D Array/Slice manipulation and a bit of maths/graphing - Implemented a RotateGrid algo
12	The N-Body Problem	I like to call this a (harmonic) frequency algo. Finding the harmonic frequency of multiple bodies/items and then finding the Least Common Multiple of those frequencies will tell you when all the bodies have returned to their initial state. - I've used this approach for a leetcode problem about prisoners in jail cells too
13	Care Package	Intcode again! It's basically every other day... - part1: 2D array manipulation again - part2: holy algo, some logic to basically play Bricks game. - This is more of a design question for how you manage state
14	Space Stoichiometry	Weighted Graph and Breadth First Traversals - Because not all of the products have a quantity of 1, it complicates the graph's data model. I ended up mapping the product/chemical name to a map of its stoichiometry where the product's number is positive & reactants were negative. - part2: not just a simple division because of "extra byproducts" of generating each piece of fuel. I just let this brute force thing run for ~30 seconds...
15	Oxygen System	YAY INTCODE 🙄 - Combination of 2D grid searching algo, backtracking algo and the the Intcode... - I've realized that I really need to stop using x and y for 2D grids and start using row and col because mathematically x is horizontal and y is vertical... My brain is all jumbled up - Created a Robot struct/class that has a computer inside of it. It goes and searches around, collecting data on the floor types at various coordinates. That data is transformed into a 2D grid/array, and then finally fed into a backtracking, searching algorithm to determine the shortest path (turns out there's only one path to the O2 tank...) - part2 is fairly straight forward 2D grid traversing and tagging a spread of oxygen to valid tiles/hallway spaces
16	Flawed Frequency Transmission	- Some really weird, contrived (as if this whole thing isn't) phase calculator?.. - part2 broke my brain. Optimally calculate subsets by precalculating running sums (linear), then getting subsets by subtracting two of the precalculated running sums. i.e. sub[2:4] = sub[0:4] - sub[0:2] - And also switching pattern recognition to make calculating a particular output O(nlogn)...
17	Set and Forget	More Intcode... Robot walking around a scaffolding... Fairly similar to previous algos, and a 2D grid traversal again - I feel like I cheated part2 by finding the pattern by eye after printing what the 2D grid looks like. Then it was a matter of giving the intcode computer the corresponding inputs (in a weird format). - Good example of iterative approaches being better than recursive approaches because the recursive approach in "continuous video mode" causes a stack overflow very quickly
18	Many-Worlds Interpretation	- Oof, this is the hardest algo so far I think... Combination of Best Pathfinding Algo (going to use a BFS/Dijkstra's) and a weighted Graph Traversal with "locked" edges - I toyed with the idea of using some kind of bitmap to track keys that were found, but ditched it so I wouldn't have to write my own wrapper around bitwise logic... Time complexity comparisons are roughly similar for comparing two maps as comparing two sets of bits, the space complexity is probably much better for 27-bits (@ and a-z) compared to a hashmap, but OH WELL. - The graph traversal required memoizing in order to run in any reasonable amount of time. - My part 2 assumptions would not work for every example which is unfortunate :/ I assumed that within a particular quadrant, if the quadrant does not have the key for a door, just remove the door.
19	Tractor Beam	- Another Intcode outputting to a 2D grid - THERE NEEDS TO BE A CONVENTION FOR X AND Y WHEN WORKING WITH 2D GRIDS This is awful, should it be mathematical? Should it represent rows and columns? Who knows?! - Little geometry (drawing squares) for part2 but nothing crazy
20	Donut Maze	Breadth first search path finding algo. Dijkstra's Algorithm to find the shortest path given a maze with "portals." Part 2 is kind of wild with the maze become 3D, but the solution is effectively the same, just more complex to implement - I remapped this in my head to more of a 3D cube instead of a donut... - That was really cool to get working... Dare I say fun...
21	Springdroid Adventure	Another simple-ish Intcode based problem, this time using some weird Assembly language that gets inputs via writing ASCII values to the Intcode computer.
22	Slam Shuffle	- Seems fairly easy at first... But the part 2 has numbers somewhere in the 32-bit number to 64-bit number range... So the part 1 code is pretty much useless... I gave up on part 2. It's some crazy linear algebra with modular inverses?.. Theoretically it makes some sense.. but I had to read someone else's solution for hours to kind of understand the implementation...
23	Category Six	Intcode computer NETWORK of 50 computers... Oof that's a lot of stuff to coordinate, but not too hard, make a Network struct. Part2 doesn't seem too different, but includes a NAT device, which is simple enough to just store in variables in the goroutine... That has to be record time for me to finish a day :) Sigh of relief after day22.
24	Planet of Discord	Almost done... When the input if 25 character you know it's going to be a crazy AoC day... Part1 is fairly straightforward 2D slice traversal. Part2 makes it a recursive map... of course I chose to utilize predefined-length arrays to minimize having to make lots of slices. If the number of minutes was not known ahead of time, then a doubly linked list could have worked to expand layers indefinitely. Or a map with int-indexes because those could be negative. I wrote a lot of code to just handle recursive structures... There's probably a way to clean this up and I definitely didn't plan my approach well enough before writing code
25	Cryostasis	One final Intcode problem