Solving the Dropbox diet challenge
March 17, 2012 5 Comments
There are some nice programming challenges on the Dropbox website, and today I would like to give a possible solution for the “Dropbox diet challenge”.
The most obvious solution is to compute all possible calories permutations and find the one where the sum of all calories is zero.
The problem with this approach is that you will end up computing useless permutations like [802, 421, 143] (free-lunch + mixed-nuts + orange-juice). This specific example will led you nowhere since all values are positives, which means that the sum cannot possibly be equals to 0.
In the solution I’m describing today, I will split the items in two groups: one with all the items with negative calory values and one with all the items with positive calory values. Using the example on the Dropbox site, we will end up with 2 lists:
- [-195, -466, -302, -42, -295, -137, -611]: rock-band, coding-six-hours, heavy-ddr-session, …
- [143, 802, 421, 316, 150]: orange-juice, free-lunch, mixed-nuts…
Then, we are going to compute all the “negative elements permutations”.
- first the 1-element permutations: [-195], [-466], [-302]…
- then the 2-elements permutations: [-195, -466], [-195, -302],…
- then…
- finally the only existing 7-elements permutation: [-195, -466, -302, -42, -295, -137, -611]
Finally, for each “negative elements permutation”, we are going to compute all the “positive elements permutations” and we are going to compare the current “negative value permutation” with each one of the “positive value permutations” that we have computed: if the sum of the elements in the 2 lists is 0, we are done.
For example, assuming that the current “negative value permutation” is [-466] (coding-6-hours), then we are going to compare this to:
- [143] : -466+143 is not 0 so we continue
- [802] : -466+802 is not 0 so we continue
- …
- [143, 802] : -466+143+802 is not 0 so we continue
- [143, 421] : -466+143+421 is not 0 so we continue
- …
- [316, 150] : -466+316+150 is equals to 0 so we have a match !
Now for the super-duper enhancement: assuming that the current “negative permutation” is [-42, -195] which adds to -237. We don’t need to compare this permutation to ALL the possible positive element permutations. Why ? because we already know that a positive element that is greater than 237 will not be part of the final solution. In our example, we will only need to compare [-42, -195] with all possible permutations of [143, 150] (802, 421 and 316 have been discarded).
The only remaining thing that we need to do is to find an algorithm that will compute the permutations we need. I found this great MSDN article by James McCaffrey that offers an easy to understand non-recursive implementation.
Here is the source code for the solution: dropboxDiet (why not a zip file ? because wordpress doesn’t allow uploading zip files! )
Laurent KUBASKI
About lkubaski
The skiing cube 
Take a look at http://en.wikipedia.org/wiki/Subset_sum_problem
Unfortunally there is no better solution than comparing all permutations filtered conveniently.
Thanks a lot for the link: I didn’t know that this problem had an “official” name !
Was your algorithm fast for big n, in a range of 40-50? Thanks!
No, this solution is slow. If you want to be able to solve this problem for “large” amounts of numbers, then you will have to use better heuristics then just “exclude all numbers bigger than the expected sum”. After all you could still have about 10^15 combinations to try when dealing with 50 elements and you are supposed to always find a solution, even with such big numbers!
So how to deal with that numbers? Use clever heuristics to reduce them. First of all, make some additional assumptions about the given numbers. You are not dealing with “random” numbers but 16 bit integers, this is important as a limited number of digits is a prerequisite you NEED to find an algorithm which scales better than O(e^n).
Now why is that so important? First of all, you can use the last bit of each number to divide the numbers into even and odd numbers. You know that you can use every amount of even numbers, but the total number of odd numbers must be even or you will never reach zero.
Now look at the second last bit, and divide again into numbers which have an 0 and those which have an 1 set. This time you need an odd number of 1s if you had an odd number of uneven pairs in the previous test and an even number if you had an even number of pairs.
How did this help? Now when you permute, start with the uneven numbers and count the number of 1s in the second bit. If you have an uneven number of odd numbers: Skip the iteration. If you have used all uneven numbers, proceed to even numbers, starting again with the ones which have 1s as the second bit, if you have an uneven number, skip it. You have just crossed out about 3/4 of all possible combinations, but you can still do better.
Why did we need to make the assumption that we only had 16bit integers? Because we are going to use that “trick” on ALL bits now! First perform a reverse sort over all the numbers with switched endian (sort by LSB instead of MSB). Now start permutating and always keep track of the current sum. If you run out of numbers with a 1 at a certain digit check if the digit in the sum is 0 at this point, otherwise skip the iteration.
If you did anything thing right, you should now be able to solve the problem several times faster now, fast enough to solve the problem for large sets of 40-50 numbers. Technically spoken, you have just reduced the number of combinations to try by 2^16! Its still O(e^n), but at least you have gotten a nice factor in the front which brings you from 10^15 down to “only” about 10^11 combinations to test. At least thats something a modern CPU can handle!
PS: You should try to implement this with in a recursive algorithm, makes things much easier š Especially easier to parallelize, and thats something you wanna do as the algorithm would scale very well with multiple processors.
Well, my solution is surely not the best one: my goal was just to find a solution without looking at existing solutions on the net.
This being said, I really like your idea: it’s a very clever concept !
For a more generic solution, you may want to look at the link provided by Alessio: http://en.wikipedia.org/wiki/Subset_sum_problem