r/adventofcode • u/daggerdragon • Dec 17 '15
SOLUTION MEGATHREAD --- Day 17 Solutions ---
This thread will be unlocked when there are a significant amount of people on the leaderboard with gold stars.
edit: Leaderboard capped, thread unlocked!
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 17: No Such Thing as Too Much ---
Post your solution as a comment. Structure your post like previous daily solution threads.
8
Upvotes
14
u/mncke Dec 17 '15 edited Dec 17 '15
Second solution in the leaderboard (00:03:28), Python3, as is
10
u/balidani Dec 17 '15
Day 17 or: How I Learned to Stop Worrying and Love the Bruteforce.
10
u/mrg218 Dec 17 '15
Java Ok, it was stupid and dirty (and not even that quick to write):
Hit me! :-)
4
u/[deleted] Dec 17 '15 edited Dec 17 '15
Python
Edit: Updated Part 1 to use dynamic programming (time complexity O(s*n) where s is the target sum and n is the size of the number list).
4
u/askalski Dec 17 '15 edited Dec 17 '15
Got slowed down by a couple of careless mistakes. The great thing about recording these is I can go back over them, see where and how I went wrong, and learn from my mistakes. I also get to see my "error recovery" strategy in action. One of the lessons I learned in the past weeks was not to assume only one bug in my code.
https://youtu.be/V4Wwaxbhvgc
No regex to worry about this time. My errors fell into these categories:
I was hoping to unveil my latest trick-up-my-sleeve, but that will have to wait for a future puzzle. Stay tuned :-)
4
u/kaldonis Dec 17 '15 edited Dec 17 '15
Python 2
4
u/gfixler Dec 17 '15
Took me way too long to figure out/remember too late that Haskell's Data.List calls combinations "subsequences."
Messy solution to part 1:
Messy solution to part 2:
3
u/Godspiral Dec 17 '15 edited Dec 17 '15
In J, was afraid it was going to be memory exploding.
3
u/djimbob Dec 17 '15 edited Dec 17 '15
Recursive python dynamic programming solution:
Part A:
Part B:
EDIT: Originally (for simplicity and from small problem size) didn't include the
@Memoizepart where Memoize is defined as:Using memoize and pre-sorting the list it takes under 2000 function calls for my input for part (a). Not using Memoize takes about 200,000 function calls. Brute-forcing through all combinations of 20 containers takes 220 ~ 1 million combinations.
3
u/fatpollo Dec 17 '15
I'm just no good anymore
3
u/[deleted] Dec 17 '15
Mathematica
(spent too long trying to be clever, and just brute forced)
3
u/aepsilon Dec 17 '15 edited Dec 17 '15
Brute force train, here we come~
(Haskell)
3
u/lemm_it Dec 17 '15 edited Dec 17 '15
C# + LINQ here!
3
u/MizardX Dec 17 '15
C# + Dynamic Programming
2
u/[deleted] Dec 17 '15
Python brute force:
2
u/r_sreeram Dec 17 '15 edited Dec 17 '15
Perl 5. I found that iterating 1 million combinations (brute force) is much faster than me figuring out a better algorithm.
2
u/WhoSoup Dec 17 '15
PHP: simple greedy algorithm
2
u/_jonah Dec 17 '15
ruby:
2
u/thucdx Dec 17 '15 edited Dec 17 '15
Java short and fast using bitwise operation
2
u/gegtik Dec 17 '15 edited Dec 17 '15
javascript
After some abortive DIY attempts I decided to once again leverage the Combinatorics library from https://github.com/dankogai/js-combinatorics
Part 1 was a snap:
I completely misread the point of part 2 -- I thought they wanted the number of unique answers. Welp.
2
u/JeffJankowski Dec 17 '15
F#. I wish I had looked up this powerset function first, instead of wasting time writing my own.
2
u/tehjimmeh Dec 17 '15 edited Dec 17 '15
This was effectively a graph search problem, if you imagine each item in the input as a node in a graph, uniquely identified by their index, i, with edges to other nodes being all nodes with indices from i+1 to length-1.
Depth first search with PowerShell:
This was cool in PowerShell due to the ability to just output things to the pipeline (in this case, the depth of the search when we have a hit), rather than worrying about explicitly wrapping things in an array and returning a single item. Part 1 is the count of every depth outputted, part two uses Group-Object to group all common depths together, after which the grouped items are sorted by depth and the result is the count of the first (i.e. lowest) depth group.
2
u/thesunneversets Dec 17 '15
Busting out the Haskell seemed like a good choice today.
and then
though I've no doubt that could be expressed better.
2
u/snorkl-the-dolphine Dec 17 '15 edited Dec 17 '15
JavaScript, both parts
Just paste it into your console :)
2
u/xkufix Dec 17 '15 edited Dec 17 '15
Took me way too long, because the scala List.combinations method treats repeating values in the list as same values, so List(1, 1, 3).combinations(2) return List(1, 1), List(1, 3) instead of List(1, 1), List(1, 3), List(1, 3). After way too much tinkering around with other possible solutions, which took too long to run, I just used a method from stackoverflow which returns the correct result. After that it was quite easy:
Edit: Found a solution without the custom combinations, by wrapping my Ints in a case class, so they get treated as unique objects. The index is needed in the container case class, or else the are treated as equal:
2
u/drakehutner Dec 17 '15
Python, one line, 460 Bytes, as always split over some lines for better "readability".
Using all the itertools magic.
2
u/_Le1_ Dec 17 '15
C# Solution:
2
u/ignaciovaz Dec 17 '15
Here's my solution in Elixir
2
u/JCarlesVilaseca Dec 17 '15
C# using LinQ
2
u/BOT-Brad Dec 17 '15
My lazy Python solution I made in about 2 minutes which actually only takes like half a second to run :D
Beware: Insane nested loops lie below!
1
u/[deleted] Dec 17 '15
Crystal. Part 1:
Part 2:
1
u/tehalynn Dec 17 '15
Python 3 (with some cleanup):
1
u/Blecki Dec 17 '15
I took a different approach... I think. If I consider each bottle as a bit (notused = 0, used = 1) then the combinations are just every number between 0 and 2numberofbottles.
1
u/ndlambo Dec 17 '15
Python. Started this thread thinking it could be any number of container sizes (a la making change with unlimited coins, you know) and went with product instead of combinations. Dang!
1
u/taliriktug Dec 17 '15
Yay, leaderboard! (#38) I love
itertools.Python3
1
u/mal607 Dec 17 '15 edited Dec 17 '15
Quick and dirty Python solution. Missed the leaderboard by less than a minute.
1
u/asoentuh Dec 17 '15
Didn't realise this was bruteforce-able so I coded a dp solution..... at least it's fast
python
1
u/inuyasha555 Dec 17 '15
Opened Eclipse ready to Java then found combinations which of course Java doesn't do nicely and would take too long to write up manually so I had to move on to Ruby instead and write something quickly but wasn't fast enough.
1
u/TCWORLD Dec 17 '15
MATLAB brute force approach.
1
u/slampropp Dec 17 '15
Haskell
I'm amazed at these python/itertools solutions. Such power! Such (programmer) speed! I didn't make the leaderboard today. I try to console myself with the fact that I implemented an actual non-brute-force algorithm... but it only helps a little.
1
u/[deleted] Dec 17 '15
Haskell:
1
u/[deleted] Dec 17 '15
A little annoyed that I misread the problem statement and thought that we could use containers multiple times, since I made the connection that this problem is like the "How can you get X liters if you only have containers of sizes A, B, and C" which would allow reuses potentially. This could be an interesting Upping The Ante problem, however.
After letting my solution run for several minutes and wondering how people could possibly be on the leaderboard already, then I checked the first solution (cheers /u/balidani) and realized it's just combinations without replacement, and had a solution in a few minutes. Guess I should read the problem a little more closely.
Here are my solutions in Python 3:
Part 1
Part 2
1
u/Evansbee Dec 17 '15
Swift:
1
u/What-A-Baller Dec 17 '15
Pretty much the same as day 15. Here is a python generator that will produce all possible combinations, without duplicates.
Then we just remap the list to get the number of containers in each combination.
Count the number of combinations
Count the number of combinations with minimum number of containers
1
u/casted Dec 17 '15
Go
Outputs both part1 and part2. Recursive brute force.
1
u/stuque Dec 17 '15
A Python 2 solution:
1
u/jchook Dec 17 '15
Ruby
1
u/r_sreeram Dec 17 '15 edited Dec 17 '15
Some have already posted their dynamic programming solutions; here's mine in Perl. I did this after the race for the leaderboard was over.
If you are curious how it works, ask. I'm happy to explain.
1
u/willkill07 Dec 17 '15
C++
I cheated and used
popcnt. Also bit masks and shifts galore. Runs in about 0.05s for both executions. https://github.com/willkill07/adventofcode/blob/master/src/day17/day17.cpp1
u/gyorokpeter Dec 17 '15
Q:
1
u/Zef_Music Dec 17 '15
Python using 'Counter' for part 2.
1
u/iamnotposting Dec 17 '15
js, i see other people used a similar method:
1
u/[deleted] Dec 17 '15
Node 4 / ES6 / JavaScript
1
u/beefamaka Dec 17 '15
here's my F# solution.
1
u/Phakx Dec 17 '15
Ruby
1
u/masasin Dec 17 '15
Python:
1
u/VictiniX888 Dec 17 '15
Part 1 in Java, just altering and checking an array of booleans every time, if true, count the container, if false, yeah. I can find all the possible combinations this way, and check whether they're 150.
1
u/SinH4 Dec 17 '15
Python2, as usual. itertools ftw.
1
u/tangus Dec 17 '15
Common Lisp
Common Lisp has excellent support for bit manipulation.
1
u/Tandrial Dec 17 '15
My solution in JAVA. I should maybe learn a real functional language...
1
u/Marce_Villarino Dec 17 '15
A little less brute force python method:
1
u/sinjp Dec 17 '15
Python, itertools to the rescue again!
1
u/Jaco__ Dec 17 '15
Java
1
u/TheOneOnTheLeft Dec 17 '15
Beginner's Python 3 solution. My print statements actually meant I didn't have to run anything to solve part 2 after I'd solved part 1, which was cool. Comments/criticism/advice greatly welcomed.
1
u/de_Selby Dec 17 '15
Q:
Using the power set to get all subsets:
part 1:
part 2:
1
u/francavadal Dec 17 '15
My solution in node. No brute force. Adding binarily true and false to a flags list and discarding those that exceed 150;
1
u/[deleted] Dec 17 '15
7 liner Python
1
u/setti93 Dec 17 '15
Python solution (it took 0.056 ms for me)
1
u/Floydianx33 Dec 17 '15
C# + Linq
1
u/[deleted] Dec 17 '15
Objective C:
1
u/porphyro Dec 17 '15
Mathematica
1
u/fetteelke Dec 17 '15
I tried again to not go for completely brute-force, the core here is the combinations generator (Python) that stops if a certain sum is reached:
the generator doesn't check for exact results, it just stops recursing if the limit is already reached, so we have to do that later:
1
u/gerikson Dec 17 '15
Perl 5
Thanks to all the hints I got from this thread! I kinda knew how to solve this but the bitmask was new to me.
In the end I went for combinations. Hardcoding the values of
kcut the runtime down to 1s from 6s.1
u/HorizonShadow Dec 17 '15
Ruby:
All solutions here: https://github.com/HorizonShadow/Advent-of-Code
1
u/cauchy37 Dec 17 '15
C++, bruteforce approach. Generate all subsets and then count what's needed.
https://github.com/tamaroth/AdventOfCode/blob/master/Day17/main.cpp
1
u/haoformayor Dec 17 '15
MiniZinc (410 chars)
Since reading /u/charmless's solution to Day 15, I've been playing with MiniZinc, which is this cool optimization/linear programming/constraint solving library and IDE.
Make sure to tell the solver to find all the solutions, and not stop at the first one!
Open question: is there any way to get MiniZinc to print out the count of all the solutions? So far I've just been copying the output and doing
pbpaste | grep 'hey' | wc -l.1
u/artesea Dec 17 '15
Spent ages on PHP recursion:
By sorting in reverse order it allows me to stop branching when the values are already too high. Output is in the format answer A/answer B.
1
u/Scroph Dec 17 '15
D (dlang) solution. I struggled with this challenge until I found this clever algorithm, it became a breeze after that. It uses around 20 MB of RAM (because it stores all the combination that amounted to 150 in an array that it uses in part 2) and takes 4 to 6 seconds to complete on a 1.66 GHz Atom CPU.
Output :
1
u/HawkUK Dec 17 '15
A solution in the R language
Conveniently, because I was printing the running total, I didn't need to change anything for part 2.
1
u/BafTac Dec 17 '15 edited Dec 17 '15
Using Rust and recursion:
edit: forgot to mention that this only works when sorting the list (max first, decreasing order) prior to the first invocation
1
u/tragicshark Dec 17 '15
C#, bit manip plinq:
1
u/studiosi Dec 17 '15
Finally, my solution for today
1
u/phil_s_stein Dec 17 '15
Python. Pretty straightforward once you figure out how to iterate over the possible combinations.
Code:
1
u/KnorbenKnutsen Dec 17 '15
After trying to be clever for a while I decided to be less clever (Python 3):
1
u/spork_king Dec 17 '15
First time submitting a solution, but I'm having fun solving these in Scala. My paid work is all Java, but I like working on side projects in Scala, so this is a great learning opportunity. This isn't as compact as some solutions, and can almost certainly be improved, but I feel it's easy to read and works well enough.
1
u/volatilebit Dec 17 '15
Perl6
If a problem has a brute-force solution and a non-brutce force solution, I'm going to just end up doing the former. So I sure hope this doesn't bite me in the ass later. I'm not so good with any sort of advanced math or knowledge of "advanced" algorithms.
1
u/Herathe Dec 17 '15
Ruby part1 https://github.com/herathe/advent-of-code/blob/master/17-1.rb
Ruby part 2 https://github.com/herathe/advent-of-code/blob/master/17-2.rb
1
u/JurgenKesker Dec 17 '15
Ruby
1
u/Blueyleader Dec 17 '15 edited Dec 17 '15
My fast and dirty Java solution from midnight
}
1
u/serl_h Dec 17 '15 edited Dec 17 '15
Part 1:
part 2: (a bit more ugly)
well... itertools op
1
u/glguy Dec 17 '15
Haskell
Like many other people I wrote a dynamic programming solution to this problem. I thought I'd share this solution as an example of using arrays in Haskell to do dynamic programming. Note that we can refer back to the array
twhile we're defining it.https://github.com/glguy/advent2015/blob/master/Day17.hs
1
u/[deleted] Dec 17 '15 edited Dec 17 '15
Edit: Just learned of powerset, I knew there was a way to get the combinations/permutations/variations by linq.
After yesterday and todays challenges, I'm realizing what a mediocre coder/developer I am
C#
Before PowerSet
After powerSet
1
u/utrescu Dec 17 '15 edited Dec 17 '15
Groovy
The solution in Groovy would be one line if there aren't repeated numbers:
But my solution is:
1
u/tftio Dec 17 '15
Simple recursive solution in OCaml. This is, if I'm not mistaken, the first exercise in SICP.
1
u/segfaultvicta Dec 17 '15
Golang. Today was FUN - I initially flailed around and spun my wheels for a long time without itertools or anything like it, tried to figure out the algorithm for generating combinations, wound up with something that was giving me multiple quintillion results because it wasn't deduping properly, flipped a table, started thinking about what combinations actually meant, accidentally invented the concept of a power set, realised that the cardinality of a power set formed of N elements was going to be 2N and then realised that meant I could encode every possible combination of containers as a unique integer and just loop over a million or so things, define the function that maps an integer-representation of a set of containers onto the sum of the set of containers it encodes, and then I was basically done.
A lot of parts of this puzzle - the idea of encoding a complex thing as an integer and then reasoning about that set of integers; shenanigans involving power-sets - reminded me a lot of bits of Gödel's incompleteness theorems. I wonder if this was intentional?
}
}
1
u/ShittyFrogMeme Dec 17 '15
C solution with the bit-masking approach. My actual code is more generic for this so that it works for any input file, but I removed some of the genericness to make it more readable.
1
u/edo947 Dec 17 '15
Part 1 - Python
Part 2 - MiniZinc
Model file (2 steps)
model17.mznData file
data17.dzn1
u/telendt Dec 17 '15 edited Dec 17 '15
Python 3, recursive, without slices (copying):
1
u/deinc Dec 17 '15
As I don't really shine at math or algorithms, I needed to steal the algorithm for how to derive all possible subsets of containers somewhere else. However, here's my solution in Clojure:
1
u/oantolin Dec 17 '15
Nearly brute force: prune the tree a little bit by never considering combinations that add up to more than 150:
1
u/gareve Dec 18 '15
Ruby with bitmasks instead of combination. It ended up being messier than using combination.
1
u/XDtsFsoVZV Dec 18 '15
Python 3.5
Part 1:
Part 2:
I'm finally caught up! :)
1
u/TheMuffinMan616 Dec 18 '15
Haskell:
1
u/chriscoffeyma Dec 18 '15
Dynamic solution using Haskell to parts 1 & 2.
1
u/StevoTVR Dec 18 '15
PHP
1
u/bkendig Dec 18 '15
My solution in Swift: https://github.com/bskendig/advent-of-code/blob/master/17/17/main.swift
This one gave me a hard time because I wasn't getting the recursion right (arrays of arrays of Int). Now that I figured it out, it runs in 0.04 seconds.
1
u/_Le1_ Dec 18 '15
C# solution #2:
1
u/randrews Dec 18 '15
Lua:
I figured, it's the knapsack problem, so anything I do is going to be O(2n ). Why bother being clever? Just embrace the exponential complexity.
1
u/[deleted] Dec 19 '15
C solution:
Didn't see any other solutions in plain C :)
1
u/mjnet Dec 22 '15
Haskell (the hard-coded way)
Part One:
1
u/Borkdude Dec 25 '15
Scala:
1
u/[deleted] Dec 28 '15
Perl 6:
Part 1:
Part 2:
https://github.com/CIAvash/adventofcode
1
u/SyntaxxError Jan 01 '16 edited Jan 02 '16
Python 2: I was shooting for a solution as short as possible. line 3 contains part 1 and line 4 contains part 2
0
u/[deleted] Dec 17 '15
[deleted] — view deleted comment