Dado um número positivo $n$ , encontre o número de alcanos com $n$ átomos de carbono, ignorando os estereoisômeros ; ou equivalente, o número de árvores não rotuladas com $n$ nós, de modo que cada nó tenha grau $\le 4$ .

Esta é a sequência OEIS A000602 .

Veja também: Parafinas - Código Rosetta

Exemplo

Para $n = 7$ , a resposta é $9$ , porque o heptano possui nove isômeros :

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

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

• 3-metil-hexano : $\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}$

• $\mathrm{H_3C-CH_2-C(CH_3)_2-CH_2-CH_3}$

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

• $\mathrm{H_3C-C(CH_3)_2-CH(CH_3)-CH_3}$

Observe que o 3-metilhexano e o 2,3-dimetilpentano são quirais , mas aqui ignoramos os estereoisômeros.

Casos de teste

$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=

Pega a entrada de stdin, produz para stdout. Observe que isso explora a licença para não manipular a entrada 0e salvar dois bytes, incorporando as definições de Ce D.Demonstração online

Nota: isso é muito lento e ineficiente na memória. Ao aparar matrizes, é obtida uma versão muito mais rápida (mais 3 bytes). Demonstração online .

Dissecação

$$\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)$.

Eu manipulei isso em uma decomposição um pouco mais golfista e, em seguida, procurei as seqüências intermediárias e descobri que elas também estão no 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}$$

As versões anteriores reutilizaram o bloco C(envolvem dois polinômios) desta resposta . Encontrei uma muito mais curta, mas não consigo atualizar essa resposta porque é de uma pergunta em cadeia.

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 da implementação Java sugerida no Código Rosetta .

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)

Experimente online!

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

Demonstração online .

Nota: isso é bastante lento. Se estiver testando com um intérprete que suporte a aplicação de uma regra várias vezes ao mesmo tempo (por exemplo, a minha - embora você tenha a versão mais recente que corrige um bug no analisador), é possível obter uma aceleração significativa adicionando duas regras:

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

que alinham uma rota através das regras existentes

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

Dissecção parcial

Em um nível alto, isso usa a mesma abordagem da minha resposta CJam.

O modelo de computação do Alchemist é essencialmente a máquina de registro de Minsky . No entanto, o Alchemist expõe muito bem a equivalência de código e dados e, ao permitir que muitos tokens no lado esquerdo de uma regra de produção efetivamente, o estado não é obrigado a ser representado por um átomo: podemos usar uma tupla de átomos, e isso permite sub-rotinas (não recursivas). Isso é muito útil para o golfe. As únicas coisas que realmente faltam são macros e depuração.

Para matrizes, estou usando uma função de emparelhamento que pode ser implementada com bastante facilidade nos RMs. A matriz vazia é representada por$0$e o resultado de anexar $x$ ordenar $A$ é $(2A+1)2^x$. Há uma sub-rotina para emparelhar: a sub-rotina é chamada Pe precede o valor de epara b. Existem dois sub-rotinas para desemparelhar: nunpairs bde ee b; e tdesemparelha dpara ee d. Isso me permitiu salvar um pouco de dados aleatórios entre variáveis, o que é importante: uma única operação de "movimentação"

a, b = b, 0

expande para pelo menos 17 bytes:

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

onde Sé o estado atual e Té o próximo estado. Uma "cópia" não destrutiva é ainda mais cara, porque deve ser feita como um "movimento" de apara be um auxiliar tmp, seguida de um "movimento" de tmpvolta para a.

Ofuscação

Criei um alias para várias variáveis ​​e eliminei cerca de 60 estados no processo de jogar golfe no programa, e muitos deles não tinham nomes particularmente significativos, mas para jogá-lo completamente, escrevi um minimizador para que os nomes agora sejam completamente indecifráveis. Boa sorte engenharia reversa isso! Aqui está o minimizador (no CJam), que faz algumas suposições sobre o código, mas pode ser adaptado para minimizar outros programas Alquimistas:

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

A tradução direta do Peter Taylor 's resposta CJam .

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

Experimente online!