16
\$\begingroup\$

Given a positive number \$n\$, find the number of alkanes with \$n\$ carbon atoms, ignoring stereoisomers; or equivalently, the number of unlabeled trees with \$n\$ nodes, such that every node has degree \$\le 4\$.

This is OEIS sequence A000602.

See also: Paraffins - Rosetta Code

Example

For \$n = 7\$, the answer is \$9\$, because heptane has nine isomers:

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

Heptane

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

2-Methylhexane

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

3-Methylhexane

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

2,2-Dimethylpentane

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

2,3-Dimethylpentane

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

2,4-Dimethylpentane

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

3,3-Dimethylpentane

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

3-Ethylpentane

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

2,2,3-Trimethylbutane

Note that 3-methylhexane and 2,3-dimethylpentane are chiral, but we ignore stereoisomers here.

Test cases

You don't need to handle the case \$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
\$\endgroup\$
6
  • 3
    \$\begingroup\$ I'd be impressed if someone manages to write a solution with Alchemist! \$\endgroup\$ Jan 11, 2019 at 10:23
  • \$\begingroup\$ @PeterTaylor Well It can output each time a digit \$\endgroup\$
    – l4m2
    Jan 11, 2019 at 17:17
  • \$\begingroup\$ @BMO Also Alchemist looks turing complete if big number support \$\endgroup\$
    – l4m2
    Jan 11, 2019 at 17:20
  • \$\begingroup\$ @l4m2: I used it before for a sequence challenge and some number challenges, you can also use unary output which is most likely easier. And yes, it is most likely TC (uses bignums), I haven't formally proved it though. \$\endgroup\$ Jan 11, 2019 at 17:27
  • \$\begingroup\$ @BMO It looks to just able to simulate CM \$\endgroup\$
    – l4m2
    Jan 11, 2019 at 17:29

4 Answers 4

11
+100
\$\begingroup\$

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=

Takes input from stdin, outputs to stdout. Note that this exploits the licence to not handle input 0 to save two bytes by inlining the definitions of C and D. Online demo

NB this is very slow and memory-inefficient. By trimming arrays a much faster version is obtained (3 bytes more). Online demo.

Dissection

OEIS gives (modulo an indexing error) the generating function decomposition $$\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}$$ where \$Z(S_n; f(x))\$ denotes the cycle index of the symmetric group \$S_n\$ applied to the function \$f(x)\$.

I manipulated this into a slightly golfier decomposition, and then looked up the intermediate sequences and discovered that they're also in 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}$$

Earlier versions reused block C (convolve two polynomials) from this answer. I've found a much shorter one, but I can't update that answer because it's from a chaining question.

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
\$\endgroup\$
7
+200
\$\begingroup\$

Alchemist (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

Online demo.

Note: this is quite slow. If testing with an interpreter which supports applying a rule multiple times at once (e.g. my one - although make sure you have the latest version which fixes a bug in the parser) then you can get a significant speed-up by adding two rules:

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

which inline a route through the existing rules

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

Partial dissection

At a high level, this uses the same approach as my CJam answer.

The computation model of Alchemist is essentially the Minsky register machine. However, Alchemist very nicely exposes the equivalence of code and data, and by allowing many tokens on the left hand side of a production rule effectively the state is not constrained to be represented by one atom: we can use a tuple of atoms, and this allows (non-recursive) subroutines. This is very useful for golf. The only things it's really lacking are macros and debuggability.

For arrays I'm using a pairing function which can be implemented quite golfily in RMs. The empty array is represented by \$0\$, and the result of prepending \$x\$ to array \$A\$ is \$(2A+1)2^x\$. There is one subroutine to pair: the subroutine is called P and it prepends the value of e to b. There are two subroutines to unpair: n unpairs b to e and b; and t unpairs d to e and d. This allowed me to save quite a bit of shuffling data between variables, which is important: a single "move" operation

a, b = b, 0

expands to at least 17 bytes:

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

where S is the current state and T is the next state. A non-destructive "copy" is even more expensive, because it has to be done as a "move" from a to b and an auxiliary tmp, followed by a "move" from tmp back to a.

Obfuscation

I aliased various variables to each other and eliminated about 60 states in the process of golfing the program, and many of them didn't have particularly meaningful names anyway, but to fully golf it I wrote an minimiser so the names are now thoroughly indecipherable. Good luck reverse engineering it! Here is the minimiser (in CJam), which makes a few assumptions about the code but could be adapted to minimise other Alchemist programs:

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
\$\endgroup\$
8
  • \$\begingroup\$ Wait... does that interpreter work? AFAICT... you pick a random rule, then figure out how many times that can be applied. Does that even work correctly? \$\endgroup\$
    – ASCII-only
    Feb 7, 2019 at 22:32
  • \$\begingroup\$ Hmm. How would you improve debuggability \$\endgroup\$
    – ASCII-only
    Feb 7, 2019 at 22:33
  • \$\begingroup\$ @ASCII-only, that would work but it's not actually what it does. It first picks a rule which is applicable and then works out how many times it can be applied. Debuggability is tricky. One of my ideas for a dissertation project back in the day was a GUI RM editor with backwards debugger. \$\endgroup\$ Feb 7, 2019 at 22:52
  • \$\begingroup\$ but... rule execution order affects program order does it not \$\endgroup\$
    – ASCII-only
    Feb 8, 2019 at 0:52
  • \$\begingroup\$ @ASCII-only, yes. That's why there are so many variables. Only about 16 of them are data: the rest are state. I've used non-determinism to golf by effectively parallelising independent "move" operations. \$\endgroup\$ Feb 8, 2019 at 7:48
5
\$\begingroup\$

Node.js 11.6.0,  229 223 221  218 bytes

Derived from the Java implementation suggested on 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)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Pari/GP, 118 bytes

A direct translation of Peter Taylor's CJam answer.

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

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.