Encontre o ímpar em uma sequência

20

O desafio:

Considere a função F(N) = 2^N + 1onde Né um número inteiro positivo menor que 31. A sequência definida por esta função é:

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

Uma entrada será gerada da seguinte maneira:

  • Pegue 5 números inteiros contíguos da sequência acima.
  • Substitua um deles por um número inteiro positivo diferente (que pode ou não fazer parte da sequência acima).
  • Reorganize opcionalmente os 5 números resultantes.

Dada uma lista de 5 números inteiros, encontre o que foi trocado e, portanto, não faz parte dos 5 números inteiros contíguos originais.

Exemplo:

  • Sublist Original: 5, 9, 17, 33, 65.
  • Substituir um: 5, 7, 17, 33, 65.
  • Reordenar: 33, 17, 5, 7, 65.

O resultado esperado seria 7.

Os 5 valores na entrada sempre serão distintos e sempre haverá uma solução exclusiva. (Por exemplo, você não precisará lidar com entradas como 3, 9, 17, 33, 129onde 3ou 129pode ter sido trocado.)

Casos de teste:

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
fonte
4
Para referência futura, confusão e mal-entendidos como esse geralmente podem ser evitados postando idéias de desafio na sandbox primeiro, onde você pode obter feedback da comunidade antes que as pessoas comecem a resolver seu desafio.
Martin Ender
@Ajay Como ainda havia alguma confusão sobre a especificação, editei o desafio mais uma vez com o que considero sua intenção por trás desse desafio. Espero não ter interpretado mal, mas me avise se entendi algo errado.
Martin Ender
@MartinEnder o novo caso de teste deve ser536870913,67108865,134217729,1,268435457
Jörg Hülsermann
@ JörgHülsermann Sinta-se à vontade para adicionar isso também, mas minha intenção era adicionar um caso de teste que cubra N = 30como um dos valores de entrada.
Martin Ender
1
Um desafio interessante, porque é muito fácil criar algoritmos errados. E, de fato, nunca vi tantas respostas incorretas postadas. Teria sido ainda pior se duplicatas foram autorizados (muitos métodos set base (incluindo o meu) falharia)
Ton Hospel

Respostas:

6

Gelatina, 15 bytes

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

TryItOnline
Todos os casos de teste também em TryItOnline

Retorna uma lista contendo uma lista contendo a saída ímpar.

Quão?

⁹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
fonte
5

JavaScript (ES6), 62 bytes

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

Algoritmo completamente novo, já que como @ edc65 apontou, o anterior foi quebrado. Explicação: Primeiro lidamos com o caso fácil procurando por um 2 ou um número que não seja maior que uma potência de 2. Se nenhum foi encontrado, existem dois casos possíveis, dependendo se o valor extra estava abaixo ou acima do valor execução original de cinco, portanto, verificamos se o menor e o segundo maior valor pertencem à mesma execução de cinco e, em caso afirmativo, culpar o maior valor, caso contrário, o menor valor.

Neil
fonte
Quase ok, mas tentar n-1&n-2com o valor2
edc65
@ edc65 Não funciona para [3, 17, 33, 65, 257].
Neil
@ edc65 Parece --n&--n|!nbom para o 2caso?
Neil
Parece bom, na verdade
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)

Todos os casos de teste estão em ideone

Para entrada válida, retorna um conjunto que contém apenas o número ímpar.
Para entrada inválida, o limite de recursão será atingido e um erro será gerado.

Jonathan Allan
fonte
4

Mathematica, 65 bytes

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

Isso define uma função fque deve ser chamada com 5 argumentos, por exemplo

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

Em princípio, a função pode ser chamada com qualquer número (diferente de zero) de argumentos, mas você pode obter resultados inesperados ...

Acho que é a primeira vez que consegui colocar toda a solução em um desafio não trivial no lado esquerdo de um =.

Explicação

Essa solução realmente coloca os recursos de correspondência de padrões do Mathematica para trabalhar para nós. A característica básica que estamos usando é que o Mathematica não pode apenas definir funções simples como, f[x_] := (* some expression in x *)mas podemos usar padrões arbitrariamente complexos no lado esquerdo, por exemplo f[{a_, b_}, x_?OddQ] := ..., adicionar uma definição à fqual é usada apenas quando é chamada com um elemento de dois elementos lista e um número inteiro ímpar. Convenientemente, já podemos atribuir nomes a elementos arbitrariamente distantes da expressão do lado esquerdo (por exemplo, no último exemplo, poderíamos nos referir imediatamente aos dois elementos da lista como ae b).

O padrão que estamos usando neste desafio é f[a___,x_,b___]. Aqui a___e b___são seqüências de zero ou mais argumentos e xé um único argumento. Como o lado direito da definição é simplesmente x, o que queremos é uma mágica que garanta que xseja usada para a entrada que estamos procurando a___e que b___sejam simplesmente curingas que cubram os elementos restantes.

Isso é feito anexando uma condição ao padrão com /;. O lado direito de /;(tudo até =) precisa retornar Truepara que esse padrão corresponda. A beleza é que o padrão de correspondência do Mathematica vai tentar cada atribuição de a, xe bpara as entradas para nós, por isso a busca para o elemento correto é feito por nós. Esta é essencialmente uma solução declarativa para o problema.

Quanto à própria condição:

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

Observe que isso não depende de xnada. Em vez disso, essa condição depende apenas dos quatro elementos restantes. Esse é outro recurso conveniente da solução de correspondência de padrões: devido aos padrões de sequência, ae bjuntos contêm todas as outras entradas.

Portanto, essa condição precisa verificar se os quatro elementos restantes são elementos contíguos da nossa sequência com no máximo uma lacuna. A idéia básica para verificar isso é que geramos os próximos quatro elementos a partir do mínimo (via ) e verificamos se os quatro elementos são um subconjunto disso. As únicas entradas em que isso pode causar problemas são aquelas que contêm a , porque isso também gera elementos de sequência válidos, portanto, precisamos lidar com isso separadamente.xi+1 = 2xi - 12

Última parte: vamos analisar a expressão real, porque há mais açúcar sintático engraçado aqui.

...a~Min~b...

Essa notação infix é abreviada Min[a,b]. Mas lembre-se disso ae bsão sequências; portanto, isso se expande para os quatro elementos Min[i1, i2, i3, i4]e nos fornece o menor elemento restante na entrada.

.../. 2->0

Se isso resultar em um 2, substituímos por um 0 (que gerará valores que não estão na sequência). O espaço é necessário porque, caso contrário, o Mathematica analisa o literal de flutuação .2.

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

Aplicamos a função sem nome à esquerda 4 vezes a esse valor e coletamos os resultados em uma lista.

2#-1&

Isso simplesmente multiplica sua entrada por 2 e a diminui.

...~SubsetQ~{a,b}

E, finalmente, verificamos que a lista que contém todos os elementos de ae bé um subconjunto disso.

Martin Ender
fonte
Eu não sabia que o Mathematica poderia fazer isso!
DanTheMan
4

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

Versão não destruída:

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

Teste:

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

Saída:

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

05AB1E , 32 30 26 24 20 bytes

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

Explicação

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

Experimente online!

Emigna
fonte
2

R, 97 bytes

Isso acabou sendo mais difícil do que eu pensava. Tenho certeza de que isso pode ser jogado de maneira significativa.

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 e explicou

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]

A match()função retornará NAse qualquer elemento do vetor de entrada não estiver na sequência e, consequentemente, podemos apenas encontrar o índice onde NAexiste na entrada e retornar isso:x[is.na(m)]

Fica um pouco mais complicado se a entrada faz parte da sequência, mas é extraviada. Como a entrada foi classificada, a distância entre cada par de índices deve ser 1. Portanto, podemos encontrar o elemento extraviado, investigando a 1stdiferença dos índices correspondentes l=diff(m)e selecionando o índice para o qual l>1. Isso seria suficiente se não fosse pelo fato de lconter 4elementos e não 5. Isso é apenas um problema se o último elemento na entrada classificada for um membro da sequência, MAS não fizer parte da subsequência (como no caso de teste final). Conseqüentemente, se o 4thelemento >1buscar a 5thentrada na entrada classificada, procure o índice no 4vetor -length:x[ifelse(l[4]>1,5,l>1)]

Billywob
fonte
1
nas versões recentes do R existe uma função anyNAque é equivalente aany(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

Exemplo de uso: g [65,129,257,513,4097]-> 4097.

Os loops em todas as sublistas contíguas de comprimento 5 de F(N)mantêm os elementos que não estão na lista de entrada xe o padrão corresponde aos de comprimento 1 (-> [s]).

Edit: @xnor salvou dois bytes removendo o limite superior do loop externo. Como é garantida a existência de uma solução, a preguiça de Haskell para no primeiro número encontrado.

nimi
fonte
Você realmente precisa do limite superior de 26?
xnor
1

Perl, 64 59 bytes

Inclui +2 para -an

Dê uma lista de entradas no 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

Se você não se importa com uma quantidade variável de espaço em torno do resultado, esse 58 bytes verson funciona:

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

Ambas as versões se repetem para sempre se a entrada não tiver solução.

Este é um código muito doentio, mas não consigo pensar em nada elegante ...

A maneira como eu (ab) uso %aé um novo truque perlgolf, até onde eu sei.

Ton Hospel
fonte
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

Repete os conjuntos dde cinco elementos de sequência consecutivos até encontrar um que contenha todos, exceto um dos elementos de entrada, e depois imprime a diferença, que é a saída em um conjunto singleton.

Os conjuntos dde cinco elementos consecutivos são construídos a partir do nada, adicionando repetidamente um novo elemento i+1e excluindo qualquer elemento antigo i/32+1que vem antes da janela atual de 5. Aqui está a aparência de seu progresso.

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

Há um 1 perdido no início da inicialização, mas é inofensivo porque é removido imediatamente. Os conjuntos menores, pois ele compõe até 5 elementos, também são inofensivos.

xnor
fonte
1

PHP, 87 76 75 bytes

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

correr com php -r '<code>' <value1> <value2> <value3> <value4> <value5>

Titus
fonte
'a = [] `não é necessário
Jörg Hülsermann 28/09
@ JörgHülsermann: É necessário para array_diff. Mas eu posso salvar um byte lá.
Titus
Isso resulta em um aviso array_diff (): O argumento 2 não é uma matriz. Nice maneira com preenchimento a matriz com o mod 5. Ele vai salvar me array_map e variam em minha proposta
Jörg Hülsermann
1
endem vez de, maxe sua anotação não é mais importante
Jörg Hülsermann 28/09
1

C #, 69 bytes

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

Patrik Westerlund
fonte
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];

}
Numberknot
fonte
Hmm, você tem certeza que isso funciona corretamente? Porque estou obtendo uma saída incorreta para os casos de teste 1, 5, 6 e 7 (apenas a segunda, terceira e quarta saída estão corretas). Além disso, é o parâmetro l31? Na pergunta, vejo apenas uma matriz int como entrada, mas não uma int adicional? : S
Kevin Cruijssen
Isso não irá falhar se o valor ímpar for o segundo (no índice 1)?
precisa saber é o seguinte
Desculpe pessoal, eu interpreto mal a pergunta. Na verdade, agora estou no hospital. Vou mudar em um curto espaço de tempo.
Numberknot
0

PHP, 76 bytes

ideia Titus implementada com o mod 5

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

126 bytes antes

<?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
fonte
função anônima: array_map(function($z){return 2**$z+1;},range($i,$i+4)). $x[key($x)]->end($x)
Tito
Colocar 1-count($x=...)a condição o livrará da interrupção: for(;1-count($x=...););echo end($x);(-13)
Titus
0

Pitão, 18 bytes

hhlD-LQ.:mh^2dSCd5

Forme a sequência, pegue sublistas de comprimento 5, remova cada sub-lista de Q, pegue o menor resultado, produza seu único elemento.

isaacg
fonte
Não funciona para[5, 9, 2, 17, 33]
Emigna 27/09/16
0

Kotlin, 55 bytes

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

Patrik Westerlund
fonte