6
\$\begingroup\$

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!

\$\endgroup\$
12
  • \$\begingroup\$ 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? \$\endgroup\$
    – msh210
    Commented Dec 18, 2016 at 21:32
  • 4
    \$\begingroup\$ Too much similar to Number of Straight-Chain Alk*nes of given length \$\endgroup\$ Commented Dec 18, 2016 at 21:32
  • \$\begingroup\$ That help at all? \$\endgroup\$
    – Adalynn
    Commented Dec 18, 2016 at 21:40
  • 5
    \$\begingroup\$ @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. \$\endgroup\$ Commented Dec 18, 2016 at 22:19
  • \$\begingroup\$ @MartinEnder The answer is simply (# of straight-chain alk*nes)/2 + (# of symmetrical straight-chain alk*nes)/2 \$\endgroup\$ Commented Dec 18, 2016 at 23:30

2 Answers 2

2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Winner by default. \$\endgroup\$
    – Adalynn
    Commented Apr 16, 2017 at 19:42
1
\$\begingroup\$

MMIX, 108 92 bytes (27 23 instrs)

Works mod \$2^{63}\$, because it uses the two-part recurrence instead of the one-part, due to the two-part recurrence being much easier to compute.

(jxd)

00000000: e3010001 e3020001 e3030003 e3040001  ẉ¢¡¢ẉ£¡¢ẉ¤¡¤ẉ¥¡¢
00000010: e3050003 e3060006 67050002 67060005  ẉ¦¡¤ẉ©¡©g¦¡£g©¡¦
00000020: 27000001 28ff0302 26ffff01 c1010200  '¡¡¢(”¤£&””¢Ḋ¢£¡
00000030: c1020300 c103ff00 28ff0605 26ffff04  Ḋ£¤¡Ḋ¤”¡(”©¦&””¥
00000040: 66040005 66050006 660600ff 5b00fff5  f¥¡¦f¦¡©f©¡”[¡”ṫ
00000050: 22000104 3f000001 f8010000           "¡¢¥?¡¡¢ẏ¢¡¡

Disassembly and explanation:

alkns   SET   $1,1          // a(0)
        SET   $2,1          // a(1)
        SET   $3,3          // a(2)
        SET   $4,1          // b(0)/b(1)
        SET   $5,3          // b(2)
        SET   $6,6          // b(4)
        CSOD  $5,$0,2       // b(3), use if n is odd
        CSOD  $6,$0,5       // b(5), use if n is odd
0H      SUBU  $0,$0,1       // loop: n--
        2ADDU $255,$3,$2    // a(n+1) = 2a(n) + a(n-1)
        SUBU  $255,$255,$1  // - a(n-2)
        SET   $1,$2         // and shift
        SET   $2,$3         // values of a
        SET   $3,$255       // down
        2ADDU $255,$6,$5    // b(n+2) = 2b(n) + b(n-2)
        SUBU  $255,$255,$4  // - b(n-4)
        CSOD  $4,$0,$5      // shift values of b down
        CSOD  $5,$0,$6      // if n is odd
        CSOD  $6,$0,$255    // (happens once if n started at 2 or 3)
        PBNZ  $0,0B         // if(n) goto loop
        ADDU  $0,$1,$4      // r(n) = (a(n) + b(n))
        SRU   $0,$0,1       // ÷ 2
        POP   1,0           // return r(n)
\$\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.