This challenge was inspired by this tweet.
Idea
Consider a circle with n evenly spaced dots around the perimeter, where each dot has a postive integer value:
Now connect the dots with non-intersecting chords:
Next consider our score, which is the sum of the products of these pairs. When n is odd, the extra orphan dot will not contribute to our score.
Finally we ask: Which pairing of dots gives us the highest score?
Task
Write a program to solve this puzzle.
Input
A list of postive integers, in order, representing the values of the dots which are spread evenly around the circumference of a circle.
Output
A list of pairs of the same integers, representing an optimal solution to the puzzle described above.
That is, the pairs you return must:
- Produce non-intersecting circle chords when connected by straight lines.
- Produce a maximal score among all possible solutions that satisfy rule 1.
The score we're maximizing is the sum of the products of the pairs, and for odd-length input does not include the unpaired number.
In some cases, such as [1, 9, 1, 9], the optimal solution will voluntarily leave unpaired numbers. In this example the solution is to pair the two 9s and leave the two 1s as singletons.
Additional notes:
- Again, for odd-length input, the unpaired number won't contribute to your score. You may include this singleton in your output or not.
- Same goes for "voluntary" singletons such as the
[1, 9, 1, 9]described above. - In addition to the optimal list of pairs, you may include the optimal score value as well, but don't have to.
- If 2 or more solutions tie, you may output any one of them, or all of them.
- The order in which the optimal pairs are given doesn't matter.
Rules
This is code golf with standard site rules. Both input and output formats are flexible. In particular, output may be:
- An array of arrays, where the inner arrays have length 2.
- An n by 2 or 2 by n matrix.
- A single flat list, so long as all the optimal pairs are adjacent.
- Anything else reasonable.
Test Cases
I included optimal score for convenience but it's not required in the output.
Input: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Output: [[2, 3], [4, 5], [6, 7], [8, 9]]
Score: 140
Input: [1, 2, 3, 4, 5, 6, 7, 8]
Output: [[1, 2], [3, 4], [5, 6], [7, 8]]
Score: 100
Input: [1, 4, 8, 7, 11, 2, 5, 9, 3, 6, 10]
Output: [[4, 3], [6, 10], [8, 7], [11, 9], [2, 5]]
Score: 237
Input: [12, 8, 2, 20, 16, 7]
Output: [[12, 8], [2, 7], [20, 16]]
Score: 430
Input: [29, 27, 23, 22, 14, 13, 21, 7, 26, 27]
Output: [[29, 27], [23, 22], [14, 7], [26, 27], [13, 21]]
Score: 2362
Input: [1, 9, 1, 9]
Output: [[9, 9]]
Score: 81
[1, 9, 1, 9]->[[9, 9]]\$\endgroup\$