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 Code-Golf ; die kürzeste Antwort in jeder Sprache gewinnt.
2 5 ... 17
Antworten:
Haskell , 63 Bytes
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!
quelle
[1,3,4,5]
gibt[1,3,5]
.all(`elem`s)c
sollte es mit der gleichen Byteanzahl beheben.05AB1E ,
98 BytesProbieren Sie es online!
Erläuterung
1 Byte mit
gcd of deltas
statt gespeichertmin delta
, inspiriert von user202729quelle
Brachylog v2, 9 Bytes
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
Z
als 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, zZ = [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 Bytess₂ᵇ-ᵐ
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
Python 2,
104978983716760 BytesVielen 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.
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.
quelle
b if b%c else c
mit[c,b][b%c>0]
.key=abs
! Es scheint so, als würden die Leute denf=
Teil häufig weglassen, wenn nicht eine rekursive Funktion verwendet wird. Sie könnten also 2 Bytes auf diese Weise sparen.a[-1]-a[-2]
durcha[2]-a[1]
- die Logik ist dieselbe, und Sie erhalten weitere 2 Bytes.Pyth , 11 Bytes
Probieren Sie es hier aus!
Vielen Dank an Steven H. für das Speichern eines Bytes!
Pyth , 12 Bytes
Probieren Sie es hier aus!
Wie es funktioniert
quelle
Q
so dass Sie das erste Element sortieren und nehmen , anstattabs(GCD(Q))
wie in%hS.+SQ}hQe
11 Bytes. TestsuiteGelee , 8 Bytes
Probieren Sie es online!
Anmerkungen:
Arbeite nur an einer alten Version von Jelly. ( dies ist zum Beispiel ein Commit ) (wobei
g
verwendet wirdfractions.gcd
, bei denen das Ergebniszeichen dasselbe wie das Eingabezeichen ist, anstattmath.gcd
dass 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.py
auf reduziert wurde nur einige Zeilen. Dennochdictionary.py
hat 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
gcd
der Unterschiede (I
Inkremente) der absolute Wert des Schritts.Zum Glück
gcd
ist der unterschrieben (siehe Hinweis oben)Das Programm macht also:
Ein zunehmender ganzzahliger Bereich vom
Ṃ
Inimum zumṀ
Aximum.Wählen Sie modular jedes n-te Element aus.
Monadic (
$
) Chain kombinierenI
(Inkremente, Differenzen) undg/
(gcd
über Elemente der Liste reduzieren ). Wenn die Inkremente positiv sind, ist dasgcd
positiv, und die Liste mit den zurückgegebenen Inkrementen wird von links nach rechts (aufsteigend) und umgekehrt angezeigt.quelle
gcd
anstattmin
uns zu binden. Schade, ich bekomme eine GCD mit Vorzeichen, sonst wäre ich um 7;)MATL , 13 Bytes
Probieren Sie es online!
Erläuterung:
quelle
JavaScript (ES6),
9290Bearbeite 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.
Weniger golfen
Prüfung
quelle
a-=d=e*e>d*d?d:e
sollte funktionieren und 2 Bytes sparen.Wolfram Language (Mathematica) , 50 Byte
Probieren Sie es online!
quelle
{##}
undLast@{##}
aber das Beste, das ich damit bekommen konnte, war 51 Bytes.Ruby ,
65 62 5554 BytesProbieren Sie es online!
-1 Byte danke an Justin Mariner
quelle
h
, indem Sie es entfernena,*,b,c
. Probieren Sie es online!Haskell ,
7369 BytesProbieren Sie es online!
quelle
J ,
49, 47,46 BytesInspiriert von Emignas Lösung.
Wie es funktioniert:
Probieren Sie es online!
quelle
Schale , 9 Bytes
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! ...quelle
F⌋
auch durch ersetzt werden▼
?gcd
war, mit negativen DeltasC # (.NET Core) ,
167 + 13 = 180145 + 13 = 158 BytesProbieren 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
quelle
Python 2 , 147 Bytes
Probieren Sie es online!
quelle
Python 2 , 78 Bytes
Probieren Sie es online!
quelle
Gelee , 8 Bytes
Probieren Sie es online!
quelle
Gleichstrom , 64 Bytes
Probieren Sie es online!
quelle
Japt , 12 Bytes
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
).quelle