Bei zwei positiven ganzen Zahlen p und q müssen Sie das Array A zurückgeben, das mit dem folgenden Algorithmus erstellt wurde:
- Beginnen Sie mit A = [p, q] und d = 2
- Fügen Sie für jedes Paar (x, y) zusammenhängender Zahlen in A, dessen Summe durch d teilbar ist, (x + y) / d zwischen x und y ein .
- Wenn mindestens ein passendes Paar gefunden wurde, erhöhen Sie d und fahren Sie mit Schritt 2 fort. Andernfalls stoppen Sie und kehren Sie zu A zurück .
Beispiel
Unten ist das Detail des Prozesses für p = 1 und q = 21 .
1 21 | Iteration #1: we start with d = 2 and A = [1, 21]
\/ | 1 + 21 is divisible by 2 -> we insert 11
22/2=11 |
|
1 11 21 | Iteration #2: d = 3, A = [1, 11, 21]
\/ | 1 + 11 is divisible by 3 -> we insert 4
12/3=4 |
|
1 4 11 21 | Iteration #3: d = 4, A = [1, 4, 11, 21]
\/ | 11 + 21 is divisible by 4 -> we insert 8
32/4=8 |
|
1 4 11 8 21 | Iteration #4: d = 5, A = [1, 4, 11, 8, 21]
\/ \/ | 1 + 4 is divisible by 5 -> we insert 1
5/5=1 15/5=3 | 4 + 11 is divisible by 5 -> we insert 3
|
1 1 4 3 11 8 21 | Iteration #5: d = 6, A = [1, 1, 4, 3, 11, 8, 21]
| no sum of two contiguous numbers is divisible by 6
| -> we stop here
Daher die erwartete Ausgabe: [1, 1, 4, 3, 11, 8, 21]
Erläuterungen und Regeln
- Die Ein- und Ausgabe kann in jedem vernünftigen Format erfolgen. Die ganzen Zahlen p und q sind garantiert größer als 0. Wenn das hilft, können Sie annehmen, dass q ≥ p ist .
- Der 2. Schritt des Algorithmus sollte nicht rekursiv auf Elemente angewendet werden, die gerade in derselben Iteration eingefügt wurden. Zum Beispiel sollte A = [1, 1] und d = 2 zu [1, 1, 1] führen (keine unendliche Liste von Einsen).
- Das ist Code-Golf , also gewinnt die kürzeste Antwort in Bytes!
Testfälle
p | q | Output
----+-----+-------------------------------------------------------------------------------
1 | 1 | [1,1,1]
1 | 2 | [1,2]
1 | 3 | [1,1,2,3]
2 | 6 | [2,1,2,1,4,1,2,6]
3 | 13 | [3,1,8,1,3,1,7,1,2,1,5,1,3,2,13]
9 | 9 | [9,6,9,6,9]
60 | 68 | [60,13,1,4,31,2,3,5,2,19,64,7,13,1,2,5,2,27,44,3,4,8,2,1,12,1,5,3,28,2,4,16,1,
| | 2,12,1,2,1,10,1,6,68]
144 | 336 | [144,68,3,4,8,1,12,1,4,2,28,13,128,44,17,92,240,58,108,5,17,1,2,5,3,28,3,1,11,
| | 60,3,6,2,42,2,4,26,192,54,132,7,1,15,1,3,1,18,1,4,2,30,3,1,12,1,9,78,46,336]
Wenn Sie Ihren Code in einem etwas größeren Testfall testen möchten, finden Sie hier die erwartete Ausgabe für:
- p = 12096 (2 6 * 3 3 * 7)
- q = 24192 (2 7 * 3 3 * 7)
code-golf
array-manipulation
Arnauld
quelle
quelle
ü
funktioniert das ... so konnte ich eine meiner vorherigen antworten verbessern :-)[1,2,3,4] ü = [[1,2],[2,3],[3,4]]
, auch wenn Sie "-d" in die Argumente einfügen , wenn Sie 05AB1E ausführen, wird die oben angehängte "Debug" -Ausgabe ausgegeben. (Hinzugefügt wurde auch der Debug-Link oben). Der Grund, warum paarweise ordentlich ist, ist, dass für die Befehle, die automatisch vektorisieren, der Befehl nur paarweise angewendet wird (die Ausführungü)
in einer Liste zeigt dies gut).-d
... angeht, fand ich es zu spät, nachdem ich mit,q
"Drucken und Stoppen" "Debuggen " durchgeführt hatte. Es war schmerzhaft.=
weil es nicht platzt und nur das letzte Element druckt, das auf den Stapel geschoben wurde.U
können Sie ersetzenX
mitŠ
.Mathematica,
72645958 BytesProbieren Sie es online!
Wie es funktioniert
Wir nehmen die Eingabe als Liste
{p,q}
. Der Iterationsschritt wird wie folgt umformuliert:(a+b)/d
zwischen jeweils zwei Elementen eina
undb
:(x+{##2,}&@@x)
berechnet die Folge vona+b
's mit einema+Null
am Ende. Wir teilen durchd
undRiffle
fügen jeweils(a+b)/d
zwischena
und einb
. Zuwachsd
.Integer
Elemente der resultierenden Liste aus. (Dies wird auch von derNull
eingeführten los{##2,}
.)Dies wird wiederholt, bis sich das Ergebnis nicht mehr ändert (was nur passieren kann, weil wir alle neuen Elemente entfernt haben, weil keine von ihnen Ganzzahlen waren).
-8 Bytes dank @MartinEnder von using
//.
anstattFixedPoint
(und von der Eingabe als Liste).-6 mehr, weil
ListConvolve
eigentlich nicht so toll istquelle
//.
TrumpsFixedPoint
, und ich würde nur die Eingabe als ein Paar Ganzzahlen anstelle von zwei separaten Ganzzahlen nehmen:(d=2;#//.x_:>x~Riffle~ListConvolve[{1,1}/d++,x]~Cases~_Integer)&
//.
mitFixedPoint
, weil ich wirklich magFixedPoint
.Integer
.Ruby , 80 Bytes
Probieren Sie es online!
Rekursive Funktion,
f
die Eingaben als Array verwendet[p, q]
.quelle
Haskell,
8581 BytesProbieren Sie es online!
Die Eingabe wird als Liste übernommen, z
[1,2]
.Edit: -4 Bytes dank @Laikoni.
quelle
l%d|l==l#d=l|e<-d+1=l#d%e
.Python 2 ,
112110108105103 Bytes-2 Bytes dank Jonathan Frech
-5 Bytes dank Erik the Outgolfer
Probieren Sie es online!
quelle
y+=[...]*(...);y+=b,
gleichbedeutend mity+=[...]*(...)+[b]
?Python 2 , 98 Bytes
Aufrufen als
f([p,q])
. Probieren Sie es online!Jonathan Allan sparte 12 Bytes. Vielen Dank ~!
Erläuterung
f
ist eine rekursive Funktion:f(A, B, d)
Wertet ausf(next_A, A, d+1)
, es sei dennA == B
, in diesem Fall wird zurückgegebenA
. (Dies wird gehandhabt vonA*(A==B)or …
: wenn A ≠ BA*(A==B)
die leere Liste ist, die falsch ist, wird der…
Teil ausgewertet; wenn A = B dannA*(A==B)
istA
, was nicht leer und somit wahr ist, wird er zurückgegeben.)next_A
wird berechnet als:Dies lässt sich am besten anhand eines Beispiels erklären. Wenn zB
d = 5
undA = [1, 4, 11, 8, 21]
:quelle
zip
anstelle der Aufzählung und[A[0]]
alssum
Anfangswert verwenden.[A[0]]
durchA[:1]
:) ersetztA*(A==B)
.Python 2 , 111 Bytes
Probieren Sie es online!
-8 danke an Rod .
-2 danke an Lynn .
quelle
i
unda[x:x]
ist kürzer alsa.insert
o
: pzip
und spare zwei Bytes !for
Schleife durchwhile A[o+1:]:o+=1;s=A[o-1]+A[o];b=s%d<1;A[o:o]=[s/d]*b;m|=b;o+=b
Schale , 22 Bytes
Nimmt eine Liste mit 2 Elementen auf, gibt eine Liste mit ganzen Zahlen und Gleitkommazahlen zurück. Probieren Sie es online!
Erläuterung
quelle
Perl 5 , 92 + 1 (
-a
) = 93 BytesProbieren Sie es online!
quelle
Netzhaut , 111 Bytes
Probieren Sie es online!
Nimmt die Eingabe als durch Leerzeichen getrennte Zahlen. Ganz naiv folgt der gegebene Algorithmus, wobei die einzige bemerkenswerte Technik darin besteht, ein Markersymbol zu verwenden,
a
, um festzustellen, wann eine der Zahlen erhalten geblieben ist. Dies wird verwendet, um mit den etwas eingeschränkten Schleifenfunktionen von Retina zu arbeiten, die es Ihnen nur ermöglichen, eine Schleife zu erstellen, bis eine Reihe von Stufen den Eingang zu diesen Stufen insgesamt nicht mehr ändert.Erläuterung:
Dies wird dasselbe Beispiel wie in der Frage verwenden.
Wir ändern das Eingabearray von Zahlen in ein durch Semikolons getrenntes unäres Array, also hätten wir:
Schreiben Sie
d
am Anfang in unseren Code und geben Sie uns:Das ist etwas komplizierter.
{
Startet eine Gruppe von Stufen, die ausgeführt werden, bis sie einen festen Punkt erreichen. Zeigt dann an,+
dass diese Stufe selbst bis zu einem festen Punkt ausgeführt werden soll. Diese Stufe fügt jedes Paar benachbarter Zahlen hinzu, fügt sie jedoch ohne das zusätzliche Semikolon ein. Jetzt hätten wir:Die andere schwierige Phase, diese, akkumuliert unseren Divisor in der ersten Erfassungsgruppe und ersetzt eine beliebige Nummer in unserer Liste ohne nachfolgendes Semikolon durch diese durch dividierte Nummer
d
. Wir fügena
diesen Zahlen auch ein Anführungszeichen hinzu, um anzuzeigen, dass etwas beibehalten wurde, und um anzuzeigen, dass;
es dauerhaft Teil des Arrays sein sollte. Jetzt hätten wir:Dadurch werden Zahlen gelöscht,
d
die vor dieser Runde weder durch noch im Array teilbar waren . Dies ändert sich in unserem Beispiel nicht.Dies stimmt vom Anfang der Zeichenfolge bis zum letzten Buchstaben
a
in der Eingabe gierig überein . Dies bedeutet, dass es höchstens eine Übereinstimmung geben kann. Wenn wir Änderungen vorgenommen haben, fügen wir eine hinzud
, andernfalls lassen wir sie unverändert , damit wir die Schleife verlassen können.Das
)
schließt die Schleife, mit der begonnen wurde{
(nicht in Frage stellen!), Und ansonsten entfernt diese Stufe nur die Markierungen, die wir zuvor gesetzt haben. Da dies das Ende der Schleife ist, würden wir die obigen Schritte viele Male wiederholen, aber ich werde einfach so weitermachen, als hätte ich die Schleife vergessen, da dies das Beispiel kontinuierlicher macht.Diese Stufe entfernt sich von unserer Ausgabe:
Diese Stufe ersetzt die unären Zahlen durch Dezimalzahlen:
In der letzten Phase werden die Semikolons entfernt:
Das Überspringen der Schleife führt hier natürlich zu einem falschen Ergebnis, aber das ist hoffentlich nicht zu verwirrend.
quelle
JavaScript (ES6),
898782 ByteVielen Dank an @Arnauld für -2 Bytes und für das Sparen von 5 weiteren Bytes.
Übernimmt die Eingabe als Array:
f([p,q])
.Testfälle
quelle
v
(v+=b[++i]
) verwenden, anstatts
1 Byte zu speichern. Sie können ein weiteres Byte speichern mit|r
statt&&r
(ich glaube , es ist sicher , aber ich habe nicht doppelte Kontrolle).|r
ja bestanden alle Testfälle.push()
.push
nur einmal statt zweimal zu verwenden. Nachdem ich diese Idee überarbeitet hatte, kam ich für 86 Bytes dazu. Vielleicht kann das verbessert werden?push(v,...)
und dannv+=
für 84 Bytes erneut verwenden .Röda , 90 Bytes
Probieren Sie es online!
quelle
Java 8, 180 Bytes
Erläuterung:
Probieren Sie es hier aus.
quelle
C # 280 Bytes
Erster Versuch mit Codegolf, das ist das ganze Programm. Probier es aus
Versuch 2, 159 Bytes
Entfernen des Gerüsts, da die Aufgabe darin besteht, eine Funktion bereitzustellen, die ein Zahlenpaar annehmen kann (ein Array funktioniert) und ein Array zurückgibt. Da ein Func <int [], int []> F verwendet werden kann, um die Anforderungen zu erfüllen, definieren Sie einfach F :
Testen Sie hier das vollständige Programm
Dies könnte kleiner sein, wenn eine generische Liste als gültige Ausgabe betrachtet wird (löschen Sie das .ToArray (), um 10 Bytes zu sparen).
Wenn die Eingabe auch geändert werden kann, muss durch die Übergabe einer Liste <int> anstelle eines Arrays die Ausgabe nicht mehr initialisiert werden (bei 126 Byte).
In diesem Fall muss es keinen Rückgabewert geben. Die Verwendung einer Aktion entfernt stattdessen die 9 Bytes, die von der return-Anweisung verwendet werden.
quelle
Jelly , 19 Bytes
Probieren Sie es online!
quelle