Advent of Code is an annual event where participants solve daily programming puzzles, each released in the form of a two-part challenge. The challenges cover various topics, and participants often use the opportunity to sharpen their problem-solving and coding skills.
I was aiming to:
- use my knowledge of algorithms and data structures;
- make solutions as general as I could;
- prioritize code readability over how fast I can write the solution — I didn't try to compete on leaderboards.
I guess this is a time to remember how division that involves negative numbers works in Go!
I always struggle to apply binary search on answer to problems. I am glad that I could change perspective and see that this approach would work!
Well, turns out there were too few intervals, so the binary search was not necessary.
The greedy algorithm worked, but I had to struggle to understand the approach. The key idea was to pick a maximum digit that has enough digits on the right.
Finally, a day when you have to reinterpret the input in part two. I like the Advent of Code for those tricks! I guess it's because I like to write parsers in general.
I noticed that all operations are commutative, so it doesn't matter if you go left to right or right to left. Also, there was neither number nor digit zero, which allowed me to cut the corner by detecting a column of spaces when the parsed column-wise number was zero. A chill Saturday problem, I would say!
I was trying to use DFS without recursion, but it bit me when I realized that I have to update the parent values.
Finally, my beloved DSU! The solution was straightforward when you know this algorithm. I just love applying it :)
That was tough! Initially, I compressed the space. Then, I inflated the compressed space twice to avoid adjacent
corners. After I colored the inside of the polygon. And after, I brute-forced: iterated over each pair of corners, and
if the area of the rectangle was greater than the maximal, I simply iterated over each tile of the rectangle to check if
it doesn't contain ..
CGO_CFLAGS=-I${GLPK_PREFIX:?}/include CGO_LDFLAGS=-L${GLPK_PREFIX:?}/lib go run ./day10Today I learned a library to solve integer linear programming problems! I proud that I could formulate the problem myself as an ILP. However, I had to search for clues to understand that this problem can be solved with an ILP.
In part two I counted the number of paths from start to the first node, from the first to the second node, and then from the second to the last node. We can multiply them to get the number of paths from start to finish that cross those two nodes. To account for the order, we can do the same but swap the order of the first and second nodes. We add those numbers to get the final result.
Nice joke! Instead of computing optimal packing of the rectangle, we just had to compare the rectangle area with the minimal requested area by multiplying the number of requested shapes by the area they occupy.