Finden Sie die ungerade in einer Sequenz heraus

20

Die Herausforderung:

Betrachten Sie die Funktion, F(N) = 2^N + 1bei der Neine 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, 129wo sie entweder ausgetauscht wurden 3oder 129wurden.)

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
Ajay
quelle
4
Zum späteren Nachschlagen können Verwirrung und Missverständnisse wie diese häufig vermieden werden, indem Sie zuerst Herausforderungsideen in die Sandbox stellen . Dort können Sie Feedback von der Community erhalten, bevor die Leute beginnen, Ihre Herausforderung zu lösen.
Martin Ender
@ Ajay Da es immer noch einige Unklarheiten bezüglich der Spezifikation gab, habe ich die Herausforderung noch einmal mit der Absicht bearbeitet, die Ihrer Meinung nach hinter dieser Herausforderung steckt. Ich hoffe, ich habe es nicht falsch interpretiert, aber lass es mich wissen, wenn ich etwas falsch gemacht habe.
Martin Ender
@ MartinEnder sollte der neue Testfall sein536870913,67108865,134217729,1,268435457
Jörg Hülsermann
@ JörgHülsermann Fühlen Sie sich frei, das auch hinzuzufügen, aber meine Absicht war es, einen Testfall hinzuzufügen, der einen N = 30der Eingabewerte abdeckt .
Martin Ender
1
Eine interessante Herausforderung, weil es so einfach ist, falsche Algorithmen zu finden. Und in der Tat habe ich noch nie so viele falsche Antworten gesehen. Es wäre noch schlimmer gewesen, wenn Duplikate erlaubt wären (viele satzbasierte Methoden (einschließlich meiner) würden fehlschlagen)
Ton Hospel

Antworten:

6

Gelee, 15 Bytes

⁹R2*‘ṡ5ḟ@€µEÐfQ

TryItOnline
Alle Testfälle auch bei TryItOnline

Gibt eine Liste mit einer Liste mit der ungeraden Ausgabe zurück.

Wie?

⁹R2*‘ṡ5ḟ@€µEÐfQ - Main link, a (list)
⁹               - literal 256 (saving a byte over literal 30)
 R              - range, [1,2,3,...]
  2*            - 2 ** x, [2,4,8,...]
    ‘           - increment, [3,5,9,...]
     ṡ5         - all contiguous slices of length 5
       ḟ@€      - filter with reversed arguments for each
          µ     - monadic chain separation
            Ðf  - filter on condition:
           E    - all equal (those previously filtered lists with only one value)
              Q - unique (there can be two, but both will have the same odd-one-out)
Jonathan Allan
quelle
5

JavaScript (ES6), 62 Byte

a=>a.find(n=>--n&--n|!n)||a.sort((a,b)=>a-b)[a[0]*16>a[3]?4:0]

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.

Neil
quelle
Fast in n-1&n-22
Ordnung,
@ edc65 Funktioniert nicht für [3, 17, 33, 65, 257].
Neil
@ edc65 Sieht das --n&--n|!nfür den 2Fall gut aus ?
Neil
Es sieht in der Tat gut aus
edc65
4

Python, 84 Bytes

def f(a,i=0):s=set(a)-{2**j+1for j in range(i,i+5)};return len(s)<2and s or f(a,i+1)

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.

Jonathan Allan
quelle
4

Mathematica, 65 Bytes

f[a___,x_,b___]/;NestList[2#-1&,a~Min~b/. 2->0,4]~SubsetQ~{a,b}=x

Dies definiert eine Funktion, fdie mit 5 Argumenten aufgerufen werden soll, z

f[5, 9, 17, 33, 829]

Grundsä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, fdie 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 als aund verweisen b).

Das Muster, das wir in dieser Herausforderung verwenden, ist f[a___,x_,b___]. Hier a___und b___sind Folgen von null oder mehr Argumenten und xist ein einzelnes Argument. Da die rechte Seite der Definition einfach ist x, möchten wir etwas Magisches, das sicherstellt, dass xes für die Eingabe verwendet wird, nach der wir suchen, a___und b___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, Truedamit dieses Muster übereinstimmt. Das Schöne ist , dass Mathematicas Musteranpasser jede einzelne Zuordnung versuchen wird a, xund ban 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:

NestList[2#-1&,a~Min~b/. 2->0,4]~SubsetQ~{a,b}

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 Sequenzmuster aund benthalten 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 - 12

Letzter Teil: Lass uns den eigentlichen Ausdruck durchgehen, denn hier gibt es etwas mehr lustigen syntaktischen Zucker.

...a~Min~b...

Diese Infixnotation ist eine Abkürzung für Min[a,b]. Denken Sie jedoch daran, dass aund bSequenzen sind, sodass diese tatsächlich auf die vier Elemente erweitert werden Min[i1, i2, i3, i4]und uns das kleinste verbleibende Element in der Eingabe liefern.

.../. 2->0

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.

NestList[...&,...,4]

Wir wenden die unbenannte Funktion links viermal auf diesen Wert an und sammeln die Ergebnisse in einer Liste.

2#-1&

Dies multipliziert einfach seine Eingabe mit 2 und dekrementiert sie.

...~SubsetQ~{a,b}

Zum Schluss überprüfen wir, ob die Liste, die alle Elemente enthält aund beine Teilmenge davon ist.

Martin Ender
quelle
Ich wusste nicht, dass Mathematica das kann!
DanTheMan
4

Schläger 198 Bytes

(λ(m)(let((l(for/list((i(range 1 31)))(+ 1(expt 2 i))))(r 1)(n(length m)))(for((i(-(length l)n)))(let
((o(for/list((j m)#:unless(member j(take(drop l i)n)))j)))(when(eq?(length o)1)(set! r o))))r))

Ungolfed-Version:

(define f
  (λ(m)
    (let ((l (for/list ((i (range 1 31))) 
               (+ 1 (expt 2 i))))
          (res 1)
          (n (length m)))
      (for ((i (- (length l) n)))
        (let ((o (for/list ((j m) 
                             #:unless (member j 
                                             (take (drop l i) n))) 
                    j)))
          (when (eq? (length o) 1)
            (set! res o))))
      res)))

Testen:

(f '(5 9 17 33 829))
(f '(9 5 17 829 33))
(f '(5 9 177 33 65))
(f '(65 129 259 513 1025))
(f '(129 259 513 1025 65))
(f '(63 129 257 513 1025))
(f '(65 129 257 513 4097))

Ausgabe:

'(829)
'(829)
'(177)
'(259)
'(259)
'(63)
'(4097)
rnso
quelle
2

05AB1E , 32 30 26 24 20 Bytes

30Lo>Œ5ùv¹yvyK}Dgi`q

Erläuterung

30Lo>    # list containing the sequence [3 .. 1073741825]
Œ5ù      # all sequence sublists of length 5
v        # for each such list
 ¹yvyK}  # remove it's elements from input
 Dgi     # if the remaining list has length 1
    `q   # end the program and print the final list flattened

Probieren Sie es online!

Emigna
quelle
2

R 97 Bytes

Das stellte sich als schwieriger heraus, als ich dachte. Ich bin mir aber sicher, dass man hier deutlich Golf spielen kann.

m=match(x<-sort(scan()),2^(1:31)+1);l=diff(m);ifelse(NA%in%m,x[is.na(m)],x[ifelse(l[4]>1,5,l>1)])

Ungolfed und erklärte

x<-sort(scan())                  # read input from stdin and sort, store as vector
m=match(x, 2^(1:31)+1)           # generate a vector of indices for which input matches the sequence
l=diff(m)                        # vector of the difference of indices (will only contain 4 elements)
ifelse(NA%in%m,                  # if m contains NA do:
       x[is.na(m)],              # return x where no match has been found, else:
       x[ifelse(l[4]>1,5,l>1)])  # return x by index where diff>1 unless it's the last object, then return x[5]

Die match()Funktion wird zurückgegeben, NAwenn 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 die 1stDifferenz der übereinstimmenden Indizes untersuchen l=diff(m)und den Index auswählen, für den l>1. Dies wäre gerade genug, wenn nicht die Tatsache, dass Elemente statt lenthä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:454th>15th4x[ifelse(l[4]>1,5,l>1)]

Billywob
quelle
1
In neueren Versionen von R gibt es eine Funktion, anyNAdieany(is.na(x))
JDL
2

Haskell, 66 64 Bytes

g x=[s|n<-[1..],[s]<-[filter(`notElem`[2^m+1|m<-[n..n+4]])x]]!!0

Anwendungsbeispiel: 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.

nimi
quelle
Benötigen Sie tatsächlich die Obergrenze von 26?
Xnor
1

Perl, 64 59 Bytes

Beinhaltet +2 für -an

Geben Sie die Eingabeliste für STDIN ein:

perl -M5.010 oddout.pl <<< "5 9 2 17 33"

oddout.pl:

#!/usr/bin/perl -an
@a=grep$_,@a{@F,map{2**$_+++1}($.++)x5}=@F while$#a;say@a

Wenn es Ihnen egal ist, wie viel Platz um das Ergebnis herum zur Verfügung steht, funktioniert diese 58-Byte-Version wie folgt:

#!/usr/bin/perl -ap
$_=join$",@a{@F,map{2**$_+++1}($.++)x5}=@F while/\b +\b/

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, %aist meines Wissens nach ein neuer Perlgolf-Trick.

Tonne Hospel
quelle
1

Python 2, 73 Bytes

s=set(input());i,=d={1}
while~-len(s-d):i*=2;d=d-{i/32+1}|{i+1}
print s-d

Durchläuft Sätze dvon 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 dvon fünf aufeinanderfolgenden Elementen werden aus dem Nichts aufgebaut, indem wiederholt ein neues Element hinzugefügt i+1und jedes alte Element gelöscht wird i/32+1, das vor dem aktuellen Fenster von 5 liegt. So sieht der Fortschritt aus.

{1}
{3}
{3, 5}
{3, 5, 9}
{3, 5, 9, 17}
{3, 5, 9, 17, 33}
{5, 9, 17, 33, 65}
{9, 17, 33, 65, 129}
{17, 33, 65, 129, 257}
{33, 65, 129, 257, 513}

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.

xnor
quelle
1

PHP, 87 76 75 Bytes

for(;count($b=array_diff($argv,$a?:[]))-2;)$a[$n%5]=1<<++$n|1;echo end($b);

renn mit php -r '<code>' <value1> <value2> <value3> <value4> <value5>

Titus
quelle
"a = []" ist nicht erforderlich
Jörg Hülsermann
@ JörgHülsermann: Es ist notwendig für array_diff. Aber ich kann dort ein Byte speichern.
Titus
Dies führt zu einer Warnung array_diff (): Argument 2 ist kein Array. Schöne Art und Weise, das Array mit dem Mod 5 zu füllen. Es wird mir array_map und range in meinem Vorschlag sparen
Jörg Hülsermann
1
endstatt maxund Ihre Notiz ist nicht mehr wichtig
Jörg Hülsermann
1

C #, 69 Bytes

int M(int[]a)=>a.Except(new int[30].Select((_,i)=>(1<<i+1)+1)).Sum();

Patrik Westerlund
quelle
0

Java 7,85 Bytes

int f(int[]a,int l){int i=1;for(;i<l;)if(a[i++-1]*2-1!=a[i])return a[i];return a[0];}

Ungolfed

int f(int[]a,int l){
    int i=1;
    for(;i<l;)
    if(a[i++-1]*2-1!=a[i])
    return a[i];
   return a[0];

}
Zahlenknoten
quelle
Hmm, bist du sicher, dass das richtig funktioniert? Weil ich für die Testfälle 1, 5, 6 und 7 eine falsche Ausgabe erhalte (nur die zweite, dritte und vierte Ausgabe sind korrekt). Ist auch der Parameter l31? In der Frage sehe ich nur ein Int-Array als Eingabe, aber kein zusätzliches Int? : S
Kevin Cruijssen
Schlägt dies nicht fehl, wenn der ungerade Wert der zweite ist (bei Index 1)?
Ton Hospel
Sorry Leute, ich habe die Frage falsch interpretiert. Eigentlich bin ich jetzt im Krankenhaus. Ich werde es in kurzer Zeit ändern.
Numberknot
0

PHP, 76 Bytes

Titus Idee mit dem Mod 5 umgesetzt

<?for(;count($x=array_diff($_GET[a],$r))-1;$r[++$i%5]=2**$i+1);echo end($x);

126 Bytes vorher

<?for(;$x=array_diff($_GET[a],array_map(function($z){return 2**$z+1;},range(++$i,$i+4)));)if(count($x)<2){echo end($x);break;}
Jörg Hülsermann
quelle
anonyme Funktion: array_map(function($z){return 2**$z+1;},range($i,$i+4)). $x[key($x)]->end($x)
Titus
Wenn Sie 1-count($x=...)die Bedingung erfüllen, werden Sie die Pause los: for(;1-count($x=...););echo end($x);(-13)
Titus
0

Pyth, 18 Bytes

hhlD-LQ.:mh^2dSCd5

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.

isaacg
quelle
Funktioniert nicht für[5, 9, 2, 17, 33]
Emigna
0

Kotlin, 55 Bytes

fun f(a:IntArray)=a.find{it-1 !in(1..30).map{1 shl it}}

Patrik Westerlund
quelle