Vamos usar as quatro operações básicas, adição +
, multiplicação *
, subtração -
e divisão /
(float, não inteiro).
A sequência de Stewie é definida da seguinte forma:
x = [x(1), x(2)] // Two initial numbers (one indexed)
x(3) = x(1) + x(2)
x(4) = x(2) * x(3)
x(5) = x(3) - x(4)
x(6) = x(4) / x(5)
x(7) = x(5) + x(6)
... and so on.
Desafio:
Pegue dois números inteiros não negativos ( x(1), x(2)
) e um número inteiro positivo N
como entrada.
x(1)
e x(2)
serão os dois primeiros números da sua sequência e N
serão o comprimento da sequência que você deve enviar. (Você pode optar por ter a lista com base em 0; nesse caso N
, será uma a menos que o comprimento).
- Você não pode assumir isso
x(2) >= x(1)
. N
sempre será>2
se for baseado em 1 (>1
se for baseado em 0).- Você não precisa lidar com a divisão com zero erros.
- Observe o segundo caso de teste. Você não receberá
0, 1
eN=6
como entrada, pois isso resultará em divisão por zero, mas você deve suportar0, 1
eN=5
.
- Observe o segundo caso de teste. Você não receberá
- Suponha que apenas uma entrada válida seja fornecida.
- A entrada e a saída podem estar em qualquer formato conveniente, mas você deve suportar pelo menos três dígitos após os pontos decimais se a saída não for um número inteiro.
Casos de teste:
1 3
8
1, 3, 4, 12, -8, -1.5, -9.5, 14.25
0 1
5
0, 1, 1, 1, 0 // N=6 would give division by zero error. You don't need to handle that case.
1 0
9
1, 0, 1, 0, 1, 0, 1, 0, 1
6 3
25
6, 3, 9, 27, -18, -1.5, -19.5, 29.25, -48.75, -0.6, -49.35, 29.61, -78.96, -0.375, -79.335, 29.7506, -109.086, -0.272727, -109.358, 29.825, -139.183, -0.214286, -139.398, 29.8709, -169.269
N
ser baseado em 0? Portanto, tome como entradas 1 menos que o N mostrado em seus exemplos. Eu acho que tomar N-2 é pedir demais para ... :-PRespostas:
MATL ,
191817 bytesEntrada está no formato:
N
(0-based),x(1)
,x(2)
(como cadeias); todos separados por novas linhas.Experimente online! Ou verifique todos os casos de teste (código ligeiramente modificado; sequências de saída separadas por uma linha em branco).
Explicação
O MATL não possui uma
eval
função adequada , masU
(str2num
) pode avaliar expressões numéricas com operadores de infix.Cada novo termo é calculado e colocado na pilha, mantendo os termos anteriores. A pilha inteira é impressa no final.
fonte
Haskell,
696864 bytesx1
ex2
são tomados como uma lista. Exemplo de uso:[1,3] # 8
->[1.0,3.0,4.0,12.0,-8.0,-1.5,-9.5,14.25]
.A preguiça torna possível definir uma lista recursiva infinita onde pegamos os primeiros n elementos.
Haskell, 66 bytes
Abordagem diferente, um pouco mais. Fim argumento é
N
,x2
,x1
. Exemplo de uso:( (.a).(.).take ) 8 3 1
->[1.0,3.0,4.0,12.0,-8.0,-1.5,-9.5,14.25]
.Define 4 funções
a
,b
,c
ed
que tomam dois argumentosy
,x
e fazer uma lista, colocandox
na frente de uma chamada para o próximo função comy
como o segundo argumento ex op y
como o primeiro. Por exemploa
é:a y x = x : (b (x+y) y)
,b
faz a multiplicação:b y x = x : (c (x*y) y)
, etc.Edit: @Michael Klein salvou um byte na 1ª variante (
#
). Felizmente, também encontrei um byte para a segunda variante, para que ambos tenham o mesmo comprimento novamente.Edição II: o @Zgarb encontrou 2 bytes na segunda versão para salvar e I 4 na primeira, para que eles não tenham mais o mesmo comprimento.
fonte
(.)
é composto por outras funções: pg x=(`take`f)where
não salva um byte: - /(h%g)y x=x:g(h x y)y
ES6 (Javascript),
79,67, 65 bytesATUALIZAR
Golfe
Teste
fonte
++i
para evitar a adição de 1 ai
duas vezes??S(n,a,i+1,a.push(...)):a
pode economizar alguns bytes.a.push
retorna o novo comprimento,S=(n,a,i=2)=>i<n?S(n,a,a.push(...)):a
i=2
embora.S=(n,a,i=2)=>i<n?S(n,a,a.push(eval(a[i-2]+"+*-/"[i%4]+a[i-1]))):a
para economizar 2 bytes.Python 3,
908074 byteso xnor provavelmente irá destruir esta solução ...
A função modifica a lista passada para ela. Use assim:
Experimente repl.it!
-6 bytes graças ao cobre
fonte
O
uma vez, é possível salvar alguns bytes executando'-/+*'[i%4]
e removendo a declaração deO
. Além disso, você pode contornar as chamadas repetidasstr
fazendo algo parecidoeval('%s'*3%(s[-2],'-/+*'[i%4],s[-1]))
.s+=[...]
pode ser substituído pors+=...,
(observe a vírgula à direita).i
como entrada, portanto, não precisa do valor padrão (i=2
pode ser justoi
). Dois bytes desativados.n
th item na sequência, este é 1 byte menor com recursão:f=lambda x,n:n<2and x[n-1]or eval('%s'*3%(f(x,n-2),'*-/+'[n%4],f(x,n-1)))
Perl 6 ,
75 7161 bytesTeste-o
Teste-o
Teste-o
Expandido:
fonte
Mathematica, 68 bytes
Mal entrou no terceiro lugar! Função sem nome de três argumentos, que usa um operador unário auxiliar
±
tal que±n
seja exatamente o enésimo elemento x (n) da sequência Stewie. Os dois primeiros argumentos são x (1) e x (2), e o terceiro argumento é o N, indicando qual x (N) produzimos.Implementação direta, usando um cálculo mod-4 para escolher qual função binária aplicar aos dois termos anteriores. Escolher a função binária correta, que é o que
1##[#-#2,#/#2,+##]
ajuda, usa alguns desses truques divertidos de golfe do Mathematica .fonte
05AB1E ,
211918 bytesA entrada é feita na ordem N (com base em 0), x (2) , x (1) .
Economizou 1 byte graças à carusocomputação .
Experimente online!
Explicação
Construímos iterativamente a pilha com o elemento mais recente na sequência no topo, mantendo todos os elementos anteriores em ordem.
Em seguida, agrupamos a pilha em uma lista no final para exibir todos os valores de uma só vez.
fonte
XY
eUV
pode economizar bytes.UX
:)Lisp comum, 158
Não é realmente competitivo, mas eu gosto de como é expresso naturalmente:
Ignoramos erros ao calcular R, o que faz com que R (e depois B) aceite o valor NIL. Isso permite gerar o resultado atual, mesmo que o próximo valor seja indefinido. Então, eventualmente, o loop falhará, mas isso está dentro das regras.
Testes
Nomeamos a função
F
e verificamos que os valores esperados são aproximadamente iguais aos testados.O motivo do teste aproximado é que os valores calculados são um pouco mais precisos do que o necessário; aqui para
(f 6 3 25)
:fonte
dc,
112110108 bytesÀs vezes, as
dc
respostas podem ser super longas e, às vezes, super curtas. Tudo depende apenas do desafio em questão, como é o caso de muitos outros idiomas. De qualquer forma, isso solicita uma entrada de linha de comando indexada em um espaço, de 3 números inteiros,x(1), x(2), N
após a chamada e gera cada elemento da sequência em linhas separadas com saídas não inteiras contendo 5 dígitos após o ponto decimal.Por exemplo, a entrada
6 3 25
resulta na seguinte saída:fonte
Perl, 62 + 3 (
-pla
sinalizador) = 65 bytesUsando:
fonte
Ruby, 79 bytes
Suspeito que isso esteja muito longe do ideal (e ainda não olhei para as outras respostas), mas ainda assim é divertido.
Eu queria me divertir um pouco
Enumerable#cycle
, mas, infelizmente, são 4 caracteres a menos para usar%4
.fonte
C ++ 14, 118 bytes
Como lambda sem nome, modificando sua entrada. Requer
v
ser umvector<double>
ouvector<float>
.Ungolfed e uso:
fonte
código de máquina x86-64, 34 bytes
Convenção de chamada = x86-64 System V x32 ABI (registre argumentos com ponteiros de 32 bits no modo longo).
A assinatura da função é
void stewie_x87_1reg(float *seq_buf, unsigned Nterms);
. A função recebe os valores iniciais x0 e x1 nos dois primeiros elementos da matriz e estende a sequência para pelo menos mais N elementos. O buffer deve ser preenchido com 2 + N-arredondado-para-o-próximo-múltiplo-de-4. (ou seja2 + ((N+3)&~3)
, apenas N + 5).Exigir buffers acolchoados é normal na montagem para funções de alto desempenho ou vetorizadas por SIMD, e esse loop desenrolado é semelhante, portanto, não acho que isso esteja distorcendo as regras demais. O chamador pode facilmente (e deve) ignorar todos os elementos de preenchimento.
Passar x0 e x1 como uma função arg ainda não no buffer nos custaria apenas 3 bytes (para a
movlps [rdi], xmm0
oumovups [rdi], xmm0
), embora isso seja uma convenção de chamada não padrão, pois o System V passastruct{ float x,y; };
em dois registros XMM separados.Isso é
objdump -drw -Mintel
produzido com um pouco de formatação para adicionar comentáriosEsta implementação de referência C compila (com
gcc -Os
) um código semelhante. O gcc escolhe a mesma estratégia que eu, de manter apenas um valor anterior em um registro.Eu experimentei de outras maneiras, incluindo uma versão x87 de dois registros que possui código como:
Você faria dessa maneira se estivesse buscando velocidade (e o SSE não estava disponível)
Colocar as cargas da memória dentro do loop em vez de uma vez na entrada pode ter ajudado, já que podemos armazenar os resultados sub e div fora de ordem, mas ainda assim precisamos de duas instruções FLD para configurar a pilha na entrada.
Também tentei usar a matemática escalar SSE / AVX (começando com valores em xmm0 e xmm1), mas o tamanho maior da instrução é matador. Usar
addps
(já que é 1B menor queaddss
) ajuda um pouquinho. Usei prefixos AVX VEX para instruções não comutativas, pois o VSUBSS tem apenas um byte a mais que SUBPS (e o mesmo comprimento que SUBSS).Testado com este equipamento de teste:
Ajuntar com
nasm -felfx32 -Worphan-labels -gdwarf2 golf-stewie-sequence.asm &&
gcc -mx32 -o stewie -Og -g golf-stewie-sequence.c golf-stewie-sequence.o
Execute o primeiro caso de teste com
./stewie 8 1 3
Se você não possui bibliotecas x32 instaladas, use
nasm -felf64
e deixe o gcc usando o padrão-m64
. Eu usei emmalloc
vez defloat seqbuf[seqlen+8]
(na pilha) para obter um endereço baixo sem ter que realmente construir como x32.Curiosidade: O YASM possui um bug: ele usa um rel32 jcc para a ramificação do loop, quando o destino da ramificação tem o mesmo endereço que um símbolo global.
monta para ...
11f: 0f 8f db ff ff ff jg 100 <stewie_x87_1reg>
fonte
05AB1E , 12 bytes
Experimente online!
fonte
Japonês , 20 bytes
Tente
fonte
Bash, 224 bytes (SEM CONCURSO)
Uma implementação tremendamente grande no BASH .
Executa a tarefa literalmente e faz tudo em um tubo contínuo, sem estruturas de fluxo de controle profanas ou recursão.
Entrada
Golfe
Menos Golfe
Teste
Etapas do pipeline
Gere uma tabela de índices de elementos + op, para cada elemento da sequência de saída (um por linha):
Use sed para converter isso em um programa linear bc :
alimente isso com bc e deixe fazer todo o trabalho
fonte
Pitão - 20 bytes
Todos os
n
custos me custam.Não funciona online, porque eval.
fonte
Ceilão, 195 bytes
Formatado e comentado:
Exemplo de uso:
Exemplo de saída:
O segundo exemplo mostra como isso lidaria com a divisão por zero. O último exemplo mostra que os resultados divergem um pouco, dependendo do tipo de aritmética (e arredondamento) usado ... Acho que a aritmética de ponto flutuante de 64 bits do Ceilão está um pouco mais próxima do que deveria ser do que o postado na pergunta .
fonte
Clojure, 99 bytes
Esta versão é mais agradável de usar na prática, mas possui 110 bytes:
Tive problemas ao interromper a função iterada e uma sequência cíclica de operações, então tive que usar um contador. Também tentei usar uma tabela de transição FSM como,
{+ * * - - / / +}
mas não consegui compactá-la com menos código.Pode ser expresso como uma função anônima
Sem golfe:
Deve ser chamado com carros alegóricos
(f 6.0 3.0 25)
, caso contrário, você obtém números racionais. Como alternativa, a iteração pode ser iniciada a partir da[a (float b) 0]
qual traz alguns caracteres extras.fonte
Oitava , 91 bytes
Experimente online!
Alguns campos de golfe:
eval
chamadaeval
chamada*-/+
(não é possível no MATLAB)'
e"
para evitar escapar dos apóstrofos (não é possível no MATLAB)n=@num2str
pois é usado duas vezes (não é possível no MATLAB)fonte