Una cadena * alcalina de cadena lineal se define como una secuencia de átomos de carbono conectados por enlaces simples (alcano), dobles (alqueno) o triples (alquino) (se usan hidrógenos implícitos). Los átomos de carbono solo pueden formar 4 enlaces, por lo que Ningún átomo de carbono puede verse obligado a tener más de cuatro enlaces. Una cadena lineal * * neta puede representarse como una lista de sus enlaces carbono-carbono.

Estos son algunos ejemplos de alc * nes válidos de cadena lineal:

[]       CH4              Methane
[1]      CH3-CH3          Ethane
[2]      CH2=CH2          Ethene
[3]      CH≡CH            Ethyne
[1,1]    CH3-CH2-CH3      Propane
[1,2]    CH3-CH=CH2       Propene
[1,3]    CH3-C≡CH         Propyne
[2,1]    CH2=CH-CH3       Propene
[2,2]    CH2=C=CH2        Allene (Propadiene)
[3,1]    CH≡C-CH3         Propyne 
[1,1,1]  CH3-CH2-CH2-CH3  Butane
...

Si bien estos no lo son, ya que al menos un átomo de carbono tendría más de 4 enlaces:

[2,3]
[3,2]
[3,3]
...

Su tarea es crear un programa / función que, dado un número entero positivo n, produzca / devuelva el número de alcanos * de cadena lineal válidos de nlongitud exacta de átomos de carbono. Este es OEIS A077998 .

Especificaciones / Aclaraciones

• Debe manejar 1correctamente volviendo 1.
• Alk * nes gusta [1,2]y [2,1]se consideran distintos.
• La salida es la longitud de una lista de todos los posibles * alnos de una longitud dada.
• Usted no tiene que manejar 0 correctamente.

Casos de prueba:

1 => 1
2 => 3
3 => 6
4 => 14

Este es el código de golf, por lo que gana el conteo de bytes más bajo .

Oasis , 9 7 bytes

xcd-+3V

Pruébalo en línea!

Explicación

Esto usa la relación de recurrencia en OEIS :

a (n) = 2 * a (n-1) + a (n-2) - a (n-3)

x    Multiply a(n-1) by 2: gives 2*a(n-1)
c    Push a(n-2)
d    Push a(n-3)
-    Subtract: gives a(n-2) - a(n-3)
+    Add: gives 2*a(n-1) + a(n-2) - a(n-3)
3    Push 3: initial value for a(n-1)
V    Push 1, 1: initial values for a(n-2), a(n-3)

MATL , 10 bytes

7K5vBiY^1)

Pruébalo en línea!

Explicación

Esto usa la caracterización encontrada en OEIS

a (n) es la entrada superior izquierda de la enésima potencia de la matriz 3 X 3 [1, 1, 1; 1, 0, 0; 1, 0, 1]

7    % Push 7
K    % Push 4
5    % Push 5
v    % Concatenate all numbers into a column vector: [7; 4; 5]
B    % Convert to binary: gives 3×3 matrix [1, 1, 1; 1, 0, 0; 1, 0, 1]
i    % Input n
Y^   % Matrix power
1)   % Take the first element of the resulting matrix, i.e. its upper-left corner.
     % Implicitly display

Oasis , 9 8 bytes

Salvó un byte gracias a Adnan

xc+d-63T

Pruébalo en línea!

Explicación

a(0) = 0
a(1) = 1
a(2) = 3
a(3) = 6

a(n) = xc+d-

x         # calculate 2*a(n-1)
 c        # calculate a(n-2)
  +       # add: 2*a(n-1) + a(n-2)
   d      # calculate a(n-3)
    -     # subtract: 2*a(n-1) + a(n-2) - a(n-3)

Jalea, 10 bytes

745DBæ*µḢḢ

Pruébalo en línea!

Utiliza el algoritmo de Luis Mendo .

Explicación

745DBæ*µḢḢ    Main link. Argument: n
745D          Get the digits of 745
    B         Convert each to binary
     æ*       Matrix power
        ḢḢ    First element of first row

Jalea, 15 bytes

3Rṗ’µ+2\<5PµÐfL

Pruébalo en línea!

Utiliza fuerza bruta.

Explicación

3Rṗ’µ+2\<5PµÐfL    Main link. Argument: n
3R                 Start with [1, 2, 3]
   ’               Take the (n-1)'th
  ṗ                Cartesian power
            Ðf     Filter on:
     +2\             Sums of overlapping pairs
        <5           1 for sums < 5, 0 otherwise
          P          Product: 1 if all pairs < 5
              L    Length

MATL , 14 bytes

q3:Z^TTZ+!5<As

Pruébalo en línea!

Explicación

Esto genera el poder cartesiano de [1 2 3]"elevado" al número de átomos menos 1, y luego utiliza la convolución para verificar que no haya dos números contiguos en cada tupla cartesiana suma más que 4.

q    % Take number of atoms n implicitly
3:   % Push [1 2 3]
Z^   % Cartesian power. Gives a matrix with each (n-1)-tuple on a row
TT   % Push [1 1]
Z+   % 2D convolution. For each tuple this gives the sum of contiguous numbers
5<   % For each entry, gives true if less than 5
!    % Transpose
A    % True if all elements of each column are true. Gives a row vector
s    % Sum of true results. Implicitly display

Mathematica, 48 bytes

MatrixPower[{{1,1,1},{1,0,0},{1,0,1}},#][[1,1]]&

Como señaló Luis Mendo , este es A006356 en el OEIS. Aquí están mis intentos originales:

Count[Length@Split[#,+##<5&]&/@Tuples[{1,2,3},#-1],0|1]&

Para una entrada n, Tuples[{1,2,3},n-1]es la lista de todas las (n-1)tuplas de elementos que {1,2,3}representan todas las secuencias posibles de enlaces simples, dobles o triples para nátomos de carbono. +##<5&es una función pura que devuelve si la suma de sus argumentos es menor que 5, por lo que Split[#,+##<5&]&divide una lista en sublistas que consisten en elementos consecutivos cuyas sumas por pares son menores que 5. Describir una alca * ne válida es equivalente a que esta lista tenga longitud 0(en el caso donde n=1) o 1, así que solo Countel número de (n-1)tuplas donde la longitud de esa lista coincide0|1 .

Count[Fold[If[+##>4,4,#2]&]/@Tuples[{1,2,3},#-1],Except@4]&

If[+##>4,4,#2]&devuelve 4si la suma de sus argumentos es mayor que 4y devuelve el segundo argumento de lo contrario. Fold[If[+##>4,4,#2]&]hace una izquierda Foldde su entrada con esta función. Así que aquí tengo Countel número de (n-1)tuplas a las que no se aplica este operador 4. El caso donde n=1está cubierto ya que Foldpermanece sin evaluar cuando su segundo argumento es la lista vacía {}.

Python, 51 bytes

f=lambda n:n<4and(n*n+n)/2or 2*f(n-1)+f(n-2)-f(n-3)

Esta es una implementación directa de la relación de recurrencia. Gracias a Tim Pederick por 3 bytes. El resultado es un flotante en Python 3 y un número entero en Python 2.

Pruébalo en línea!

Pyth - 16 bytes

Utiliza fuerza bruta.

lf.AgL4+VTtT^S3t

Test Suite .

Ruby, 62 bytes

->n{c=0
(10**n/10).times{|i|"#{i}#{i*11}"=~/[3-9]/||c+=1}
c}

Enfoque de fuerza bruta base 10 horriblemente ineficiente. Podría mejorarse a la base 5 para bytes adicionales.

Los números se generan donde cada dígito representa un enlace (n-1 dígitos) 0representa un orden de enlace de 1,2 representa un orden de enlace de 3. Los dígitos sobre 2 no son válidos.

Multiplicamos esto por 11 para sumar un par de dígitos adyacentes. De nuevo, los dígitos sobre 3 no son válidos.

Combinamos los dos números en una cadena y realizamos una expresión regular para buscar dígitos no válidos. Si no se encuentra ninguno, incrementamos el contador.

en programa de prueba

f=->n{c=0
(10**n/10).times{|i|"#{i}#{i*11}"=~/[3-9]/||c+=1}
c}

p f[gets.to_i]

Ruby, 51 bytes

->n{a=[1,1,3]
n.times{a<<2*a[-1]+a[-2]-a[-3]}
a[n]}

Basado en la relación de recurrencia según OEIS A006356.

Comienza con una matriz para los elementos 0,1 y 2 de la secuencia que son 1 (según lo calculado por mí, para que funcione), 1 y 3 respectivamente.

Iterativamente agrega nmás elementos a la secuencia, luego devuelve el elementon . Siempre calcula 2 elementos más de lo que realmente necesita, pero sigue siendo el tiempo lineal, que es mucho más eficiente que mi respuesta anterior.

en programa de prueba

f=->n{a=[1,1,3]
n.times{a<<2*a[-1]+a[-2]-a[-3]}
a[n]}

p f[gets.to_i]

Mathematica, 42 40 bytes

El recuento de bytes supone una codificación compatible de un solo byte como CP-1252 (el valor predeterminado en las instalaciones de Windows).

±0=±1=1;±2=3;±n_:=±(n-1)2+±(n-2)-±(n-3);

Esto simplemente implementa la recurrencia dada en OEIS como operador unario.

CJam (19 bytes)

{2,{__-2=+1b+}@*W=}

Conjunto de pruebas en línea . Este es un bloque anónimo (función) que toma un elemento en la pila y deja uno en la pila. Tenga en cuenta que el conjunto de pruebas incluyea(0) = 1 .

La recurrencia utilizada se basa en la observación de la secuencia OEIS relacionada A006356 :

Es igual a la transformación INVERTIR de (1, 2, 1, 1, 1, ...) equivalente a a (n) = a (n-1) + 2 * a (n-2) + a (n-3) + a (n-4) + ... + 1. a (6) = 70 = (31 + 2 * 14 + 6 + 3 + 1 + 1). - Gary W. Adamson, 27 de abril de 2009

pero con el desplazamiento apropiado, lo que elimina la necesidad de la final + 1como ahora está cubierto por a(0).

Disección

{         e# Define a block
  2,      e#   Take starting sequence [0 1] (beginning at index -1 for golfiness)
  {       e#   Loop...
    _     e#     Copy sequence so far
    _-2=+ e#     Append an extra copy of a(n-2)
    1b    e#     Sum
    +     e#     Append
  }@*     e#   ...n times
  W=      e#   Take the final value from the sequence
}

Brain-Flak, 56 bytes

Utiliza el algoritmo detallado en el primer comentario en la página OEIS.

Pruébalo en línea!

({}[()]<(((())))>){({}[()]<{({}<>({}))<>}<>>)}{}({}<>{})

Explicación

La secuencia se puede definir como tal:

For u(k), v(k), and w(k) such that
u(1) = v(1) = w(1) = 1
u(k+1) = u(k) + v(k) + w(k)
v(k+1) = u(k) + v(k)
w(k+1) = u(k)
u(k) is the number of straight-chain alk*nes with length k

El programa comienza en 1y aplica repetidamente esta recurrencia para calcularu(k)

Código anotado (anotación real por venir)

# Setup: decrement the input by one and push three 1's to the stack under it
({}[()]<(((())))>)

# Calculation:
{                          }           # While the input is not zero (main loop)
 ({}[()]                  )            # Pop the counter decrement it by one and push it
        <                >             # Before the counter gets pushed back to the stack...
         {            }                # Loop while the top of the stack is not zero (subloop)
          (        )                   # Push...
           {}                          # The top of the stack (popped)...
             <>                        # to the other stack...
               ({})                    # plus the top of the other stack (peeked)
                    <>                 # Switch back to the first stack.
                       <>              # Switch to the other stack
                            {}         # Pop the input (now zero)
                              (      ) # Push...
                               {}      # The top of the stack (u(k))...
                                 <>    # to the other stack...
                                   {}  # plus the top of the other stack (zero).

Visualización de las pilas.

En una iteración del bucle principal, esto es lo que sucede (tenga en cuenta que los ceros pueden o no estar presentes, pero no importa de ninguna manera):

Start of main loop iteration/subloop first iteration:
A    B

u
v
w
0    0
^

After first subloop iteration:
A    B

v
w    u
0    0
^

After second subloop iteration:
A    B

    u+v
w    u
0    0
^

After third subloop iteration (top of stack is zero so subloop terminates):

A    B

   u+v+w
    u+v
     u
0    0
^

End of main loop iteration:
A    B

   u+v+w
    u+v
     u
0    0
     ^

El estado de las pilas es ahora el mismo que era al comienzo del bucle excepto que la pila actual ahora cuenta con los siguientes valores para u, vy wen él.

Perl 6, 48

{my @a=1,0,0;@a=reverse [\+] @a for 1..$_;@a[0]}

Originalmente

sub f {$_>2??2*f($_-1)+f($_-2)-f($_-3)!!(1,1,3)[$_]}

pero olvidé que necesitaba el sub fpara que triunfe la solución iterativa.

Dyalog APL, 30 bytes

{⍵<3:⍵⌷1 3⋄+/∧/¨4≥2+/¨,⍳1↓⍵/3}

Utiliza fuerza bruta. Explicación (mi mejor intento en uno, al menos):

⍵<3:⍵⌷1 3 - if ⍵ (function arg) is 1 (case 1) or 2 (case 2), return 1 (case 1) or 3 (case 2)
⋄ - separate statements
⍵/3 - otherwise, 3 repeated ⍵ times
1↓ - without the first element
⍳ - the matrix of possible indices of a matrix of that size
,  - ravel, return a list of all the elements of the matrix
2+/¨ - sum of each contiguous pair on each element
4≥ - tests whether each element is less than or equal to 4
∧/¨ - all elements are true, applied to each item.
+/ - Sum.

Dyalog APL, 29 bytes

{⍵<4:⍵⌷1 3 6⋄+/2 1 ¯1×∇¨⍵-⍳3}

Funciona utilizando la definición recursiva de la secuencia de enteros OEIS A006356.

Python con Numpy, 62 bytes

Tuve que probarlo, pero parece Python puro y la recursión es más corta que numpy y el cálculo explícito basado en la matriz en la página OEIS.

from numpy import*
lambda n:(mat('1 1 1;1 0 0;1 0 1')**n)[0,0]

R, 61 58 55 51 50 bytes

Toma datos de stdin, usa exponenciación de matrices para determinar el resultado exacto.

el(expm::`%^%`(matrix(!-3:5%in%2^(0:2),3),scan()))

Si prefiere una solución recursiva, aquí hay una implementación sencilla de la relación de recurrencia enumerada en OEIS, para 55 bytes .

f=function(n)`if`(n<4,(n*n+n)/2,2*f(n-1)+f(n-2)-f(n-3))

Excel, 123 bytes

Implementa la fórmula de OEIS:

=4*(SIN(4*PI()/7)^2*(1+2*COS(2*PI()/7))^A1+SIN(8*PI()/7)^2*(1+2*COS(4*PI()/7))^A1+SIN(2*PI()/7)^2*(1+2*COS(8*PI()/7))^A1)/7

Como siempre, ingrese la A1fórmula en cualquier otra celda.

Desenterró viejas identidades de Trig para ver si podría ser útil. Ahora me duele la cabeza.

Lithp , 79 bytes

#N:(((if(< N 4)((/(+ N(* N N))2))((-(+(* 2(f(- N 1)))(f(- N 2)))(f(- N 3)))))))

Implementa la secuencia recursiva de enteros enumerada en OEIS.

Implementación legible y conjunto de pruebas.

% alkaline.lithp
% run with: ./run.js alkaline.lithp
(
    (def f #N : ((
        (if (< N 4) (
            (/ (+ N (* N N)) 2)
        ) (else (
            (- (+ (* 2 (f (- N 1))) (f (- N 2))) (f (- N 3)))
        )))
    )))

    % Test cases 1 to 4
    (import lists)
    (each (seq 1 4) #I :: ((print (f I))))
)