/ We want to test a set of numbers to see whether the sum of any 
/ 1, 2, ... howmany
/ of them is unique after taking absolute values.
/ See examples at the bottom of this file.

/ take out duplicates and return
sortuniq:{[list]
  list: ?list
  :list[<list]
}

/ Much faster.
intersect: {[x;y]
 i:  x ?/: y
 j: & i < #x
 :?y[j]
}


/ return that part of orig that can't be obtained by adding
/ up howmany  or fewer members of choices.
/ tests whether these add up to any element of choices
test: {[choices; howmany]
  guys: choices
  out: choices 
  i: 1
  while[i < howmany
    guys: sortuniq' ,/ guys ,/:\: choices
    jj:  & #:' guys > i
    guys: ? guys[jj]
    out,: guys
    i+: 1
  ]
  out: out ,\: ()
  out: ?:' out
  out: out @' <:' out / sort these
  out: ? out / delete redundant lists
  sums:  _abs' ,/ +/' out
  part: = sums
  i: & (#:' part ) > 1
  if[0 < #i
     first: *i
     :(("duplicate sum "); (out[part[first;0]]; out[part[first;1]]))
  ]
  maxsum: |/sums
  i: sums ? maxsum
  :(("Everything is ok."); |/sums; out[i]) 
}


/ Example to show no errors
howmany: 3
choices: 1 2 4 8 16
test[choices; howmany]

/ Ted Alper and Charles Taylor and Tom Brown, positive -- tot is 1129
/ Best is Yves Piguet with an amazing 1,064
howmany: 3
choices:      1, 2, 4, 8, 15, 28, 52, 102, 187, 256, 375, 498
choices: 1 2 4 8 15 29 90 136 202 258 314 492
test[choices; howmany]

/ Dan Hirschberg best integer solution for 3, sum is 734.
howmany: 3
/ ted alper is this one (leading to  744)
choices:      -1, 4, 6, 8, 16, 32, -65, -118, -164, -248, -332, 668
/ hirschberg second one (total is 916)
choice:   2 3 4 8 16 30 57 111 200 326 390 -454  
/ hirschberg first one, leading to 734
choices:  2 3 4 8 16 30 56 110 173 244 317 -626 
test[choices; howmany]

/ Ted Alper positive number for 4 -- tot is 2737
howmany: 4
choices:      9, 16, 18, 20, 24, 32, 64, 119, 220, 404, 744, 1369
choices: 1 2 4 8 16 31 60 116 230 438 817 1404
test[choices; howmany]

/ Dan Hirschberg and Ted Alperbest integer solution for 4. sum is 1577
/ Different solutions.
howmany: 4
/ hirschberg second one (total is 2717) -- he flipped sums
choices: 2 3 4 8 16 32 61 119 236 431 801 -1366
/ hirschberg first one, leading to 1577
choices:  1 2 4 8 16 31 60 116 224 432 805 -1507
test[choices;howmany]
/ alper
choices: 2, 3, 4, 8, 16, 32, 61, 116, 224, 416, 771, -1468

test[choices;howmany]