8
\$\begingroup\$

In this challenge, you will recieve a comma-separated list of weights as input, such as

1,3,4,7,8,11

And you must output the smallest amount of weights that can add to that set. For example, the output for this set would be

1,3,7

Because you could represent all of those weights with just those three:

1     = 1
3     = 3
1+3   = 4
7     = 7
1+7   = 8
1+3+7 = 11

There may be more than one solution. For example, your solution for the input 1,2 could be 1,1 or 1,2. As long as it finds the minimum amount of weights that can represent the input set, it is a valid solution.

Weights may not be used more than once. If you need to use one twice, you must output it twice. For example, 2,3 is not a valid solution for 2,3,5,7 because you can't use the 2 twice for 2+2+3=7.

Input is guaranteed not to have duplicated numbers.

This is so shortest code by character count wins.

Network access is forbidden (so none of your "clever" wget solutions @JohannesKuhn cough cough) ;)

Simpleest cases:

1,5,6,9,10,14,15               => 1,5,9
7,14,15,21,22,29               => 7,14,15
4,5,6,7,9,10,11,12,13,15,16,18 => 4,5,6,7
2,3,5,7                        => 2,2,3 or 2,3,7

And some trickier ones:

10,16,19,23,26,27,30,37,41,43,44,46,50,53,57,60,61,64,68,71,77,80,84,87
  => 3,7,16,27,34
20,30,36,50,56,63,66,73,79,86
  => 7,13,23,43
27,35,44,46,51,53,55,60,63,64,68,69,72,77,79,81,86,88,90,95,97,105,106,114,123,132
  => 9,18,26,37,42
\$\endgroup\$
16
  • \$\begingroup\$ very similar to codegolf.stackexchange.com/questions/12399/… \$\endgroup\$ Nov 4, 2013 at 5:42
  • \$\begingroup\$ @Jan, one significant difference is that the challenge you cite called for a set, whereas this one permits duplicates (e.g., 7,7,7,8 above), which increases complexity manyfold. \$\endgroup\$ Nov 4, 2013 at 18:14
  • \$\begingroup\$ Can we assume the input weights are unique (so we don't have to remove dups, simple as that would be)? Also, you may consider requiring that solutions be able to solve a given test case; otherwise the shortest solution may be a brute-force enumerator that can only deal with tiny problems (e.g., if there are n inputs weights and m is the largest, enumerate all subsequences of (1..m) and for each subsequence, enumerate every combination of between 1 and n instances of each element of the sequence.) \$\endgroup\$ Nov 4, 2013 at 19:09
  • \$\begingroup\$ @CarySwoveland Edited for the "unique" part. I already have test cases. \$\endgroup\$
    – Doorknob
    Nov 4, 2013 at 23:45
  • \$\begingroup\$ How can {7,7,7,8} be a solution? 8 is not in the input set. \$\endgroup\$
    – DavidC
    Nov 5, 2013 at 2:37

2 Answers 2

3
\$\begingroup\$

Mathematica 80 75

Update: See at bottom an update on Doorknob's challenging last test, added on Nov.5


This passes all but the last test. However, it does not attempt to use a digit more than once. And it only searches from solutions that are subsets of the larger data set.

The function generates all of the subsets of the input data set and then tests which subsets can be used to construct the complete set. After the viable subsets are found, it chooses the smallest sets.

s=Subsets
f@i_:=GatherBy[Select[s@i,Complement[i, Total /@ s@#]=={}&],Length]〚1〛

Tests

f[{1, 3, 4, 7, 8, 11}]

{{1, 3, 7}}


f[{1, 5, 6, 9, 10, 14, 15}]

{{1, 5, 9}}


f[{7, 14, 15, 21, 22, 29}]

{{7, 14, 15}}


f[{4, 5, 6, 7, 9, 10, 11, 12, 13, 15, 16, 18}]

{{4, 5, 6, 7}}


f[{2, 3, 5, 7}]

{{2, 3, 5}, {2, 3, 7}}


Update

Below I'll provide an initial analysis that may help get started toward a solution.

The data:

data = {10, 16, 19, 23, 26, 27, 30, 37, 41, 43, 44, 46, 50, 53, 57, 60, 61, 64, 68, 71, 77, 80, 84, 87};

Differently from the earlier approach, we want to consider, in the solution set, numbers that do NOT appear in the data set.

The approach makes use of absolute differences between pairs of numbers in the data set.

g[d_] := DeleteCases[Reverse@SortBy[Tally[Union[Sort /@ Tuples[d, {2}]] /. {a_, b_} :> Abs[a - b]], Last], {0, _}] 

Let's look at the number of times each difference appears; we'll only grab the first 8 cases, starting from the most common difference].

g[data][[1;;8]]

{{7, 14}, {27, 13}, {34, 12}, {3, 11}, {20, 10}, {16, 10}, {4, 10}, {11, 9}}

14 pairs differed by 7; 13 pairs differed by 27, and so on.

Now let's test subsets starting with {difference1},{difference1, difference2}, and so on, until we can hopefully account for all the original elements in the data set.

h reveals those numbers from the original set that cannot be constructed by composing sums from the subset.

h[t_] := Complement[data, Total /@ Subsets@t]

By the fifth try, there are still 10 elements that cannot be formed from {7, 27, 34, 3, 20}:

h[{7, 27, 34, 3, 20}]

{16, 19, 26, 43, 46, 53, 60, 77, 80, 87}

But on the next try, all numbers of the data set are accounted for:

h[{7, 27, 34, 3, 20, 16}]

{}

This is still not as economical as {3,7,16,27,34}, but it's close.


There are still some additional things to take into account.

  1. If 1 is in the data set, it will be required in the solution set.
  2. There may well be some "loners" in the original set that cannot be composed from the most common differences. These would need to be included apart from the difference tests.

These are more issues than I can handle at the moment. But I hope it sheds some light on this very interesting challenge.

\$\endgroup\$
7
  • \$\begingroup\$ hmm... currently devising testcase that requires duplicates :P \$\endgroup\$
    – Doorknob
    Nov 5, 2013 at 2:32
  • \$\begingroup\$ I'll leave my solution posted for now and see if I can add a condition to test duplicates. \$\endgroup\$
    – DavidC
    Nov 5, 2013 at 2:35
  • 3
    \$\begingroup\$ If a solution exists where a weight w is repeated, then the same solution with one of the ws changed to 2 * w also works, because you can use the 2 * w everywhere you used w + w before. This can be repeated until the solution has no repeats. Therefore, you need not attempt to use repeats. \$\endgroup\$ Nov 5, 2013 at 3:35
  • \$\begingroup\$ You don't really need the parenthesis. Get the s=Subsets; out of the function \$\endgroup\$ Nov 5, 2013 at 18:39
  • \$\begingroup\$ Right about the parentheses. \$\endgroup\$
    – DavidC
    Nov 5, 2013 at 19:13
0
\$\begingroup\$

Ruby 289

This is a straight enumeration, so it will obtain minimal solutions, but it may take years--possibly light years--to solve some problems. All the "simplest cases" solve in at most a few seconds (though I got 7,8,14 and 1,2,4 for the 3rd and 5th cases, respectively). Tricky #2 solved in about 3 hours, but the other two are just too big for enumeration, at least for the way I've gone about it.

An array of size n that generates the given array by summing subsets of its elements is of minimal size if it can be shown that there is no array of size < n that does that. I can see no other way to prove optimality, so I start the enumeration with subsets of size m, where m is a known lower bound, and then increase the size to m+1 after having enumerated subsets of size m and shown they none of those "span" the given array, and so on, until I find an optimum. Of course, if I have enumerated all subsets up to size n, I could use a heuristic for size n+1, so that if I found a spanning array of that size, I would know it is optimal. Can anyone suggest an alternative way to prove a solution is optimal in the general case?

I've included a few optional checks to eliminate some combinations early on. Removing those checks would save 87 characters. They are as follows (a is the given array):

  • an array of size n can generate at most 2^n-1 distinct positive numbers; hence, 2^n-1 >= a.size, or n >= log2(a.size).ceil (the "lower bound" I referred to above).
  • a candidate generating array b of size n can be ruled out if:
    • b.min > a.min
    • sum of elements of b < a.max or
    • b.max < v, where v = a.max.to_f/n+(n-1).to_f/2.ceil (to_f being conversion to float).

The last of these, which is checked first, implements

sum of elements of b <= sum(b.max-n+1..b.max) < a.max

Note v is constant for all generator arrays of size n.

I've also made use of @cardboard_box's very helful observation that there is no need to consider duplicates in the generating array.

In my code,

(1..a.max).to_a.combination(n) 

generates all combinations of the numbers 1 to a.max, taken n at a time (where a.max = a.last = a[-1]). For each combination b:

(1...2**n).each{|j|h[b.zip(j.to_s(2).rjust(n,?0).split('')).reduce(0){|t,(u,v)|t+(v==?1?u:0)}]=0}

fills a hash h with all numbers that are sums over non-empty subsets of b. The hash keys are those numbers; the values are arbitrary. (I chose to set the latter to zero.)

a.all?{|e|h[e]}}

checks whether every element of the given array a is a key in the hash (h[e] != nil, or just h[e]).

Suppose

n = 3 and b=[2,5,7].

Then we iterate over the range:

(1...2**8) = (1...8) # 1,2,..,7

The binary representation of each number in this range is used to stab out the elements of b to sum. For j = 3 (j being the range index),

3.to_s(2)                  # =>  "11"
"11".rjust(3,?0)           # => "011"
"011".split('')            # => ["0","1","1"]
[2,5,7].zip(["1","0","1"]) # => [[2,"0"],[5,"1"],[7,"1"]]
[[2,"0"],[5,"1"],[7,"1"]].reduce(0){|t,(u,v)|t+(v==?1?u:0)}]=0 # => t = 0+5+7 = 12 

The code:

x=a[-1]
n=Math.log2(a.size).ceil
loop do
v=(1.0*x/n+(n-1)/2.0).ceil
(1..x).to_a.combination(n).each{|b|
next if b[-1]<v||b[0]>a[0]||b.reduce(&:+)<x
h={}
(1...2**n).each{|j|h[b.zip(j.to_s(2).rjust(n,?0).split('')).reduce(0){|t,(u,v)|t+(v==?1?u:0)}]=0}
(p b;exit)if a.all?{|e|h[e]}}
n+=1
end
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.