How: Not to do the Advent of Code
The thought process, failure and results of a mathematical beauty in a game puzzle...
New Year - New Challenge
Thanks to the lock-down and to the beginning of the New Year! I decided, as many other year-cycle-enthusiast, to exercise a bit more.
In my case, it goes top down, including legs, arms, shoulders, hips, abs, and brain too. That is the reason why, I decided to punish those linear-travel-brown-switches and set the mind in game-on mode to resolve the challenging puzzles of the Advent of Code 2021.
Link is here: About - Advent of Code 2021
What is it interesting about resolving Puzzles?
I should start by saying that I literally suck at solving puzzles, my wife Virginie and my son Nacho, can put together a physical puzzle of 5000 pieces, like this last Christmas, in matter of hours, but for me to literally find the edges or even the pieces with the same motifs is like mission impossible.
Nevertheless, Math, Pattern, Numeric, Algebra, Series and Logic puzzles I love, and whilst the Advent of Code is about participating against the clock, and testing your ego against a leader board to find if your solution solves the puzzle in the shortest time, for me, the challenge is purely to engage outside of the daily noise, meetings, and used as a distraction allowing me to think. The wonderful moment to ponder about the problem and their potential solutions,
I use puzzles as an intersection between: Game Theory, Sociology, Art, Biology, Mathematics, Physics, History, Information and Computer Science.
But, hold on, how would it be possible to bring all those disciplines, all together? is it really possible? My answer is YES, it is possible. A problem is like a pyramid, it always offers many ways to solve it. Sentiment analysis in this article will clearly indicate that a level of proudness and glorification are correlated to the author words, but in total honesty... my interest is to present to you: all the failures required to arrive not just to the solution of the puzzle, but to a solution that makes you feel good.
I think Schopenhauer and Nietzsche would have enjoyed watching the Advent of Code, as it is according to their belief that suffering is the only thing that bestows value upon the world. And it is suffering what you feel when the computation you are trying to achieve, simply throws an "OutOfMemory" exception.
Let's see what this hypothetical game suffering is all about...
Being Quick or Being Fast
The good news about resolving the puzzles after the entire thing is finished, is that you could enjoy working at your pace, and competing with your mind, and challenging your knowledge. I must trust, that I have googled Advent of Code 2021 Day X just to find out, if there is anybody else, also blocked in the same question, or to find hints. But, as much as I dislike the idea of not progressing, I dislike even more the idea of plagiarism, or loose the faith that I can actually figure the solution out. Is sort of self-motivation, to proof to myself, that I could find my own way to solve the problem.
In fact, the motivation of writing this article, is because I spent 2 days, thinking in circles, writing in walls, and drafting in paper, what I am about to explain with some code examples in this article. At the time of completing successfully the puzzle, I was curious then to find analogies, or how my solution ranked across the pack... surprisingly, what I found, is that it did not match any of the ones publicly available, because most of them, focused in the use of simpler data structures or in literally implement an algorithm, as opposed to a population problem. A good example between the trades of implementing a solution, or thinking about the problem in hand. Matrix Population Models happen to be of great help here. Which is how I did arrive to the solution of day 6. Now let's find out all the zig-zags between my final solution.
Answering Part 1
I will skip the part of explaining the puzzle, but you can find it here:
Answering the first part was not hard.
The thought process to find this solution, overlooking what Kahneman prevent us in all his books, was about thinking too fast. And the process of reading something about a population and pattern repeating over time, pushed me to immediately associate it to a recurrent or recursive pattern easily translated to a recursive function.
Whilst this does the job, it suffers when the list exponentially grows, which is what happens when moving to the second part of the puzzle.
First Approach Part 2
Off course, I felt great, when I saw that the recurrent function converged after 80 days of iteration in the context of the puzzle, but then, my joy turned into tears, when I typed 256 in the function parameter "c", and started to feel my laptop's fan going crazy.
Then, I knew something was going on, and to avoid the quick and dirty "print" approach, I decided to fill a population variable just to get an idea of how big the array was becoming after 100, 150, 200 iterations. The new function looked like this:
With 200 iterations, before my laptop melt down, I realized that this list, already contained around 204 Million entries, and that indeed the growth was really big.
Then I thought, that I could split the problem, like breaking the populations into smaller problems, and then running them in parallel, but it didn't feel right, and again felt like throwing resources to the problem, the classic trying to go around the problem, instead of giving my brain another chance to understand the growth ratio.
Then I remembered Virginie, my wife, explaining in one of our breakfast chats, about the growth of bacteria in some of her experiments as a Bio-Engineer, and mentioning the importance of the "log" function for the interpretation of the growth phenomenon. And this, turned thought process into investigating the transformation of the problem space. So I set into finding out if converting the populations with log could simplify the problem. It turned the problem into a potential Data Science problem, resolved with a Linear Model, or at least that was what I got in my mind.
And at this point, things went all south for me, why? because of this:
And its log plot...
I plotted this image, and it all appears that by getting the log function of the population I collected, I could do a linear prediction, however, the image may be a bit pixelated due to upload quality, but in close inspection, there is a little margin of error, so is not a straight line, which means, that even the most accurate model, will not be able to predict with ZERO margin of error, the points that follow. If you think that is possible, would love to hear in the comment of the article ;-)
Anyway, I plotted that, and then exactly what happens after you plot one thing, the next one comes, and then the next, and then the next, and in less time that you know, your notebook is filled with plots following an end-less trail, lacking proper rationale or intention, the art of EDA. Nevertheless the idea of finding a trail felt really good.
Here more patterns for you, this one the lag difference over the log function results...
When I saw this, my mind also tricked me to split the signal, Fast Fourier Transform, Time-Series Analysis, and my mind again loop endlessly in tools and problems that had no affinity to the problem of population in hand. Signals vs. Populations.
Exit the Rabbit Hole
Then I remembered that if each generation of fish could be represented as a vector, and the transformations as a matrix, there was something perhaps an opportunity to tackle this with math. Finally the use of "eigenvectors" could be the light at the end of the tunnel. At this point, a hard reset happened in my brain, and I decided to now resource to pen and paper first. I found abstracts that explained the behavior of populations with matrices, and that gave me some confidence that indeed I was somehow walking in the right direction. I also suspected that converting the problem to a Matrix Problem, will solve my ultimate objective, which was a memory problem, and a size or computation efficiency problem, as the problem will benefit from parallel CPU computation with AVX instructions and Fortran supporting in the back with BLAS.
Here my scratch paper, with the patterns in the transformations found in the first iterations...
Getting into the final piece, was not easy, I literally manually tested that the vector transitions were performing the right computation, but as the numbers started to unfold, I started to feel more confident that this was approximating the right solution.
Algebra came to the rescue, together with the associative and commutative features of matrices.
Finally, I put together the last part, and converted the idea, to the final piece of code that indeed, successfully completed the puzzle and the challenge, and help me enter the weekend with a glass of white wine and Virginie in my side, listening to his husband talking about the power of matrices and vectors, and asserting that everything, almost everything can be solved in 3 lines of code. Enjoy!
Final Thoughts
Like in puzzles, I think enterprises, professionals, and pretty much every industry is in a sort of time race. Delivery obfuscates comprehension, and craftsmanship is overlooked or hard to appraise. Speed ubiquitously wins. The purpose to endure, simplify or comprehend is lost in the advent of time. To me, and thinking about finding meaning to what we do, I think we should worry more about how we do things, and before just throwing more resources in it, we see the long term impact of our actions, think about our environment, about energy consumption, and overall, about how to do more with less. My desire in this article, is to realistically reflect on how we approach problems in our jobs, using a game as an example. And how the idea of working smarter rather than harder could indeed help find meaning and change our principles on sustainability. This puzzle helped me realize that developing solutions that are fast, don't have to necessarily compete with abstract beauty.
Have a great weekend!