Nombre d' alcanes

16

Étant donné un nombre positif , trouver le nombre d' alcanes avec n atomes de carbone, en ignorant les stéréoisomères ; ou de manière équivalente, le nombre d'arbres sans étiquette avec n nœuds, de sorte que chaque nœud a un degré 4 .nnn4

Il s'agit de la séquence OEIS A000602 .

Voir aussi: Paraffines - Rosetta Code

Exemple

Pour n=sept , la réponse est 9 , car l' heptane a neuf isomères :

  • Heptane : H3C-CH2-CH2-CH2-CH2-CH2-CH3

Heptane

  • 2-méthylhexane : H3C-CH(CH3)-CH2-CH2-CH2-CH3

2-méthylhexane

  • 3-méthylhexane : H3C-CH2-CH(CH3)-CH2-CH2-CH3

3-méthylhexane

  • 2,2-diméthylpentane : H3C-C(CH3)2-CH2-CH2-CH3

2,2-diméthylpentane

  • 2,3-diméthylpentane : H3C-CH(CH3)-CH(CH3)-CH2-CH3

2,3-diméthylpentane

  • 2,4-diméthylpentane : H3C-CH(CH3)-CH2-CH(CH3)-CH3

2,4-diméthylpentane

  • 3,3-diméthylpentane : H3C-CH2-C(CH3)2-CH2-CH3

3,3-diméthylpentane

  • 3-éthylpentane : H3C-CH2-C(CH2CH3)-CH2-CH3

3-éthylpentane

  • H3C-C(CH3)2-CH(CH3)-CH3

2,2,3-triméthylbutane

Notez que le 3-méthylhexane et le 2,3-diméthylpentane sont chiraux , mais nous ignorons les stéréoisomères ici.

Cas de test

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
alephalpha
la source
3
Je serais impressionné si quelqu'un réussit à écrire une solution avec Alchemist !
ბიმო
@PeterTaylor Well Il peut sortir à chaque fois un chiffre
l4m2
@ l4m2: Je l'ai utilisé auparavant pour un défi de séquence et certains défis de nombre , vous pouvez également utiliser une sortie unaire qui est très probablement plus facile. Et oui, il est très probable que TC ( utilise des bignums ), je ne l'ai cependant pas formellement prouvé.
ბიმო
@BMO Il semble juste capable de simuler CM
l4m2

Réponses:

11

CJam ( 100 98 91 89 83 octets)

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

Prend l'entrée de stdin, les sorties vers stdout. Notez que cela exploite la licence pour ne pas gérer les entrées 0pour économiser deux octets en insérant les définitions de Cet D. Démo en ligne

NB c'est très lent et peu efficace en mémoire. En réduisant les tableaux, une version beaucoup plus rapide est obtenue (3 octets de plus). Démo en ligne .

Dissection

OEIS donne (modulo une erreur d'indexation) la décomposition de la fonction génératrice

UNE000598(X)=1+XZ(S3;UNE000598(X))UNE000678(X)=XZ(S4;UNE000598(X))UNE000599(X)=Z(S2;UNE000598(X)-1)UNE000602(X)=UNE000678(X)-UNE000599(X)+UNE000598(X2)
Z(Sn;F(X)) désigne l'indice de cycle du groupe symétrique Sn appliqué à la fonction F(X).

J'ai manipulé cela dans une décomposition légèrement golfeur, puis j'ai recherché les séquences intermédiaires et découvert qu'elles se trouvent également dans OEIS:

UNE000642(X)=Z(S2,UNE000598(X))UNE000631(X)=Z(S2,UNE000642(X))UNE000602(X)=UNE000642(X)+XUNE000642(X2)-XUNE000631(X)

Les versions antérieures réutilisaient le bloc C(convolve deux polynômes) de cette réponse . J'en ai trouvé une beaucoup plus courte, mais je ne peux pas mettre à jour cette réponse car elle provient d'une question de chaînage.

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
Peter Taylor
la source
5

Node.js 11.6.0 ,  229 223 221  218 octets

Dérivé de l'implémentation Java suggérée sur 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)

Essayez-le en ligne!

Arnauld
la source
5

Alchimiste (1547 octets)

_->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

Démo en ligne .

Remarque: c'est assez lent. Si vous testez avec un interpréteur qui prend en charge l'application d'une règle plusieurs fois à la fois (par exemple la mienne - bien que assurez-vous que vous disposez de la dernière version qui corrige un bogue dans l'analyseur), vous pouvez obtenir une accélération significative en ajoutant deux règles:

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

qui alignent un itinéraire à travers les règles existantes

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

Dissection partielle

À un niveau élevé, cela utilise la même approche que ma réponse CJam.

Le modèle de calcul d'Alchemist est essentiellement la machine à registres Minsky . Cependant, Alchemist expose très bien l'équivalence du code et des données, et en autorisant de nombreux jetons sur le côté gauche d'une règle de production, l'état n'est pas contraint d'être représenté par un atome: nous pouvons utiliser un tuple d'atomes, et cela autorise les sous-programmes (non récursifs). Ceci est très utile pour le golf. Les seules choses qui manquent vraiment sont les macros et le débogage.

Pour les tableaux, j'utilise une fonction de couplage qui peut être implémentée de manière assez golfique dans les RM. Le tableau vide est représenté par0et le résultat du pré-paiement X mettre en réseau UNE est (2UNE+1)2X. Il existe un sous-programme à associer: le sous-programme est appelé Pet il ajoute la valeur de eà b. Il existe deux sous-routines à ndissocier : les dissociations bde eet b; et tdissocie dvers eet d. Cela m'a permis d'économiser pas mal de données mélangées entre les variables, ce qui est important: une seule opération de "déplacement"

a, b = b, 0

s'étend à au moins 17 octets:

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

Sest l'état actuel et Tl'état suivant. Une "copie" non destructive est encore plus coûteuse, car elle doit être effectuée comme un "déplacement" de avers bet un auxiliaire tmp, suivi d'un "déplacement" de tmpretour vers a.

Obfuscation

Je me suis aliasé diverses variables et j'ai éliminé environ 60 états dans le processus de golf du programme, et beaucoup d'entre eux n'avaient pas de noms particulièrement significatifs de toute façon, mais pour le jouer pleinement, j'ai écrit un minimiseur afin que les noms soient maintenant complètement indéchiffrables. Bonne chance en ingénierie inverse! Voici le minimiseur (dans CJam), qui fait quelques hypothèses sur le code mais pourrait être adapté pour minimiser d'autres programmes 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
Peter Taylor
la source
Attendez ... est-ce que cet interprète fonctionne? AFAICT ... vous choisissez une règle aléatoire, puis déterminez combien de fois cela peut être appliqué. Est-ce que cela fonctionne même correctement?
ASCII uniquement le
Hmm. Comment amélioreriez-vous le débogage
ASCII uniquement le
@ ASCII uniquement, cela fonctionnerait mais ce n'est pas vraiment ce qu'il fait. Il choisit d'abord une règle qui est applicable, puis détermine combien de fois il peut être appliqué. Le débogage est délicat. Une de mes idées pour un projet de thèse à l'époque était un éditeur GUI RM avec un débogueur à l'envers.
Peter Taylor
mais ... l'ordre d'exécution des règles affecte l'ordre des programmes, n'est-ce pas
ASCII uniquement
@ ASCII uniquement, oui. C'est pourquoi il y a tant de variables. Seulement environ 16 d'entre eux sont des données: les autres sont des états. J'ai utilisé le non-déterminisme pour jouer au golf en parallélisant efficacement les opérations de "mouvement" indépendantes.
Peter Taylor