Le défi:

Considérez la fonction F(N) = 2^N + 1où Nest un entier positif inférieur à 31. La séquence définie par cette fonction est:

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

Une entrée sera générée comme suit:

• Prenez 5 entiers contigus de la séquence ci-dessus.
• Remplacez l'un d'eux par un entier positif différent (qui peut ou non faire partie de la séquence ci-dessus).
• Réorganisez éventuellement les 5 numéros résultants.

Étant donné une telle liste de 5 entiers, recherchez celui qui a été échangé et ne fait donc pas partie des 5 entiers contigus d'origine.

Exemple:

• Sublist Original: 5, 9, 17, 33, 65.
• Remplacer un: 5, 7, 17, 33, 65.
• Réorganiser: 33, 17, 5, 7, 65.

Le résultat attendu serait 7.

Les 5 valeurs en entrée seront toujours distinctes et il y aura toujours une solution unique. (Par exemple, vous n'aurez pas à gérer des entrées comme l' 3, 9, 17, 33, 129endroit où l'un 3ou l' autre 129aurait pu être échangé.)

Cas de test:

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

Gelée, 15 octets

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

TryItOnline
Tous les cas de test également sur TryItOnline

Renvoie une liste contenant une liste contenant l'intrus.

Comment?

⁹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)

JavaScript (ES6), 62 octets

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

Algorithme complètement nouveau, car comme l'a souligné @ edc65, le précédent était cassé. Explication: Nous traitons d'abord le cas facile en recherchant un 2 ou un nombre qui n'est pas supérieur à une puissance de 2. Si aucun n'a été trouvé, il y a deux cas possibles, selon que la valeur supplémentaire était inférieure ou supérieure à la série d'origine de cinq, nous vérifions donc si la plus petite et la deuxième valeur la plus grande appartiennent à la même série de cinq et si c'est le cas, blâmer la plus grande valeur sinon la plus petite valeur.

Python, 84 octets

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)

Tous les cas de test sont à idéone

Pour une entrée valide, renvoie un ensemble contenant uniquement le impair-un.
Pour une entrée non valide, la limite de récursivité sera atteinte et une erreur sera levée.

Mathematica, 65 octets

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

Ceci définit une fonction fqui doit être appelée avec 5 arguments, par exemple

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

En principe, la fonction peut être appelée avec n'importe quel nombre (non nul) d'arguments, mais vous pourriez obtenir des résultats inattendus ...

Je pense que c'est la première fois que je réussis à mettre la solution entière à un défi non trivial dans la partie gauche de a =.

Explication

Cette solution met vraiment les capacités de correspondance de motifs de Mathematica à notre service. La fonctionnalité de base que nous utilisons est que Mathematica ne peut pas simplement définir des fonctions simples comme, f[x_] := (* some expression in x *)mais nous pouvons utiliser des modèles arbitrairement complexes sur le côté gauche, par exemple f[{a_, b_}, x_?OddQ] := ...ajouterait une définition à flaquelle n'est utilisée que lorsqu'elle est appelée avec un élément à deux éléments. liste et un entier impair. De manière pratique, nous pouvons déjà donner des noms à des éléments arbitrairement loin dans l'expression de gauche (par exemple, dans le dernier exemple, nous pourrions immédiatement faire référence aux deux éléments de la liste comme aet b).

Le modèle que nous utilisons dans ce défi est f[a___,x_,b___]. Ici a___et b___sont des séquences de zéro ou plusieurs arguments et xest un seul argument. Étant donné que le côté droit de la définition est simplement x, ce que nous voulons, c'est de la magie qui assure qu'il xest utilisé pour l'entrée que nous recherchons a___et ce b___sont simplement des caractères génériques qui couvrent les éléments restants.

Pour ce faire, associez une condition au motif avec /;. Le côté droit de /;(tout jusqu'au =) doit revenir Truepour que ce modèle corresponde. La beauté est que le matcher modèle de Mathematica essaiera chaque mission unique a, xet baux entrées pour nous, donc la recherche de l'élément correct est fait pour nous. Il s'agit essentiellement d'une solution déclarative au problème.

Quant à la condition elle-même:

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

Notez que cela ne dépend pas xdu tout. Au lieu de cela, cette condition dépend uniquement des quatre éléments restants. Ceci est une autre caractéristique pratique de la solution de correspondance de motif: en raison des modèles de séquence, aet bcontiennent ensemble toutes les autres entrées.

Cette condition doit donc vérifier si les quatre éléments restants sont des éléments contigus de notre séquence avec au plus un espace. L'idée de base pour vérifier cela est que nous générons les quatre éléments suivants à partir du minimum (via ) et vérifions si les quatre éléments sont un sous-ensemble de cela. Les seules entrées où cela peut causer des problèmes sont celles qui contiennent un , car cela génère également des éléments de séquence valides, nous devons donc les gérer séparément.xi+1 = 2xi - 12

Dernière partie: passons par l'expression réelle, car il y a du sucre syntaxique plus drôle ici.

...a~Min~b...

Cette notation infixe est l'abréviation de Min[a,b]. Mais rappelez-vous que aet bsont des séquences, donc cela se développe en fait aux quatre éléments Min[i1, i2, i3, i4]et nous donne le plus petit élément restant dans l'entrée.

.../. 2->0

Si cela donne un 2, nous le remplaçons par un 0 (ce qui générera des valeurs qui ne sont pas dans la séquence). L'espace est nécessaire car sinon Mathematica analyse le littéral float .2.

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

Nous appliquons la fonction sans nom à gauche 4 fois à cette valeur et collectons les résultats dans une liste.

2#-1&

Cela multiplie simplement son entrée par 2 et la décrémente.

...~SubsetQ~{a,b}

Et enfin, nous vérifions que la liste contenant tous les éléments de aet en best un sous-ensemble.

Raquette 198 octets

(λ(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))

Version non golfée:

(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)))

Essai:

(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))

Production:

'(829)
'(829)
'(177)
'(259)
'(259)
'(63)
'(4097)

05AB1E , 32 30 26 24 20 octets

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

Explication

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

Essayez-le en ligne!

R, 97 octets

Cela s'est avéré plus difficile que je ne le pensais. Je suis sûr que cela peut être joué de manière significative.

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)])

Non golfé et expliqué

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]

La match()fonction retournera NAsi l'élément any du vecteur d'entrée n'est pas dans la séquence et par conséquent, nous pouvons simplement trouver l'index où NAexistent dans l'entrée et retourner ceci:x[is.na(m)]

Cela devient un peu plus compliqué si l'entrée fait partie de la séquence mais est mal placée. Parce que l'entrée a été triée, la distance entre chaque paire d' indices doit être 1. Nous pouvons donc trouver l'élément mal placé en recherchant la 1stdifférence des indices appariés l=diff(m)et en sélectionnant l'indice pour lequel l>1. Ce serait juste suffisant s'il n'y avait pas le fait de lcontenir des 4éléments plutôt que 5. Ce n'est un problème que si le dernier élément de l'entrée triée est un membre de la séquence MAIS ne fait pas partie de la sous-séquence (comme dans le cas de test final). Par conséquent, si l' 4thélément >1récupère l' 5thentrée dans l'entrée triée, recherchez l'index dans le 4vecteur -length:x[ifelse(l[4]>1,5,l>1)]

Haskell, 66 64 octets

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

Exemple d'utilisation: g [65,129,257,513,4097]-> 4097.

Boucle dans toutes les sous-listes contiguës de longueur 5 de F(N), conserve les éléments qui ne sont pas dans la liste d'entrée xet le modèle correspond à ceux de longueur 1 (-> [s]).

Edit: @xnor a enregistré deux octets en supprimant la limite supérieure de la boucle externe. Comme une solution est garantie d'exister, la paresse de Haskell s'arrête au premier numéro trouvé.

Perl, 64 59 octets

Comprend +2 pour -an

Donnez une liste de saisie sur STDIN:

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

Si cela ne vous dérange pas d'espace variable autour du résultat, ce verset de 58 octets fonctionne:

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

Les deux versions bouclent pour toujours si l'entrée n'a pas de solution.

C'est un code très malade, mais je ne vois rien d'élégant ...

La façon dont je (ab) utilise %aest un nouveau tour de Perlgolf pour autant que je sache.

Python 2, 73 octets

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

Itère à travers des ensembles dde cinq éléments de séquence consécutifs jusqu'à ce qu'il en trouve un qui contient tous les éléments d'entrée sauf un, puis imprime la différence, qui est la sortie dans un ensemble singleton.

Les ensembles dde cinq éléments consécutifs sont construits à partir de rien en ajoutant à plusieurs reprises un nouvel élément i+1et en supprimant tout ancien élément i/32+1qui précède la fenêtre actuelle de 5. Voici à quoi ressemble sa progression.

{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}

Il y a un 1 errant au début de l'initialisation, mais il est inoffensif car il est immédiatement supprimé. Les ensembles plus petits, car ils contiennent jusqu'à 5 éléments, sont également inoffensifs.

PHP, 87 76 75 octets

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

courir avec php -r '<code>' <value1> <value2> <value3> <value4> <value5>

C #, 69 octets

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

Java 7,85 octets

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];}

Non golfé

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];

}

PHP, 76 octets

implémenté l'idée Titus avec le mod 5

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

126 octets avant

<?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;}

Pyth, 18 octets

hhlD-LQ.:mh^2dSCd5

Formez la séquence, prenez des sous-listes de longueur 5, supprimez chaque sous-liste de Q, prenez le résultat le plus court, sortez son seul élément.

Kotlin, 55 octets

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