Minimale spärliche Lineale

20

Ein Standardlineal der Länge n hat Abstandsmarkierungen an den Positionen 0, 1, ..., n (in welchen Einheiten auch immer). Ein dünn besetztes Lineal hat eine Teilmenge dieser Marken. Ein Lineal kann den Abstand k messen, wenn es Markierungen an den Positionen p und q mit p - q = k hat .

Die Herausforderung

Geben Sie bei einer positiven Ganzzahl n die Mindestanzahl von Markierungen aus, die in einem dünnen Lineal der Länge n erforderlich sind , damit alle Abstände 1, 2, ..., n gemessen werden können .

Dies ist OEIS A046693 .

Als Beispiel für die Eingabe 6 ist die Ausgabe 4. Ein Lineal mit den Markierungen 0, 1, 4, 6 funktioniert also wie folgt: 1−0 = 1, 6−4 = 2, 4−1 = 3, 4−0 = 4, 6-1 = 5 und 6-0 = 6.

Zusätzliche Regeln

  • Der Algorithmus sollte für beliebig große n gültig sein . Es ist jedoch akzeptabel, wenn das Programm durch Speicher-, Zeit- oder Datentypbeschränkungen eingeschränkt ist.
  • Input / Output kann auf jede vernünftige Weise genommen / produziert werden .
  • Programme oder Funktionen sind in jeder Programmiersprache zulässig . Standardlücken sind verboten.
  • Kürzester Code in Bytes gewinnt.

Testfälle

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
Luis Mendo
quelle
Related
Luis Mendo

Antworten:

2

Jelly , 14 Bytes

ŒcIQL
‘ŒPÇÐṀḢL

Eine monadische Verknüpfung, die nicht negative ganze Zahlen aufnimmt und zurückgibt.

Probieren Sie es online! (erste 15 Werte hier - nicht effizient)

Wie?

Findet alle Lineale, die man mit den Markierungen 1 bis n + 1 (Potenzmenge von [1, n + 1]) machen kann, geordnet nach der Anzahl der Markierungen, und behält nur die bei, die maximal messbare Abstände schaffen (die Länge der Differenzmenge zwischen allen geordneten Markenpaaren), gibt dann die Länge der ersten zurück (dh [eine der] kürzesten [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
Jonathan Allan
quelle
5

Mathematica, 84 Bytes

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

Probieren Sie es online!

J42161217
quelle
5

Pyth , 14 Bytes

lh.Ml{-M^Z2ySh

Probieren Sie es hier aus!

Pyth , 21 bis 19 Bytes

hlMf!-SQmaFd.cT2ySh

Probieren Sie es hier aus!

Wie es funktioniert

Ich werde dies nach dem Golfen aktualisieren.

hSlMfqSQS {maFd.cT2ySh ~ Volles Programm. Q = Eingabe.

                   Sh ~ Der ganzzahlige Bereich [1, Q + 1].
                  y ~ Powerset.
    f ~ Filter (verwendet eine Variable T).
              .cT2 ~ Alle Zwei-Elemente-Kombinationen von T.
          m ~ Karte.
           aFd ~ Reduzieren um absolute Differenz.
        S {~ Deduplizieren, sortieren.
     qSQ ~ Ist gleich dem ganzzahligen Bereich [1, Q]?
  lM ~ Karte mit Länge.
hS ~ Minimum.

Vielen Dank an Isaacg , der ein Byte für meinen zweiten Ansatz gespeichert und mich dazu inspiriert hat, 3 Byte von meinem aktuellen Ansatz abzuweichen !

Mr. Xcoder
quelle
Da das Powerset nach Länge sortiert ist, ist das erste Snicht erforderlich .
Isaacg
@isaacg Danke! Ihre großartige Antwort (+1) hat mich auch dazu inspiriert, 3 Bytes bei meinem neuen Ansatz einzusparen, sodass es 14 Bytes sind.
Mr. Xcoder
5

Python 2 , 129 128 126 Bytes

danke an totalhuman für -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)]

Probieren Sie es online!

Die Ausgabe erfolgt über den Exit-Code

ovs
quelle
4

Schale , 20 bis 18 Bytes

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

Danke @ H.PWiz für -2 Bytes!

Probieren Sie es online!

Erläuterung

λ               )…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
ბიმო
quelle
oa-ist das gleiche wie
H.PWiz
@ H.PWiz es kommt wirklich nur darauf an, dass ihre Längen gleich sind, da es keine Unterschiede außerhalb des [0..N] Bereichs geben kann.
Martin Ender
Sie könnten wahrscheinlich sogar verwenden .
Martin Ender
3

Pyth, 15 Bytes

lhf!-SQ-M^T2yUh

Testsuite

Wie es funktioniert

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
isaacg
quelle
1

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}

Probieren Sie es online!

GB
quelle