Expand description
Advent of Code 2015 Day 15: https://adventofcode.com/2015/day/15
Today’s problem was a little challenging. Looking for inspiration for how to solve it I looked at some of the solutions on the advent of code subreddit but found that almost all of the solutions brute-forced/hardcoded the number of ingredients to four. This was unacceptable to me because I wanted a generic solution that would work for any number of ingredients (also because I wanted to be able to use the same functions to test my solution against the examples which only had two ingredients). I originally brute-forced it in my own way by generating a huge vector with all of the possible ingredients and the possible teaspoons from 0-100 and then generated all of the combinations (take length of ingredients) filtering out any combination that didn’t add up to the correct number of teaspoons and/or didn’t use all four (or length of ingredients) of the ingredients. This worked and provided the correct answer, but it was painfully slow. On my machine each part took about five minutes. To improve this I knew that I needed to reduce the overall number of possible ingredient combinations. I did this by instead computing the cartesian product of a vector for each ingredient in all of its possible quantities. This greatly reduced the overall number of combinations that needed to be checked/excluded. While it still doesn’t run extremely fast each part now runs in about 30 seconds which for a generic solution is acceptable to me.
Functions§
- The solution for the day fifteen challenge.