Une règle standard de longueur n a des repères de distance aux positions 0, 1, ..., n (dans toutes les unités). Une règle clairsemée a un sous-ensemble de ces marques. Une règle peut mesurer la distance k si elle a des marques aux positions p et q avec p - q = k .

Le défi

Étant donné un entier positif n , sortez le nombre minimum de marques requises dans une règle clairsemée de longueur n afin qu'il puisse mesurer toutes les distances 1, 2, ..., n .

Il s'agit d' OEIS A046693 .

Par exemple, pour l'entrée 6, la sortie est 4. À savoir, une règle avec des marques à 0, 1, 4, 6 fonctionne, car 1−0 = 1, 6−4 = 2, 4−1 = 3, 4−0 = 4, 6−1 = 5 et 6−0 = 6.

Règles supplémentaires

• L'algorithme doit être valide pour un n arbitrairement grand . Cependant, il est acceptable si le programme est limité par des restrictions de mémoire, de temps ou de type de données.
• Les entrées / sorties peuvent être prises / produites par tout moyen raisonnable .
• Les programmes ou fonctions sont autorisés, dans n'importe quel langage de programmation . Les failles standard sont interdites.
• Le code le plus court en octets gagne.

Cas de test

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

Gelée , 14 octets

ŒcIQL
‘ŒPÇÐṀḢL

Un lien monadique prenant et retournant des entiers non négatifs.

Essayez-le en ligne! (15 premières valeurs ici - pas efficace)

Comment?

Trouve toutes les règles que l'on pourrait faire en utilisant les marques 1 à n + 1 (l'ensemble de puissance de [1, n + 1]) ordonnées par leur nombre de marquages, et ne conserve que celles qui créent des distances mesurables maximales (la longueur du ensemble de différences entre toutes les paires de marques ordonnées), puis renvoie la longueur de la première (c'est-à-dire [l'une des] les plus courtes [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

Wolfram Language (Mathematica) , 65 octets

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

Essayez-le en ligne!

Mathematica, 84 octets

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

Essayez-le en ligne!

Pyth , 14 octets

lh.Ml{-M^Z2ySh

Essayez-le ici!

Pyth , 21 19 octets

hlMf!-SQmaFd.cT2ySh

Essayez-le ici!

Comment ça fonctionne

Je mettrai cela à jour après avoir joué au golf.

hSlMfqSQS {maFd.cT2ySh ~ Programme complet. Q = entrée.

                   Sh ~ La plage entière [1, Q + 1].
                  y ~ Powerset.
    f ~ Filtre (utilise une variable T).
              .cT2 ~ Toutes les combinaisons de deux éléments de T.
          m ~ Carte.
           aFd ~ Réduit de la différence absolue.
        S {~ Dédupliquer, trier.
     qSQ ~ Est-il égal à la plage entière [1, Q]?
  lM ~ Carte avec longueur.
hS ~ Minimum.

Merci à isaacg d' avoir enregistré un octet pour ma deuxième approche et de m'avoir inspiré à jouer au golf à 3 octets de mon approche actuelle!

Python 2 , 129 128 126 126 octets

Merci à totalement humain pour -1 octet

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)]

Essayez-le en ligne!

la sortie se fait via le code de sortie

Coque , 20 18 octets

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

Merci @ H.PWiz pour -2 octets!

Essayez-le en ligne!

Explication

λ               )…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

Gelée , 17 octets

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

Essayez-le en ligne!

1 octet enregistré grâce à Jonathan Allan !

Pyth, 15 octets

lhf!-SQ-M^T2yUh

Suite de tests

Comment ça fonctionne

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

Gelée , 17 octets

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

Essayez-le en ligne!

J'ai emprunté une astuce à la réponse de M. Xcoder pour -1.
-1 merci à Jonathan Allan .

Rubis , 98 octets

->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}

Essayez-le en ligne!