Minimal sparse rulers

Question

A standard ruler of length n has distance marks at positions 0, 1, ..., n (in whichever units). A sparse ruler has a subset of those marks. A ruler can measure the distance k if it has marks at positions p and q with p−q=k.

The challenge

Given a positive integer n, output the minimum number of marks required in a sparse ruler of length n so that it can measure all distances 1, 2, ..., n.

This is OEIS A046693.

As an example, for input 6 the output is 4. Namely, a ruler with marks at 0, 1, 4, 6 works, as 1−0=1, 6−4=2, 4−1=3, 4−0=4, 6−1=5, and 6−0=6.

Additional rules

• The algorithm should be valid for arbitrarily large n. However, it is acceptable if the program is limited by memory, time or data type restrictions.
• Input/output can be taken/produced by any reasonable means.
• Programs or functions are allowed, in any programming language. Standard loopholes are forbidden.
• Shortest code in bytes wins.

Test cases

1   ->   2
2   ->   3
3   ->   3
4   ->   4
5   ->   4
6   ->   4
7   ->   5
8   ->   5
9   ->   5
10  ->   6
11  ->   6
12  ->   6
13  ->   6
14  ->   7
15  ->   7
16  ->   7
17  ->   7
18  ->   8
19  ->   8
20  ->   8
21  ->   8
22  ->   8
23  ->   8
24  ->   9
25  ->   9
26  ->   9
27  ->   9
28  ->   9
29  ->   9
30  ->  10
31  ->  10 
32  ->  10

Answer 1

Wolfram Language (Mathematica), 65 bytes

Tr[1^#]&@@Cases[Subsets[n=0~Range~#],k_/;Union@@Abs[k-#&/@k]==n]&

Try it online!

Answer 2

Mathematica, 84 bytes

#&@@(l=Length)/@Select[(S=Subsets)@Range[0,d=#],l@Union[Differences/@S[#,{2}]]==d&]&

Try it online!

Answer 3

Pyth, 14 bytes

lh.Ml{-M^Z2ySh

Try it here!

Pyth, 21 19 bytes

hlMf!-SQmaFd.cT2ySh

Try it here!

How it works

I'll update this after golfing.

hSlMfqSQS{maFd.cT2ySh ~ Full program. Q = input.

                   Sh ~ The integer range [1, Q + 1].
                  y   ~ Powerset.
    f                 ~ Filter (uses a variable T).
              .cT2    ~ All two-element combinations of T.
          m           ~ Map.
           aFd        ~ Reduce by absolute difference.
        S{            ~ Deduplicate, sort.
     qSQ              ~ Is equal to the integer range [1, Q]?
  lM                  ~ Map with length.
hS                    ~ Minimum.

Thanks to isaacg for saving a byte for my second approach and inspiring me to golf 3 bytes off my current approach!

Answer 4

Python 2, 129 128 126 bytes

thanks to totallyhuman for -1 byte

from itertools import*
r=range(1,input()+2)
[{a-b+1for a in l for b in l}>set(r)>exit(i)for i in r for l in combinations(r,i)]

Try it online!

output is via exit code

Answer 5

Husk, 20 18 bytes

λ▼mLfȯ≡⁰u´×≠tṖ⁰)…0

Thanks @H.PWiz for -2 bytes!

Try it online!

Explanation

λ               )…0  -- lambda with argument ⁰ as [0..N]
              Ṗ⁰     -- all subsets of [0..N]
             t       -- tail (remove empty subset)
    f(      )        -- filter by following function:
           ≠         --   absolute differences
         ´×          --   of all pairs drawn from itself
        u            --   remove duplicates
      ≡⁰             --   "equal" to [0..N]
  mL                 -- map length
 ▼                   -- minimum

Answer 6

Jelly, 17 bytes

‘ŒPµạþ`FQḊṫ³µÐfḢL

Try it online!

Saved 1 byte thanks to Jonathan Allan!

Answer 7

Pyth, 15 bytes

lhf!-SQ-M^T2yUh

Test suite

How it works

lhf!-SQ-M^T2yUh
             Uh    [0, 1, ... n]
            y      Powerset - all possible rulers
  f                Filer rulers on
         ^T2       All pairs of marks, in both orders
       -M          Differences - (a)
     SQ            [1, ... n], the desired list of differences - (b)
    -              Remove (a) from (b)
   !               Check that there's nothing left.
 h                 The first remaining ruler (powerset is ordered by size)
l                  Length

Answer 8

Jelly, 17 bytes

_þ`ẎQṢw
‘ŒPçÐfRḢL

Try it online!

Borrowed a trick from Mr. Xcoder's answer for -1.
-1 thanks to Jonathan Allan.

Answer 9

Jelly, 14 bytes

ŒcIQL
‘ŒPÇÐṀḢL

A monadic link taking and returning non-negative integers.

Try it online! (first 15 values here - not efficient)

How?

Finds all the rulers one could make using marks 1 through to n+1 (the power-set of [1,n+1]) ordered by their marking-count, and keeps only those which create maximal measurable distances (the length of the set of differences between all ordered pairs of marks), then returns the length of the first (i.e. [one of] the shortest one[s]).

ŒcIQL - Link 1: number of measurable distances: list of numbers, ruler  e.g. [1,2,3,7]
Œc    - all pairs                                [[1,2],[1,3],[1,7],[2,3],[2,7],[3,7]]
  I   - incremental differences                                          [1,2,6,1,5,4]
   Q  - de-duplicate                                                       [1,2,6,5,4]
    L - length                                                                      5

‘ŒPÇÐṀḢL - Main link: number, n              e.g. 4
‘        - increment                              5
 ŒP      - power-set (implicit range of input)   [[],[1],[2],[3],[4],[5],[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[2,5],[3,4],[3,5],[4,5],[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5],[1,2,3,4],[1,2,3,5],[1,2,4,5],[1,3,4,5],[2,3,4,5],[1,2,3,4,5]]
    ÐṀ   - keep those maximal under:
   Ç     -   call the last link (1) as a monad   [[1,2,3,5],[1,2,4,5],[1,3,4,5],[1,2,3,4,5]]
      Ḣ  - head                                  [1,2,3,5]
       L - length                                 4

Answer 10

JavaScript (ES7), 115 bytes

Returns the \$n\$-th term.

Adapted from my answer to this other challenge.

f=(n,N)=>(g=q=>--q&&(h=j=>~j?q>>j&1**h(j-1)&&N/a.push(a.map(x=>h|=1<<j+~x)&&j):a=[])(n)+h>>n|g(q))(2<<n)?N:f(n,-~N)

Try it online!

Answer 11

Ruby, 98 bytes

->n{(w=*0..n).find{|x|w.combination(x+1).find{|y|y.product(y).map{|a,b|(b-a).abs}.uniq.size>n}}+1}

Try it online!