Pair Capacitors

Question

Capacitors are notorious for being manufactured with high tolerances. This is acceptable in many cases, but some times a capacity with tight tolerances is required. A common strategy to get a capacity with the exact value you need is to use two carefully measured capacitors in parallel such that their capacities add up to something in the range you need.

The goal in this challenge is, given a (multi) set of capacities, to pair the capacitors such that the total capacity of each pair is in a given range. You also need to find the best set of pairings, that is, the set of pairings such that as many pairs as possible are found.

Constraints

1. Input comprises in a format of choice
   • an unordered list of capacities representing the (multi) set of capacitors you have
   • a pair of capacities representing the lower and upper bound of the target range (inclusive)
2. all capacities in the input are positive integers smaller than 2³⁰, the unit is pF (not that that matters).
3. In addition to the list of capacities in the input, the set of capacitors you have also contains an infinite amount of capacitors with a value of 0 pF.
4. Output comprises in a format of choice a list of pairs of capacities such that the sum of each pair is in the target range specified. Neither the order of pairs nor the order of capacities within a pair is specified.
5. No capacity in the output may appear more often than it appears in the set of capacitors you have. In other words: The pairs you output must not overlap.
6. There shall be no possible output satisfying conditions 4 and 5 that contains more pairs of capacities than the output your program produces.
7. Your program shall terminate in O(n!) time where n is the length of the list representing the set of capacitors you have
8. Loopholes shall not be abused
9. The target range shall not be empty

Scoring

Your score is the length of your solution in octets. If your solution manages to solve this problem in polynomial time O(n^k) for some k, divide your score by 10. I do not know if this is actually possible.

Sample input

• range 100 to 100, input array 100 100 100, valid output:

  0 100
  0 100
  0 100
  

• range 100 to 120, input array 20 80 100, valid output:

  0 100
  20 80
  

  the output 20 100 is not valid

• range 90 to 100, input array 50 20 40 90 80 30 60 70 40, valid output:

  0 90
  20 80
  30 70
  40 60
  40 50
  

• range 90 to 90, input array 20 30 40 40 50 60 70 80 90, valid output:

  0 90
  20 70
  30 60
  40 50
  

• range 90 to 110, input array 40 60 50, valid output:

  40 60
  

Answer 1

CJam, 5.6

This is a direct re-implementation of the algorithm in orlp's answer. If you upvote my answer, please make sure that you also upvote this answer. I also suggest that the answer with the original algorithm is accepted, because I very much doubt that I would have figured out how to solve this elegantly in O(n*log(n)).

l~_,0a*+${(\)@_2$+4$~2$\>{;;\;\+}{<{;+}{oSop}?}?_,1>}g;;

Try it online

Sample input:

[90 100] [50 20 40 90 80 30 60 70 40]

Explanation:

l~      Get and interpret input.
_,      Get length of resistor list.
0a*+    Append the same number of 0 values.
$       Sort the list.
{       Loop until less than 2 entries in list.
  (       Pop off first value.
  \)      Pop off last value.
  @_      Pull first value to top, and copy it.
  2$      Copy last value to top.
  +       Add first and last value.
  4$~     Copy specified range to top, and unwrap the two values.
  2$      Copy sum to top.
  \>      Swap and compare for sum to be higher than top of range.
  {       It's higher.
    ;;\;    Some stack cleanup.
    \+      Put first value back to start of resistor list.
  }
  {       Not higher, so two cases left: value is in range, or lower.
    <       Compare if sum is lower than bottom of range.
    {       It's lower.
      ;+      Clean up stack and put last value back to end of resistor list.
    }
    {       Inside range, time to produce some output.
      o       Output first value.
      So      Output space.
      p       Output second value and newline.
    }?      Ternary operator for comparison with lower limit.
  }?      Ternary operator for comparison with upper limit.
  _,      Get length of remaining resistor list.
  1>      Check if greater 1.
}g      End of while loop for processing resistor list.
;;      Clean up stack, output was generated on the fly.

Answer 2

Python 2, 11.5

A Python golf for once:

(a,b),l=input()
l=[0]*len(l)+sorted(l)
while l:
 e=l[0]+l[-1]
 if a<=e<=b:print l[0],l[-1]
 l=l[e<=b:len(l)-(a<=e)]

I add one 0 pF capacitor for every regular one, there are never any more needed. Then we sort the capacitors and keep pairing the lowest and highest capacitor. If the sum is within the allowable range we print it, if it is above the range we discard the highest, if it's below discard the lowest.

Example input / output:

[[90,100], [20,30,40,40,50,60,70,80,90]]

0 90
20 80
30 70
40 60
40 50