# Most Valuable Circle Chords

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?

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:

1. Produce non-intersecting circle chords when connected by straight lines.
2. 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.

• 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

• Suggest [1, 9, 1, 9] -> [[9, 9]]
– att
Jul 11 '21 at 18:40
• @att Nice clarification. I added the test case and a note in the output spec. Jul 11 '21 at 18:47
• @pajonk It is mentioned in the question twice. Now connect the dots with non-intersecting chords:, 1. Produce non-intersecting circle chords when connected by straight lines.
– user100752
Jul 11 '21 at 19:52
• I'm confused on the voluntary singletons. Would we still count the 1s even though they're unpaired? Why would that be if we don't count a leftover singleton in the odd-dot case? Jul 13 '21 at 4:30
• Oh! But they can't cross! NVM got it. Jul 15 '21 at 9:45

# Jelly, 45 43 bytes

ṖẎƤṚ+"JpẎ€¥"Ʋṭ@€"J,€¥ɗẎṭḷ
Jçƒ0RWW¤Ẏị¹ZPSƊÐṀ


Try it online!

Uses a modified f(n), which is defined as sets of chords containing the vertex n.

# Jelly, 45 bytes

ṖṚ+"JpẎ€¥"Ʋṭ@€"J,€¥ɗẎ;ṛ/{ṭḷ
Jçƒ0RWW¤Ṫị¹ZPSƊÐṀ


Try it online!

Painfully long, but runs pretty fast.

Basic algorithm is to compute all the possible sets of chords (as indices) via memoization. Let's define f(n) as the list of all possible sets of chords using first n nodes, i.e. 1..n. f(0) and f(1) contain a single empty set, and f(2) is [[], [[1, 2]]]. Also, let's define f(0..n) to be [f(0), f(1), ..., f(n)]. Then the following recurrence holds:

f(n+1) = f(n) ++
cartesian product of f(0) and (1 + f(n-1)), with [1, n+1] added to each set ++
cartesian product of f(1) and (2 + f(n-2)), with [2, n+1] added to each set ++
... ++
cartesian product of f(n-1) and (n + f(0)), with [n, n+1] added to each set


where ++ is list concatenation and + is vectorized addition.

ṖṚ+"JpẎ€¥"Ʋṭ@€"J,€¥ɗẎ;ṛ/{ṭḷ    Aux. dyadic link: left=f(0..n), right=n+1
Ṗ                              H = f(0..n-1)
AAAAAAAAAAbbbbccccɗ           A(H) b (H c n+1)
Ṛ+"J                          Reverse H and add 1..n (zipped)
pẎ€¥"                     Cartesian product by concatenation with H
ṭ@€"                Zipped append the following to each set:
J,€¥            [1,n+1], ..., [n,n+1]
Ẏ          Collect lists of sets into one list of sets
;ṛ/{      Combine with the sets without n+1
ṭḷ    Push into f(0..n) to get f(0..n+1)

J                    Indices of the list
çƒ0RWW¤             Reduce over it using the aux link, starting from [[[]]]
Ṫị¹          Take the last result; convert the indices to actual values
ZPSƊÐṀ    Find the set of chords with the highest sum of product


Probably I can golf it by not taking the right argument of the aux link (which is simply the length of the left arg), but I don't want to torture myself further...

# Jelly,  28  27 bytes

JŒcŒPŒcZFṢƑ<QƑƊƊ€ẠƊƇịZPSɗÐṀ


A monadic Link that accepts a list of integers and yields a list of all most valuable lists of chord-end pairs.

Try it online! Very inefficient.

### How?

JŒcŒPŒcZFṢƑ<QƑƊƊ€ẠƊƇịZPSɗÐṀ - Link: list A
J                           - get indices -> [1,2,...,length(A)]
Œc                         - pairs
ŒP                       - powerset
Ƈ        - filter keep those for which:
Œc                     -     pairs
€           -     for each:
Z                    -         transpose
F                   -         flatten
Ƒ                 -           is invariant under:
Ṣ                  -             sort -> x
Ƒ              -           is invariant under:
Q               -             deduplicate -> y
<                -           (x) less than (y)?
Ạ          -     all?
ị       - index into (A)*
ÐṀ - keep those maximal under:
Z      -     transpose (the entry)
P     -     product (vectorised across this transposed entry)
S    -     sum (of those products)

* Note: ị takes A on the right Implicitly due to the next
it does not need to be), this saves a byte.


# Jelly, 27 26 bytes

JŒcŒPŒc_€/ṠÆḊ¬Ʋ€ẠƊƇịZPSɗÐṀ


Try it online!

-1 byte thanks to @caird.

Independently arrived at something very similar to Jonathan Allan's solution.

The only difference is _€/ṠÆḊ¬Ʋ part, which tests if two pairs of indices are two non-intersecting chords.

Because of how ŒP (powerset) and Œc (unordered pairs) generate the results, it is sufficient to filter out the pairs of pairs which have the element-wise ordering of [[1, 3], [2, 4]], [[1, 2], [1, 3]], [[1, 2], [2, 3]], or [[1, 3], [2, 3]]. The pairs [[1, 2], [3, 4]] and [[1, 4], [2, 3]] should be kept intact. Test this condition.

_€/ṠÆḊ¬Ʋ    Given a 2x2 matrix of values, test if they're valid chords
_€/Ṡ        Sign of cartesian pair-wise difference
ÆḊ      Determinant
¬     1 if zero, 0 otherwise

• You can steal Jonathan's golf to save a byte: use ịZPSɗÐṀ instead of ị³ZPSƊÐṀ, Try it online! Jul 12 '21 at 18:31

# Wolfram Language (Mathematica), 1149888 86 bytes

f@r_:=SortBy[f@Drop[r,#]~Append~r[[#]]&/@Subsets[j=0;++j&/@r,{2}],Dot@@-#&]~Last~{}


Try it online!

j=0;++j&/@r                     range over input
Subsets[ % ,{2}]                get pairs
f@Drop[r,#]                     recurse on values not between indices
~Append~r[[#]]        and append chord
/@ %    for each pair
SortBy[ % ,Dot@@-#&]~Last~     get the set of chords with the highest sum of products,
{}   if there are no chord sets (i.e. len(r)<2), return an empty set


Since - has lower precedence than  (Transpose), Dot@@-#& is interpreted as Dot@@(-(#))&, which turns out to be equivalent to Dot@@(#)& since the negatives cancel out.

Here's a walkthrough for when f is called on {1,8,2,9}:

r                       =   {1, 8, 2, 9}
j=0;++j&/@r             =   {1, 2, 3, 4}
Subsets[ % ,{2}]        =   {1,2}       {1,3}       {1,4}       {2,3}       {2,4}       {3,4}
map:
Drop[r,#]           =   {    2 9}   {      9}   {       }   {1     9}   {1      }   {1 8    }
r[[#]]              =   {1 8    }   {1   2  }   {1     9}   {  8 2  }   {  8   9}   {    2 9}
Append[f@ %2 ,      =   {{2,9}      {           {           {{1,9}      {           {{1,8}
% ]         =    {1,8}}      {1,2}}      {1,9}}      {8,2}}      {8,9}}      {2,9}}
sorting function:
Dot@@-#            =   26          2           9           25          72          26
SortBy[ ... ]~Last~{}   =                                                   {{8,9}}

• If you get a chance I'd like to see an explanation. Jul 11 '21 at 22:23
• @Jonah Added. The written explanation felt lacking, so I hope the walkthrough illustrates what's going on...
– att
Jul 11 '21 at 23:45
• Thanks very much! Jul 11 '21 at 23:52

# Python 3, 135 117 bytes

f=lambda x:x and max([[[x[0],v]][:i]+f(x[1:i])+f(x[i+1:])for i,v in enumerate(x)],key=lambda y:sum(a*b for a,b in y))


-18 thanks to @ovs and @dingledooper

thanks to @EliteDaMyth for earlier correction

Try it online!

• 126 bytes by including the case of not using the first dot in the list comprehension.
– ovs
Jul 11 '21 at 20:26
• 117 bytes Jul 11 '21 at 20:31
• Very nice, both. I was about to replace [x[0],x[i]] with x[:i+1:i], but that doesn't work for the new i=0 case! Jul 11 '21 at 20:55

# Jelly, 29 bytes

JŒcŒPFQƑ$ƇŒcZFṢƑƊƇƊÐḟị¹P€S$ÐṀ


Try it online!

This is a total mess, extremely inefficient, possibly not working correctly and probably very outgolfable.

-2 bytes thanks to caird

• "This is a total mess, extremely inefficient, possibly not working correctly and probably very outgolfable." Have an upvote! I am curious what the big-O is here -- it's slow even for lists of 6. Jul 11 '21 at 22:19
• Œc is an alias for œc2, saving 2 bytes Jul 11 '21 at 22:52