Rekonstruieren Sie eine arithmetische Folge

23

Bei einer endlichen arithmetischen Folge von positiven ganzen Zahlen, wobei einige Ausdrücke aus der Mitte entfernt sind, rekonstruieren Sie die gesamte Folge.

Die Aufgabe

Stellen Sie sich eine arithmetische Folge vor: Eine Liste positiver Ganzzahlen, in der der Unterschied zwischen zwei aufeinanderfolgenden Elementen gleich ist.

2 5 8 11 14 17

Angenommen, eine oder mehrere Ganzzahlen werden aus der Sequenz entfernt, unter folgenden Bedingungen:

  • Die entfernten ganzen Zahlen sind aufeinanderfolgende Terme der Sequenz.
  • Die ersten und letzten Ganzzahlen in der Sequenz werden nicht entfernt.
  • Es bleiben mindestens drei ganze Zahlen in der Sequenz.

Mögliche Entfernungen für die obige Sequenz sind:

2 5 8 14 17  (removed 11)
2 5 17       (removed 8 11 14)
2 14 17      (removed 5 8 11)

Ihre Aufgabe: Stellen Sie mit einer dieser Teilsequenzen die ursprüngliche vollständige Sequenz wieder her.

Einzelheiten

Sie können davon ausgehen, dass die Eingabe gültig ist (eine Lösung hat) und mindestens ein Begriff fehlt. Alle Zahlen in der Sequenz sind positive ganze Zahlen (> 0). Die Sequenz kann einen positiven oder negativen Unterschied zwischen Begriffen aufweisen (dh sie kann zunehmen oder abnehmen). Es wird keine konstante Sequenz sein (zB 5 5 5).

Ihre Lösung kann ein vollständiges Programm oder eine Funktion sein . Alle Standardeingabe- und -ausgabemethoden sind zulässig.

Ihre Eingabe und Ausgabe kann eine Zeichenfolge (mit einem sinnvollen Trennzeichen), eine Liste von Zeichenfolgen oder eine Liste von Zahlen sein. Sie können die Zahlen in jeder für Ihre Sprache geeigneten Basis darstellen.

Bitte erwähnen Sie ungewöhnliche I / O-Methoden / -Formate in Ihrer Einreichung, damit andere Ihren Code einfacher testen können.

Testfälle

In: 2 5 8 14 17
Out: 2 5 8 11 14 17
In: 2 5 17
Out: 2 5 8 11 14 17
In: 2 14 17
Out: 2 5 8 11 14 17
In: 21 9 6 3
Out: 21 18 15 12 9 6 3
In: 10 9 5
Out: 10 9 8 7 6 5
In: 1 10 91 100
Out: 1 10 19 28 37 46 55 64 73 82 91 100

Das ist ; die kürzeste Antwort in jeder Sprache gewinnt.

DLosc
quelle
Related
DLosc
Wäre interessant gewesen, die Eingabe in der Form zu haben2 5 ... 17
schnaader

Antworten:

9

Haskell , 63 Bytes

f(a:b:c)|s<-[a,b..last c],all(`elem`s)c=s
f a=r$f$r a
r=reverse

Probieren Sie es online!

Grundsätzlich funktioniert dies, indem versucht wird, das Ergebnis von vorne und, falls dies fehlschlägt, von hinten aufzubauen. Dies basiert auf der Tatsache, dass das erste und das letzte Element der Eingabe immer korrekt sind, dass gelöschte Elemente aufeinanderfolgend sein müssen und dass die Eingabe immer mindestens drei Elemente enthält. Ich muss nur davon ausgehen, dass das vorletzte oder zweitletzte Mitglied korrekt ist und überprüft, ob es funktioniert. Zum Glück hat Haskell eine sehr schöne Syntax für die Erstellung von Rechenserien.

EDIT: Danke an @xnor für das Aufzeigen eines Fehlers und das Bereitstellen einer Lösung!

user1472751
quelle
5
Obwohl dies hübsch ist, scheint es nicht immer zu funktionieren: [1,3,4,5]gibt [1,3,5].
Xnor
1
Und ich denke, all(`elem`s)csollte es mit der gleichen Byteanzahl beheben.
Xnor
6

05AB1E , 9 8 Bytes

Ÿs¥¿Äô€н

Probieren Sie es online!

Erläuterung

  • Konstruieren Sie den Bereich [first, ..., last] mit einer Differenz von +/- 1
  • Berechnen Sie die Deltas der Eingabe
  • Holen Sie sich den absoluten Wert des GCD der Deltas
  • Teilen Sie das gesamte Sortiment in Stücke dieser Größe auf
  • Holen Sie sich das erste Element jedes Blocks

1 Byte mit gcd of deltasstatt gespeichertmin delta , inspiriert von user202729

Emigna
quelle
5

Brachylog v2, 9 Bytes

⊆.s₂ᵇ-ᵐ=∧

Probieren Sie es online!

Dies ist eine Funktionsübermittlung. Mit dem Brachylog-Interpreter kann eine Funktion wie ein vollständiges Programm ausgewertet werden, indem sie Zals Befehlszeilenargument angegeben wird. In diesem Fall wird die Eingabe in dem Format angegeben, z. B., [1, 2, 4]und die Ausgabe wird in einem ähnlichen Format zurückgegeben, z Z = [1, 2, 3, 4]. (Für eine Funktionsübermittlung haben die Ein- und Ausgaben natürlich kein Format. Sie sind nur Listen.)

Dies löst tatsächlich ein schwierigeres Problem als das vom OP geforderte: Es berechnet die kürzeste arithmetische Folge von Ganzzahlen, die die angegebenen Werte in der angegebenen Reihenfolge enthalten, unabhängig davon, ob die Löschungen aufeinander folgen oder nicht. Da Brute Force verwendet wird, kann es sehr langsam sein, wenn viele Werte gelöscht werden.

Erläuterung

Das Programm besteht aus drei Hauptteilen.

Findet eine Übersequenz der Eingabe (dh eine Sequenz, die die Eingabe als Untersequenz hat). Wenn von einem Brachylog-Programm mehr als eine Ausgabe möglich ist, ist die gewählte Ausgabe die erste Ausgabe in Tiebreak-Reihenfolge, und die Tiebreak-Reihenfolge wird durch den ersten Befehl im Programm bestimmt, der eine Meinung dazu hat. Gibt in diesem Fall eine Reihenfolge an, bei der kurze Ausgaben gegenüber langen bevorzugt werden. Die Ausgabe, die wir erhalten, ist also die kürzeste Supersequenz der Eingabe, die den Einschränkungen im Rest des Programms entspricht.

.... wird verwendet, um den Wert auszugeben, den es als Eingabe sieht (in diesem Fall die Supersequenz), aber auch um zu behaupten, dass eine bestimmte Bedingung darauf zutrifft. Mit anderen Worten, wir geben die kürzeste Supersequenz aus, die einer bestimmten Bedingung entspricht (und ignorieren alle Zwischenergebnisse, die verwendet werden, um festzustellen, ob die Bedingung erfüllt ist).

Schließlich haben wir s₂ᵇ-ᵐ =, dh "alle Deltas der Sequenz sind gleich", die Bedingung, die wir auf den Ausgang anwenden. (Der Rückgabewert ist eine Liste von Deltas, nicht die Supersequenz selbst. Deshalb brauchen wir das .…, um sicherzustellen, dass das Richtige ausgegeben wird.)

Brachylog wird hier zurückgehalten, weil es keine eingebauten Elemente gibt, die die Berechnung von Deltas, das Anwenden einer Operation auf überlappende Paare aus einer Liste oder dergleichen handhaben können. Stattdessen müssen wir sagen , was wir ausdrücklich bedeuten: s₂ᵇfindet alle ( ) Teilstrings ( s) die Länge 2 ( ) (die Verwendung erforderlich , um eine Verbindung zwischen Unbekannten in dem Teil und in der Supersequenz zu halten, die häufiger verwendet würde dies brechen Verknüpfung). Führt dann -ᵐeine Subtraktion von jedem dieser Paare durch, um ein Delta zu erzeugen. Es ist ärgerlich, fünf Bytes s₂ᵇ-ᵐfür etwas schreiben zu müssen, für das die meisten modernen Golfsprachen eine Voreinstellung haben, aber so geht Codegolf manchmal, denke ich.


quelle
4

Python 2, 104 97 89 83 71 67 60 Bytes

Vielen Dank an Chas Brown für das Speichern von 4 Bytes.
Danke an ovs für das Speichern von 7 Bytes.

Geben Sie die Liste mit Argumenten ein.

lambda a,b,*c:range(a,c[-1],min(b-a,c[0]-b,key=abs))+[c[-1]]

Probieren Sie es online!

Erläuterung:

Da die entfernten Elemente aufeinanderfolgend sind, ist es ausreichend, die Unterschiede zwischen zwei Paaren aufeinanderfolgender Elemente zu prüfen.

Colera Su
quelle
Sie können maximal 3 Bytes speichern durch Ersetzen b if b%c else cmit [c,b][b%c>0].
Chas Brown
@ChasBrown Danke, obwohl ich mir bald einen besseren Ansatz einfallen ließ.
Colera So
1
Schön mit dem key=abs! Es scheint so, als würden die Leute den f=Teil häufig weglassen, wenn nicht eine rekursive Funktion verwendet wird. Sie könnten also 2 Bytes auf diese Weise sparen.
Chas Brown
1
Ersetzen Sie auch a[-1]-a[-2]durch a[2]-a[1]- die Logik ist dieselbe, und Sie erhalten weitere 2 Bytes.
Chas Brown
1
60 Bytes
Ovs
4

Pyth , 11 Bytes

%hS.+SQ}hQe

Probieren Sie es hier aus!

Vielen Dank an Steven H. für das Speichern eines Bytes!

Pyth , 12 Bytes

%.aiF.+Q}hQe

Probieren Sie es hier aus!

Wie es funktioniert

% .aiF. + Q} hQe ~ Volles Programm.

     . + Q ~ Holen Sie sich die Deltas.
   iF ~ Mit GCD reduzieren.
 .a ~ Absolutwert.
% ~ Modular. Holen Sie sich jedes n-te Element von ...
        } ~ Der inklusive Zahlenbereich zwischen ...
         hQ ~ Das erste Element und ...
           e ~ Das letzte Element.
Mr. Xcoder
quelle
Vorsortieren , Qso dass Sie das erste Element sortieren und nehmen , anstatt abs(GCD(Q))wie in %hS.+SQ}hQe11 Bytes. Testsuite
Steven H.
3

Gelee , 8 Bytes

ṂrṀmIg/$

Probieren Sie es online!

Anmerkungen:

  • Arbeite nur an einer alten Version von Jelly. ( dies ist zum Beispiel ein Commit ) (wobei gverwendet wird fractions.gcd, bei denen das Ergebniszeichen dasselbe wie das Eingabezeichen ist, anstatt math.gcddass immer ein positiver Wert zurückgegeben wird).

  • Der obige TIO-Link ist Python 3 TIO-Link, der Python-Code besteht aus Jelly-Quellcode aus dem oben erwähnten Commit, mit Ausnahme von allem (3 Dateien), das in dieselbe Datei gepackt ist (damit TIO ausgeführt wird) und dictionary.pyauf reduziert wurde nur einige Zeilen. Dennoch dictionary.pyhat dies nichts mit dieser Antwort zu tun, da keine komprimierte Zeichenfolge verwendet wird. (das “...»Konstrukt)

Erläuterung:

Erstens, da ein kontinuierliches Segment gelöscht wird und mindestens 3 Elemente übrig bleiben, verbleiben zwei aufeinanderfolgende Nummern in der alten Liste, und die Deltas sind alle Vielfache des Schritts. Daher ist die Liste gcdder Unterschiede ( IInkremente) der absolute Wert des Schritts.

Zum Glück gcdist der unterschrieben (siehe Hinweis oben)

Das Programm macht also:

ṂrṀ

Ein zunehmender ganzzahliger Bereich vom Inimum zum Aximum.

m

Wählen Sie modular jedes n-te Element aus.

Ig/$

Monadic ( $) Chain kombinieren I(Inkremente, Differenzen) und g/( gcdüber Elemente der Liste reduzieren ). Wenn die Inkremente positiv sind, ist das gcdpositiv, und die Liste mit den zurückgegebenen Inkrementen wird von links nach rechts (aufsteigend) und umgekehrt angezeigt.

user202729
quelle
Yay! Beats the 05AB1E Antwort um 1 Byte!
User202729
Verwenden, gcdanstatt minuns zu binden. Schade, ich bekomme eine GCD mit Vorzeichen, sonst wäre ich um 7;)
Emigna
3

MATL , 13 Bytes

1)0GdYkG0)3$:

Probieren Sie es online!

Erläuterung:

Consider the example input [2 14 17]:
           # implicit input, STACK: [[2 14 17]]
1)         # push 1, index, STACK: [2]
0G         # push 0, duplicate input, STACK: [2, 0, [2 14 17]]
d          # take differences, STACK: [2, 0, [12, 3]]
Yk         # get value in [12, 3] nearest to 0, STACK: [2, 3]
G0)        # get last element in input, STACK: [2, 3, 17]
3$:        # 3-input :, computes 2:3:17, the range from 2 to 17 by 3
           # STACK: [[2 5 8 11 14 17]], implicit output.

Giuseppe
quelle
3

JavaScript (ES6), 92 90

Bearbeite 2 Bytes, die dank Arnauld gespeichert wurden

Einfach, denn es reicht aus, die Unterschiede zwischen den ersten beiden und den letzten beiden zu überprüfen. Aber immer noch unglaublich lang.

s=>(e=(z=s.pop(a=s[0]))-s.pop(d=s[1]-a),[...Array((z-(a-=d=e*e>d*d?d:e))/d)].map(_=>a+=d))

Weniger golfen

s=>{
  a =s[0]
  b =s[1]
  z = s.pop()
  y = s.pop()
  d = b-a
  e = z-y
  d = e*e>d*d?d:e  
  n = (z-a)/d+1
  return [...Array(n)].map((_,i) => a + i*d)
}

Prüfung

var F=
s=>(e=(z=s.pop(a=s[0]))-s.pop(d=s[1]-a),[...Array((z-(a-=d=e*e>d*d?d:e))/d)].map(_=>a+=d))

var test=`In: 2 5 8 14 17 Out: 2 5 8 11 14 17
In: 2 5 17 Out: 2 5 8 11 14 17
In: 2 14 17 Out: 2 5 8 11 14 17
In: 21 9 6 3 Out: 21 18 15 12 9 6 3
In: 10 9 5 Out: 10 9 8 7 6 5
In: 1 10 91 100 Out: 1 10 19 28 37 46 55 64 73 82 91 100`.split`\n`
.map(r=>r.split`Out`.map(x=>x.match(/\d+/g)))

test.forEach(([i,k])=>{
  var o=F(i.slice(0))
  var ok = o+''==k
  console.log(ok?'OK':'KO',i+' => '+o)
})

edc65
quelle
a-=d=e*e>d*d?d:esollte funktionieren und 2 Bytes sparen.
Arnauld
@ Arnauld es funktioniert in der Tat danke
edc65
2

Wolfram Language (Mathematica) , 50 Byte

Range[#&@@#,#[[-1]],#&@@Differences@#~SortBy~Abs]&

Probieren Sie es online!

JungHwan min
quelle
Umfasst eine "Liste von Zahlen" die Angabe der Zahlen als einzelne Argumente? In diesem Fall könnten Sie anscheinend eine gute Anzahl von Bytes einsparen.
numbermaniac
@numbermaniac Ich glaube nicht, da es kein eingebautes Gerät gibt, das die letzten Eingaben
abruft
Ahh ... wahr. Hab das vergessen.
numbermaniac
Sie können {##}und Last@{##}aber das Beste, das ich damit bekommen konnte, war 51 Bytes.
numbermaniac
2

Ruby , 65 62 55 54 Bytes

->l{a,*,b,c=l;[*a.step(c,[l[1]-a,c-b].min_by(&:abs))]}

Probieren Sie es online!

-1 Byte danke an Justin Mariner

GB
quelle
Sie können ein Byte speichern h, indem Sie es entfernen a,*,b,c. Probieren Sie es online!
Justin Mariner
1

Haskell , 73 69 Bytes

f(h:t)=do(#)<-[(-),(+)];[h,h#minimum(abs<$>zipWith(-)t(h:t))..last t]

Probieren Sie es online!

Laikoni
quelle
1
Ich habe eine 63-Byte-Lösung gefunden, aber sie unterscheidet sich ziemlich von Ihrer. Soll ich einen separaten Beitrag machen?
user1472751
@ user1472751 Ich bin kein Laikoni, aber diese Seite war sowohl für den Wettbewerb als auch für die Zusammenarbeit gedacht. Also würde ich es posten.
H.PWiz
@ user1472751 Netter Ansatz! Bitte mach weiter und poste es als deine eigene Antwort.
Laikoni
1

J , 49, 47, 46 Bytes

(0-[:<./2|@-/\]){.@[&]\({.<.{:)+[:i.{:(+*)@-{.

Inspiriert von Emignas Lösung.

Wie es funktioniert:

 (0-[:<./2|@-/\]){.@[&]\({.<.{:)+[:i.{:(+*)@-{. - fork of 3 verbs

                        ({.<.{:)+[:i.{:(+*)@-{. - generates a list in the entire range of values
                                     {:     -{. - last minus first element  
                                       (+*)@    - adds the signum of the difference
                                 [:i.           - makes a list 
                       ({.<.{:)                 - the smallest of first and last elements                                     
                               +                - adds the offset to the list (translates all elements according to the first one)

 (0-[:<./2|@-/\])                               - finds the step
         2|@-/\]                                - the absolute differences between all consecutive elements
    [:<./                                       - the smallest one
  0-                                            - negate (for splitting)

                 {.@[&]\                        - splits the list from the right verb into left verb's result sublists and takes their first elements

Probieren Sie es online!

Galen Ivanov
quelle
1

Schale , 9 Bytes

m←C▼Ẋ≠⁰…⁰

Probieren Sie es online!

Vielen Dank an H.PWiz für die Halbierung der Byteanzahl , indem er darauf hinweist, dass das Anwenden auf eine Liste dies ändert! ...

Mr. Xcoder
quelle
@ HP.Wiz X_X Ich wusste nicht, dass Husk solche Bereiche auflistet ... Sind Sie sicher, dass Sie es nicht als separate Antwort veröffentlichen möchten?
Mr. Xcoder
@ HP.Wiz Danke vielmals !
Mr. Xcoder
Kann F⌋auch durch ersetzt werden ?
H.PWiz
@ H.PWiz @ _ @ Warum funktioniert das überhaupt?
Mr. Xcoder
Die kleinste (absolute) Differenz ist die ursprüngliche Differenz. Der einzige Grund dafür gcdwar, mit negativen Deltas
umzugehen
1

C # (.NET Core) , 167 + 13 = 180 145 + 13 = 158 Bytes

a=>{int x=a[1]-a[0],y=a[2]-a[1],d=x*x<y*y?x:y,s=Math.Abs((a[a.Length-1]-a[0])/d),i=0,j=a[0];var r=new int[s+1];for(;i<=s;j+=d)r[i++]=j;return r;}

Probieren Sie es online!

+13 für using System;

Überraschenderweise hatte diese Herausforderung mehr Nuancen, als ich ursprünglich erwartet hatte.

Danksagung

-22 Bytes gespart aufgrund einiger netter Vereinfachungen von @DLosc.

DeGolfed

a=>{
    int x = a[1]-a[0],        // difference between first and second numbers
        y = a[2]-a[1],        // difference between second to last and last numbers
        d = x*x < y*y? x : y, // smallest absolute value difference
        s = Math.Abs((a[a.Length-1] - a[0]) / d), // number of steps in the reconstructed sequence (not the number of elements)
        i = 0,                // step position
        j = a[0];             // next number in reconstructed sequence

    var r = new int[s+1];

    // reconstruct the sequence
    for(; i <= s; j+=d)
        r[i++]=j;

    return r;
}
Ayb4btu
quelle
0

Python 2 , 147 Bytes

from fractions import*
a=input()
b=[j-i for i,j in zip(a[:-1],a[1:])]
l=min(gcd(i,j)for i in b for j in b)
print list(range(a[0],a[-1]+l/abs(l),l))

Probieren Sie es online!

Neil
quelle
0

Japt , 12 Bytes

ÌõUg Uäa ñ g

Versuch es


Erläuterung

Generieren Sie ein Array von Ganzzahlen ( õ) vom letzten Element des Eingabearrays ( Ì) bis zum ersten ( Ug). Berechnen Sie den Schritt zwischen den Elementen, indem Sie alle zwei Elementpaare aus der Eingabe abrufen und sie um die absolute Differenz ( Uäa) reduzieren, dann ñdieses Array sortieren ( ) und das erste Element nehmen ( g).

Zottelig
quelle