This is the only Advent of Code post this year in my blog.
After failed attempt to post full progress of my Advent of Code attempt two years in a row. I finally made decision to only post after I successfully solve all of the problem this year. You can see all of my AoC post under advent of code tag in this blog.
I feel like this year’s problem is easier than last two year before. Maybe because I am getting smarter after those two years.
I also feel like there are too many 2D grid problems in AoC this year. Maybe there are about 10 problems and some of them are in consecutive days.
But overall, I enjoy all of this year’s problems.
These are my favorite problems from this year’s AoC.
This problem is basically just solving system of linear equations with two variables.
Of course I already forget all of my linear algebra knowledge. So, I just implement simple Cramer’s rule solution.
This problem is simple, it just do some simulation by moving robots with certain vertical and horizontal velocity after certain time on the 2D grid.
The interesting thing is in part 2, I have to find easter egg in the form of christmas tree formation of these robots on the 2D Grid.
Here is the easter egg.
.............................*.......................................................................
......................................................................................*..............
..............*...........*..........................................................................
..................*...............................*.....................*............................
...............................................................................*.....................
...................*.................................................................................
*.......*............................................................................................
...................................*............*........*...........*...............................
............................*.........*.*...................*........................................
.....................................................................................................
.....................................................................................................
.........................................*..............*.............*........................*.....
.................................................................................................*...
...*.................................................................................................
............................................................................*............*...........
.....................................................................................................
.....................................................................................................
......*..............................................................................................
.............................*.......................................................................
...................*...................................*.............................................
....................................................................*................................
.......................................................*..........................................*..
...............................................................................*.....................
.....................................................................................................
......................*.*............................................................................
........................................**..........*............................*...................
...*.................................................................................*...............
......................................................................*................*.............
.....................................................................................................
..............*..............*.......................................................................
.....................................................................................................
..........*.............................................*............................................
........................*............................................................................
......................*.................*......*.....................................................
....................................*................................................................
....................*...............................................*..*.............................
...........*.........................................................................................
..*.................................................................*...*......................*.....
.....................................................................................................
...................*******************************..........................*.......*................
...................*.............................*...................................................
...................*.............................*...................................................
...................*.............................*...................................................
...................*.............................*....................................*..............
...................*..............*..............*....................*..............................
...................*.............***.............*...................................................
...................*............*****............*...................................................
...............*...*...........*******...........*................*..................................
......*............*..........*********..........*.*.................................................
...................*............*****............*.........*.........................................
.........*.........*...........*******...........*...................................................
.........*.........*..........*********..........*..*................................................
...................*.........***********.........*...................................................
...................*........*************........*...................................................
........*..........*..........*********..........*.......................*.............*.............
.............*.....*.........***********.........*........................................*..........
...................*........*************........*...................*....**.........................
......*............*.......***************.......*........*..........................*...............
...................*......*****************......*........*............................*.............
...................*........*************........*.......................................*...........
.......*...........*.......***************.......*...................................................
...................*......*****************......*........*..........................................
*...........*......*.....*******************.....*...................................................
...................*....*********************....*.....*.............................................
...................*.............***.............*......................*............................
.............*.*...*.............***.............*...................................................
...................*.............***.............*............*......................................
..*................*.............................*.......................*...........................
...................*.............................*...........................*.......................
...................*.............................*.................**................................
...................*.............................*...................................................
...................*******************************...................................................
............................................................*...*...........................*.*......
..........*.......................................................*..................................
...................................*.................................*...............................
..............................*......................................................................
...................................*............................*....................................
.....................................................................................................
.............*.......................................................................................
........*..........................................*.....................*.......................*...
..........................................................................*..........................
........................................................................*............................
....*................................................................................................
...................................................................................*.................
..............*..................................................................*...................
..............................................*......................................................
.....................................................................................................
......................*..............................................................................
................*....................................................................................
...............................................*.....................................................
.....................................................................................................
........................*...........................................*..............*..........*......
..............................................*..............*.......................................
.....................................................................................................
.........................................................*...............*...........................
.....................................................................................................
...............................................................................*.....................
.............................................................................*.......................
................................................................*..*..*.........................*..*.
.....................................................................................................
.....................................................................................................
..................................*............................*.......................*.............
.........................................................*...........................................
From all of the 2D grid problems, this one is my favorite.
The problem is just finding shortest path using Djikstra’s
algorithm. The interesting part is I need to save the distance in
terms of (position, direction). Because I am too lazy to implement proper data
structure for this, I create this typedef monstrosity.
...
typedef pair<int, int> pii;
typedef pair<pii, char> pos_dir;
typedef pair<int, pos_dir> dist_pos_dir;
...
priority_queue<dist_pos_dir, vector<dist_pos_dir>, greater<dist_pos_dir>> pq;
map<pos_dir, int> dist;
...I like this problem because this is the only problem with the solution straight up just dynamic programming.
The summary of the problem: given a list of strings and target string, we have to check if we can construct the target string by concatenating any string from the list.
This one is an interesting graph problem.
For part 1, I need to find how many triangle sub-graph in the graph. This part is easy and straightforward.
For part 2, I need to find maximum clique in the graph. I am using Bron–Kerbosch algorithm and implement the solution.
I learn something new because of this problem.
I think this is the hardest problem of this year.
Given initial state of input and list of logic gate, I need to find the final output. This is just for the part 1 and very straightforward.
For part 2, I need to find the wrong wiring and swap them so that this logic circuit become addition operation from the inputs.
After doing some observation and visualization, I realize this is just 45 bit full adder circuit.
Because I am too lazy to implement the solution, I just visualize the circuit and find it manually by looking at the circuit.
Overall I am happy with my result this year.
All of my solution this year can be found in my github repo. Some solutions are accompanied by write up to explain my approach for the solution.
I hope next year problem is not dominated by 2D grid problem and there are more variation of the problem.
Also I hope that I’m not getting dumber next year.
Cheers.