Golomb rulers are sets of non-negative integers such that no two pairs of integers in the set are the same distance apart.
[0, 1, 4, 6] is a Golomb ruler because all distances between two integers in this set are unique:
0, 1 -> distance 1 0, 4 -> distance 4 0, 6 -> distance 6 1, 4 -> distance 3 1, 6 -> distance 5 4, 6 -> distance 2
For the sake of simplicity in this challenge (and since translation is trivial), we impose that a Golomb ruler always contains the number
0 (which the previous example does).
Since this set is of length
4, we say that this is a Golomb ruler of order
4. The biggest distance in this set (or element, since
0 is always in the set) is
6, therefore we say that this is a Golomb Ruler of length
Find Golomb rulers of order
100 (inclusive) that have as small lengths as you can find. The rulers you find need not be optimal (see below).
A Golomb ruler of order
N, is said to be optimal if there is no other Golomb ruler of order
N which has a smaller length.
Optimal Golomb rulers are known for orders less than 28, though finding and proving optimality is harder and harder as the order increases.
Therefore, it is not expected that you find the optimal Golomb ruler for any of the orders between
100 (and even less expected that you can prove they are optimal).
There are no time limits in the execution of your program.
The list below is the list of lengths of Golomb rulers from
100 (in order) evaluated with a naïve search strategy (Thanks to @PeterTaylor for this list):
[4850 5122 5242 5297 5750 5997 6373 6800 6924 7459 7546 7788 8219 8502 8729 8941 9881 10199 10586 10897 11288 11613 11875 12033 12930 13393 14046 14533 14900 15165 15687 15971 16618 17354 17931 18844 19070 19630 19669 20721 21947 22525 23290 23563 23880 24595 24767 25630 26036 26254 27218]
The sum of all those lengths is
Your score will be the sum of the lengths of all your Golomb rulers between
100, divided by the sum of the lengths of Golomb rulers between
100 in the baseline:
In case you did not find a Golomb ruler for a specific order, you shall compute your score the same way, using the double of the length in the baseline for that specific order.
The answer with the lowest score wins.
In case of a tie, the lengths of the biggest order where the two answers differ are compared, and the shortest one wins. In case both answers have the same lengths for all orders, then the answer that was posted first wins.