Mini-golfe de segunda-feira: Uma série de desafios curtos de golfe com código , publicados (espero!) Toda segunda-feira.
Uma sequência semelhante a Fibonacci é obtida usando o mesmo método que a famosa sequência de Fibonacci ; ou seja, cada número F (n) é encontrado adicionando os dois números anteriores na sequência ( F (n) = F (n-1) + F (n-2) ) ou subtraindo os próximos dois números ( F (n) = F (n + 2) - F (n + 1) ). A principal diferença é que essas seqüências podem começar com dois números. A indexação zero dessas seqüências é discutível, mas por enquanto, vamos usar esta regra:
- O número 0 em uma sequência semelhante a Fibonacci é o último número que é menor que o número anterior.
Como exemplo, a sequência de Fibonacci pode ser escrita como 1, 0, 1, 1, 2, 3, 5...
, portanto, o número 0 na sequência é o único 0
.
Desafio
O objetivo do desafio é escrever um programa ou função que aceite três números inteiros, em qualquer formato:
- A e B , os dois números com os quais começar a gerar uma sequência.
- N , o comprimento da sequência resultante para a saída.
E gera os primeiros N números da sequência, começando no 0º.
Detalhes
- A , B e N podem ser obtidos em qualquer ordem e formato, desde que estejam visivelmente separados. Se você usar um pedido / formato diferente, especifique o que é.
- Você pode assumir que A , B e N são sempre números inteiros positivos.
- Você pode supor que N não exceda 100 e a sequência resultante não conterá
x >= 2^31
. - Se A for maior que B , então B é o número 0 na sequência.
- A saída deve ser separada por espaços, vírgulas e / ou novas linhas.
- Um espaço à direita ou nova linha é permitido, mas não uma vírgula à direita.
Casos de teste
Exemplo 1:
8 13 10
Trabalhando para trás 8 13
até encontrarmos um número maior que o anterior, obtemos 13 8 5 3 2 1 1 0 1
. Assim, 0
é o número 0 nesta sequência. No futuro, imprimimos 0
e os próximos 9 membros:
0 1 1 2 3 5 8 13 21 34
Exemplo 2:
23 37 5
Mais uma vez, trabalhando para trás para encontrar o número 0, encontramos 37 23 14 9 5 4 1 3
. O número 0 desta vez é 1
, então nós o imprimimos, juntamente com os próximos 4 membros:
1 4 5 9 14
Exemplo 3:
4 3 8
Com este, não precisamos retroceder para encontrar o número 0, porque 3
é menor que 4
:
3 7 10 17 27 44 71 115
Exemplo 4:
29 47 11
Resultado:
1 3 4 7 11 18 29 47 76 123 199
Pontuação
Este é o code-golf , pelo que o código válido mais curto em bytes vence. O desempatador vai para a submissão postada anteriormente. O vencedor será escolhido na próxima segunda-feira, 28 de setembro. Boa sorte!
Edit: Parabéns ao seu vencedor, @Jakube, usando Pyth para incríveis 23 bytes!
[8, 13, 10]
)?Respostas:
Pitão, 23 bytes
Experimente on-line: Demonstration or Test Suite
Estilo bastante incomum de programação Pyth. Às vezes, a programação funcional tem suas desvantagens.
Explicação:
fonte
Retina ,
6554 bytesAqui,
<empty>
representa uma linha de fuga vazia. Execute o código como um único arquivo com o-s
sinalizador.O formato de entrada é
onde os números são representados em unário . A saída é uma lista separada por vírgula, também em unário. Por exemplo:
seria
e rendimento
Explicação
Primeiro, reduzimos
A
eB
para o 0º e o -1º elemento. Ele+
informa à Retina para continuar repetindo essa substituição de regex até que o regex pare de corresponder ou a substituição não modifique a string. As capturas de regexA
em grupo 1 com(1*)
, e, em seguida, garante queB
é pelo menos tão grande comoA
durante a capturaB-A
com\1(1*)
em grupo 2. Isso garante que este loop termina uma vezA>B
.A substituição simplesmente se transforma
A,B
aoB-A,A
definir a correspondência como$2,$1
.Agora já temos o primeiro número da saída necessária na string (assim como a anterior), da qual precisaremos nos livrar mais tarde. Esta substituição agora adiciona um outro número como a soma dos dois últimos números, tendo um
1
partirN
. Como já temos um número, queremos que isso aconteça apenasN-1
. Fazemos isso garantindo\B
que ainda exista pelo menos;11
no final da string. Se chamarmos os dois últimos valores da sequênciaC
eD
, o regex será capturadoC
no grupo 1 e,D
no grupo dois. Nós escrevemos isso de volta$1$2
. Então também escrevemos o$2$1
que se traduz em,D+C
. Observe que não escrevemos de volta o single em1
que combinamosN
, diminuindo assim.Finalmente, precisamos nos livrar do -1º elemento da sequência, bem como das sobras
;1
deN
, o que fazemos simplesmente combinando qualquer um deles e substituindo-o pela string vazia.fonte
Python 2,
9387676160 bytesObtém a entrada (como uma lista python literal
[8,10,13]
)Elabora o 0º termo
Em seguida, imprime a sequência de adições até que o comprimento seja atingido
fonte
for _ in[1]*l:
, é um pouco mais curto de fazerexec"stuff;"*l
for _ in[1]*l:stuff
comexec"stuff;"*l
. @xnor não colocou a parte do material no loop for. Oufor _ in[1]*l:
paraexec";"*l
j>=i
porj/i
. Acabei de descobrir isso! (Porque Pode-se presumir que A, B, e N são sempre inteiros positivos )CJam,
2623 bytesAgradecimentos a Dennis por salvar 3 bytes.
Recebe a entrada em ordem
N B A
(separada por qualquer tipo de espaço em branco). Imprime o resultado como uma lista separada por nova linha e termina com um erro .Teste aqui.
Explicação
Isso vai um passo além ao encontrar o 0º elemento. Ou seja, ele termina quando um dos valores é negativo.
fonte
q~{_@\-_g)}g\@{_@+_p}*t
(N B A
) salva três bytes.B>A
procurar, tem que procurarB not smaller than A
ou algo assim, mas não consigo descobrir como fazer isso no CJam. EDIT: A solução de Dennis imprime a saída correta.<!
vez de>
.!
nisso. Eu simplesmente adicionado um para fazê-lo funcionar;)Labirinto ,
5854494644 bytesAgradecemos ao Sp3000 por sugerir o uso de negação bit a bit, que salvou dois bytes.
O formato de entrada é
B A N
. A saída é uma lista separada por nova linha.Explicação
(Um pouco desatualizado. A idéia básica ainda é a mesma, mas o layout do código é diferente agora.)
Isso usa a mesma idéia da minha resposta CJam (então os créditos ainda vão para Dennis): ao rastrear a sequência, não paramos até obter um valor negativo (o que nos deixa com o -1º e o 2º elemento da sequência). Então, começamos a adicioná-los antes de imprimir o primeiro valor.
Isso usa alguns truques de golfe do Labyrinth. Vamos analisar o código nas seções:
O IP começa no
?
caminho certo (que lêA
). No"
(no-op), ele atinge um beco sem saída, então se vira, executando o?
novo (leituraB
). Por fim,}
passaB
para a pilha auxiliar. O beco sem saída economiza um byte sobre o ingênuoAgora, o loop que encontra o início da sequência:
O
)(
(incremento-decremento) é um no-op, mas é necessário garantir que a parte superior da pilha seja positiva na junção (de modo que o IP vire para o leste).:
duplicatasA
,{
move-seB
de volta para a pilha principal,-
calculaA-B
. O que realmente queremos éB-A
, porém,`
nega o valor.Agora, este é um cruzamento de quatro direções. Para resultados negativos, o IP vira à esquerda na direção de
?
, lendoN
e passando para a próxima parte do programa. Se o resultado for zero, o IP continua se movendo para o sul, faz uma curva no canto e permanece no loop. Se o resultado for positivo, o IP vira à direita (oeste), vira na esquina e vira outra à direita (oeste novamente), para que também permaneça no circuito. Eu acho que isso pode se tornar um padrão comum, para distinguir valores negativos de não negativos (ou positivos de não positivos):Pelo menos ainda não consegui encontrar um layout mais compacto / útil para este caso.
De qualquer forma, embora
A
não seja negativo, o loop continua,}
se moveA
para a pilha auxiliar e=
trocaA
eB
.Uma vez que
A
é negativo,?
lêN
e passamos para o segundo loop:Sabemos que isso
N
é positivo, para que possamos contar com o IP na curva à esquerda (norte). O corpo do loop agora é simplesmente:Em palavras: move ambos
N
eA
para a pilha auxiliar. DuplicarB
, troque a cópia comA
e adicioneA
à outra cópia deB
. Duplique-o novamente para imprimir o valor atual deB
. Imprima uma nova linha. MovaB
eN
volte para a pilha principal e diminuaN
.Enquanto
N
positivo, o IP fará uma curva à direita (norte) continuando o loop. QuandoN
chega a zero, o código termina de uma maneira bastante sofisticada:O IP continua seguindo em frente (oeste). O
?
tenta ler outro número inteiro, mas já alcançamos o EOF, então ele realmente pressiona0
.`
tenta negar isso, mas ainda é zero. Portanto, o IP ainda segue para o oeste, faz uma curva no canto e continua descendo para o@
que encerra o programa.Pergunto-me se eu poderia colocar o
@
em uma posição ainda mais barato (custa actualmente 3 espaços em branco), rodando os três"
ao redor do`
no composto não-ops (como)(
), mas eu não tenho sido capaz de fazer esse trabalho ainda.fonte
C,
105102100 bytesObrigado a @ C0deH4cker por jogar fora 2 bytes!
Experimente online no Ideone .
fonte
Matlab / Octave, 115
125bytesA função deve ser chamada como
f([8 13],10)
.Exemplo (Matlab):
Ou tente online (oitava) .
fonte
f([a b],n)
deve ser permitido.x=f(x,n)
nas contagens de cabeçalho função ...Haskell,
67 6556 bytesObrigado a @nimi por sugestões
Isso define uma função de infixo ternário
%
, que é chamada no formato(n%a)b
, por exemplo:Explicação
A função infixa binário
#
, definidos na primeira linha, leva em dois inteirosa
eb
e retorna o infinito de Fibonacci-sequência como ondea
eb
ocorrer como elementos consecutivos.A função
%
simplesmente pega os primeirosn
elementos dea#b
.fonte
let f=a:scanl(+)(a+b)f in f
(-> full#
:a#b|a>b=let f=a:scanl(+)(a+b)f in f|1>0=(b-a)#a
e salvar dois bytes.> <>,
3331 + 1 para -v = 32 bytesA entrada deve ser pressionada na pilha usando -v, pois a análise de números decimais não é trivial em> <>.
Explicação:
Eu representarei a pilha após cada (grupo de) operações. Começa com [F (n), F (n + 1), N]
As primeiras linhas vão da série ao seu 0º termo:
A segunda linha sobe a série até que imprima N termos:
fonte
00.
na primeira linha para&
. Teoricamente,!
deve funcionar, mas acho que> <> preenche a largura das linhas para coincidir com a largura da mais longa (editar: é por isso que eu acho que você tinha00.
em primeiro lugar).!
ou?
(no final da linha) se estiver na linha mais longa. Você pode experimentá-lo com algo parecido1n!
e isso dará erro, mas se houver uma linha abaixo dela com algo mais longo do que issolorumipsum
, não será.Java,
1137876 bytesO crédito vai para a ETHproduction por fornecer o algoritmo usado nesta resposta.
Tente aqui .
Explicação:
Abordagem original,
11393 bytesParece mais golfe;)
Experimente aqui .
Explicação:
fonte
b=b-a
parab-=a
, e o mesmo coma=b+a
. Ele vai salvar 2 bytesJavascript (ES6),
837363 bytesIsso pode ter sido jogado ao máximo. Veremos.
Ungolfed:
fonte
Mathematica 112
Será que o golfe eventualmente
fonte
CJam, 40 bytes
Passos de bebê. Este é o meu primeiro programa CJam, por isso estou orgulhoso de que funcione.
Ele recebe entrada da mesma forma que nos exemplos.
Já vi que era possível reduzi-lo para 33 bytes usando a
{ ... }*
construção.E eu poderia até reduzi-lo mais um usando o operador ternário para limpar a pilha e gerar um erro.
fonte
Ruby, 141 bytes
Execução
A função f produz a saída desejada, os nomes dos argumentos correspondem aos nomes das variáveis da pergunta
Nada inteligente:
fonte
Mathematica, 59 bytes
fonte
Ruby,
817573Encurtado em 6 bytes ao substituir o loop for pelo range.map
Salvo outros 2 bytes movendo a instrução print
fonte
Pyke, 24 bytes (não concorrente)
Experimente aqui!
fonte
Gelatina , 14 bytes
Experimente online!
fonte
Lisp comum, 91 bytes
Experimente online!
fonte