Lunes Mini-Golf # 1: Solucionador reverso de Fibonacci

28

Mini golf de lunes: una serie de desafíos de corto , publicados (¡con suerte!) Todos los lunes.

Se obtiene una secuencia similar a Fibonacci utilizando el mismo método que la famosa secuencia de Fibonacci ; es decir, cada número F (n) se encuentra sumando los dos números anteriores en la secuencia ( F (n) = F (n-1) + F (n-2) ), o restando los dos números siguientes ( F (n) = F (n + 2) - F (n + 1) ). La principal diferencia es que estas secuencias pueden comenzar con dos números cualquiera. La indexación cero de estas secuencias es discutible, pero por ahora, vamos a usar esta regla:

  • El número 0 en una secuencia similar a Fibonacci es el último número que es más pequeño que el número anterior.

Como ejemplo, la secuencia de Fibonacci podría escribirse como 1, 0, 1, 1, 2, 3, 5..., por lo que el número 0 en la secuencia es el único 0.

Reto

El objetivo del desafío es escribir un programa o función que tome tres enteros, en cualquier formato:

  • A y B , los dos números con los que comenzar a generar una secuencia.
  • N , la longitud de la secuencia resultante a la salida.

Y genera los primeros N números de la secuencia, comenzando en el 0.

Detalles

  • A , B y N pueden tomarse en cualquier orden y formato, siempre que estén visiblemente separados. Si utiliza un orden / formato diferente, especifique cuál es.
  • Puede suponer que A , B y N son siempre enteros positivos.
  • Puede suponer que N no es más de 100 y que la secuencia resultante no contendrá x >= 2^31.
  • Si A es mayor que B , entonces B es el número 0 de la secuencia.
  • La salida debe estar separada por espacios, comas y / o nuevas líneas.
  • Se permite un espacio final o una nueva línea, pero no una coma final.

Casos de prueba

Ejemplo 1:

8 13 10

Trabajando hacia atrás desde 8 13que encontramos un número mayor que el anterior, obtenemos 13 8 5 3 2 1 1 0 1. Por lo tanto, 0es el número 0 en esta secuencia. Trabajando a partir de esto, imprimimos 0y los siguientes 9 miembros:

0 1 1 2 3 5 8 13 21 34

Ejemplo 2

23 37 5

Nuevamente trabajando hacia atrás para encontrar el número 0, encontramos 37 23 14 9 5 4 1 3. Esta vez el número 0 es 1, así que lo imprimimos, junto con los siguientes 4 miembros:

1 4 5 9 14

Ejemplo 3

4 3 8

Con este, no tenemos que trabajar hacia atrás para encontrar el número 0, porque 3es más pequeño que 4:

3 7 10 17 27 44 71 115

Ejemplo 4

29 47 11

Resultado:

1 3 4 7 11 18 29 47 76 123 199

Tanteo

Este es el , por lo que gana el código válido más corto en bytes. Tiebreaker va a la presentación publicada anteriormente. El ganador será elegido el próximo lunes 28 de septiembre. ¡Buena suerte!

Editar: ¡ Felicidades a tu ganador, @Jakube, por usar Pyth por unos increíbles 23 bytes!

ETHproducciones
fuente
10
Eliminé la etiqueta [monday-mini-golf] que creaste. No creo que debamos crear etiquetas para grupos de desafíos más o menos arbitrarios. La etiqueta realmente no te dice nada sobre el desafío, y si quieres encontrar todo esto, uno podría buscar la frase en la barra de búsqueda. Alternativamente, si incluye un enlace a este primer desafío en cada entrega futura, todos se vincularán en "Preguntas vinculadas" en la barra lateral.
Martin Ender
@ MartinBüttner OK, gracias; Lo tendré en mente.
ETHproductions
¿Puedo tomar la entrada como lo quiero (un literal de lista de Python [8, 13, 10])?
Azul
3
El desafío actualmente dice escribir un programa . ¿Eso significa que las funciones no están permitidas? (CC @LuisMendo)
Dennis
3
@Dennis Lo siento, se me pasó por la cabeza. Las funciones también están permitidas. ¡Gracias por señalar eso!
ETHproductions

Respuestas:

12

Pyth, 23 bytes

AQWgHGA,-HGG)VvwHA,H+GH

Pruébelo en línea: Demostración o conjunto de pruebas

Estilo bastante inusual de programación Pyth. A veces, la programación funcional tiene sus desventajas.

Explicación:

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
fuente
12

Retina , 65 54 bytes

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

Aquí, <empty>representa una línea final vacía. Ejecute el código como un solo archivo con la -sbandera.

El formato de entrada es

A,B;N

donde los números están representados en unario . La salida es una lista separada por comas, también en unario. Por ejemplo:

8 13 10

sería

11111111,1111111111111;1111111111

y rendir

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

Explicación

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

Primero, reducimos Ay Bal elemento 0 y -1. El +le dice a Retina que siga repitiendo esta sustitución de expresiones regulares hasta que la expresión regular deje de coincidir o la sustitución no modifique la cadena. La expresión regular captura Aen el grupo 1 con (1*), y luego se asegura de que Bsea ​​al menos tan grande como Adurante la captura B-Acon \1(1*)en el grupo 2. Esto asegura que este ciclo finalice una vez A>B.

La sustitución simplemente convierte A,Ben B-A,Aestableciendo el partido a $2,$1.

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

Ahora ya tenemos el primer número de la salida requerida en la cadena (así como el anterior, del cual tendremos que deshacernos más adelante). Esta sustitución ahora agrega otro número como la suma de los dos últimos números mientras toma un 1de N. Como ya tenemos un número, queremos que esto suceda solo N-1. Hacemos esto asegurándonos de \Bque todavía hay al menos ;11al final de la cadena. Si llamamos a los dos últimos valores de la secuencia Cy D, la expresión regular se captura Cen el grupo 1 y ,Den el grupo dos. Los escribimos de vuelta con $1$2. Luego también escribimos lo $2$1que se traduce en ,D+C. Tenga en cuenta que no escribimos el single con el 1que coincidimosN, decrementándolo así.

^1*,|;1
<empty>

Finalmente, necesitamos deshacernos del -1º elemento de la secuencia, así como los restos ;1de N, lo que simplemente hacemos al unir cualquiera de ellos y reemplazarlo con la cadena vacía.

Martin Ender
fuente
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

Obtiene la entrada (como una lista literal de Python [8,10,13])

Resuelve el término 0

Luego imprime la secuencia de adiciones hasta alcanzar la longitud

Azul
fuente
1
Buen método Para el ciclo sin índice for _ in[1]*l:, es un poco más corto de hacerexec"stuff;"*l
xnor
@xnor: Me parece significativamente más largo.
recursivo
Comparar for _ in[1]*l:stuffa exec"stuff;"*l. @xnor no puso la parte de cosas en el bucle for. O for _ in[1]*l:aexec";"*l
Azul
2
Se puede reemplazar j>=icon j/i. ¡Acabo de descubrir eso! (Debido a que Usted puede asumir que A, B, y N son siempre números enteros positivos )
mbomb007
6

CJam, 26 23 bytes

Gracias a Dennis por guardar 3 bytes.

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

Toma la entrada en orden N B A(separados por cualquier tipo de espacio en blanco). Imprime el resultado como una lista separada por una nueva línea y termina con un error .

Pruébalo aquí.

Explicación

Esto va un paso más allá al encontrar el elemento 0. Es decir, termina una vez que uno de los valores es 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
fuente
q~{_@\-_g)}g\@{_@+_p}*t( N B A) guarda tres bytes.
Dennis
Mientras intentaba resolver esto en CJam, tuve problemas con la entrada del ejemplo 1. Ahora veo que esta solución tampoco da el resultado esperado. ¿Dónde está la falla aquí? Creo que en lugar de verificarlo B>Atiene que verificar B not smaller than Ao algo así, pero no puedo entender cómo hacerlo en CJam. EDITAR: la solución de Dennis imprime la salida correcta.
Cabbie407
Bueno, lo resolví en mi solución.
Cabbie407
@ Cabbie407 Tienes razón, debería haberlo usado en <!lugar de >.
Martin Ender
Ah bien. Me preguntaba dónde poner eso !en esto. Simplemente agregué uno para que funcione;)
Cabbie407
5

Laberinto , 58 54 49 46 44 bytes

Gracias a Sp3000 por sugerir el uso de la negación bit a bit, que ahorró dos bytes.

??#"{=
  ;  -
@"~~:}
~""
?
"}}:=
(   +
{{\!:

El formato de entrada es B A N. El resultado es una lista separada por una nueva línea.

Explicación

(Ligeramente desactualizado. La idea básica sigue siendo la misma, pero el diseño del código es diferente ahora).

Esto usa la misma idea que mi respuesta de CJam (por lo que los créditos aún van a Dennis): cuando retrocedemos la secuencia no nos detenemos hasta que obtenemos un valor negativo (lo que nos deja con el elemento -1 ° y -2 ° de la secuencia). Luego, comenzamos a agregarlos antes de imprimir el primer valor.

Esto utiliza un par de ingeniosos trucos de golf Labyrinth. Veamos el código en secciones:

?"
}

La IP comienza a la ?derecha (que se lee A). En el "(un no-op) llega a un callejón sin salida, por lo que se da vuelta, ejecutando ?nuevamente (lectura B). Por último, se }mueve Ba la pila auxiliar. El callejón sin salida salva un byte sobre el ingenuo

?
?
}

Ahora el ciclo que encuentra el comienzo de la secuencia:

)(:{
"  -
" "`?...
=}""

El )((incremento-decremento) no funciona, pero es necesario asegurarse de que la parte superior de la pila sea positiva en la unión (de modo que la IP gire hacia el este). :duplicados A, {se mueve Batrás a la chimenea principal, -computa A-B. Sin B-Aembargo, lo que realmente queremos es que `niegue el valor.

Este es ahora un cruce de cuatro vías. Para obtener resultados negativos, la IP gira a la izquierda hacia ?, leyendo Ny pasando a la siguiente parte del programa. Si el resultado es cero, la IP sigue avanzando hacia el sur, gira en la esquina y permanece en el bucle. Si el resultado es positivo, el IP da un giro a la derecha (oeste), gira en la esquina y da otro giro a la derecha (oeste nuevamente) para que también permanezca en el bucle. Creo que esto podría convertirse en un patrón común, para distinguir valores negativos de valores no negativos (o positivos de no positivos):

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

Al menos todavía no he podido encontrar un diseño más compacto / útil para este caso.

De todos modos, mientras Ano es negativo, el bucle continúa, se }mueve Aa la pila auxiliar y =cambia Ay B.

Una vez que Aes negativo, ?lee Ny pasamos al segundo ciclo:

 }:=+:
 }   !
?"({{\

Sabemos que Nes positivo, por lo que podemos confiar en que la IP gire a la izquierda (norte). El cuerpo del bucle ahora es simplemente:

}}:=+:!\{{(

En palabras: mueve ambos Ny Asobre la pila auxiliar. Duplicar B, intercambiar la copia con Ay agregar Aa la otra copia de B. Duplíquelo nuevamente para imprimir el valor actual de B. Imprime una nueva línea. Mover By Nvolver a la pila principal y disminuir N.

Si bien Nes positivo, la IP tomará un giro a la derecha (norte) continuando el ciclo. Una vez que Nllega a cero, el código termina de una manera bastante elegante:

El IP sigue avanzando en línea recta (oeste). Los ?intentos para leer otro número entero, pero ya han llegado a EOF, por lo que en realidad empuja 0su lugar. `intenta negar eso, pero eso sigue siendo cero. Por lo tanto, la IP aún se mueve hacia el oeste, da una vuelta en la esquina y luego sigue bajando hacia la @que termina el programa.

Me pregunto si podía colocar el @en una posición aún más barato (que actualmente cuesta 3 caracteres de espacio en blanco) girando los tres "alrededor de la `en el compuesto no-ops (como )(), pero no he sido capaz de hacer que el trabajo todavía.

Martin Ender
fuente
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);}

¡Gracias a @ C0deH4cker por jugar 2 bytes!

Pruébelo en línea en Ideone .

Dennis
fuente
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);

La función debe llamarse como f([8 13],10).

Ejemplo (Matlab):

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

O pruébelo en línea (Octave) .

Luis Mendo
fuente
De acuerdo con las reglas, puede modificar la entrada, por lo que f([a b],n)debe permitirse.
vaso
@beaker ¡Gracias! Iba a hacer eso ... pero luego leí la regla "La entrada y la salida pueden estar separadas por espacios, comas o líneas nuevas" y me confundí. Pediré aclaraciones
Luis Mendo
Sí, no sé si x=f(x,n)en el recuento de cabecera de la función ...
vaso de precipitados
@AlexA. Estaba respondiendo al comentario de Luis sobre la regla "La entrada y la salida pueden estar separadas por espacios, comas o líneas nuevas" y los OP "A, B y N pueden tomarse en cualquier orden y formato, siempre que estén visiblemente separados ". Debido a que A y B ya no se separarían visiblemente en el encabezado de la función, me preguntaba si sería permisible tener solo 2 argumentos de función.
vaso
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#)

Gracias a @nimi por las sugerencias.

Esto define una función infija ternaria %, que se invoca en el formato (n%a)b, por ejemplo:

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

Explicación

La función infija binario #, definida en la primera línea, toma en dos enteros ay by devuelve el infinito Fibonacci-como secuencia en la que ay bse producen 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.

La función %simplemente toma los primeros nelementos de a#b.

Zgarb
fuente
Puede crear la secuencia de Fibonacci con 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)#ay guardar dos bytes.
nimi
@nimi Gracias; Corrí con su idea y ahorré un total de 9 bytes.
Zgarb
3

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

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

La entrada debe insertarse en la pila usando -v ya que analizar números decimales no es trivial en> <>.

Explicacion:

Representaré la pila después de cada (grupo de) operaciones. Comienza con [F (n), F (n + 1), N]

Las primeras líneas bajan de la serie a su término 0:

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

La segunda línea sube la serie hasta que haya impreso N términos:

< 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
fuente
Debería poder reducir su número de bytes en 2 cambiando 00.en la primera línea a &. Teóricamente, !debería funcionar, pero creo que> <> rellena el ancho de las líneas para que coincida con el ancho de la más larga (editar: es por eso que imagino que tenía 00.en primer lugar).
cole
Sí, no estoy muy seguro de eso, ¡he visto gente aquí usar! De una manera que ignoraba los espacios. Sé que el intérprete en línea en fishlanguage.com no funciona de esa manera, pero tal vez el intérprete de Python sí. Y funciona bien, gracias
Aaron
El intérprete en línea trabaja con !o ?(al final de la línea) si está en la línea más larga. Puede probarlo con algo así 1n!y generará un error, pero si hay una línea debajo de él con algo más largo que eso lorumipsum, no lo hará.
cole
"La salida debe estar separada por espacios, comas y / o nuevas líneas". Lo sentimos, pero tendrás que usar la otra versión. Buen trabajo, sin embargo!
ETHproductions
Solucionado, usé \ n en lugar de espacios para guardar 2 bytes
Aaron
2

Java, 113 78 76 bytes

El crédito va a ETHproduction por proporcionar el algoritmo que uso en esta respuesta.

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

Tratar aquí .

Explicación:

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

Enfoque original, 113 93 bytes

Parece más golfy;)

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):"";}

Pruébalo aquí .

Explicación:

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.
    ;
}
El numero uno
fuente
3
¿Qué? Java es más corto que JS?!? Tiene que haber algo que estoy haciendo mal ...
ETHproductions
@ETHproductions Realmente copié su algoritmo (y luego lo jugué): P
TheNumberOne
Eso está bien para mí, tomé algunas de sus mejoras;) Olvidé que imprimir cada elemento por separado era válido en JS.
ETHproductions
Puede acortar b=b-aa b-=a, y lo mismo con a=b+a. Ahorrará 2 bytes
Javier Díaz
+1 por hacer una presentación de lenguaje detallado tan breve. ¡Por lo general, los envíos de Java son los más largos!
DankMemes
2

Javascript (ES6), 83 73 63 bytes

Esto podría haber sido jugado al máximo. Ya veremos.

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

Sin golf:

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
  }
}
ETHproducciones
fuente
1

Mathematica 112

Lo jugará golf 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
fuente
1

CJam, 40 bytes

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

Pequeños pasos. Este es mi primer programa CJam, así que estoy orgulloso de que funcione.

Toma entrada en la misma forma que en los ejemplos.

Ahora he visto que podría reducirlo a 33 bytes usando la { ... }*construcción.

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

E incluso podría reducirlo en uno más utilizando el operador ternario para limpiar la pila y producir un error.

Cabbie407
fuente
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 

Ejecución

La función f produce la salida deseada, los nombres de los argumentos coinciden con los nombres de las variables de la pregunta

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

Nada inteligente:

  • La función u ( arriba ) calcula n elementos en la secuencia de Fibonacci que comienzan con a, b utilizando la recursividad
  • La función d ( abajo ) encuentra el elemento 0 y 1 dados dos elementos finales usando recursividad
  • La función f ( fibonacci ) pone los dos juntos
alexanderbird
fuente
1

Mathematica, 59 bytes

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

Rubí, 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}

Acortado por 6 Bytes al reemplazar for-loop con 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}

Se guardaron otros 2 bytes moviendo la declaración de impresión

Yuri Kazakov
fuente
0

Lisp común, 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)))))

Pruébalo en línea!

Renzo
fuente