This is much like my earlier challenge, except, this time, order doesn't matter.

A straight-chain alk*ne is defined as a sequence of carbon atoms connected by single (alkane), double (alkene), or triple bonds (alkyne), (implicit hydrogens are used.) Carbon atoms can only form 4 bonds, so no carbon atom may be forced to have more than four bonds. A straight-chain alk*ne can be represented as a list of its carbon-carbon bonds.

These are some examples of valid (not necessarily distinct) straight-chain alk*nes:

[]       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
...

While these are not, as at least one carbon atom would have more than 4 bonds:

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

Two straight-chain alk*nes, p and q are considered equivalent if p is q reversed, or p is q.

[1] = [1]
[1,2] = [2,1]
[1,3] = [3,1]
[1,1,2] = [2,1,1]
[1,2,2] = [2,2,1]

Your task is to create a program/function that, given a positive integer n, outputs/returns the number of valid straight-chain alk*nes of exactly n carbon atoms in length.

Specifications/Clarifications

  • You must handle 1 correctly by returning 1.
  • Alk*nes like [1,2] and [2,1] are NOT considered distinct.
  • Output is the length of a list of all the possible alk*nes of a given length.
  • You do not have to handle 0 correctly.

Test Cases:

1 => 1
2 => 3
3 => 4
4 => 10
5 => 18
6 => 42

This is code golf, so the lowest byte count wins!

  • Are we supposed to guess what the correct number is? If not, can you specify how we figure it out? Specifically: Is every sequence (of the given length) that doesn't contain two adjacent numbers that sum to more than 4 valid? If so, can you edit that info in the question post? – msh210 Dec 18 '16 at 21:32
  • 4
    Too much similar to Number of Straight-Chain Alk*nes of given length – JungHwan Min Dec 18 '16 at 21:32
  • That help at all? – Zacharý Dec 18 '16 at 21:40
  • 5
    @JungHwanMin Why do you think so? I'm not seeing an obvious way to reuse any of the non-brute force answers from that challenge. – Martin Ender Dec 18 '16 at 22:19
  • @MartinEnder The answer is simply (# of straight-chain alk*nes)/2 + (# of symmetrical straight-chain alk*nes)/2 – JungHwan Min Dec 18 '16 at 23:30
up vote 1 down vote accepted

JavaScript (ES6), 107 bytes

A=n=>n>9?2*A(n-1)+3*A(n-2)+3*A(n-7)+A(n-8)-5*A(n-3)-A(n-4)-2*A(n-6)-A(n-9):[0,1,3,4,10,18,42,84,192,409][n]

Recursive solution, using the recurrence relation that was pointed out in the comments of the question. Execution time rises much quicker than the input (complexity of O(9^N) if I'm not mistaken), so be careful with values higher than 20.

  • Winner by default. – Zacharý Apr 16 '17 at 19:42

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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