These are my scripts for all the puzzles at https://adventofcode.com/2023 I will be uploading all days that I solve with a short commentary on thought process/description. All the puzzles (with the exception of Day 17) have been solved without looking up any hint related to the event. Note that my naming process for the input texts is input + the date. So for the first day, it was input1.txt, the second day input2.txt... etc.
There is not much to say about part 1, you just iterate through each line forward or backwards and pick the first number you see then concatentate them and sum all those for each line. For part 2, it's a bit trickier since there are numbers spelled out. A first idea is to replace the spelling of the number with the number itself (for example replace "two" with "2") which could work but there are issues. The main issue is when two spelled out numbers share a letter (like "eightwo") here if you replace the "eight" it will be "8wo" but then you lost the "two". The safest way to do it is to replace each spelled out number with the number but also the first and last letter of the spelled out number. For example "one" is replaced by "o1e", "two" by "t2o", "three" by "t3e"... etc. No spelled out number combinations share more than one letter so this is enough.
Day 2 was the first day I solved from the advent of code (shoutout to Alex for showing it to me). It was fairly easy in part 1 we just needed to implement a condition on each game and see which games fulfill that. On part 2 instead of a condition we just need to see the minimum amounts of each color of cubes that are needed for each game to be possible. Then multiply them together and add those numbers for each game.
Day 3 was my second day of advent of code and it was a very interesting one. For part 1, we have to find the numbers in the input that are adjacent to a symbol. To do this I iterated over the input until I found a symbol then "looked" in all 8 directions for numbers (being careful to include the whole number) and then I erased the number to not double count it. Part 2 was also interesting as it was asking us to find the "" symbols that are adjacent to exactly 2 numbers. My solution, even though it gives the correct answer, does not take into account an edge case. It does not take into account the case where a single number borders two different "" symbols. However, judging from my input the inputs might be hard coded as to avoid this. Regardless I could have made the code resistant to that edge case possibly with a bit more time. The code itself is basically the same as part 1 but only accounting for the "*" symbols and only those that have two numbers adjacent.
Part 1 is just comparing lists and finding matches. For each match you multiply the value of the card by 2 (or set it to 1 if it was 0), then you add all the values of the cards. Part 2 is much more confusing now instead of increasing the value of the cards, matches increase the number of future cards you get. The way I solved it was by using a list of the multiplicities of each card that I had and increased that number according to the instructions. So if card 6 had multiplicity 5 (i.e. I had 5 total copies of card 6) and card 6 had 7 matches then I added 5 to the multiplicity of cards 7 8 9 10 11 12 13.
Day 5 was one of my favorites and one of the most difficult. Part 1 was a bit of a hurdle writing all the mappings. The key is figuring out that each mapping (for the range that it operates on) is just adding the difference of the beginning of the image (where it takes you) of the map with the beginning of the domain (where it came from). Part 2 was much more difficult, in principle it was the same logic as part one, however, the number of seeds now was huge since instead of individual seeds they were now ranges of seeds. Computing them 1 by 1 was not an option. The way I solved it was that instead of operating with the maps on the seeds individually, I operated on the ranges. So I processed each range through the maps, splitting it accordingly at the map borders and it turned out pretty nice. Code was pretty tedious to write but it runs almost instantly so I am very happy with the result.
I had been wanting to do an exercise in some form other than python so day 6 seemed to be the perfect specimen. Indeed day 6 is simple algebra if done right. All we have to notice is that the distance traveled with respect to time has a symmetry along an axis. That is the distance is
Day 7 was a fun little exercise. The main theme is evaluating hands in a game similar to poker. The evaluation is based primarily on type (five of a kind, four of a kind... etc.) and secondarily on the strongest card in hand (from left to right). To solve this I implemented an evaluation function. It evaluates each hand in base 13 (since there are 13 different cards). The last card in hand counts for its value times
Day 8 was fairly straightforward. The key idea for part 1 is using a dictionary to easily move between locations then once you reach the location "ZZZ" you are done and you check the number of steps. Part 2 has a small trick into it. You basically have to do the same procedure but for multiple locations simultaneously and you only finish when all of them finish. You can't use the direct way because the number of steps is too large. To solve this you must see that all movements between locations are periodic for each initial point and you can calculate the period for each individual starting location using the algorithm from part 1. Then after finding all periods, the result we need is just the least common multiple of all the periods we found.
Day 9 was also straightforward. The solution is pretty much presented in the example. The only important thing to notice (in order to extrapolate the data) is that in the example, the extrapolating diagram has a "Pascal triangle" type of condition (but with subtraction instead of addition). With that information we can easily do as in the example and extrapolate the next value. Part 2 was the same idea but instead of extrapolating forward, we extrapolate backwards. The solution is pretty similar to part 1 though.
Day 10 was essentially finding the length of a loop that was made with ascii characters in the input file. The code is a bit inefficient since it checks all four directions around the starting point (and so counts the loop twice) but it is still basically instant so I didn't bother to make it better. Part 2 was a bit more interesting as we had to find the area enclosed within the loop. To do this I just counted all the tiles that were within a parallelogram that contained the loop and then checked whether each tile was inside or not. To find out if a tile is inside I had to use a bit of topology. Essentially I ran the loop in one of the two directions and assigned to each tile of the loop a value depending on if the loop ran left or right through that tile (or value 0 if the loop ran up or down). Then for each tile potentially inside I counted how many "left" and "right" tiles it encountered when going up. If the total "leftness" is 0 then the tile is not inside the loop. The only thing to be careful is that if the tile is a corner tile then its left/right value is halved.
For part 1, I just did as instructed and expanded the universe, then I just made a list of all the positions of galaxies and used the taxicab geometry to find their pairwise relative distance. For part 2 you could in theory do the same thing as part one but with a bigger expansion coefficient, however, this is not computationally efficient (or realistically feasible) so you have to go about it in a smarter way. The way I did it was to just mark the positions of the galaxies on the unexpanded universe then check how many rows and columns are to be expanded between them and add that to their relative distance.
Note, day 12 was completed after almost every other day (except days 17 and 25 part 2). Part 1 was easy to solve with the brute force method, even though it was obvious it is not the most optimal method. Brute force being the method of checking every possible combination of "#" and "." that fit the pattern and seeing if it's a valid configuration. Part 2 as expected was way more computationally heavy so the brute force method wouldn't work. The method I employed was trying to implement all the techniques that someone would try when doing the computation by hand including finding which series of "#" go to which spot and excluding some combinations beforehand. Another important function that sped up the process was the one that calculates the number of valid configurations when having a string of length n consisting only of "?" and we input k times "#" but only one at a time. The function uses a simple recurrence relation:
Day 13 was pretty easy. For part 1 we just have to compare lines or rows to see if they match. part 2 is basically doing the same but while changing one character in every pattern. To find which character we have to change, we just try all of them and find which one gives a new reflection line.
Day 14 was interesting, the first part was pretty easy, we just have to check for each "." whether there is an "O" or a "#" somewhere below it, if it's an "O" then we swap the two. Then after doing that for all entries we just calculate the load based on the position of the "O"s. Part 2 was a bit more interesting, it involves tilting the pattern in other directions than North. To do that I simply made a function to rotate clockwise the whole pattern and then rotated North as before. The interesting part comes from the fact that we need to do a whole cycle of rotations a billion times. Clearly that is not computationally efficient so we have to find a smarter way. My guess was that after a few cycles the pattern would reach a stable position which would not change with more cycles. What actually happens is that the pattern enters a loop of positions that alternate periodically. To solve it I just ran the cycle enough times to reach this periodicity and then I calculated the period (which was 18, this was done by hand but it wouldn't be hard to add the period calculation into the algorithm). Finally, I only evaluated the positions
Day 15 was pretty easy, the first part is just applying some hash algorithm. The second part was confusing to read but it's pretty clear from the description that we are supposed to use dictionaries which make the puzzle pretty easy.
Day 16 was a nice puzzle. It is mainly following algorithmic instructions for the "beam" and then handling the multiple beams that pop up. The way I solved it was to just follow one beam and whenever it split I continued on one path and appended the other beam to a list of beams. When the beam reched a wall or went to a space and direction another beam has already been to then I'd remove it from the list. When the list is empty then all the beams would have been accounted for and then we can just count the tiles it has been to. For part 2 we have to do the same but for all directions and initial positions (along the border) and find which one energizes the most tiles. Honestly, the shape is not that large so the border is in the order of a few hundred tiles. I did the brute force way and I got the answer after a few minutes of runtime. There is probably a better way considering this part alone has a runtime greater than the combined runtime of all other days and parts but I couldn't think of it and a few minutes isn't that long. I thought whether the part where the beam hits the wall gives the same value as the beam coming from that wall but the beam path is not reversible (because of the splitters). To be hones,t seeing as all the energized values are either ~8000 or around ~100, the solution might be that there is a tile and direction that if the beam goes through then it picks up a huge amount of tiles (but always the same amount since it's the same beam) so whenever it hits that tile we can just add the amount and forget about doing the calculations. However, it might be too annoying to code that solution after solving the problem. If I solve everything else then I might return to this one to do it better
(Note that Day 17 was completed much later than all the days with the exception of day 25 part 2 which required day 17 to have been completed prior). Day 17 was insanely difficult for me. The premise was finding the path that would give the lowest "heat loss". Initially, I tried finding a random good path and optimizing it. However, all my attempts didn't amount to anything. After new year's I just tried running some algorithms to optimize the paths occasionally but nothing came out of it. Then later I decided I'd see a hint and the only hint I saw was a comment saying "change the map instead of finding a path" or something like that. So what I ended up doing was the following: I attempted to find the "least" heat loss value for each block. In fact, given the restrictions of the puzzle, for each square there would be 12 possible states with different "minimum" heat loss. That is because the puzzle says that the path is only allowed to move 3 consecutive blocks in one direction so for each block I had to find the least heat loss in the combination of the 4 directions and the 3 states of having moved in consecutive blocks (e.g. 2-right, 3-left, 1-up). To do that essentially we just check the surrounding blocks. Then we would have to iterate over all blocks, and multiple times, that is because depending on how we iterate, sometimes we would have to backtrack, i.e. the quickest path to some block might be coming from a block that is "after" it. The most natural iteration I could think was to iterate over the diagonal. That is, in matrix notation first do it for the block [0,0]. Then for blocks [1,0] and [0,1] then for [2,0],[1,1] and [0,2] etc. As mentioned before, we would have to repeat this process a bunch of times (in fact we would have to repeat for as many times as the minimum path takes a direciton towards "earlier" blocks in the iteration. Finally, we need to check the final block and find its shortest value among the 12 states. For part 2 the puzzle is pretty similar. In fact because part 1 was so hard for me, I was concerned for part 2 a bit. However, it turned out to be pretty trivial with the method I used earlier. The only difference is that now the path must travel at least 4 blocks in each direction before turning and at most 10. I just changed the states of each block to be 40 (reflecting the 10 consecutive blocks times 4 directions) and tweaked it a bit to account for traveling at least 4 blocks in each direction. For both parts it should be important to note when to stop iterating. Theoretically, there is a finite upper bound after which all states will be optimized and we would have the answer. That bound is far too high though to actually perform that many computations, instead I just computed until I got the condition that the states of the last block remain unchanging. That condition proved to be insufficient for part 2 but it just required ~30 more iterations and it worked. Again theoretically it should work for every input after a certain number of iterations so the amount of times needed to perform this might need to change from input to input.
Day 18 was another interesting puzzle. Part 1 wasn't that difficult. The main point was "drawing" correctly the shape and then finding a way to tell whether a space is inside the shape or not. The way I did it was using a bit of topology (similar to day 10). The curve went clockwise so it means that when approaching the curve from the west, we will first hit a region where the curve went "upwards". As long as the "upness" is positive (and not 0) we are inside the shape. When we hit a point where the curve goes downwards then the "upness" goes back to 0 and we are outside the shape. A little care needs to be taken on corner points which in order for the algorithm to work, should count as half the "upness" of edge points. Part 2 now made the shape much much larger. Counting individually the spaces inside is no longer feasible so we have to find a more efficient way. One thing to notice though is that the shape still remains as simple as in part 1 (meaning it still has the same amount of corners), its size is just larger. We can take advantage of this and realize that the vast majority of rows will be duplicates of other rows (similarly for columns). So I used what I called "important rows" (and columns). Those are the rows and columns that contain corners (as well as the rows and columns next to these). Then we just have to evaluate what happens on those rows/columns and then everything in-between is just a repeat of what happened in the last important row/column. This method makes this very large computation almost instant.
Day 19 was very interesting. Part 1 was just translating the commands of the input into commands in code. To solve it I used a nested function which terminated when the configuration was accepted or rejected. Part 2 is where it gets interesting. Here we had to figure out the configuration space of the parameters that are accepted. To do this I used a similar function to part 1 but instead of a single configuration it uses ranges of configurations as input. When it hits an instruction (such as an inequality), the range splits and the function is called again with the new range. If finally some range gets accepted then the size of the configuration space is added to the sum.
Day 20 was also interesting. The first part is an implementation of how the "mechanism" works. Part 2 is once again the tricky one. The solution I did was maybe a bit of a meta one. I had a look at the input and saw that in order for the module "rx" to produce the needed pulse, it needed modules "dt", "ts", "qs" and "js" to produce a high pulse simultaneously. Then it was just understanding that these four modules are independent and produce a high pulse periodically. Then it was just a matter of finding the period of the four of them together. To do that I just multiplied their individual periods (it would have been more correct to use the least common multiple but the numbers didn't seem to share any prime factors so it didn't end up mattering).
Day 21 follows in the same footsteps as the previous days. Part 1 was just an implementation of the rules. Part 2 is where once again the exercise gets tricky. To solve it again we have to look a bit at the input. First of all, the starting point "S" is in the center of the input. Secondly, the number of steps (26501365) modulo the length of the grid (131) is 65 which is exactly how many steps we need to go from the center to the edge. This means that at the end of the steps we would have reached exactly the edge of one grid. This isn't obvious because the "progression" of the steps could always be slowed down by some "#" symbol. But once again, if we look at the input we will notice that on the row and column that "S" is, there are no "#". Furthermore, on a small diamond-shaped region starting from the top of the grid and going to the east, then south, then west, there are no "#". Now it is obvious that calculating the number we need the brute force way is not feasible. So we have to use the previous clues to help us make the problem easier. Putting it all together we can infer that at the end of all the steps the process would have covered all odd, non-cut-off, "."-blocks that are within a diamond region, starting from the top of the grid that is floor(26501365/131) grids above the starting one and going east then south then west. To accurate calculate that we need four parameters. First is the number of odd blocks that get covered completely by the process on one grid. We need that because many of the grids that are inside the big diamond will be odd and they will be completely filled in. Then we need the number of even blocks that get covered. We need that also because we notice that once the process jumps from the initial grid to an adjacent one then instead of filling in odd blocks we fill in even blocks. Finally we need two more calculations: The number of even and odd blocks that get filled in when we only do a single diamond process (aka running the process until it reaches the border). We need that because we can notice and calculate that all the grids we need to count are actually combinations of those four parameters. The exact formula is a bit cumbersome to derive but it mainly requires counting which grids inside the diamond are even, which are odd and then adding together the partly-filled-in grids on the boundary to get full grids and diamonds. Finally, I will briefly explain how to obtain the four parameters. The diamonds for even and odd we get by doing the process for 64 and 65 steps respectively. To get the even and odd number of blocks that get covered when running the process to its completion, we just need to pick a very huge (even or odd respectively) number and run the process with that. In practice, picking a number slightly larger than the length of the grid should be enough.
Day 22 wasn't too hard conceptually but you could fall into traps as I did in part 2. Part 1 took a while but mainly because I established a ton of dictionaries which allowed me to use different parameters as keys (for example the brick id, the height and other stuff). It would have been better/easier to use a dataframe but I didn't want to bother too much with external libraries. Part 2 would have been easy and after a lot of trying I had a very nice solution but I made a critical mistake. Esentially what I was doing (partly unintentionally) was iterating over the bricks based on height and I would stop if I didn't find the bottom of a brick. That caused a problem because there was a case where a brick of height 4 was supporting another brick on top but the algorithm would stop before seeing that top brick which caused a very slight error in comparison to the actual value. The overall solution is as follows, for each brick I create a list with only itself, then I check if I remove all blocks that are in the list, what blocks will fall. Then I add those blocks to the list and so on until I reach the top. I initially tried other ways but they either overcounted or undercounted, for example naively you could say that if I remove a block then the number of blocks that would fall is the sum of the blocks that would fall if the blocks that are supported by the initial block were removed. That would be wrong though since it overcounts the blocks that fall by the action of multiple other blocks and undercounts blocks that would fall only if multiple other blocks disappear. Finally two very important dictionaries that I had were what I called "brick_stability" and showed basically for each brick, what other bricks does it "touch" (one dictionary for the top, one for the bottom). This was essential in determining whether a block was entirely supported by another below it or not.
Day 23 was similar to the previous days. Both part 1 and part 2 require us to maximize the path length. For part 1 the path is fairly simple so the brute force approach, i.e. just counting all paths and picking the longest works. Part 2 increases the number of paths significantly so it requires a bit of optimization. In part 2, with the "icy slopes" removed, the whole path is pretty symmetric (meaning if you can walk from A to B then you can walk from B to A). Furthermore, all "intersections", that is, all the tiles that branch out to three or more directions, are a single tile long. Given that information, the puzzle can be reduced to a Graph Theory exercise. If intersections are the vertices of the graph, the paths that connect them are the edges of the graphs. Then the problem becomes a problem of connecting the first and final vertices through the longest path possible (and without visiting the same node more than once). There is also a small ambiguity if there are two different paths connecting the same pair of vertices but then we just take the longer one (there is no case where we would ever need the shorter one). Now the problem is much simpler computationally. We can then use the brute force approach keeping in mind the restrictions.
Day 24 was about (or at least one way to solve it was) solving a system of equations. For part 1 we just need to solve a standard 2x2 equation for every pair of trajectories. I did it by using the determinants method. Part 2 was much more difficult as expected. We need to find the perfect initial position and initial velocity of a rock so it would hit all the hailstones sometime in the future. If we take a good look at the system, we'll see that it's overdetermined. Meaning we have more equations than unknowns. Knowing this fact I tried solving this problem as a mathematician which might not be the most efficient way. For every hailstone we have an equation of the form
Day 25 part 1 was an interesting exercise in graph theory and slightly topology. We essentially have a graph and we need to find the three edges we need to cut in order to make it disconnected. More precisely we need to calculate the size of the two disconnected sets of vertices. My approach was the following: find a sizeable "core" within the graph that most likely belongs to only one of the nearly-disconnected sets of vertices. Then try to find as many other vertices as possible that also, most likely belong to the same set. Then take the complement of that set and do the same there while removing the elements here from the previous set. If the initial core is sizeable enough this procedure should stabilize and should give us the two nearly-disconnected sets. In more detail I started from a random element in the graph and then I moved around until I had a big enough circle. Then I took all of the elements in that circle that were connected by at least three vertices to the rest of the circle. This is now the core. These elements most likely belong to a single set of the two. Now from every other element not in the core, I added to the core whichever element had at least two vertices connecting it to the core. Note that this is not mathematically rigorous but if an element is connected to a set with two or more vertices then it is most likely part of the set. The alternative would be that both of those vertices have to be cut in order for the two sets to become disconnected which is unlikely to have that on a single element. Afterwards we take the complement of the elements we considered so far and yet again perform the two vertex condition on every other element. We continue this procedure until the two sets don't change in size. Then these two sets should be the two nearly-disconnected sets we wanted to find. Note again that this procedure might not work on every input and it might need some tinkering to work on other inputs but in principle it shouldn't need much change. Part 2 of day 25 requires to solve all previous problems so I will return to that after finishing days 12 and 17. Update: apparently part 2 just needs us to complete all previous puzzles and there is no puzzle for itself so I guess there is nothing more to post.
All the puzzles were pretty fun. Some were tricky and clever. It was fun solving them as they came out. The puzzle the took me the longest was day 17, that is probably because I was stuck thinking about finding the best path. Once I got out of that mentality with the help of the hint, I solved it within a few hours. Day 12 part 2 was also very hard for me. I had to optimize the problem to an extreme degree in order to have a computation in a reasonable amount of time. Another day that was pretty memorable was day 5 which is when I truly realized that I'd have to think of some tricky methods to solve the puzzles. Overall I had fun doing it, there was very much a difficulty variance in a lot of the puzzles, some were very easy, some were extremely hard (which might have to do with people's backgrounds too). Depending on my free time I might do it next year too. I am not sure if I will come back to this repo, maybe I might optimize some scripts or fix some typos in the future. Thanks for reading!