Leaderboard

Set of Golden Rulers

The Problem

This problem is a variation of the classic Golomb ruler.

There are $n$ Gold Rulers. On the front of Gold Ruler $k$, there are $k-1$ marks, dividing the ruler into $k$ segments. In the middle of each segment, the length of that segment is marked, all in whole units. Each ruler allows direct measurement of the length between any two marks (including the ends of the ruler). To find the length between two marks, simply add up the lengths of the segments included.
It is easy to see that Gold Ruler $k$ can directly measure $k(k+1)/2$ integer lengths. Therefore, a total of $n$ rulers can measure $L = n(n+1)(n+2)/6$ lengths.
If these lengths are exactly from $1$ to $L$, then these $n$ rulers are called a perfect set of golden rulers.

It is known that for $n \leq 6$, the perfect golden ruler sets all exist. For example, up to symmetry, there exists a unique solution for $n = 6$. (The $k$-th row represents the lengths of the segments of the $k$-th ruler): $$ \begin{array}{cccccc} 39\\ 15 & 27\\ 7 & 33 & 11\\ 2 & 22 & 19 & 13\\ 8 & 10 & 16 & 12 & 9\\ 1 & 4 & 25 & 6 & 14 & 3 \end{array} $$ The measured $56$ lengths are exactly $1$ to $56$.

However, when $n > 6$, whether a solution exists is unknown, and it is very likely that no perfect set of golden rulers exists.

Submission Format

Try to solve $n=7$.
Please input a CSV of $28$ positive integers (each number does not exceed $10000$), representing the lengths of segments from ruler $1$ to ruler $7$ in order.

Let the set of all measured lengths be $\mathcal{P}$. The score is computed as: $$\mathsf{score}(\mathcal{P}) := \lvert \mathcal{P} \cap \{1,2,\dots,84\} \rvert$$ That is, to count how many distinct lengths from $1$ to $84$ can be measured.
The goal is to maximize the score.

Score Implementation

The following is a Python implementation of the score function to help you get started.


from itertools import combinations


def score(nums: list[int]):
    N = 7

    # Check the length of array
    if len(nums) != N*(N+1)//2:
        return None

    # Check the value range of array elements
    for x in nums:
        if x < 1 or x > 10000:
            return None

    # Calculate the set of lengths measured by all rulers
    diffs = set()
    for k in range(N):
        v = [0]
        a = 0
        for i in range(k*(k+1)//2, k*(k+1)//2+k+1):
            a += nums[i]
            v.append(a)
        for n1, n2 in combinations(v, 2):
            diffs.add(abs(n1 - n2))

    # Calculate score
    perfect = set(range(1, N*(N+1)*(N+2)//6+1))
    return len(perfect.intersection(diffs))