Die Herausforderung:
Betrachten Sie die Funktion, F(N) = 2^N + 1
bei der N
eine positive ganze Zahl kleiner als ist 31
. Die von dieser Funktion definierte Reihenfolge lautet:
3, 5, 9, 17, 33, 65, 129, 257, 513, 1025, 2049, 4097, 8193, 16385, 32769, 65537, 131073, 262145, 524289, 1048577, 2097153, 4194305, 8388609, 16777217, 33554433, 67108865, 134217729, 268435457, 536870913, 1073741825
Eine Eingabe wird wie folgt generiert:
- Nehmen Sie 5 aufeinander folgende ganze Zahlen aus der obigen Reihenfolge.
- Ersetzen Sie eine von ihnen durch eine andere positive ganze Zahl (die Teil der obigen Sequenz sein kann oder nicht).
- Ordnen Sie die 5 resultierenden Zahlen optional neu an.
Suchen Sie anhand einer solchen Liste von 5 ganzen Zahlen diejenige, die vertauscht wurde und daher nicht Teil der ursprünglichen 5 zusammenhängenden ganzen Zahlen ist.
Beispiel:
- Original sublist:
5, 9, 17, 33, 65
. - Ersetzen Sie ein:
5, 7, 17, 33, 65
. - Reorder:
33, 17, 5, 7, 65
.
Die erwartete Ausgabe wäre 7
.
Die 5 Werte in der Eingabe sind immer unterschiedlich und es gibt immer eine eindeutige Lösung. (Zum Beispiel müssen Sie sich nicht mit Eingaben befassen, wie z. B. 3, 9, 17, 33, 129
wo sie entweder ausgetauscht wurden 3
oder 129
wurden.)
Testfälle:
5,9,17,33,829
o/p: 829
9,5,17,829,33
o/p: 829
33, 17, 5, 7, 65
o/p: 7
5,9,177,33,65
o/p: 177
65,129,259,513,1025
o/p: 259
129,259,513,1025,65
o/p: 259
63,129,257,513,1025
o/p: 63
65,129,257,513,4097
o/p: 4097
5, 9, 2, 17, 33
o/p: 2
536870913, 67108865, 1073741825, 1, 268435457
o/p: 1
536870913,67108865,134217729,1,268435457
N = 30
der Eingabewerte abdeckt .Antworten:
Gelee, 15 Bytes
TryItOnline
Alle Testfälle auch bei TryItOnline
Gibt eine Liste mit einer Liste mit der ungeraden Ausgabe zurück.
Wie?
quelle
JavaScript (ES6), 62 Byte
Völlig neuer Algorithmus, da, wie @ edc65 anmerkte, der vorherige kaputt war. Erklärung: Wir beschäftigen uns zuerst mit dem einfachen Fall, indem wir nach einer 2 oder einer Zahl suchen, die nicht größer als eine Potenz von 2 ist. Wenn keine gefunden wurde, gibt es zwei mögliche Fälle, je nachdem, ob der zusätzliche Wert unter oder über dem lag ursprünglicher Lauf von fünf, also prüfen wir, ob der kleinste und der zweitgrößte Wert zum selben Lauf von fünf gehören und geben dem größten Wert die Schuld, ansonsten dem kleinsten Wert.
quelle
n-1&n-2
2
[3, 17, 33, 65, 257]
.--n&--n|!n
für den2
Fall gut aus ?Python, 84 Bytes
Alle Testfälle sind auf ideone
Bei einer gültigen Eingabe wird eine Menge zurückgegeben, die nur die ungerade Eins enthält.
Bei ungültiger Eingabe wird das Rekursionslimit erreicht und ein Fehler ausgegeben.
quelle
Mathematica, 65 Bytes
Dies definiert eine Funktion,
f
die mit 5 Argumenten aufgerufen werden soll, zGrundsätzlich kann die Funktion mit einer beliebigen Anzahl von Argumenten (ungleich Null) aufgerufen werden, es kann jedoch zu unerwarteten Ergebnissen kommen ...
Ich denke, dies ist das erste Mal, dass es mir gelungen ist, die gesamte Lösung für eine nicht triviale Herausforderung in die linke Seite von a zu stellen
=
.Erläuterung
Mit dieser Lösung können die Pattern Matching-Funktionen von Mathematica wirklich für uns eingesetzt werden. Das grundlegende Merkmal, das wir verwenden, ist, dass Mathematica nicht nur einfache Funktionen wie definieren kann,
f[x_] := (* some expression in x *)
sondern auf der linken Seite beliebig komplexe Muster verwenden kann, z. B.f[{a_, b_}, x_?OddQ] := ...
eine Definition hinzufügen würde,f
die nur verwendet wird, wenn sie mit einem Zwei-Element aufgerufen wird Liste und eine ungerade ganze Zahl. Zweckmäßigerweise können wir Elementen bereits Namen geben, die sich beliebig weit unten auf der linken Seite des Ausdrucks befinden (z. B. könnten wir im letzten Beispiel sofort auf die beiden Listenelemente alsa
und verweisenb
).Das Muster, das wir in dieser Herausforderung verwenden, ist
f[a___,x_,b___]
. Hiera___
undb___
sind Folgen von null oder mehr Argumenten undx
ist ein einzelnes Argument. Da die rechte Seite der Definition einfach istx
, möchten wir etwas Magisches, das sicherstellt, dassx
es für die Eingabe verwendet wird, nach der wir suchen,a___
undb___
einfach Platzhalter sind, die die verbleibenden Elemente abdecken.Dies geschieht durch Anhängen einer Bedingung an das Muster mit
/;
. Die rechte Seite von/;
(alles bis zu=
) muss zurückkehren,True
damit dieses Muster übereinstimmt. Das Schöne ist , dass Mathematicas Musteranpasser jede einzelne Zuordnung versuchen wirda
,x
undb
an die Eingänge für uns, so dass die Suche nach dem richtigen Element ist für uns getan hat . Dies ist im Wesentlichen eine deklarative Lösung des Problems.Wie für die Bedingung selbst:
Beachten Sie, dass dies überhaupt nicht abhängt
x
. Stattdessen hängt diese Bedingung nur von den verbleibenden vier Elementen ab. Dies ist ein weiteres praktisches Merkmal der Mustervergleichslösung: Aufgrund der Sequenzmustera
undb
enthalten zusammen alle anderen Eingaben.Diese Bedingung muss also prüfen, ob die verbleibenden vier Elemente zusammenhängende Elemente aus unserer Sequenz mit höchstens einer Lücke sind. Die Grundidee, um dies zu überprüfen, ist, dass wir die nächsten vier Elemente aus dem Minimum (Via ) generieren und prüfen, ob die vier Elemente eine Teilmenge davon sind. Die einzigen Eingaben, bei denen dies zu Problemen führen kann, sind Eingaben mit a , da hierdurch auch gültige Sequenzelemente generiert werden. Daher müssen wir diese separat behandeln.
xi+1 = 2xi - 1
2
Letzter Teil: Lass uns den eigentlichen Ausdruck durchgehen, denn hier gibt es etwas mehr lustigen syntaktischen Zucker.
Diese Infixnotation ist eine Abkürzung für
Min[a,b]
. Denken Sie jedoch daran, dassa
undb
Sequenzen sind, sodass diese tatsächlich auf die vier Elemente erweitert werdenMin[i1, i2, i3, i4]
und uns das kleinste verbleibende Element in der Eingabe liefern.Wenn dies zu einer 2 führt, ersetzen wir sie durch eine 0 (was Werte erzeugt, die nicht in der Reihenfolge sind). Der Raum ist notwendig, weil Mathematica sonst das float-Literal parst
.2
.Wir wenden die unbenannte Funktion links viermal auf diesen Wert an und sammeln die Ergebnisse in einer Liste.
Dies multipliziert einfach seine Eingabe mit 2 und dekrementiert sie.
Zum Schluss überprüfen wir, ob die Liste, die alle Elemente enthält
a
undb
eine Teilmenge davon ist.quelle
Schläger 198 Bytes
Ungolfed-Version:
Testen:
Ausgabe:
quelle
05AB1E ,
3230262420 BytesErläuterung
Probieren Sie es online!
quelle
R 97 Bytes
Das stellte sich als schwieriger heraus, als ich dachte. Ich bin mir aber sicher, dass man hier deutlich Golf spielen kann.
Ungolfed und erklärte
Die
match()
Funktion wird zurückgegeben,NA
wenn sich ein Element des Eingabevektors nicht in der Sequenz befindet und wir daher nur den Index finden können, woNA
in der Eingabe vorhanden ist, und dies zurückgeben:x[is.na(m)]
Es wird etwas komplizierter, wenn die Eingabe Teil der Sequenz ist, aber falsch platziert wird. Da der Eingang sortiert wurde, wird der Abstand zwischen jedem Paar von Indizes sollte
1
. Wir können daher das falsch platzierte Element finden, indem wir die1st
Differenz der übereinstimmenden Indizes untersuchenl=diff(m)
und den Index auswählen, für denl>1
. Dies wäre gerade genug, wenn nicht die Tatsache, dass Elemente stattl
enthält . Dies ist nur dann ein Problem, wenn das letzte Element in der sortierten Eingabe Mitglied der Sequenz ist, jedoch nicht Teil der Untersequenz (wie im letzten Testfall). Wenn das Element den Eintrag in der sortierten Eingabe abruft, suchen Sie andernfalls nach dem Index im -Längenvektor:4
5
4th
>1
5th
4
x[ifelse(l[4]>1,5,l>1)]
quelle
anyNA
dieany(is.na(x))
Haskell,
6664 BytesAnwendungsbeispiel:
g [65,129,257,513,4097]
->4097
.Durchläuft alle zusammenhängenden Unterlisten der Länge 5 von
F(N)
, behält die Elemente bei, die nicht in der Eingabeliste enthalten sindx
und das Muster entspricht denen der Länge 1 (->[s]
).Edit: @xnor sparte zwei Bytes, indem die obere Grenze der äußeren Schleife entfernt wurde. Da es garantiert eine Lösung gibt, hört Haskells Faulheit bei der ersten gefundenen Zahl auf.
quelle
Perl,
6459 BytesBeinhaltet +2 für
-an
Geben Sie die Eingabeliste für STDIN ein:
oddout.pl
:Wenn es Ihnen egal ist, wie viel Platz um das Ergebnis herum zur Verfügung steht, funktioniert diese 58-Byte-Version wie folgt:
Beide Versionen werden für immer wiederholt, wenn der Eingang keine Lösung hat.
Das ist ein sehr kranker Code, aber mir fällt nichts Elegantes ein ...
Die Art und Weise, wie ich (ab) benutze,
%a
ist meines Wissens nach ein neuer Perlgolf-Trick.quelle
Python 2, 73 Bytes
Durchläuft Sätze
d
von fünf aufeinanderfolgenden Sequenzelementen, bis eines gefunden wird, das alle bis auf eines der Eingabeelemente enthält, und gibt dann die Differenz aus, die die Ausgabe in einem Singleton-Satz darstellt.Die Mengen
d
von fünf aufeinanderfolgenden Elementen werden aus dem Nichts aufgebaut, indem wiederholt ein neues Element hinzugefügti+1
und jedes alte Element gelöscht wirdi/32+1
, das vor dem aktuellen Fenster von 5 liegt. So sieht der Fortschritt aus.Am Anfang der Initialisierung befindet sich eine Streuung 1, die jedoch harmlos ist, da sie sofort entfernt wird. Die kleineren Sets mit bis zu 5 Elementen sind ebenfalls harmlos.
quelle
PHP,
877675 Bytesrenn mit
php -r '<code>' <value1> <value2> <value3> <value4> <value5>
quelle
array_diff
. Aber ich kann dort ein Byte speichern.end
stattmax
und Ihre Notiz ist nicht mehr wichtigC #, 69 Bytes
int M(int[]a)=>a.Except(new int[30].Select((_,i)=>(1<<i+1)+1)).Sum();
quelle
Java 7,85 Bytes
Ungolfed
quelle
l
31? In der Frage sehe ich nur ein Int-Array als Eingabe, aber kein zusätzliches Int? : SPHP, 76 Bytes
Titus Idee mit dem Mod 5 umgesetzt
126 Bytes vorher
quelle
array_map(function($z){return 2**$z+1;},range($i,$i+4))
.$x[key($x)]
->end($x)
1-count($x=...)
die Bedingung erfüllen, werden Sie die Pause los:for(;1-count($x=...););echo end($x);
(-13)Pyth, 18 Bytes
Bilden Sie die Sequenz, nehmen Sie Unterlisten der Länge 5, entfernen Sie jede Unterliste von Q, nehmen Sie das kürzeste Ergebnis und geben Sie das einzige Element aus.
quelle
[5, 9, 2, 17, 33]
Kotlin, 55 Bytes
fun f(a:IntArray)=a.find{it-1 !in(1..30).map{1 shl it}}
quelle