A puzzle box shows a row of arrows, given as the complex numbers amps. Under each arrow is a dial with four clicks: every click turns that arrow a quarter turn anticlockwise, which is a multiplication by i (1j). So each arrow can be shown as a, ia, -a or -ia. The box lights up as brightly as the sum of the shown arrows is long.
Write brightest(amps) that returns the largest length \left|\sum_k r_k a_k\right| that any setting of the dials can reach, where every r_k is one of 1, 1j, -1, -1j.
There are 4^n settings for n arrows, far too many to try for 500 arrows. (Later in this path, multiplying one amplitude by i will be a gate called S, and steering many arrows so that they add up is how quantum algorithms make the right answer likely.)
Examples
Input: amps = [1, 1j]
Output: 2.0
Explanation: three clicks on the second dial turn 1j into -1j * 1j = 1, and 1 + 1 = 2.
Input: amps = [5+4j, 5-4j]
Output: 12.727922061357855
Explanation: untouched, the sum is 10. One click on the second dial turns 5-4j into 4+5j,
and (5+4j) + (4+5j) = 9+9j, of length 9 * sqrt(2). No setting does better.
The empty row, and a row of zeros, gives 0.0.
Constraints
0 <= len(amps) <= 500, and every arrow has modulus at most 1000- a plain-Python solution should finish each test within about a second; trying all settings works only up to about 8 arrows
- answers are compared with a tolerance of
1e-6
Goals
- Model a quarter turn as multiplication by 1j
- Reason about which choices can be optimal instead of trying all 4^n of them
- Turn a sweep over directions into a sorted list and running sums