20
\$\begingroup\$

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 pq=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

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
\$\endgroup\$

10 Answers 10

2
\$\begingroup\$

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
\$\endgroup\$
8
\$\begingroup\$

Wolfram Language (Mathematica), 65 bytes

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

Try it online!

\$\endgroup\$
5
\$\begingroup\$

Mathematica, 84 bytes

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

Try it online!

\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Since the powerset is ordered by length, the first S is unnecessary. \$\endgroup\$ – isaacg Nov 26 '17 at 22:12
  • \$\begingroup\$ @isaacg Thanks! Your great answer (+1) also inspired me to save 3 bytes off my new approach, making it 14 bytes. \$\endgroup\$ – Mr. Xcoder Nov 27 '17 at 5:50
5
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ oa- is the same as \$\endgroup\$ – H.PWiz Nov 26 '17 at 21:04
  • \$\begingroup\$ @H.PWiz it really only matters that their lengths are the same, because there can't be any differences outside the [0..N] range. \$\endgroup\$ – Martin Ender Nov 26 '17 at 21:20
  • \$\begingroup\$ You could probably even use . \$\endgroup\$ – Martin Ender Nov 26 '17 at 21:20
4
\$\begingroup\$

Jelly, 17 bytes

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

Try it online!

Saved 1 byte thanks to Jonathan Allan!

\$\endgroup\$
  • \$\begingroup\$ The power-set is sorted from shortest to longest so I think ḢL should be OK.. \$\endgroup\$ – Jonathan Allan Nov 26 '17 at 23:02
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ The power-set is sorted from shortest to longest so I think ḢL should be OK.. \$\endgroup\$ – Jonathan Allan Nov 26 '17 at 23:02
1
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.