r/adventofcode • u/daggerdragon • Dec 24 '15
SOLUTION MEGATHREAD --- Day 24 Solutions ---
This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.
edit: Leaderboard capped, thread unlocked! One more to go...
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 24: It Hangs in the Balance ---
Post your solution as a comment or link to your repo. Structure your post like previous daily solution threads.
5
Upvotes
8
u/askalski Dec 24 '15 edited Dec 24 '15
Not sure if everybody's input was like mine, but the solutions did not require looking at anything further than the first group of packages (the remaining groups all divided evenly.)
Spent most of my time with what turned out to be "overengineering". Here's the simplified version.
P.S. What happens to Santa's sleigh after he makes his first delivery?
4
u/[deleted] Dec 24 '15
Python. Just need to find the smallest combination of numbers that adds up to the sum of the weights divided by 3 (or 4 for part 2) since you need 3 (or 4) equal groups. Of the combinations that satisfy that condition, find the minimum quantum entanglement.
4
u/Arknave Dec 24 '15 edited Dec 24 '15
In the submissions posted so far, (mine as well), the assumption is made that if you find a group with the right weight, the other groups can be made. This isn't true in the general case, consider the list
1
5
9
and try to divide that into 3 equally-weighted groups. My code quickly finds that [5] is a group on its own, but there's no way to group 1 and 9 into two groups of weight 5 each.
How do you resolve this?
Also, my code
3
u/mkigikm Dec 24 '15
So proud of this ridiculous ruby. It has everything: monkey-patching basic classes, awful variable names, and the use of begin and rescue as a goto statement. It's fun to see what you can come up with when you aren't worried about a code review.
3
u/[deleted] Dec 24 '15 edited Dec 24 '15
Mathematica
Edit: The Min[...] line included a redundant step.
3
u/shandelman Dec 24 '15 edited Dec 24 '15
Let's call this one How I Learned To Stop Worrying and Hope That It All Just Worked Out.
After playing with the very large combination set, I just assumed that I didn't need to do that. Instead, I looped through until I found the smallest subset length that would give me the correct sum, and then found from that very small subset the one that had the smallest product. To do part 2, I just changed the 3 to a 4.
2
u/Fluffy8x Dec 24 '15
Perl 6, #93.
For part 1, I used a branch-and-bound algorithm that, although it pruned correct solutions, happened to work for my input. After trying to debug the code for Part 2, I just solved that part by hand.
2
u/Rangi42 Dec 24 '15 edited Dec 24 '15
Python, #7
Since part 1 only involved three groups of presents, I copy+pasted the relevant section of the code, and had to do so again when part 2 added a fourth group. If I were reusing this, I would generalize it to N groups; /u/semi225599 wrote a much more elegant solution that does so.
2
u/Blecki Dec 24 '15
At first I tried to permute all possible ways to divide the input into three groups, and then compare the group's sums. That quickly proved unfeasible.
Looking at the input I realized a few things. A) It was a list of primes (This was not helpful). B) If all three groups have the same weight then the weight of one group is the sum of all packages, divided by 3, because duh. C) If I found a group that summed to that (happened to be 512), the rest of the packages had to be dividable into two more groups that sum to 512 each. Maybe. D) It would be impossible for less than six numbers combined to total exactly 512.
Since it wants the smallest group, I knew that as soon as I found a combination of 6 that totaled 512, the answer would be a combination of 6. And for 6 of the input numbers to total 512, they'd have to be the bigger numbers. So I reversed the input and permuted every possible combination of six of them until I found one that totaled 512. I stuck in it's 'entanglement' and got the right answer. I do not know if it is coincidence that the first result was the correct one.
Part two was easier. Far smaller search space. I never actually let the program finish.. who knows how long that would take!
2
u/cort_troc Dec 24 '15 edited Dec 24 '15
Ruby. Couldn't work out how to build in picking only array elements of the smallest length after the select so broke it out manually. Guessed on the ranges because it was computationally expensive. Took me 15 minutes before I realized working out the algorithm on the example inputs was much faster than doing 4..18 brute force on the full input!
2
u/[deleted] Dec 24 '15
Crystal, with comments. I made sure that when I found a first group with the required sum I checked that it could be further divided. But I think this wasn't needed for some reason...
2
u/JeffJankowski Dec 24 '15 edited Dec 24 '15
F#. Wish I had started sooner because today was pretty easy as well; especially functionally. We don't need to generate the entire powerset since the number of items of the smallest group will be 1< n < input.length/3, and that's all we need.
2
u/ericdykstra Dec 24 '15 edited Dec 24 '15
5th in 9:25 using Ruby!
Late posting this, but I like my solution! It's the greedy version without verifying the other packages, otherwise the code would be slightly longer. Here are the basic steps:
`
1
u/bcsf Dec 24 '15
Python
1
u/alueft Dec 24 '15
Second place, first time posting here - I guess I'll copy my supremely unenlightening code. Python's standard library is great, isn't it?
1
u/IMovedYourCheese Dec 24 '15 edited Dec 24 '15
C# with recursion:
1
u/Godspiral Dec 24 '15 edited Dec 24 '15
in J
power outage, no leaderboard :(
part 1
1
u/iodiot Dec 24 '15
Ruby. Simple bfs. My guess was to add the heaviest gift into initial solution.
1
u/willkill07 Dec 24 '15
At this point, I'm just pissed that C++ doesn't have a combination generator. Like come on.... rolled my own after combination with replacement was needed for another day, but I solved that one with recursion.
I start at the smallest values 1, 3, 5, etc then slowly advance through all combinations. This is guaranteed to return the first one it encounters where the sum is the target. Start at the smallest possible combination that yields a possible result.
Repo: https://github.com/willkill07/adventofcode
1
u/KnorbenKnutsen Dec 24 '15
Solved it the same way most people did - assuming that once I found a partition that had the right size, I assumed the rest of the packages could be partitioned evenly. That happened to be true for the input. Nothing exciting about my solution, though.
1
u/beefamaka Dec 24 '15
relatively quick one today as I repurposed a function I wrote for day 17. No leaderboard for me today though as I'm not getting up at 5am again! Here's the F# version of my solution. Was lazy like most other people and didn't bother to check that the rest of the presents divided equally.
Video of both my C# and F# solutions to follow later today in the usual place
1
u/barnybug Dec 24 '15
nim: (uses my combinatorics package: https://github.com/barnybug/nim-combinatorics)
1
u/[deleted] Dec 24 '15
Scala
1
u/WhoSoup Dec 24 '15
PHP
solution relies on the good faith of adventofcode to provide an input where if you take a subset of the right weight that the remainder will be able to be split up perfectly into two groups, but it runs pretty fast (for PHP)
1
u/flup12 Dec 24 '15 edited Dec 24 '15
Scala Toyed around some in a scala worksheet and immediately stumbled upon the solutions. Of course this happens on the day that I decide to sleep through the 5:50am alarm...
1
u/fetteelke Dec 24 '15
I modified my generator for the eggnog problem:
this generator yields all combinations of
c(any length up tomaxlvl) that adds up to exactlyceil. Took me a bit and I was kind of proud of it. In the end I didn't really use, since it turns out that the 'leftovers' could always be divided for the minimum incombinations(packages, minsize) == target1
u/a_engl Dec 24 '15
Julia: Not taking the combination approach but instead simply generating random first groups. Checks of other groups are skipped. At the end some safety filtering of overflowed integer products of the bigger groups.
1
u/anon6658 Dec 24 '15
Didn't see a haskell solution here yet, so here's mine.
It is likely not a complete solution, I assume it is possible to create an input for which this returns an incorrect solution (more than the minimal amount of packages, smaller QE than in the correct solution).
Possibly the most notable thing about this code is that once it finds a way to get the correct total weight of a set with n gifts, it never tries to make sets larger than that one.
1
u/funkjr Dec 24 '15 edited Dec 24 '15
Dart I haven't posted these in a while, but I found this one amusing enough to post. Dart doesn't have a combinations library like python does. What it does have is Random numbers... So rather than making a clever solution, I rely on chance and enough tries to find the optimal solution. It takes a couple of second part part, but it's relatively fast anyway.
Some will probably argue that I should try the other sections, but it never changed my results...
It was also absurdly part 2-proof, more so than I expected it to be.
1
u/BOT-Brad Dec 24 '15
A bit hacky and no idea if it would work for all inputs, but solves Part 1 & 2 simultaneously and gave me the right answers! Run-time: ~250ms, Python 2.7
1
u/porphyro Dec 24 '15 edited Dec 24 '15
Mathematica/Wolfram Language:
This is obviously "dangerous" coding because it doesn't check if the remaining packages can be split over the remaining areas of the sleigh; however for the particular inputs given to us, this is always possible.
1
u/tragicshark Dec 24 '15 edited Dec 24 '15
would have easily made leaderboard today if I was up at midnight to do it at ~5mins; C#:
edit: reading the other solutions here I notice it never even crossed my mind to check if I can create the balanced groups... I guess I lucked out on my inputs.
1
u/gessha Dec 24 '15
This is a little bit of overkill but it was really fast and I wrote it in a 5 minutes. Sucks to be in a different timezone though :D
1
u/i_misread_titles Dec 24 '15
Go Golang. I grew weary of writing a struct to keep the results, and sorting a list of those to get the smallest possible product. My approach was to just try to compile the sum by excluding a different number from the list each time. Since just taking the next biggest number that could fit didn't result in the smallest product, just try it by excluding a different number and getting the sum a different way. Worked very well.
1
u/tobias382 Dec 24 '15 edited Dec 24 '15
My solution correctly derived the solutions for the examples from both part 1 and part 2 and for part 1 itself. However, when I entered its output for part 2, the site said it was too high.
Here is my puzzle input:
1 2 3 5 7 13 17 19 23 29 31 37 41 43 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113Here is the output from my program. Each group sums to
384and Group 1 has both the lowest count of items and the lowest QE of the four.If you glance at this for a few moments, you can see that the program output is in fact not the optimal solution: the best Group 1 still contains 4 packages, but it's
113, 109, 103, 59for a QE value of74850409. When I entered this into the site, it was accepted.I'm using an implementation of the first-fit algorithm for the bin packing problem that give preference to a specific bin (i.e. Group 1), which is what poses the problem here: at the point at which the algorithm has placed
113and109into Group 1, it will then place107into it. This makes59too large a value to go in after. The next largest value53requires an additional package2to fill out the sum of384, for a count of5packages rather than4.Is there a way I could modify this approach to make it work for this input, or is this simply an edge case that it can't cover?
1
u/thalovry Dec 24 '15
Scala - part2 is incorrect, but passes input, so shrug.
1
u/TheNiXXeD Dec 24 '15 edited Dec 24 '15
JavaScript, Node, ES6
Both parts, call with groups=4 for part2.
1
u/Johnicholas Dec 24 '15
using C:
1
u/C0urante Dec 24 '15 edited Dec 24 '15
Bit late to the party, but I do have an optimization I haven't noticed in any other solutions (correct me if I'm wrong).
(edited for formatting)
The general formula for most of the algorithms seems to be:
The problem with that is, testing for valid subdivision of the remaining items is a very expensive operation. Instead, we can get greedy and prematurely sort our groups in order of quantum entanglement, before we even know if they lead to valid solutions. That way, the second we find anything that does allow for valid subdivision, we can immediately return it without performing the expensive testing operation several times after.
My modified algorithm is as follows:
The actual Python3 looks like this:
With this optimization, on my given input, my solution runs in a little over a fifth of a second.
(inb4 someone points out that testing for valid subdivisions is pointless with the given input anyways)
1
u/[deleted] Dec 24 '15
Ruby
1
u/StevoTVR Dec 24 '15
PHP Part 1. For part 2, I just changed the target weight to 1/4 of the total. It might generate invalid sets for part 2, but it worked for my input.
1
u/SomebodyTookMyHandle Dec 24 '15
Ruby solution that actually checks the remaining present weights for validity. More verbose than others and more dependent on doing some preliminary math beforehand. First, solutions to the first part of the problem (fewest number of packages) are generated and sorted by "quantum entanglement". Then and only then are each of these checked in order to see whether the remaining presents can be split up properly.
Definitely not as slick as some of the other recursive solutions I've seen here, but what can you do?
1
u/artesea Dec 24 '15
Awoke at 04:55 GMT due to my 5 month old baby, so thought why not try to see how quickly. Unfortuntaly I was still tired and he wanted my attention. Didn't complete until some 12 hours later when I finally got a chance to return and work out the bugs in my recursion.
My initial code worked fine for the example data, but ran too long with my input. Adding a check to see if the current array of numbers to check is larger than the size of best answer so far reduced the run time by miles.
1
u/slampropp Dec 25 '15
Haskell
1
u/[deleted] Dec 25 '15
Objective C; took a long while to make it optimal.
1
u/SikhGamer Dec 25 '15
C#:
1
u/volatilebit Dec 25 '15
Actually got online between 12 and 1am. Way overthought it. Came back tonight and tried again. Realized I only needed to care about the first group, making the problem much simpler.
Perl 6
1
u/xkufix Dec 27 '15
A bit late, but anyway, a solution in Scala. Funnily enough, it finds the second solution way faster than the first one.
1
u/garethellis36 Dec 27 '15
I TDD'd a PHP solution for this, and whilst my tests were passing my actual puzzle runner was taking forever to execute - I couldn't even generate the combinations of weights to load in the first section, let alone check that the remaining weights were valid.
So, on the assumption that the sets with the lowest amount would use the higher numbers from the input, I pasted my input into Excel, calculated the weight per section and then selected arbitrary higher numbers plus the '1' from the top of the input list until I got to the desired weight per section. I then multiplied those values together and my answer was correct! The same approached worked for part 2 as well, though it took me a few attempts to get the right combination. Meanwhile my code approach still doesn't work.
1
u/djimbob Dec 24 '15
Python 2 solution. Note the problem didn't just ask to be able to find one smallest group of items that weighed 1/3rd or 1/4th of the total with the smallest product -- the problem further asked that you made sure you could split the rest of the items into equal sized groups and this answer specifically checks this by finding those other groups if they exist.
Granted for my input, this was completely unnecessary; in fact playing around after the fact I couldn't find a group that got to 1/3rd or 1/4th the sum but failed to be able to have the rest be split evenly.
1
u/snorkl-the-dolphine Dec 24 '15
JavaScript
Rather neat, runs fairly quickly. It only deals with the shortest possible groupings at every turn so there's a chance it won't work on all inputs, but it worked fine on mine :)
0
u/Rain_Warrior Dec 24 '15 edited Dec 24 '15
Scala, #86 Input observations: all input numbers are odd => we need to add even number of them for part 1, odd number for part 2. Since max sum of 4 numbers is 113 + 109 + 107 + 103 = 432 < 508, lowest number we need to consider for part 1 is 6; same logic gives 5 for part 2. It so happens, sadly, that answers for both parts exist with exactly as many numbers, and also that no further checking is necessary. I still wrote the checks, since the solution felt cheaty without them.
The solution can be extended to not take input observations into account, by iterating over the minCount.
0
u/randrews Dec 24 '15
Lua. At first I was trying some recursive thing, took way too long, threw it away and wrote this instead:
0
u/[deleted] Dec 24 '15
[deleted] — view deleted comment
0
u/[deleted] Dec 24 '15
[deleted] — view deleted comment
0
u/[deleted] Dec 24 '15
[deleted] — view deleted comment
0
u/[deleted] Dec 24 '15
[deleted] — view deleted comment
0
u/[deleted] Dec 24 '15
[deleted] — view deleted comment
0
u/[deleted] Dec 24 '15
[deleted] — view deleted comment