Segunda-feira Mini-Golf # 1: Solver Reverso de Fibonacci

28

Mini-golfe de segunda-feira: Uma série de desafios curtos , 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 13até 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 0e 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 , 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!

ETHproductions
fonte
10
Eu removi a tag [segunda-feira-mini-golfe] que você criou. Acho que não devemos criar tags para grupos de desafios mais ou menos arbitrários. A tag realmente não diz nada sobre o desafio e, se você quiser encontrar tudo isso, basta procurar a frase na barra de pesquisa. Como alternativa, se você incluir um link para esse primeiro desafio em todas as parcelas futuras, todos serão vinculados em "Perguntas vinculadas" na barra lateral.
Martin Ender
@ MartinBüttner OK, obrigado; Vou manter isso em mente.
ETHproductions
Posso pegar a entrada como eu quero (uma lista literal de python [8, 13, 10])?
Blue
3
O desafio atualmente diz escrever um programa . Isso significa que funções não são permitidas? (CC @LuisMendo)
Dennis
3
@ Dennis Desculpe, escorregou minha mente. Funções também são permitidas. Obrigado por apontar isso!
ETHproductions

Respostas:

12

Pitão, 23 bytes

AQWgHGA,-HGG)VvwHA,H+GH

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:

AQWgHGA,-HGG)VvwHA,H+GH  Q = input list of the two starting numbers
AQ                       G, H = Q (unpacking Q)
  WgHG                   while H >= G:
      A,-HGG                G, H = [H - G, G]
            )            end while
              vw         read a number from input
             V           for N in range(^):
                H           print H
                 A,H+GH     G, H = [H, G + H]
Jakube
fonte
12

Retina , 65 54 bytes

+`(1*),\1(1*)
$2,$1
+`(1*)(,1*);1\B
$1$2$2$1;
^1*,|;1
<empty>

Aqui, <empty>representa uma linha de fuga vazia. Execute o código como um único arquivo com o -ssinalizador.

O formato de entrada é

A,B;N

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:

8 13 10

seria

11111111,1111111111111;1111111111

e rendimento

,1,1,11,111,11111,11111111,1111111111111,111111111111111111111,1111111111111111111111111111111111

Explicação

+`(1*),\1(1*)
$2,$1

Primeiro, reduzimos Ae Bpara 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 regex Aem grupo 1 com (1*), e, em seguida, garante que Bé pelo menos tão grande como Adurante a captura B-Acom \1(1*)em grupo 2. Isso garante que este loop termina uma vez A>B.

A substituição simplesmente se transforma A,Bao B-A,Adefinir a correspondência como $2,$1.

+`(1*)(,1*);1\B
$1$2$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 1partir N. Como já temos um número, queremos que isso aconteça apenas N-1. Fazemos isso garantindo \Bque ainda exista pelo menos ;11no final da string. Se chamarmos os dois últimos valores da sequência Ce D, o regex será capturado Cno grupo 1 e ,Dno grupo dois. Nós escrevemos isso de volta $1$2. Então também escrevemos o $2$1que se traduz em ,D+C. Observe que não escrevemos de volta o single em 1que combinamosN, diminuindo assim.

^1*,|;1
<empty>

Finalmente, precisamos nos livrar do -1º elemento da sequência, bem como das sobras ;1de N, o que fazemos simplesmente combinando qualquer um deles e substituindo-o pela string vazia.

Martin Ender
fonte
7

Python 2, 93 87 67 61 60 bytes

i,j,l=input()
while j/i:i,j=j-i,i
exec"i,j=j,i+j;print i;"*l

Obté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

Azul
fonte
1
Bom método. Para o loop sem índice for _ in[1]*l:, é um pouco mais curto de fazerexec"stuff;"*l
xnor
@ xnor: Parece-me significativamente mais longo.
recursivo
Compare for _ in[1]*l:stuffcom exec"stuff;"*l. @xnor não colocou a parte do material no loop for. Ou for _ in[1]*l:paraexec";"*l
Blue
2
Você pode substituir j>=ipor j/i. Acabei de descobrir isso! (Porque Pode-se presumir que A, B, e N são sempre inteiros positivos )
mbomb007
6

CJam, 26 23 bytes

Agradecimentos a Dennis por salvar 3 bytes.

q~{_@\-_g)}g\@{_@+_p}*t

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.

q~      e# Read and evaluate input, pushing N, B and A on the stack.
{       e# do while...
  _@\-  e#   B, A = A, B-A
  _W>   e#   Check if A is still non-negative.
}g
\@      e# Reorder N B A into A B N.
{       e# Run the following N times...
  _@+   e#   A, B = B, A+B
  _p    e#   Print B.
}*
t       e# The last A, B are still on the stack. We remove them by trying to
        e# execute a ternary operator: it pops the first two values but then
        e# terminates the program with an error, because there is no third value.
Martin Ender
fonte
q~{_@\-_g)}g\@{_@+_p}*t( N B A) salva três bytes.
Dennis
Enquanto eu tentava resolver isso no CJam, tive problemas com a entrada do exemplo 1. Agora vejo que essa solução também não fornece a saída esperada. Onde está a falha aqui? Penso que, em vez de B>Aprocurar, tem que procurar B not smaller than Aou algo assim, mas não consigo descobrir como fazer isso no CJam. EDIT: A solução de Dennis imprime a saída correta.
precisa saber é o seguinte
Bem, eu resolvi isso na minha solução.
precisa saber é o seguinte
@ Cabbie407 Você está correto, eu deveria ter usado em <!vez de >.
Martin Ender
Ah ok. Eu me perguntava onde colocar isso !nisso. Eu simplesmente adicionado um para fazê-lo funcionar;)
Cabbie407
5

Labirinto , 58 54 49 46 44 bytes

Agradecemos 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 (leitura B). Por fim, }passa Bpara a pilha auxiliar. O beco sem saída economiza um byte sobre o ingênuo

?
?
}

Agora, 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). :duplicatas A, {move-se Bde volta para a pilha principal, -calcula A-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 ?, lendo Ne 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):

                v
                "
               """>negative
non-negative <"""

Pelo menos ainda não consegui encontrar um layout mais compacto / útil para este caso.

De qualquer forma, embora Anão seja negativo, o loop continua, }se move Apara a pilha auxiliar e =troca Ae B.

Uma vez que Aé negativo, ?Ne 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 Ne Apara a pilha auxiliar. Duplicar B, troque a cópia com Ae adicione Aà outra cópia de B. Duplique-o novamente para imprimir o valor atual de B. Imprima uma nova linha. Mova Be Nvolte para a pilha principal e diminua N.

Enquanto Npositivo, o IP fará uma curva à direita (norte) continuando o loop. Quando Nchega 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 pressiona 0. `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.

Martin Ender
fonte
5

C, 105 102 100 bytes

main(a,b,n,t){for(scanf("%d%d%d",&a,&b,&n);t=b-a,t>=0;a=t)b=a;for(;n--;b=t)t=a+b,printf("%d ",a=b);}

Obrigado a @ C0deH4cker por jogar fora 2 bytes!

Experimente online no Ideone .

Dennis
fonte
4

Matlab / Octave, 115 125 bytes

function x=f(x,n)
while x(2)>=x(1)
x=[abs(x(1)-x(2)) x];end
x=x([2 1]);for k=1:n-1
x=[x(1)+x(2) x];end
x=x(n:-1:1);

A função deve ser chamada como f([8 13],10).

Exemplo (Matlab):

>> f([8 13],10)
ans =
     0     1     1     2     3     5     8    13    21    34

Ou tente online (oitava) .

Luis Mendo
fonte
De acordo com as regras, você pode modificar a entrada, portanto f([a b],n)deve ser permitido.
beaker
Obrigado @beaker! Eu ia fazer isso ... mas depois li a regra "A entrada e a saída podem ser separadas por espaços, vírgulas ou novas linhas" e fiquei confuso. Vou pedir esclarecimentos
Luis Mendo
Sim, eu não sei se x=f(x,n)nas contagens de cabeçalho função ...
copo
@AlexA. Eu estava respondendo ao comentário de Luis sobre a regra "A entrada e a saída podem ser separadas por espaços, vírgulas ou novas linhas" e os "A, B e N do OP podem ser obtidos em qualquer ordem e formato, desde que sejam visivelmente separados ". Como A e B não seriam mais visivelmente separados no cabeçalho da função, eu estava questionando se ter apenas 2 argumentos de função seria permitido.
proveta de
3

Haskell, 67 65 56 bytes

a#b|a>b=b:scanl(+)(a+b)(a#b)|1>0=(b-a)#a
n%a=take n.(a#)

Obrigado a @nimi por sugestões

Isso define uma função de infixo ternário %, que é chamada no formato (n%a)b, por exemplo:

> (10%8)13
[0,1,1,2,3,5,8,13,21,34]

Explicação

A função infixa binário #, definidos na primeira linha, leva em dois inteiros ae be retorna o infinito de Fibonacci-sequência como onde ae bocorrer como elementos consecutivos.

a#b                                       -- Define a#b:
   |a>b=                                  -- if a>b, then a#b is
        b:                                -- the sequence that starts with b and
          scanl(+)     (a#b)              -- continues with the sums of prefixes of a#b
                  (a+b)                   -- plus the additional term a+b;
                            |1>0=(b-a)#a  -- otherwise, it's (b-a)#a.

A função %simplesmente pega os primeiros nelementos de a#b.

Zgarb
fonte
Você pode criar a sequência fibonacci com 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)#ae salvar dois bytes.
nimi
Obrigado @nimi; Eu corri com a sua ideia e salvei um total de 9 bytes.
Zgarb 22/09/2015
3

> <>, 33 31 + 1 para -v = 32 bytes

&:{:@(?v:}-$&
-1;!?:&<$+{oan::$&

A 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:

& removes N from the stack to put it into a register. [F(n), F(n+1)]
:{:@ move the stack and duplicate items to get [F(n+1), F(n), F(n+1), F(n)]
(?v compares the two top items of the stack and branch to the second line if F(n+1) < F(n) [F(n+1), F(n)]
:} move the stack and duplicate its top to get [F(n), F(n+1), F(n)]
- substracts the two top items and put the result on top of the stack [F(n), F(n+1) - F(n)]
$ switchs the top two values of the stack. [F(n+1) - F(n), F(n)]
& retrieve the value from the register. iteration complete, since [F(n+1) - F(n), F(n), N] can also be read as [F(n-1), F(n), N]

A segunda linha sobe a série até que imprima N termos:

< changes the code pointer direction to the left [F(0), F(-1)]
& retrieves the stored value back from the stack [F(0), F(-1), N]
:?!; copies N to compare it to 0, stops if it is [F(0), F(-1), N]
1- decreases it [F(0), F(-1), N-1]
& stores it back [F(0), F(-1)]
$:: makes the stack [F(-1), F(0), F(0), F(0)]
n{ prints the top of the stack then left shifts it [F(0), F(0), F(-1)]
ao displays a line feed (ascii character 0x0a) [F(0), F(0), F(-1)]
+ adds the two top values [F(0), F(-1) + F(0)]
$ switch the two top values. iteration complete since [F(-1) + F(0), F(0)] which can be read as [F(1), F(0)]
Aaron
fonte
Você deve reduzir sua contagem de bytes em 2, alterando 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ê tinha 00.em primeiro lugar).
cole
Sim, não tenho muita certeza disso, vi pessoas aqui usarem! De uma maneira que ignorava os espaços. Sei que o intérprete on-line em fishlanguage.com não funciona dessa maneira, mas talvez o intérprete python funcione. e faz o truque bem de qualquer maneira, obrigado!
Aaron
O intérprete online trabalha com !ou ?(no final da linha) se estiver na linha mais longa. Você pode experimentá-lo com algo parecido 1n!e isso dará erro, mas se houver uma linha abaixo dela com algo mais longo do que isso lorumipsum, não será.
cole
"A saída deve ser separada por espaços, vírgulas e / ou novas linhas." Desculpe, mas você terá que usar a outra versão. Bom trabalho!
ETHproductions
Fixa-lo, eu usei \ n em vez de espaços para salvar 2 bytes
Aaron
2

Java, 113 78 76 bytes

O crédito vai para a ETHproduction por fornecer o algoritmo usado nesta resposta.

(a,b,n)->{for(;a<=b;b-=a)a=b-a;for(;n-->0;b+=a,a=b-a)System.out.println(b);}

Tente aqui .

Explicação:

(a,b,n)->{
    for (;a<=b;b=b-a)a=b-a;  //Compute previous terms while a <= b
    for (;n-->0;b=a+b,a=b-a) //Compute and print next terms while n > 0
    System.out.println(b);   //Print term
}

Abordagem original, 113 93 bytes

Parece mais golfe;)

String a(int a,int b,int n){return n<0?a+" "+a(b,a+b,n+1):n>0?a>b?a(b,a+b,-n):a(b-a,a,n):"";}

Experimente aqui .

Explicação:

String a(int a, int b, int n){
    return 
    n < 0 ?                           //If n < 0
        a + " " + a(b, a + b, n + 1)  //Return a + next terms and increment n.
    :                                 //Else
        n > 0 ?                       //If n > 0
            a > b ?                   //If a > b
                a(b, a + b, -n)       //Negate n and return terms.
            :                         //If a <= b
                a(b - a, a, n)        //Generate previous term.
        :                             //If n == 0
            ""                        //Return nothing.
    ;
}
O número um
fonte
3
O que? Java é mais curto que JS?!? Tem de haver algo que eu estou fazendo de errado ....
ETHproductions
@ETHproductions Na verdade, copiei o seu algoritmo (e depois joguei no golfe): P
TheNumberOne
Está tudo bem comigo, tirei algumas de suas melhorias;) Eu esqueci que imprimir cada item separadamente era válido em JS.
ETHproductions
Você pode reduzir b=b-apara b-=a, e o mesmo com a=b+a. Ele vai salvar 2 bytes
Javier Diaz
+1 por tornar um envio de idioma detalhado tão curto. Normalmente, os envios de Java são os mais longos!
DankMemes 23/09
2

Javascript (ES6), 83 73 63 bytes

Isso pode ter sido jogado ao máximo. Veremos.

(a,b,n)=>{while(a<=b)b-=a=b-a;for(;n--;console.log(a=b-a))b+=a}

Ungolfed:

function f(a,b,n) {
  // repeat until we find the 0th item...
  while (a <= b) {  // if a = 5, b = 8:
    a = b - a;      // a = (8 - 5) = 3
    b = b - a;      // b = (8 - 3) = 5
  }
  // repeat n times...
  while (n-- > 0) { // if a = 5, b = 8:
    b += a;         // b = (8 + 5) = 13
    a = b - a;      // a = (13 - 5) = 8
    console.log(a); // print out each item
  }
}
ETHproductions
fonte
1

Mathematica 112

Será que o golfe eventualmente

z[a_, b_, n_] := (
  f[0] := Min[a, b];
  f[1] := Max[a, b];
  f[x_] := f[x - 1] + f[x - 2];
  f /@ Range[n]
  )
WizardOfMenlo
fonte
1

CJam, 40 bytes

l~:A;{_@_@)<}{_@\-\}w\{A(:A0>}{_p_@+}w\;

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.

l~:A;{_@_@)<}{_@-z\}w\A{_p_@+}*;;

E eu poderia até reduzi-lo mais um usando o operador ternário para limpar a pilha e gerar um erro.

Cabbie407
fonte
1

Ruby, 141 bytes

def u a,b,n,z=""
n<1 ? z.chop : u(b,a+b,n-1,z+"#{a} ")
end 
def d a,b,z=0
a.abs>b ? z : d(b-a,a,[a,b]) 
end 
def f a,b,n
x,y=d a,b 
u x,y,n
end 

Execução

A função f produz a saída desejada, os nomes dos argumentos correspondem aos nomes das variáveis ​​da pergunta

f(8,13,10) # returns => "0 1 1 2 3 5 8 13 21 34"

Nada inteligente:

  • você ( cima ) calcula n elementos na sequência de fibonacci começando com a, b usando recursão
  • d ( para baixo ) localiza o 0º e o 1º elemento, dados dois elementos finais usando recursão
  • A função f ( fibonacci ) coloca os dois juntos
alexanderbird
fonte
1

Mathematica, 59 bytes

If[#>#2,LinearRecurrence[{1,1},#2+{0,#},#3],#0[#2-#,#,#3]]&
alefalpha
fonte
0

Ruby, 81 75 73

a,b,n=23,37,5;while(c=b-a)<a;b,a=a,c;end;p a;[*2..n].map{b=c+a;c,a=a,b;p b}

Encurtado em 6 bytes ao substituir o loop for pelo range.map

a,b,n=23,37,5;while(c=b-a)<a;b,a=a,c;end;p a;[*2..n].map{p b=c+a;c,a=a,b}

Salvo outros 2 bytes movendo a instrução print

Yuri Kazakov
fonte
0

Lisp comum, 91 bytes

(lambda(a b n)(do((x a(- y x))(y b x))((> x y)(dotimes(k n)(print y)(psetf y(+ y x)x y)))))

Experimente online!

Renzo
fonte