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],…
- 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:
-  : -466+143 is not 0 so we continue
-  : -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! )