Dado un número positivo $n$ , encuentre el número de alcanos con $n$ átomos de carbono, ignorando los estereoisómeros ; o equivalentemente, el número de árboles sin etiqueta con $n$ nodos, de modo que cada nodo tenga un grado $\le 4$ .

Esta es la secuencia OEIS A000602 .

Ver también: Parafinas - Código Rosetta

Ejemplo

Para $n = 7$ , la respuesta es $9$ , porque el heptano tiene nueve isómeros :

• Heptano : $\mathrm{H_3C-CH_2-CH_2-CH_2-CH_2-CH_2-CH_3}$

• 2-metilhexano : $\mathrm{H_3C-CH(CH_3)-CH_2-CH_2-CH_2-CH_3}$

• 3-metilhexano : $\mathrm{H_3C-CH_2-CH(CH_3)-CH_2-CH_2-CH_3}$

• 2,2-dimetilpentano : $\mathrm{H_3C-C(CH_3)_2-CH_2-CH_2-CH_3}$

• 2,3-dimetilpentano : $\mathrm{H_3C-CH(CH_3)-CH(CH_3)-CH_2-CH_3}$

• 2,4-dimetilpentano : $\mathrm{H_3C-CH(CH_3)-CH_2-CH(CH_3)-CH_3}$

• 3,3-dimetilpentano : $\mathrm{H_3C-CH_2-C(CH_3)_2-CH_2-CH_3}$

• 3-etilpentano : $\mathrm{H_3C-CH_2-C(CH_2CH_3)-CH_2-CH_3}$

• 2,2,3-trimetilbutano : $\mathrm{H_3C-C(CH_3)_2-CH(CH_3)-CH_3}$

Tenga en cuenta que el 3-metilhexano y el 2,3-dimetilpentano son quirales , pero aquí ignoramos los estereoisómeros.

Casos de prueba

$n = 0$

intput	output
=============
0	1
1	1
2	1
3	1
4	2
5	3
6	5
7	9
8	18
9	35
10	75
11	159
12	355
13	802
14	1858
15	4347
16	10359
17	24894
18	60523
19	148284
20	366319

CJam ( 100 98 91 89 83 bytes)

1a{_[XX]*\_{_0a*}:E~\{E\_{ff*W%{0@+.+}*}:C~.+2f/}:D~.+C.+3f/1\+}q~:I*DE1$D.-X\+.+I=

Toma entrada de stdin, salidas a stdout. Tenga en cuenta que esto explota la licencia para no manejar la entrada 0para guardar dos bytes al incluir las definiciones de Cy D. Demostración en línea

Nota: esto es muy lento e ineficiente en cuanto a memoria. Al recortar las matrices se obtiene una versión mucho más rápida (3 bytes más). Demo en línea .

Disección

$$\begin{eqnarray} A000598(x) &=& 1 + x Z(S_3; A000598(x)) \\ A000678(x) &=& x Z(S_4; A000598(x)) \\ A000599(x) &=& Z(S_2; A000598(x) - 1) \\ A000602(x) &=& A000678(x) - A000599(x) + A000598(x^2) \\ \end{eqnarray}$$ $Z(S_n; f(x))$$S_n$$f(x)$

Manipulé esto en una descomposición ligeramente más golfista, y luego busqué las secuencias intermedias y descubrí que también están en OEIS:

$$\begin{eqnarray} A000642(x) &=& Z(S_2, A000598(x)) \\ A000631(x) &=& Z(S_2, A000642(x)) \\ A000602(x) &=& A000642(x) + x A000642(x^2) - x A000631(x) \end{eqnarray}$$

Las versiones anteriores reutilizaron el bloque C(convolucionan dos polinomios) de esta respuesta . He encontrado una mucho más corta, pero no puedo actualizar esa respuesta porque es de una pregunta encadenada.

1a            e# Starting from [1]...
{             e# Loop I times (see below) to build A000598 by f -> 1 + Z(S_3; f)
  _[XX]*      e#   Copy and double-inflate to f(x^3)
  \_          e#   Flip and copy: stack is f(x^3) f(x) f(x)
  {_0a*}:E~   e#   Assign copy-and-inflate to E and execute
              e#   Stack: f(x^3) f(x) f(x) f(x^2)
  \           e#   Flip
  {           e#   Define and execute block D, which applies f -> Z(S_2;f)
              e#     Stack: ... f
    E\_       e#     Stack: ... f(x^2) f(x) f(x)
    {         e#     Define and execute block C, which convolves two sequences
      ff*     e#       Multiply copies of the second sequence by each term of the first
      W%      e#       Reverse
      {       e#       Fold
        0@+.+ e#         Prepend a 0 to the first and pointwise sum
      }*
    }:C~      e#     Stack: ... f(x^2) f(x)^2
    .+2f/     e#     Pointwise average
  }:D~        e#   Stack: f(x^3) f(x) f(x^2) Z(S_2;f(x))
  .+C         e#   Stack: f(x^3) f(x)*(f(x^2) + Z(S_2;f(x)))
  .+3f/       e#   Add and divide by 3 to finish computing Z(S_3; f)
  1\+         e#   Prepend a 1
}
q~:I          e# Read input to I
*             e# Loop that many times
              e# Stack: I+1 terms of A000598 followed by junk
D             e# Stack: I+1 terms of A000642 followed by junk
E1$D          e# Stack: A000642 A000642(x^2) A000631
.-X\+.+       e# Stack: A000602
I=            e# Extract term I

Node.js 11.6.0 ,  229 223 221  218 bytes

Derivado de la implementación de Java sugerida en Rosetta Code .

f=(N,L=1,u=[...r=[c=[],1,...Buffer(N)]],k=u[(g=(n,B,S,i,b=B,m,d=0)=>{for(;++b<5;)for(x=c[B]=(d+r[m=n])*(d++?c[B]/d:i),u[S+=n]+=L*2<S&&x,r[S]+=b<4&&x;--m;)g(m,b,S,c[B])})(L,0,1,1),L]-=~(x=r[L++/2])*x>>1)=>L>N?k:f(N,L,u)

Pruébalo en línea!

Alquimista (1547 bytes)

_->In_NN+2b+al+g
al+g+0NN->ak
al+g+NN->ah
ah+b->ah+m+d+z+a
ah+0b->C+Z+Q
Z+j+z->Z+j+d
Z+j+0z->M+s
M+g+b->M+g+r
M+g+h->M+g+d
M+g+0b+0h+q->J+U
J+o+h->J+o+m
J+o+a->J+o+d
J+o+0h+0a->2C+an+Q
an+j+h->an+j+d
an+j+0h->aC+s
aC+g->e+am+P
am+l+b->am+l+d
am+l+0b->al+s
ak+b->ak+m+d
ak+0b->C+aj+Q
aj+j+h->aj+j+b
aj+j+0h->I+n
I+f+e->I+f+a
I+f+b->I+f+m+d+z
I+f+0e+0b->C+ai+Q
ai+j+h->ai+j+b
ai+j+0h->aB+n
aB+f->H
H+z->H+d
H+a+e->H
H+0z+0e->G+i
G+i+0b->ag
G+i+b->az+b+n
az+f+0b->Out_a
az+f+b->G+b+n
G+f->G+t
ag+e->ag
ag+0e->af+t
af+i+e->af+i+a
af+i+0e->Out_a
Q->F+s
F+g+b->F+g+y
F+g+A->F+g
F+g+0b+0A->av+o
av+o+0m->w
av+o+m->m+ae+A
ae+m->ae+b
ae+0m->u+n
u+f+b->u+f+m
u+f+e->u+f+E
u+f+A->u+f+k+c
u+f+0b+0e+0A->ad
ad+c->ad+A
ad+0c->ac
ac+y->ac+d+c
ac+0y->ab
ab+c->ab+y
ab+0c->V+l
V+l+0k->x
V+l+k->aa+t
aa+i+0e->W
aa+i+e->Y
Y+E->Y+D+c
Y+0E->X
X+c->X+E
X+0c->aa+i
W+D->W+e
W+0D->V+P
x+E->x
x+d->x
x+b->x+k
x+0E+0d+0b->aw
aw+h->aw+d
aw+0h->aE+s
aE+g->p
p+b->p+2r
p+k->p+d
p+B->p
p+q->p
p+0b+0k+0B+0q->r+q+av+U
w+h->w+d
w+y->w+r
w+C->w+B+q
w+0h+0y+0C->aD+U
aD+o->j
U->au+s
au+g+b->au+g+d
au+g+0b->v
v+d->d+aA+t
aA+i+k->R
aA+i+0k->at
at+B->at+k+c
at+0B->L
L+c->L+B
L+r->L+b
L+0c+0r->as+n
as+f+b->as+f+r
as+f+0b->R
R+0e->K
R+e+q->ar+D+c
ar+e+q->ar+c
ar+0q->aq
aq+c->aq+q
aq+0c->R
K+D->K+e
K+h->K+b
K+0D+0h->ap+P
ap+l+b->ap+l+h
ap+l+0b->v
v+0d+k->v
v+0d+r->v
v+0d+0k+0r->o
s+0d->g
s+d->d+ao+t
ao+i->ao+P
ao+l->s
P->O+c
O+b->2c+O
O+0b->N
N+c->b+N
N+0c+e->O
N+0c+0e->l
n+b->n+c
n+0b->T
T+c->ay
T+0c->e+n
ay+c->b+T
ay+0c->f
t+d->t+c
t+0d->S
S+c->ax
S+0c->e+t
ax+c->d+S
ax+0c->i

Demostración en línea .

Nota: esto es bastante lento. Si prueba con un intérprete que admite la aplicación de una regla varias veces a la vez (por ejemplo, mi , aunque asegúrese de tener la última versión que corrige un error en el analizador), puede obtener una aceleración significativa agregando dos reglas:

T+2c->b+T
S+2c->d+S

que en línea una ruta a través de las reglas existentes

T+c->ay
ay+c->b+T
S+c->ax
ax+c->d+S

Disección parcial

En un nivel alto, esto usa el mismo enfoque que mi respuesta de CJam.

El modelo de cálculo de Alchemist es esencialmente la máquina de registro Minsky . Sin embargo, Alchemist expone muy bien la equivalencia de código y datos, y al permitir muchas fichas en el lado izquierdo de una regla de producción de manera efectiva, el estado no está limitado a ser representado por un átomo: podemos usar una tupla de átomos, y esto permite subrutinas (no recursivas). Esto es muy útil para el golf. Lo único que realmente le falta son las macros y la depuración.

Para las matrices estoy usando una función de emparejamiento que se puede implementar bastante bien en RM. La matriz vacía está representada por$0$y el resultado de anteponer $x$ para armar $A$ es $(2A+1)2^x$. Hay una subrutina para emparejar: se llama a la subrutina Py antepone el valor de ea b. Hay dos subrutinas a desvincular: nunpairs ba ey b; y se tdesvincula dde ey d. Esto me permitió guardar bastantes datos aleatorios entre variables, lo cual es importante: una sola operación de "movimiento"

a, b = b, 0

se expande al menos a 17 bytes:

S+a->S+b
S+0a->T

donde Ses el estado actual y Tes el siguiente estado. Una "copia" no destructiva es aún más costosa, ya que debe hacerse como un "movimiento" desde y ahacia bun auxiliar tmp, seguido de un "movimiento" desde tmpatrás hacia a.

Ofuscación

Aliasé varias variables entre sí y eliminé unos 60 estados en el proceso de jugar golf en el programa, y ​​muchos de ellos no tenían nombres particularmente significativos de todos modos, pero para jugar golf completamente escribí un minimizador para que los nombres ahora sean completamente indescifrables. ¡Buena suerte en ingeniería inversa! Aquí está el minimizador (en CJam), que hace algunas suposiciones sobre el código, pero podría adaptarse para minimizar otros programas de Alchemist:

e# Obfuscate / minimise Alchemist program

e# Tokenise
qN%[SNS]e_*S%

e# Get token frequencies for substitution purposes, special-casing the I/O ones
_["+" "0" "2" "->" "_" N "In_n" "n" "Out_tmp2" "tmp2"]-
$e`$W%1f=

e# Empirically we want a two-char input for n and a one-char one for tmp2
["In_n" "Out_tmp2" "n" "tmp2"]\+
["In_NN" "Out_a" "NN"] "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"1/:A+ A2m*:e_"NN"a-+
1$,<

er
_s,p

Pari / GP , 118 bytes

Una traducción directa de la respuesta de CJam de Peter Taylor .

n->(s(k)=subst(a,x,x^k));(z()=(a^2+s(2))/2);a=O(1);for(i=0,n,a=1+x*(a*z()+(s(3)-a^3)/3));a=z();Pol(a+x*(s(2)-z()))\x^n

Pruébalo en línea!