Golf una trenza numérica creciente

23

Descripción de la trenza

En esta trenza, cuando una cadena cruza sobre la parte superior de otra cadena, agrega el valor de la otra cadena a sí mismo y todos los demás valores de cadena pasan. La trenza tiene tres hebras y cada hebra comienza en 1. El primer cruce es la hebra más a la izquierda que cruza sobre la hebra del medio. El siguiente cruce es el filamento más a la derecha que cruza sobre el nuevo filamento medio (anteriormente el filamento más a la izquierda). Estos dos pasos de los cruces se repiten. En otras palabras, el primer crossover es [a, b, c] -> [b, a+b, c]y el segundo es [a, b, c] -> [a, b+c, b]. Usando estas reglas aquí están los primeros seis niveles de la trenza:

1,1,1
1,2,1
1,3,2
3,4,2
3,6,4
6,9,4

Tu tarea

Escriba un programa o función de golf que acepte un número entero como el nivel de trenza y genere los tres valores para ese nivel de la trenza. Debe indicar si sus niveles están basados ​​en cero o en uno. La entrada y salida pueden venir en cualquier formato razonable y se permite el espacio en blanco final.

Casos de prueba (basados ​​en 1)

1 -> 1,1,1

2 -> 1,2,1

5 -> 3,6,4

10 -> 28,41,19
Robert Hickman
fuente

Respuestas:

7

MATL , 18 17 16 bytes

7Bi:"2:4PB@EX!Y*

La entrada está basada en 0.

Pruébalo en línea! O verificar todos los casos de prueba .

Explicación

Dado un vector de fila [a b c], el siguiente vector se obtiene después de la matriz, multiplicándolo por cualquiera

[1 0 0;
 0 1 1;
 0 1 0]

o

[0 1 0;
 1 1 0;
 0 0 1]

dependiendo de si el índice de iteración es impar o par. Por ejemplo, el producto matriz [1 3 2]*[0 1 0; 1 1 0; 0 0 1]da [3 4 2]. Luego [3,4,2]*[1 0 0; 0 1 1; 0 1 0]da [3 6 4], y así sucesivamente.

Tenga en cuenta también que la segunda matriz es igual a la primera girada 180 grados, que puede explotarse para ahorrar unos pocos bytes.

7        % Push 7
B        % Convert to binary. Gives [1 1 1]. This is the initial level
i        % Take input n
:        % Push range [1 2 ... n]
"        % For each
  5      %   Push 5
  I:     %   Push range [1 2 3]
  -      %   Subtract, element-wise: gives [4 3 2]
  B      %   Convert to binary. This gives the matrix [1 0 0; 0 1 1; 0 1 0]
  @      %   Push current iteration index
  E      %   Multiply by 2. Gives 2 in the firt iteration, 4 in the second etc
  X!     %   Rotate matrix 90 degrees either 2 or 0 times
  Y*     %   Matrix multiply
         % End. Implicitly display
Luis Mendo
fuente
¿Has considerado emparejar los pasos? De esa manera, tiene una matriz [[0, 1, 0], [1, 1, 1], [1, 1, 0]]y las diferentes posiciones iniciales son bastante similares para pares e imparesn
Peter Taylor
@ PeterTaylor Gracias por la idea. En este caso, variar el vector inicial y dividir la entrada por 2 parece ser más costoso en bytes
Luis Mendo
5

Haskell, 51 bytes

f p@(a,b,c)=p:(b,a+b,c):f(b,a+b+c,a+b)
(f(1,1,1)!!)

Esto usa indexación basada en 0. Ejemplo de uso: (f(1,1,1)!!) 10-> (28,60,41).

fcrea la lista infinita de tripletas de trenzas y (f(1,1,1)!!)elige la enésima. fen sí mismo es una recursión simple que hace una lista de su argumento, seguido por el crossover izquierdo y una llamada recursiva con crossover izquierdo y derecho.

nimi
fuente
4

Ruby, 60 57 bytes

->n{f=->x{x<2?1:f[x-1]+f[x-3]};[f[n-2|1],f[n],f[n-1&-2]]}

Los niveles están basados ​​en 1.

Basado en la siguiente fórmula:

f(-1) = 1
f(0)  = 1
f(1)  = 1
f(x)  = f(x-1) + f(x-3)

braid(x) = {
    [f(x-1), f(x), f(x-2)]  if x is even,
    [f(x-2), f(x), f(x-1)]  if x is odd
}

Gracias a Neil por 3 bytes de descuento con algunas ingeniosas travesuras bit a bit.

Pomo de la puerta
fuente
1
Operadores de bits: FTW [f[n-2|1],f[n],f[n-1&-2]].
Neil
@Neil Eso está muy bien, gracias!
Pomo de la puerta
3

Jalea , 14 bytes

Ḋ+\;Ḣ
6BÇ⁸¡Ṛ⁸¡

Pruébalo en línea!

Cómo funciona

6BÇ⁸¡Ṛ⁸¡  Main link. Argument: n (integer)

6B        Convert 6 to binary, yielding [1, 1, 0], which is the braid at index 0.
  Ç⁸¡     Call the helper link n times.
     Ṛ⁸¡  Reverse the resulting array n times.


Ḋ+\;Ḣ     Helper link. Argument: [a, b, c] (integer array)

Ḋ         Dequeue, yielding [b, c].
 +\       Cumulative sum, yielding [b, b+c].
   ;Ḣ     Concatenate with the head of [a, b, c], yielding [b, b+c, a].
Dennis
fuente
2

TI-Basic, 58 bytes

De una sola base.

Prompt N
{1,1,1
For(I,1,Ans
If fPart(I/2
Then
{Ans(2),Ans(1)+Ans(2),Ans(3
Else
{Ans(1),Ans(2)+Ans(3),Ans(2
End
End
Timtech
fuente
¿Cómo son estos 58 bytes? Cuento 114 .. me estoy perdiendo algo?
briantist
Los comandos @briantist TI-Basic tienen uno o dos bytes de longitud. Por ejemplo, Promptes un comando de 2 bytes.
JungHwan Min
@JungHwanMin genial, no se dio cuenta. Tenía la sensación de que había algo que no estaba viendo. Dejaré mi comentario para otros que no están familiarizados.
briantist
2
Para ver qué tokens son uno o dos bytes, puede consultar tibasicdev.wikidot.com/tokens
Timtech
@JungHwanMin Prompt es solo un byte. Pero gracias por explicar el concepto de tokens :)
Timtech
2

PowerShell 2+, 75 bytes

Índice basado en 1

$a=1,1,0;1..$args[0]|%{$d=(0,2)[$_%2];$a[1],$a[$d]=($a[1]+$a[$d]),$a[1]};$a

Pruébalo en línea! o Pruebe todos los casos de prueba!

El bucle siempre se ejecuta una vez, por lo que para el caso del nivel de trenza, 1simplemente comienzo con una matriz de 1,1,0modo que el resultado del algoritmo lo haga 1,1,1.

$a[1]siempre es el medio, entonces solo determino si el otro elemento index ( $d) va a ser 0o en 2función de si el nivel actual es par o impar. PowerShell admite múltiples tareas a la vez, por lo que el intercambio se vuelve tan fácil como lo $x,$y=$y,$xque básicamente es lo que estoy haciendo con los elementos de la matriz, simplemente incrustando la adición dentro de esa asignación.

briantista
fuente
2

Javascript (ES6), 55 bytes

x=>(f=y=>y<2?1:f(y-1)+f(y-3),[f(x-2|1),f(x),f(x-1&-2)])

repl.it

Basado en 1

Este es solo un puerto de la respuesta de Ruby de @ Doorknob con el increíble golf bit a bit de @ Neil.

Robert Hickman
fuente
1

Befunge, 64 bytes

110p100p1&v
01:\_v#:-1<\p00<v\+g
..g.@>_10g
\1-:!#^_\:00g+\v>10p

Pruébalo en línea!

Explicación

110p                Initialise a to 1 (at location 1;0).  
    100p            Initialise c to 1 (at location 0;0).
        1           Initialise b to 1 (on the stack, since it'll be most frequently used).
         &v         Read n from stdin and turn down.

          <         The main loop starts here, executing right to left.
        -1          Decrement n.
    _v#:            Duplicate and check if zero; if not, continue left.
   \                Swap b to the top of the stack, leaving n below it.
01:            g    Make a duplicate copy, and read a from memory (at location 1;0). 
              +     Add a to b, the result becoming the new b.
            v\      Swap the original b to the top of the stack and turn down.
            >10p    Turn around and save the original b as a (at location 1;0).
\1-                 Swap n back to the top of the stack and decrement.
   :!#^_            Duplicate and check if zero; if not continue right.
        \           Swap b to the top of the stack, leaving n below it.
         :00g       Make a duplicate copy, and read c from memory (at location 0;0).
             +      Add c to b, the result becoming the new b.
              \v    Swap the original b to the top of the stack and turn down.
            p00<    Turn around and save the original b as c (at location 0;0).
           \        Swap n back to the top of the stack.
          <         And repeat the loop from the beginning.

      >             If either of the zero tests succeed, we end up on line 3 going right.
       _            This just drops the n that is now zero, and continues to the right.
        10g         Read the final value of a (at location 1;0).
..                  Output a along with the b that was already on the stack.
  g                 Read the final value of c (the 0;0 location is implied).
   .@               Output c and exit.
James Holderness
fuente
1

Java 8, 121

Esto usa niveles basados ​​en uno:

(int l)->{int a=1,b=a,c=a,i=a;while(i<l)if(i++%2>0){b^=a;a^=b;b=(a^b)+a;}else{b^=c;c^=b;b=(c^b)+c;}return a+","+b+","+c;}

Sin golf, con programa de prueba:

import java.util.function.IntFunction;

public class GolfANumericalGrowingBraid {

  public static void main(String[] args) {
    for (int level : new int[] { 1, 2, 5, 10 }) {
      output((int l) -> {
        int a = 1, b = a, c = a, i = a;
        while (i < l) {
          if (i++ % 2 > 0) {
            b ^= a;
            a ^= b;
            b = (a ^ b) + a;
          }
          else {
            b ^= c;
            c ^= b;
            b = (c ^ b) + c;
          }
        }
        return a + "," + b + "," + c;
      } , level);
    }
  }

  private static void output(IntFunction<String> function, int level) {
    System.out.println(function.apply(level));
  }
}

Salida:

1,1,1
1,2,1
3,6,4
28,41,19


fuente
0

Lenguaje GameMaker, 113 bytes

Un índice, basado en la solución recursiva de Doorknob. No preguntes por qué no puedes inicializar una matriz primitiva de una vez en GameMaker, realmente no sé ...

Programa principal (69 bytes):

a=argument0 if a mod 2c=1b[0]=a(a-c-1)b[1]=a(a)b[2]=a(a+c-2)return b

Subprograma a(46 bytes):

a=argument0 if a<2return 1return a(a-1)+a(a-3)
Timtech
fuente
0

Perl 6 , 60 bytes

{(1 xx 3,->[\a,\b,\c]{$++%2??(a,b+c,b)!!(b,b+a,c)}...*)[$_]}

De base cero.

Directamente generó la secuencia infinita perezosa, y luego la indexa.
Probablemente hay mejores enfoques.

smls
fuente
0

Clojure, 98 bytes

#(ffirst(drop %(iterate(fn[[v[a b c d]]][[(v a)(+(v b)(v c))(v d)][b a d c]])[[1 1 0][0 1 2 1]])))

Realiza un seguimiento del valor actual vy desde qué posiciones se debe realizar la suma para la próxima ronda. Inicia un estado antes [1 1 1]de tener una indexación basada en 1.

NikoNyrh
fuente
0

C # 88 86 Bytes

f(int n,int a=1,int b=1,int c=1)=>n>1?n--%2>0?f(n,b,a+b,c):f(n,a,b+c,b):a+","+b+","+c;

Explicación

f(int n,int a=1,int b=1,int c=1)=>  //Using an expression bodied function to allow for defaults and remove return statement
    n>1?                            //recurse or return result
        n--%2>0?                    //get odd or even then decrement n
            f(n,b,a+b,c)            //odd recursion
           :f(n,a,b+c,b)            //even recursion
       :a+","+b+","+c;              //build output
JustinM - Restablece a Monica
fuente
0

Mathematica, 68 bytes

If[#<3,{1,#,1},{{#,+##2,#2}&,{#2,#+#2,#3}&}[[Mod[#,2,1]]]@@#0[#-1]]&

Definición recursiva directa de una función sin nombre, tomando un argumento entero positivo y devolviendo una lista ordenada de tres enteros.

Greg Martin
fuente