Monthly Coding Challenge
Advent of code is a monthly coding challenge where in each day you get a puzzle and a follow on puzzle to solve. Unfortunately I didn’t write this post until I had most of them solved, so a little bit of what I was doing at the time was lost. On the bright side though, the hardest problems (for me) are the ones that probably have the most detail listed below.
Once you start getting further along in AOC, the problems don’t allow you to pick brute force solutions, and even better (or worse) the problems are designed where there is an easy brute force answer that doesn’t work, and then you have to go figure out the correct way to do things.
The trickiest part of this problem was actually reading the problem. Even after someone at work told me this, I still missed it the first time and stopped processing one time through instead of running through over and over till I got the answer. Make sure to read carefully.
This was mostly reformatting input data into an array and then finding the values needed.
This was one of these problems where I just walked away from it for a few days, and let my brain work on it in the background. I ended up creating a recursive solution that fills out the map correctly in the end. There is defiantly room for improvement here (slow), but I ended up getting two forms of visualization and an animated gif of it running.
This was actually the last puzzle I solved, because it seemed like a pain in the ass at the time (and it kind of was.) But I lucked out because in a later puzzle I learned about dijkstra’s algorithm, and that made finding paths to people in this puzzle much easier. Also, when you use a state to check if a player is dead (as opposed to removing them from the array of players) make sure you filter those out EVERYWHERE you check stuff, that tripped me up for awhile.
The first part of day 19 was pretty easy, just push the code through the elf code runner I wrote. The second part was a bit harder, as you needed to actually figure out what the code was actually doing. I actually skipped this part, and came back to it later, and by that time I had written a simple visual debugger for elf code so I could watch it run through. After watching many iterations of the program running over and over I finally realized that all it was doing was finding all the numbers that register 1 is divisible by and then adding all those numbers together. Once you do that, a program that takes centuries to run, turns into a program that runs in about a second.
This came up a few times during the challenge, using numpy with pypy was 2 twice as slow (or more) than just using python. The second part of this ran 1 minute 30 second under python with the sample program, and 2 minutes 30 seconds with pypy while I was using numpy arrays. Switching from a numpy array to a python list took the runtime down to 12 seconds.
Here is an article from pypy on making your programs run faster.
Eventually I figured out that you can’t brute force this problem no matter how much you optimize your brute force algorithm. Then I found Dijkstra’s algorithm , and after some more head banging, I finally got the correct answer. Although I had to expand my search area a bit to actually get the correct answer.
One of the places I got stuck on this problem, was I was trying to calculate the equipment change in the wrong place, the equipment change is actually another node on the graph. Once you see the final solution, it’s quite eloquent (especially compared to the brute force version.)
I was stuck on part 2 for a bit on this one, and I finally broke down and checked out how other people were doing it. (which I guess is a good thing, because this means I actually learned something.) I used Z3 to write an optimizer to figure out the values, and in the processes I added a bunch of comments on how it works for future me, and learned all about Z3. Will definitely be using this more in the future.
Another part of programming, is to know how to know what tools/data structures go to what problem types, and how to look at a problem and figure out the problem type. (optimization, path finding…etc) Day 24:
I think the hardest part of day 24 was parsing, and reading the instructions over and over. Coding was pretty much straight forward, the only bug that hung me up was allowing people to select a unit they would do no damage too. Also, print out debug output helps you see when you program goes into a loop, so when you increase the attack points for the immune units you get into a case where you have 2 sets of units that can’t attack each other, and will keep looping your program unless you stop it.
The part I got stuck on here, was when adding a new point, you have to go back and look at all the old points to see if anything is in range now. I solved this issue by first finding all the points connected, and then following all the connecting points and adding them together. Conclusion
AOC is a great way to improve your coding skills, and figure out the correct way to use data structures (linked lists are horrible for searching through). Don’t make it about finishing before other people, make it about learning new things, and finding (or building) new tools to help you solve the problems. If you get stuck, find different ways to visualize the data; also work the problem out on paper, even if you can’t work it all the way out on paper, the process of just writing parts of it out will trigger your brain to think about the problem differently. Don’t try to solve problems in your head, your brain and memory can only hold so much information. Get your ideas out on paper, and free up some space in your brain to think. If you get stuck, just walk away from the problem and come back to it later. Don’t worry, your brain is still working on it. Screw that Goblin Vs. Elf problem.
All my code can be found on GitHub.