Monthly Coding Challenge (work in progress)
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.
(post is still filling in, eventually I’ll have comments for each day; check github for the code for each day.)
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.
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.)
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.
- 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 the code can be found on GitHub.