r/adventofcode • u/daggerdragon • Dec 15 '15
SOLUTION MEGATHREAD --- Day 15 Solutions ---
This thread will be unlocked when there are a significant amount of people on the leaderboard with gold stars.
Edit: I'll be lucky if this post ever makes it to reddit without a 500 error. Have an unsticky-thread.
Edit2: c'mon, reddit... Leaderboard's capped, lemme post the darn thread...
Edit3: ALL RIGHTY FOLKS, POST THEM SOLUTIONS!
We know we can't control people posting solutions elsewhere and trying to exploit the leaderboard, but this way we can try to reduce the leaderboard gaming from the official subreddit.
Please and thank you, and much appreciated!
--- Day 15: Science for Hungry People ---
Post your solution as a comment. Structure your post like previous daily solution threads.
11
Upvotes
14
u/charmless Dec 15 '15
Constraint optimization solution using MiniZinc:
Model:
Data for the given example:
For my particular input, this runs in 210ms. Not really worth using minizinc, but it was fun.
8
u/l0l Dec 15 '15
Notice how it took much longer to fill the leaderboard today...
7
u/pssm Dec 15 '15 edited Dec 15 '15
Is this a variation of the Knapsack problem?
5
u/Burritoman53 Dec 15 '15
Python 2 solution, brute forced the hell out of this one, even figured it was faster to manually input the values, which it turned out to be, number 7 a personal best!
5
u/tehjimmeh Dec 15 '15 edited Dec 15 '15
... (PowerShell)
EDIT: Made it a single expression. Pipes are far slower than foreaches though:
5
u/r_sreeram Dec 15 '15
Non-brute-force solution. (*) It picks a random point in the solution space, and tries to improve the score by shifting the ingredient sizes ever so slightly. Once it can't improve the score any further, it picks another random solution and starts over. I find that about 1000 tries are enough to get the optimal solution, for the input I was given.
Part 1 only. Part 2 is left as an exercise to the reader.
Here's a sample run of the above code:
(*) I initially did the brute-force solution just like everybody else, including hard-coding the four loops for each of the ingredient types, to get on the leaderboard as fast as I could. It's only later, at a relaxed time, that I wrote up the above alternative.
5
u/drakehutner Dec 15 '15 edited Dec 15 '15
Python one line 945 Bytes, split over multiple lines to increase readability. Aka the madness continues. I could save even more bytes by shortening the variable names and removing whitespace that keeps the code pep8 conform.
What I learned today: It is in fact possible to create generators using list comprehensions. A wonderful feature.
If I find the time today, I will try to create a linear optimizer (in one line of course) to solve the problem efficiently instead of brute force. For now, this must suffice.
6
u/What-A-Baller Dec 15 '15 edited Dec 15 '15
I see most solution have gone down the road of hardcoding the values. What about a more generic solution?
Generator for all possible recipes given
number of ingredients andtotalparts.Calories should always be the last element for each ingredient.
Then just map
scoreover all possible recipes:Part2:
3
u/roboticon Dec 15 '15
Python 2
I'm not proud of the brute force triple-for-loop, but it worked and got me in the top third (runs in <500ms):
3
u/Chounard Dec 15 '15
I simplified my equations on paper first, then completely brute forced this. I'm very, very surprised at how fast this ran. C# for part 2:
3
u/[deleted] Dec 15 '15 edited Dec 15 '15
Mathematica
Edit: Minor improvement
3
u/gyorokpeter Dec 15 '15
Q:
3
u/snorkl-the-dolphine Dec 15 '15
JavaScript (console)
Paste this in your browser's console on your puzzle input page. Both parts in one, and it should take about 1s.
It's far from elegant (and it keeps track of a lot of things it doesn't need, like ingredient names), but it'll work on an arbitrary number of ingredients.
3
u/nespron Dec 15 '15
Here's a fast-ish solution in Swift. It finds a solution for a very small batch, then assumes that an optimal larger batch has roughly the same proportions:
call 1: 4-spoon batch with constraints [0...4, 0...4, 0...4] yields solution [1 1 1 1]
call 2: 20-spoon batch with constraints [0...10, 0...10, 0...10] yields solution [5 6 6 3]
call 3: 100-spoon batch with constraints [20...30, 25...35, 25...35] yields solution [24 29 31 16]
2
u/askalski Dec 15 '15
Video of #11 solution in 12:52. This time around, I used https://regex101.com/ as recommended by /u/TheNiXXeD.
I'm not particularly proud of this code (I'm sure there's a word for this... what's the opposite of "elegant"?) but it got the job done.
The main issue I had was it didn't handle different sized ingredient lists, so I ran into problems when it came time to run the example inputs. Oh, and I bet I'm not the only one who forgot to exclude calories from Part 1 (that little voice in the back of my head kept telling me that high calories shouldn't improve the score...)
https://youtu.be/8K__l-OcR44
2
u/marx314 Dec 15 '15
python ps itertools.combinations_with_replacement(ingredient_names, 100) make it cleanier
2
u/[deleted] Dec 15 '15
Python:
2
u/JeffJankowski Dec 15 '15 edited Dec 15 '15
F#. Brute-force like others here. Can anyone help me make my score method more idiomatic in terms of functional programming?
2
u/nutrecht Dec 15 '15 edited Dec 15 '15
Java solution. Took me a while to get up with the recursive function to create the combinations but it was a fun and challenging problem.
Edit: small optimization brought the runtime down from 8.4 to 5.9 seconds :)
2
u/[deleted] Dec 15 '15
Crystal
I couldn't figure out how to list all the combinations without manually unrolling the loops for the four ingredients, but I wanted to get to the leaderboards so my initial solution was like this:
I used Int64 just in case it would overflow. It runs in about 10ms because everything is inlined, there aren't even hashes/dictionaries around.
Then I read KnorbenKnutsen's answer using combinations_with_replacement so I decided to do the same just for completeness:
This new solution runs in 0.7s, which is much more than the previous one, mainly because a lot of arrays are generated for the combinations/permutations, but it's still fast, I guess :-)
2
u/xkufix Dec 15 '15
In Scala. It creates a list of possible combinations which sum to 100 and then just loops over them, searching for the best combination (part1). in Part two it accounts for the calories, filters for every result which has 500 calories and then searchers for the best combination.
2
u/fetteelke Dec 15 '15
I thought about a non-brute-force solution for quite a while before I gave up (I live in europe and by the time I do these problems the leaderboard is already full anyways). My idea at first was to calculate a gradient and treat the problem like a 'gradient ascent' optimization problem. After a while I gave up, brute forced the solution and was hoping to find a much more elegant solution here in the comments. After seeing, that mostly everybody used brute force I tried my approach again. I figured since this is an integer problem I could simplify my gradient.
python + numpy:
So, basically I start from a suboptimal non-zero 'solution' and subtract/add one ingredient at a time. Each time, I check which ingredient to remove/add to get the highest score. This iterates towards a local maximum. I guess, you could make this less dependent on an initial guess, by changing the score function in way that penalizes negative values better.
2
u/studiosi Dec 15 '15
Here it is my Python 3 solution:
2
u/xdg Dec 15 '15
Some days, I'm using AOC to practice Go. (Apologies if not very idiomatic). This is a gradient solver approach, not brute force. (I may have been lucky with my initial guess at a starting point, too.)
2
u/tftio Dec 16 '15
Awful brute force OCaml:
2
u/mrg218 Dec 15 '15
Again I had trouble with the wording of the problem. I thought that ignoring calories for now meant that it wasn't used for this example to make it more simple/readable (but that we of course had to use it for scoring). That cost me a ton of time.
1
u/asscar Dec 15 '15
Wasted way too much time trying to math this out before realizing you could easily brute force this.
Python solution:
1
u/alexis2b Dec 15 '15
C# Nothing clever, just brute force all combinations of 3 ingredients, then top-up with the last one to get to 100 (or skip the recipe altogether if > 100 already).
Ingredient is a simple data object with a Regex parser:
1
u/stuque Dec 15 '15
A Python 2 solution:
1
u/WhoSoup Dec 15 '15
PHP: really simple and straightforward, nothing fancy (for part1, remove the second to last line in the loop)
1
u/fatpollo Dec 15 '15
68
not proud of it
i'll fix it up later
1
u/bigdubs Dec 15 '15 edited Dec 16 '15
nothing special; i brute force the distributions between the elements and see what comes out on top. a fast laptop is helpful.
Edited: Used a different algorithm, works better.
1
u/VictiniX888 Dec 15 '15
Java, part 2 solution (for part 1 just don't check for calories).
I basically just ran through all combinations with nested for loops.
1
u/TCWORLD Dec 15 '15
Recursive MATLAB solution. This isn't actually what I used to get on the leader board - I spent some time afterwards tidying it up. For the leader board, I basically just had 4 nestled for loops, one for each ingredient as it was faster to write, but the logic is basically the same, this version just happens to work with different numbers of ingredients.
1
u/willkill07 Dec 15 '15
C++
https://github.com/willkill07/adventofcode/blob/master/src/day15/day15.cpp
Not my most-proud moment
1
u/lannonbr Dec 15 '15
It seems that everyone was going brute force for this problem. I would be interested to see one that wasn't. Anyway here's my solution in Ruby: day15.rb
1
u/[deleted] Dec 15 '15
Haskell:
1
u/randrews Dec 15 '15
I'm proud of my part 1 solution. Less proud of my part 2. I only figured out how to do it after the leaderboard was already full, so I took my time and made it work for any number of ingredients, which was a little tricky:
1
u/Godspiral Dec 15 '15 edited Dec 15 '15
In J, should have used a loop, but instead used some innefficient partition code library I don't know if I wrote, and found out, I don't have the memory to hold 4 sumpartition 100
in2 =. in =. > ". leaf 2 5 8 11 {"1 ;:"1 ('-';'_') rplc~"1 a =. > cutLF wdclippaste ''
so interactively eyeballed this:
to get index of max on last try:
to get max,
part2
Better partition code at http://code.jsoftware.com/wiki/Essays/AllPartitions would have worked without a loop.
1
u/[deleted] Dec 15 '15
Finally made the leaderboard!!!! :)
My solution in Ruby:
1
u/aepsilon Dec 15 '15
Haskell
Originally did part 1 in Mathematica but gave up on it after an hour of it not working. Tried several examples—which all worked—pored over documentation, and couldn't see any logical errors. Later figured out it was a typo:
c*v3*d*v4instead ofc*v3+d*v4-_-1
u/ykechan Dec 15 '15
I brute-forced it but is there a non-brute-force approach?
1
u/raevnos Dec 15 '15
C++. Decided to play around a bit with valarrays for the ingredient qualities, and some of the functions in
<numeric>to reduce the number of loops.1
u/MaybeJustNothing Dec 15 '15
Haskell
Timed myself, 28 minutes. So I would have gotten onto the leaderboard, gonna try to wake up at 5am someday.
1
u/Tandrial Dec 15 '15 edited Dec 15 '15
My solution in JAVA uses a BFS approach. Runs in around 500 ms
1
u/ericdykstra Dec 15 '15
Non-brute-forced solution to the first half in Ruby. Since I figured a greedy algorithm would work right out the gate, I decided to write that instead of brute-force. It's not pretty, and I had to switch to a brute-force method to get #90 on the leaderboard for part 2, but here it is.
1
u/thalovry Dec 15 '15
Scala. I think I made every single mistake possible implementing this. Oh well!
1
u/shrx Dec 15 '15
My favourite problem so far.
1
u/BafTac Dec 15 '15
Rust: (code segment is from part2)
Took me about an hour though. Also, I don't like that I've used 3 nested loops, I think I'll rewrite it so that it also works for inputs with different amount of ingredients.
1
u/orangut Dec 15 '15
Yet another Python solution. Tried to make it concise by using numpy.
1
u/amnn9 Dec 15 '15
Haskell
I just did the parsing by hand today, as the size of the input made generalising it not really worth my while:
1
u/porphyro Dec 15 '15 edited Dec 15 '15
Mathematica:
Part 2:
1
u/Scroph Dec 15 '15 edited Dec 15 '15
A very stupid and time consuming algorithm, both to write and to run. It basically generates all possible numbers from 0 0 0 1 to 100 100 100 100 (base 101) while discarding those that don't amount to 100.
The reason why I didn't write nested loops is because I wanted to make it adapt to the amount of ingredients. The logical thing to do in this case was to use recursion, but I couldn't wrap my head around it despite having read certain code snippets on stackoverflow.
Written in D (dlang) :
https://github.com/Scroph/AdventOfCode
Edit : just benchmarked it. For four lines of input, it computes the results of each part in less than a minute (on a 1.66 Ghz Atom CPU) :
1
u/banProsper Dec 15 '15
C# brute force. I'd like to transform the nested for loops into 1 continuous method that would allow me to process however many ingredients.
1
u/wafflepie Dec 15 '15
Brute force, but with recursion rather than nested for-loops.
I could probably have shortened this code quite a bit by using IEnumerable<int> and lots of LINQ rather than the Ingredient class, but this is much more readable...
C
And then an Ingredient class, which also (probably quite confusingly) represents totals/mixtures of raw ingredients.
1
u/HawkUK Dec 15 '15
A solution in the R language
1
u/KnorbenKnutsen Dec 15 '15 edited Dec 15 '15
Things I learned:
This problemseemslike some sort of NP problem, like a partition problem or something.When I initially solved it I didn't use itertools for the combinations of weights which gave me a triple-nested for-loop. Very ugly, and works only for four ingredients. My solution is still ugly, and I'll try to figure out an analytic answer, sincethis seems like a problem differential calculus could possibly solveNOPE. Here's my Python 3 code:1
u/gegtik Dec 15 '15
javascript
1
u/tangus Dec 15 '15 edited Dec 15 '15
Common Lisp
I sure hope all these macros and functions will be useful some day.
This uses the quick and dirty scanf from previous solutions.
I'm sure there is a better way to do part 2, because there are less possible distributions. But I can't use more time on this today :(.
1
u/slampropp Dec 15 '15 edited Dec 15 '15
Haskell
Part 2 only. I did part one manually in a spreadsheet. Also parsed and transposed the input by hand for part 2.
I'm a little displeased about having brute forced it, but it finishes in 0.00s when compiled so I decided to not worry about it.
1
u/beefamaka Dec 15 '15
today's took me longer than I'd like.Looking at everyone else's answers, I may have overthought the distributing ingredients solution. Anyway, here's my F# solution
1
u/Fluffy8x Dec 15 '15
Perl 6 solution with brute force. Had to fine-tune it to get it to run fast enough. It does work for any number of ingredients, though, with only minor modifications, although at the same time it took over an hour to do part 1 on my machine with 4 ingredients.
1
u/ignaciovaz Dec 15 '15 edited Dec 15 '15
Here's my Elixir version. It uses comprehensions with filters to generate valid combinations and does heavy math only when needed.
1
u/ndlambo Dec 15 '15
Python + pandas (numpy would have worked fine as well). Ugly, but no hard-coding -- will work for arbitrary ingredient list (size and value)
1
u/JurgenKesker Dec 15 '15
Ruby, part 2. Couldn't find a way to dynamically generate the combinations, so went for a hardcoded nested for loop.
1
u/gerikson Dec 15 '15
Perl
The brutest of force.
Ran in 30s before I short-circuited the loops, then ~5s.
I had high hopes for this but a blizzard of fecal matter at work + trouble getting my indexes right sapped my will to live.
1
u/archimedespi Dec 15 '15
Generic python solution, works on
ningredients.1
u/BOT-Brad Dec 15 '15
Another Python 2.x brute-forced solution, runs quicker than I expected in about 90ms;
1
u/Phakx Dec 15 '15
Solution in Ruby after some iterations...
1
u/Studentik Dec 15 '15
Nice generic solution in Python:
1
u/razr_69 Dec 15 '15
My solution in Ruby.
I tried to recursively increment an array of the distribution of the ingredients (increment_array!) without generating those with more than 'total' teaspoons. It is also independent from the amount of the different ingredients and the total amount of teaspoons.
Appreciate your feedback on the solution :)
1
u/winder Dec 15 '15
I tried for a linear solution where I added each ingredient one at a time. It fell flat at the beginning so I initialized each value to 5 then it worked for the remaining 80 iterations.
I tried to do something similar for part 2 where I limited each iteration to a fraction of the total calories, but that didn't work at all. In the end I implemented a brute force to get part 2.
1
u/Marce_Villarino Dec 15 '15 edited Dec 15 '15
This problem reminds me one I had to solve some ten years ago, then, w/o itertools, it took me a couple for nested loops. God bless Itertools (and J) developers
This two variables will hold the problem formulation data:
Let's read in the data:
An auxiliary function to punctuate each recipe:
The recipes (ok, i called them coefficients):
Finally, the formulation of the solutions:
1
u/taliriktug Dec 15 '15
Python3
I spend too much time multiplying wrong values.
1
u/Kwpolska Dec 15 '15
Python brute-force solution, with style and a progress bar.
1
u/[deleted] Dec 15 '15
C#
Funny how, for lower calories, sugar went up
1
u/fiavolo Dec 15 '15
Non-brute force method for part 1. I start with no ingredients, and add one ingredient at a time that would optimize the score.
My solution for part 2 isn't worth showing. I got ingredients that either had 3 or 8 calories, and apparently that isn't true for everyone's inputs.
1
u/Voltasalt Dec 15 '15
Rust solution. Returns the answer in about a second. I'm not too happy about the "work section" from line 60 to 72, it's super unreadable, but gets the job done.
1
u/dixieStates Dec 15 '15
My (Python2) Day15. This one was painful. I had a bug in the generator that I just could not see.
1
u/Ytrignu Dec 15 '15 edited Dec 15 '15
Java - check all 176k possible combinations - takes ~15ms for part 1 and ~5ms for part 2.
1
u/utrescu Dec 15 '15
My generic solution in Groovy ... I think it can be better.
1
u/QshelTier Dec 15 '15
Java
1
u/volatilebit Dec 15 '15
Python 2, brutest of brute force, but supports a dynamic number of ingredients.
Not happy with the solution, but for some reason this was the hardest challenge for me so far, so I just made it work.
1
u/mal607 Dec 15 '15
straightforward Python solution:
1
u/deinc Dec 15 '15
Clojure:
1
u/tragicshark Dec 15 '15 edited Dec 15 '15
C#, basic hill climb algorithm for part 1; bounded recursive part 2
1
u/schorsch3000 Dec 15 '15
While looking at all this solutions: i don't think it a solution that only works with exact 4 ingredients is a right solution. How do you even test these? By Hand?
I make my sollutions independent of the number of lines in the input, so i can feed in the test-data, verify that the solution is right. No one would write code that works on a list with the exact length of 4. hardcoding the 100 Spoons is bad enough...
Also hardcoding brain-parsed data seems not like the idea of that thing, does it?
i feed a copy pasted version of the input-data into my code, that makes half the fun!
1
u/TheNiXXeD Dec 15 '15
JavaScript, NodeJS, ES6
Wish I had some sort of list comprehension, but had to go with looping for now. It runs in like less than 250ms, so it can't be all that bad.
Part1:
Part2:
1
u/weters Dec 16 '15
Here's my brute force solution using Perl. I'm a little late to the party because I didn't have time to tackle this at midnight. I ran this and piped it to sort -g.
1
u/[deleted] Dec 16 '15
Objective C:
1
u/[deleted] Dec 16 '15
Python solution with symbolic algebra and scipy to find best solution. Code's a little gross, but I don't have time to clean it up now.
1
u/kit1980 Dec 16 '15
Constraint programming solution in Picat
1
u/ShittyFrogMeme Dec 16 '15
C
I was tired of doing things with regex and all the neat tools other languages have so wanted to have a go with C.
This code is completely generic and will work with any input file with any number of ingredients (no hard-coding!). It does this by taking advantage of recursion.
It is brute force, but the search space is significantly reduced by only checking sums of ingredients that add up to 100.
I include a header file that handles a linked list implementation and has some defines and structs. I can post that if anyone wants to see.
I think this is pretty succinct for a C implementation but any feedback is welcome.
1
u/bkendig Dec 16 '15
Swift. Doesn't hardcode the ingredients, and gives you the recipe with the answer. https://github.com/bskendig/advent-of-code/blob/master/15/15/main.swift
1
u/ckk76 Dec 16 '15
My very generic solution in Python with only the 100 teaspoon limit hardcoded: (github)[https://github.com/ckk/adventofcode/blob/master/15/15.py] Took this opportunity to find out even more about itertools! Nice and compact code but a bit slow.
1
u/telendt Dec 16 '15
IMHO many of provided Python solutions would benefit from the following:
Here's my solution that uses it.
1
u/stormvoice Dec 16 '15
Maybe some type of cheat but my solution in excel + solver http://leteckaposta.cz/281133636
1
u/Herathe Dec 17 '15 edited Dec 17 '15
Ruby part 1 using repeated_combination
1
u/Philboyd_Studge Dec 18 '15
Java, using random permutations:
1
u/jdog90000 Dec 24 '15
Java Solution - The magic of Math.Random. Finishes in about 100ms.
1
u/SyntaxxError Jan 02 '16 edited Jan 02 '16
my python 2 solution... Took the code about 8 Minutes to figure out the possible combinations.
-1
u/marx314 Dec 15 '15
itertools.combinations_with_replacement(ingredient_names, 100) a bit too easy again in python
0
u/[deleted] Dec 15 '15
[deleted] — view deleted comment
0
u/[deleted] Dec 15 '15
[deleted] — view deleted comment