Minimizing The Sum of Absolute Values – Day 7 Advent of Code part 1 ๐
This year I took part in the advent of code event. If you’ve never heard about it, I attach tl;dr bellow. Today, I’d like to share my solution for Day 7 problem, because I find it very interesting.
In the first half of the post I describe comparison in time complexity of two solutions (programming). In the second half I outline the proof of one solution (math). What is the Advent of Code # For sure you had some kind of advent calendar in the past (or you still have), e.
Practical Mathematical Optimization ๐ก๐๐ง
In the previous post I’ve presented the basics of stating mathematical optimization problems and JuMP framework in julia. Today let’s follow up with concrete examples! Please checkout the accompanying jupyter notebook even though you might not feel like a programmer. It’s very clear and shows how easy it is to obtain solutions!
Introduction Into Mathematical Optimization Way of Thinking ๐งฎ
In the post about fitting pizzas inside another pizza I’ve shown the following picture and promised a post about recreating it.
Pizzas packed in pizza However, I would not like to assume that everyone is familiar with the optimization theory (you may graduate from Computer Science and still not know a lot) so I want to present an introduction here as high school math and quadratic equations are enough to understand those concepts.
How to Sum Like a Boss (Almost) ฮฃ
In a recent post, I presented how memory layout may influence a matrix summing speed. It’s interesting to see that there are plenty of pitfalls we might fall into when writing sum function and memory layout is not the only one. Please first read the previous post on summing if you haven’t already.
Without thinking why, let’s take a look at those two functions:
Speed of Traversing Matrix โ vs โ
Today I would like to mention a low-level peculiarity I was taught in highschool, but passed over during my studies.
Why it differs whetter matrix is traversed by rows or columns? # Even though we think of a matrices as a two dimensional creatures, inside a computer they have to be stored as a sequence of numbers. Therefore there are two schemas one can follow, row-first and column-first. Historically they are called C-style and Fortran-style respectively.
Pizza Twice as Big ๐
One morning I was standing in a queue in my local bakery, and I’ve seen a woman buying one of those small quasi-pizzas. Pizzas ~20cm in diameter. Immediately I thought about how profitable it is when compared to the full-size 42cm pizza. Since the area of a larger pizza is 4 times bigger, of course, it’s not worth buying smaller pizzas.
Then I thought about fitting smaller pizzas inside the bigger one.