Advent of Code 2015

Three quick things:

• Check Advent of Code for yourself!
• Brief info on what I’ll be doing here
• My Github Repo for AOC 2015

Without further ado, here goes!

Day 1

This is very much a warm-up exercise the instructions say. Processing characters and simply counting up and down. I thought it’d be funny to have a Santa class that can count, so there’s that.

Day 2

First of all, don’t use feet as a measurement unit. That’s clearly the reason elves are having some issues!

Joking aside, this is a really nice intro to parsing strings (i.e. extracting numbers) and making sure to read the instructions carefully. Both of these become increasingly important with more complex exercises down the road. Again, totally unneccessary to have a Present Class, but hey wouldn’t it be nice if presents measured and packaged themselves?

Day 3

Now this is where it starts to get really interesting. Two dimensionsl grids are a frequent companion in this sort of exercises and for a good reason. They offer interesting puzzles having to think about multiple dimensions while at the same time this is still something that can easily be visualized.

In this particular case though, Santa moves in only one direction, one move at a time. And the total moves he makes are going to be less than 10000 (depending on your input, I’ll use 10000 as an example). Not only that, but we are also immediately told that he will be visiting some houses multiple times (drunk elves lol). Let’s also assume that the most Santa moves in any given direction is 1999 units. Therefore, his movement will be contained in a 2000 x 2000 grid.

Using the numbers above, if we want to pre-create a grid that will be guaranteed to capture any sort of movement Santa does, and, even assuming he never goes to the same house twice (which we know he does), we would end up filling 10000 units out of a 2000 x 2000 grid, so only 0.25% of the grid. The vast majority of it would be useless!

This is why I decided to instead, save each grid point as a key in a dictionary and expand it as needed – as santa travels. Alternatively, we could cut down the 2000 x 2000 to the minimum needed, or, to get even fancier, use a sparse matrix representation (in Python that can be obtained in scipy) – i.e. a matrix that basically doesn’t consume memory for zero values.

I have commented this out in the code, but feel free to try it. In my case, for Part 1, optimizing the grid as much as possible, here’s the differences (in bytes): Sparse matrix representation wins, and the dictionary is still smaller than the numpy array with the smallest possible dimensions to accomodate for Santa’s travels;

Now if this were a real world problem, another thing to consider would be speed of execution – which I didn’t measure here. We’d have to compare how quick it is to gradually fill in a Dictionary as opposed to having a prebuilt grid and filling it in that way.

I’ve also plotted the density of Santa’s visits, just for fun – there’s going to be a whole bunch of unhappy people (all the white spaces) and a few incredibly happy ones (the yellow spaces, visited around 16 times)!

Day 4

Aight, full disclosure: I tried reading up on MD5 and hashes and quickly decided – if the text of the exercise is too lazy to provide me with descriptions of how this works, then I should find a library that does it.

import hashlib

And there it is, day 4 solved, EZ.

To be fair, in everyday practice, this is actually an important question to answer: “Is there a library/module that already does what I want to accomplish? Is there a cleaner or more optimized way to do it?”

Day 5

The biggest insight for this one, I believe, is to flip the logic on its head. Since a “nice” string has various requirements to be checked, it’s more efficient to quickly flag it as “naughty” as soon as it fails one.

Besides that, this is where me personally, I like to use LLMs to try to optimize code or see a different way of doing it (i.e. this can 100% be done with for loops). In doing so, I learned that the “zip” function in python can be used to bind together two lists that aren’t of the same size! It will still match them and cut off the end of the longer one, basically. Who knew! Also, I’m pretty sure that’s not a very safe practice, that would likelly make a Rustacean’s head explode, lol.

Day 6

Remember how on day 3 I said that a grid was not necessarily needed? Forget that stupid advice.

This day is also the first time I saw it useful to resort to using regex. Just a simple one in this case, to get the numbers out of instructions. The trickiest thing here is to make sure to access the correct coordinates in the grid and apply the right instructions.

I do also want to add something that should be common practice, but I myself (too often) forget. Which is, when checking for possible conditions, to account for any unexpected ones. In this case, “turn on”, “turn off”, and “toggle”, but what if there’s a typo? Some of the elves seem to be getting drunk, how do we know Santa’s not too?

Anyway, I had regrets after plotting part 1, but part 2 actually looks really nice!

Day 7

This puzzle can be somewhat tricky to solve, as there are different conditions and logic that needs to be implemented. Each on its own, not a big deal, but as the lines of code add in the program, it does become a little unwieldy. I absolutely recommend testing each piece of logic separately before getting them all together.

Also in retrospect, I think it would’ve been better to design a program that continuously loops through the possible equations until all are solved. Each loop would only finds the equations that can currently instantly solved (i.e. 123 -> y) and ignoring any that require other equations (for example y -> d if we don’t yet know the value of y). In the second iteration, y -> d could be solved and so on.

Instead, I added another layer of complexity and code spaghettification by essentially making a recursive function. I thought at the time that would be better as it would avoid looping over the equations and basically just follow the chain until an equation that could be solved. Looking back at it though, it became quite a beautiful mess.

Lastly, as this can be easy to miss, the puzzle uses 16 bit type integers. Meaning that there will be overfloww and the int resets to 0 after hitting the max value.

Day 8

Ahh, lovely string escape characters. One of the reasons why Windows’s backslash ( \ ) sucks so much compared to Unix forward slash ( / ). The solution to this exercise is deceptively simple using Python + regex. But figuring out the correct escape characters and what to search for … That for me was the crux of the issue.

In particular, what caused me a lot of headdache was the fact that I did separate regex searches without removing what was found. So when I went to search for backslashes ( \\ ), I accidentally re-counted some quotes and hexes. And even as I was fixing that, it took me a while to correctly exclude actual hex values, versus the fake ones (example: \x5z may look like one but it’s not, as the letters only go up to f).

I’m surprised I’m not dreaming in regex not.

p.s. yes, just like with day 4, you can find a library that evaluates the strings correctly making this puzzle trivial.

Day 9

Ah yes, the classic travelling salesman problem. I briefly considered looking into how to make a graph in Python and optimize travel route doing so. It took me a whopping 15 seconds to say naaaah … At the end of the day, there don’t seem to be too many possible destinations, let’s permutate!

The biggest insight that I can share here was to create a double dictionary. Yes, that duplicates some values, but it also makes it super easy to unpack. Just pick any 2 cities, in any order and throw them in there – bam, get a distance.

Day 10

This is a really cool sequence I didn’t know about! Definitely check this puzzle!

Otherwise, this is also an excellent example of the importance of optimized algorithms. For python, this little thing is much faster than for looping and I needed to use it for part 2 of the puzzle:

from itertools import groupby

As a side note, as a physicist, I have to add this (absolutely unnecessary for the solution of the puzzle). If you watch the video provided in Advent of Code, you’ll learn that there’s a Conway constant, that approximates the length of the series well as it increases. Well, going from 40 to 50, and using the constant, the calculated (approximated) result is only 0.00246% off. In the real world, I am damn near sure that would absolutely fall within the measurement error – i.e., the real measurement would have an error rate higher than that and therefore, my approximated calculation would be nearly as good and indistinguishable as the real one. Thanks for coming to my TED talk.

Day 11

What can I say. The importance of standard libraries, lol. The fact that there’s an easy way to increment at least a-z by converting to unicode and increasing by 1 is fantastic. Otherwise I’d have to write a function that basically teaches the English alphabet.

Besides that, this puzzle pulls some tricks from other ones (like making sure to go for the easiest condition to invalidate a pwd) and just requires correctly setting it up – for example, working from the last letter to first and correctly incrementing it one by one, much like you would with addition.

Day 12

I think most programming languages have a way of reading a .json file in, but for the first part of the problem I decided to just ignore it and treat it as plain text instead! … for part 2 that would’ve added way too much complexity, so reading .json properly and then just being smart at recognizing which parts to ignore! (note: you might have to change the extension type of the file you downloaded!)

Day 13

This one was basically a reiteration of Day 9 for me (at least how I structured it and thought about it), with just two slight adjustments: one is that the last person in the circle needs to be connected with the first one, and the other is that when checking two people, each has to have their score adjusted.

Afterwards (completely unneccessarily might I add), I used an LLM to get a base setup drawing of a circle and played around with it until I had it looking as I wanted.

Day 14

This puzzle is a good example of a “ah damn it” moment. That is, sometimes I get lucky and the way I setup the first part works great to amend it for the second one, but not here. See, here I thought I was being clever and efficient by using the int dividing and remainder to calculate how far away the reindeer got! Straight to the finish line!

… And then part 2 is like, nope, back to the drawing board!

Also, Santa’s just hateful! Using the first socing system at least the competition was fierce, the second one? Not even close! (I’m not showing the actual points as the author of AOC requests not to share any of that info – but the higher the bar, the more points a reindeer got relative to others).

Day 15

For this puzzle, I imagine it’s much better to go find an algorithm that’s able to find the maximum of a function with four variables… Which of course, I didn’t do. I often rely on various min/max algorithms with machine learning so here I decided to instead, do it myself.

I decided to take 2 ingredients at a time and change their content (increase one / decrease other) until I got tho the max score. And then take another 2 ingredients and keep repeating. There’s no particular reason to do it 100 times (in fact, it’s overkill – I could write a logic to stop repeating once the max doesn’t change).

And then part 2 once again slapped me upside down and required a different approach. The only good news is that with part 1, I got peak cookie with max score – so the goal is now to reduce the calories from this point. I could not think of a great way of doing this other than trying all possibilities that would accomplish this goal, using recursion and deepcopies.

This is one aspect that can be very complicated in programming in general – what is mutable and what is immutable? In other wrods, do I want to change the value of x, or do I want tokeep multiple copies of x around, with different values?

Day 16

The nice thing about Advent of Code is that after a challenging problem or two, there’s frequently a breather. This one was fun, short and sweet. Just figure out how to parse the different items that aunt Sue(s) have and complete some simple checks! Time to start getting coal to the 499 Sues who didn’t give me a present …

Day 17

And another day using combinatorics! Here I had to reverse course from my initial idea of selection, because some container volumes are repeating, but they have to be considered as different.

Bet these elves are blasting Korpiklaani while getting wasted …

Day 18

Aahhh, Conway’s game of life, one of my favorites! Need I say more? The challenge here is to correctly identify the boarders, counting cells properly and updating all at once!

Day 19

The first part is pretty straightforward. Just finding the molecules and replacing. And then part 2. I think so far this has been my most challenging one to solve. I tried all combinations starting from e, I tried going from the back and replacing. Thought of optimizing the length of replacement. And so on. Not going to lie, I was getting stuck pretty bad.

I then ended up browsing Reddit to see if there was a mention of an algorithm that I wasn’t aware of. And somehow, somewhere I saw the word “random” and it clicked. I shouldn’t be trying the same replacement multiple times in a row! Instead, randomly pick a different one and keep going! Low and behold, that worked. Phew, a little longer and Santa might have to put Rudolph down.

Day 20

In tretrospect, this is a prime case example of where a small stupid decision has long lasting reprecussions. When I first started this, I attempted to find all the divisors up to the number / 2. I didn’t think much of it, but the program was taking too long to execute. So I tried being smarter with the way I search (not check every house, but maybe every other, or try to find the lowest common multiplier, etc…).

Turns out, I should’ve gone with my initial gut (and remembering that to try and find the divisors of a number you only need to go up to the square root of that number). Lessons learned!

There’s definitelly more interesting stuff that can be done here, but for starters, it appears that both the max and mins are getting wider apart comparing the Motivated elves (infinitely delivering presents) vs the Lazy ones (stopping delivery at 50 houses – better watch out, or be replaced by Amazon soon!).

Day 21

I really enjoyed this puzzle, and not only because RPGs are great! The main insight was to simply construct all the possible combinations of weapon, shield and rings, adding the No Shield or No Ring (and I mistakingly initially let the option to NOT chose a weapon – which can’t happen). And then try, from cheapest onwards (or vice-versa)!

Also, every chance I get, I recommend Elden Ring to people. The world created by George R. R. Martin, and masterfully turned into a spectacular game by Hidetaka Miyazaki (From Software). BEHOLD, DOG!

p.s. no I don’t count Dota 2 as an RPG. Dota 2 is a way of life.

Day 22

In my view, this was probably the hardest puzzle of them all, and definitely one of the most fun! I couldn’t think of a good way of optimizing it, so instead, just simulate different possibilities (casting any and all spells) and seeing what happens!

This is also an excellent example of where a simple oversight can completely derail and add to the time needed to solve something! In my case, I accidentally wrote it in such a way that new spells reset the armor back to 0, instead of continuing the count. Whoops.

Besides that, the way to optimize this would be to exit the functions not only when too much mana has been used, but also when arriving at same game states with more mana used (i.e. same hit points / effects). Oh well there’s going to be other chances for that!

Day 23

After that hard magic work, back to the real world with registers! And with it, the solution is pretty straightforward as well. A bit more regex and a reminder that re.match is in most cases not nearly as useful as re.search.

Day 24

The weight limits how many combinations are viable! Ha, who said quantum entanglement is challenging to understand? In all honesty, fater Day 22, it was quite pleasant to have a relaxing few to follow.

Day 25

Another one that I quite enjoyed – figuring out how to determine which number it is in succession based on row and col. Once that is solved, all good to go and Let it Snow!

Aaand we’re done! Thanks for reading, see you at next year’s page (once I get to it)!