Jumlah Basa Rantai Lurus dengan panjang tertentu

28

Alk * rantai lurus didefinisikan sebagai urutan atom karbon yang dihubungkan oleh ikatan tunggal (alkana), rangkap dua (alkena), atau rangkap tiga (alkuna), (digunakan hidrogen implisit.) Atom karbon hanya dapat membentuk 4 ikatan, jadi tidak ada atom karbon yang dipaksa memiliki lebih dari empat ikatan. Alk * rantai lurus dapat direpresentasikan sebagai daftar ikatan karbon-karbonnya.

Ini adalah beberapa contoh alkali rantai lurus yang valid:

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

Meskipun tidak, karena setidaknya satu atom karbon akan memiliki lebih dari 4 ikatan:

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

Tugas Anda adalah membuat program / fungsi yang, jika diberi bilangan bulat positif n, mengeluarkan / mengembalikan jumlah rantai lurus yang valid ndengan panjang persis atom karbon. Ini adalah OEIS A077998 .

Spesifikasi / Klarifikasi

  • Anda harus menangani 1dengan benar dengan kembali 1.
  • Orang-orang suka [1,2]dan [2,1]dianggap berbeda.
  • Output adalah panjang daftar semua kemungkinan alk panjang.
  • Anda tidak harus menangani 0 dengan benar.

Kasus uji:

1 => 1
2 => 3
3 => 6
4 => 14

Ini adalah kode golf, jadi jumlah byte terendah menang!

Zacharý
sumber
hanya untuk memperjelas, rantai valid jika semua pasangan berturut-turut dijumlahkan <=4, kan?
Maltysen
Tetap. @Maltysen: ya.
Zacharý
4
Mengapa ada urutan OEIS untuk semuanya? : P
HyperNeutrino
2
@ ZakaryT, tepatnya ada satu hidrokarbon dengan nol atom karbon, dan itu yang juga memiliki nol atom hidrogen. Argumennya sama persis dengan segitiga Pascal yang memiliki 1 di atas daripada 0, atau untuk ratusan urutan kombinatorik lainnya.
Peter Taylor
1
@ Emigna, itu karena urutan yang salah ditautkan. Saya akan memperbaikinya.
Peter Taylor

Jawaban:

7

Oasis , 9 7 byte

xcd-+3V

Cobalah online!

Penjelasan

Ini menggunakan hubungan pengulangan di OEIS :

a (n) = 2 * a (n-1) + a (n-2) - a (n-3)

x    Multiply a(n-1) by 2: gives 2*a(n-1)
c    Push a(n-2)
d    Push a(n-3)
-    Subtract: gives a(n-2) - a(n-3)
+    Add: gives 2*a(n-1) + a(n-2) - a(n-3)
3    Push 3: initial value for a(n-1)
V    Push 1, 1: initial values for a(n-2), a(n-3)
Luis Mendo
sumber
1
Penggunaan nilai awal yang bagus! Anda menang kali ini;)
Emigna
Ya, mungkin tidak ada cara untuk mengalahkan ini.
Zacharý
4
@ ZakaryT Hanya jika seseorang dapat menemukan cara untuk membuat program ada xkcddi dalamnya.
hBy2Py
4
@ hBy2Py Baiklah, xkcd-+311berfungsi , karena ksaat ini bukan pilihan ...
Luis Mendo
10

MATL , 10 byte

7K5vBiY^1)

Cobalah online!

Penjelasan

Ini menggunakan karakterisasi yang ditemukan di OEIS

a (n) adalah entri kiri atas kekuatan ke-n dari matriks 3 X 3 [1, 1, 1; 1, 0, 0; 1, 0, 1]

7    % Push 7
K    % Push 4
5    % Push 5
v    % Concatenate all numbers into a column vector: [7; 4; 5]
B    % Convert to binary: gives 3×3 matrix [1, 1, 1; 1, 0, 0; 1, 0, 1]
i    % Input n
Y^   % Matrix power
1)   % Take the first element of the resulting matrix, i.e. its upper-left corner.
     % Implicitly display
Luis Mendo
sumber
6

Oasis , 9 8 byte

Menyimpan satu byte, terima kasih kepada Adnan

xc+d-63T

Cobalah online!

Penjelasan

a(0) = 0
a(1) = 1
a(2) = 3
a(3) = 6

a(n) = xc+d-

x         # calculate 2*a(n-1)
 c        # calculate a(n-2)
  +       # add: 2*a(n-1) + a(n-2)
   d      # calculate a(n-3)
    -     # subtract: 2*a(n-1) + a(n-2) - a(n-3)
Emigna
sumber
1
Bagus! Juga, xkependekan dari 2*:).
Adnan
1
Kalahkan ya :-P (Saya belum melihat ada jawaban OASIS)
Luis Mendo
@ Adnan Apakah ada cara untuk memberi tahu Oasis bahwa Anda ingin menggeser indeks urutan output sebesar 1? Maksudku, kurangi 1 dengan argumen input (alih-alih menggunakan inisial di 0sini)
Luis Mendo
1
@LuisMendo Ah, itu belum diterapkan. Tapi itu ide yang bagus untuk rilis selanjutnya :).
Adnan
Untuk referensi di masa mendatang, ini sekarang diterapkan
Luis Mendo
4

Jelly, 10 byte

745DBæ*µḢḢ

Cobalah online!

Menggunakan algoritma Luis Mendo .

Penjelasan

745DBæ*µḢḢ    Main link. Argument: n
745D          Get the digits of 745
    B         Convert each to binary
     æ*       Matrix power
        ḢḢ    First element of first row

Jelly, 15 byte

3Rṗ’µ+2\<5PµÐfL

Cobalah online!

Menggunakan kekuatan kasar.

Penjelasan

3Rṗ’µ+2\<5PµÐfL    Main link. Argument: n
3R                 Start with [1, 2, 3]
   ’               Take the (n-1)'th
  ṗ                Cartesian power
            Ðf     Filter on:
     +2\             Sums of overlapping pairs
        <5           1 for sums < 5, 0 otherwise
          P          Product: 1 if all pairs < 5
              L    Length
PurkkaKoodari
sumber
4

MATL , 14 byte

q3:Z^TTZ+!5<As

Cobalah online!

Penjelasan

Ini menghasilkan kekuatan Cartesian dari [1 2 3]"dinaikkan" ke jumlah atom minus 1, dan kemudian menggunakan konvolusi untuk memeriksa bahwa tidak ada dua angka yang berdekatan dalam setiap jumlah tupel Cartesian lebih dari 4.

q    % Take number of atoms n implicitly
3:   % Push [1 2 3]
Z^   % Cartesian power. Gives a matrix with each (n-1)-tuple on a row
TT   % Push [1 1]
Z+   % 2D convolution. For each tuple this gives the sum of contiguous numbers
5<   % For each entry, gives true if less than 5
!    % Transpose
A    % True if all elements of each column are true. Gives a row vector
s    % Sum of true results. Implicitly display
Luis Mendo
sumber
3

Mathematica, 48 byte

MatrixPower[{{1,1,1},{1,0,0},{1,0,1}},#][[1,1]]&

Seperti yang ditunjukkan Luis Mendo , ini adalah A006356 di OEIS. Ini adalah upaya asli saya:

Count[Length@Split[#,+##<5&]&/@Tuples[{1,2,3},#-1],0|1]&

Untuk input n, Tuples[{1,2,3},n-1]adalah daftar semua (n-1)elemen elemen dalam {1,2,3}mewakili semua kemungkinan urutan ikatan tunggal, rangkap, atau rangkap tiga untuk natom karbon. +##<5&adalah fungsi murni yang mengembalikan apakah jumlah argumennya kurang dari 5, sehingga Split[#,+##<5&]&membagi daftar menjadi sublists yang terdiri dari elemen berurutan yang jumlah berpasangannya kurang dari 5. Menggambarkan alk * ne yang valid setara dengan daftar ini yang memiliki panjang 0(dalam kasus di mana n=1) atau 1, jadi saya hanya Countjumlah (n-1)-tupel di mana panjang daftar itu cocok 0|1.

Count[Fold[If[+##>4,4,#2]&]/@Tuples[{1,2,3},#-1],Except@4]&

If[+##>4,4,#2]&kembali 4jika jumlah argumennya lebih besar dari 4dan mengembalikan argumen kedua sebaliknya. Fold[If[+##>4,4,#2]&]melakukan Foldinput kiri dengan fungsi ini. Jadi di sini saya Countjumlah (n-1)-tuple yang tidak diberikan operator yang menerapkan ini 4. Kasus di mana n=1dicakup sejak Foldtetap tidak dievaluasi ketika argumen kedua adalah daftar kosong {}.

ngenisis
sumber
1
Apakah ini akan berhasil? (Jenis robek langsung dari OEIS dengan penyesuaian) LinearRecurrence[{2,1,-1},{1,3,6},#][[#]]&?
Zacharý
Bagian dari mengapa saya suka situs ini adalah mempelajari semua fitur yang ditawarkan Mathematica :)
ngenisis
Oleh this site, maksud Anda Oei atau PPCG?
Zacharý
PPCG. Saya telah mengambil banyak Matematika dari saran orang.
ngenisis
3

Python, 51 byte

f=lambda n:n<4and(n*n+n)/2or 2*f(n-1)+f(n-2)-f(n-3)

Ini adalah implementasi langsung dari hubungan perulangan. Terima kasih kepada Tim Pederick untuk 3 byte. Outputnya adalah float di Python 3 dan integer di Python 2.

Cobalah online!

Mego
sumber
(n*n+n)/2lebih pendek dari [1,3,6][n-1]. Dan jika Anda menggunakan Python 3 dan tidak suka berakhir dengan output floating-point, (n*n+n)//2masih lebih pendek.
Tim Pederick
2

Pyth - 16 byte

Menggunakan kekuatan kasar.

lf.AgL4+VTtT^S3t

Test Suite .

Maltysen
sumber
1
Akan menyenangkan untuk memberikan deskripsi bagi kita yang tidak "grok" Pyth.
Zacharý
2

Ruby, 62 byte

->n{c=0
(10**n/10).times{|i|"#{i}#{i*11}"=~/[3-9]/||c+=1}
c}

Pendekatan brute force 10 base yang sangat tidak efisien. Dapat ditingkatkan ke basis 5 untuk byte tambahan.

Angka-angka dihasilkan ketika setiap digit mewakili ikatan (n-1 digit.) 0Mewakili urutan ikatan 1, 2mewakili urutan ikatan 3. Digit lebih dari 2 tidak valid.

Kami mengalikannya dengan 11 untuk menjumlahkan pasangan angka yang berdekatan. Sekali lagi angka di atas 3 tidak valid.

Kami menggabungkan dua angka dalam sebuah string dan melakukan regex untuk mencari digit yang tidak valid. Jika tidak ada yang ditemukan, kami menambah penghitung.

dalam program uji

f=->n{c=0
(10**n/10).times{|i|"#{i}#{i*11}"=~/[3-9]/||c+=1}
c}

p f[gets.to_i]
Level River St
sumber
2

Ruby, 51 byte

->n{a=[1,1,3]
n.times{a<<2*a[-1]+a[-2]-a[-3]}
a[n]}

Berdasarkan hubungan perulangan per OEIS A006356.

Mulai dengan larik untuk elemen 0,1 dan 2 dari urutan yang 1 (sebagaimana dihitung oleh saya, untuk membuatnya bekerja), masing-masing 1 dan 3.

Iteratif menambahkan nlebih banyak elemen ke urutan, lalu mengembalikan elemen n. Itu selalu menghitung 2 elemen lebih dari yang sebenarnya perlu, tapi masih waktu linier, yang jauh lebih efisien daripada jawaban saya sebelumnya.

dalam program uji

f=->n{a=[1,1,3]
n.times{a<<2*a[-1]+a[-2]-a[-3]}
a[n]}

p f[gets.to_i]
Level River St
sumber
2

Mathematica, 42 40 byte

Hitungan byte mengasumsikan pengodean byte tunggal yang kompatibel seperti CP-1252 (default pada instalasi Windows).

±0=±1=1;±2=3;±n_:=±(n-1)2+±(n-2)-±(n-3);

Ini hanya mengimplementasikan pengulangan yang diberikan pada OEIS sebagai operator unary.

Martin Ender
sumber
2

CJam (19 byte)

{2,{__-2=+1b+}@*W=}

Test suite online . Ini adalah blok anonim (fungsi) yang mengambil satu item di tumpukan dan meninggalkan satu di tumpukan. Perhatikan bahwa paket uji termasuk a(0) = 1.

Pengulangan yang digunakan didasarkan pada pengamatan untuk urutan OEIS terkait A006356 :

Sama dengan transformasi INVERT dari (1, 2, 1, 1, 1, ...) yang setara dengan a (n) = a (n-1) + 2 * a (n-2) + a (n-3) + a (n-4) + ... + 1. a (6) = 70 = (31 + 2 * 14 + 6 + 3 + 1 + 1). - Gary W. Adamson, 27 Apr 2009

tetapi dengan offset yang sesuai, yang menghilangkan kebutuhan untuk final + 1seperti sekarang tercakup oleh a(0).

Pembedahan

{         e# Define a block
  2,      e#   Take starting sequence [0 1] (beginning at index -1 for golfiness)
  {       e#   Loop...
    _     e#     Copy sequence so far
    _-2=+ e#     Append an extra copy of a(n-2)
    1b    e#     Sum
    +     e#     Append
  }@*     e#   ...n times
  W=      e#   Take the final value from the sequence
}
Peter Taylor
sumber
2

Brain-Flak, 56 byte

Gunakan algoritme yang dirinci dalam komentar pertama pada halaman OEIS.

Cobalah online!

({}[()]<(((())))>){({}[()]<{({}<>({}))<>}<>>)}{}({}<>{})

Penjelasan

Urutan dapat didefinisikan sebagai berikut:

For u(k), v(k), and w(k) such that
u(1) = v(1) = w(1) = 1
u(k+1) = u(k) + v(k) + w(k)
v(k+1) = u(k) + v(k)
w(k+1) = u(k)
u(k) is the number of straight-chain alk*nes with length k

Program dimulai pada 1dan berulang kali menerapkan pengulangan ini untuk menghitungu(k)

Kode Beranotasi (anotasi aktual yang akan datang)

# Setup: decrement the input by one and push three 1's to the stack under it
({}[()]<(((())))>)

# Calculation:
{                          }           # While the input is not zero (main loop)
 ({}[()]                  )            # Pop the counter decrement it by one and push it
        <                >             # Before the counter gets pushed back to the stack...
         {            }                # Loop while the top of the stack is not zero (subloop)
          (        )                   # Push...
           {}                          # The top of the stack (popped)...
             <>                        # to the other stack...
               ({})                    # plus the top of the other stack (peeked)
                    <>                 # Switch back to the first stack.
                       <>              # Switch to the other stack
                            {}         # Pop the input (now zero)
                              (      ) # Push...
                               {}      # The top of the stack (u(k))...
                                 <>    # to the other stack...
                                   {}  # plus the top of the other stack (zero).

Visualisasi tumpukan

Dalam satu iterasi dari loop utama inilah yang terjadi (perhatikan bahwa nol mungkin ada atau tidak ada tetapi tidak masalah dengan cara apa pun):

Start of main loop iteration/subloop first iteration:
A    B

u
v
w
0    0
^

After first subloop iteration:
A    B

v
w    u
0    0
^

After second subloop iteration:
A    B

    u+v
w    u
0    0
^

After third subloop iteration (top of stack is zero so subloop terminates):

A    B

   u+v+w
    u+v
     u
0    0
^

End of main loop iteration:
A    B

   u+v+w
    u+v
     u
0    0
     ^

Keadaan tumpukan sekarang sama seperti itu pada awal loop kecuali bahwa tumpukan saat ini sekarang memiliki nilai-nilai berikutnya untuk u, vdan wdi atasnya.

0 '
sumber
2

Perl 6, 48

{my @a=1,0,0;@a=reverse [\+] @a for 1..$_;@a[0]}

Semula

sub f {$_>2??2*f($_-1)+f($_-2)-f($_-3)!!(1,1,3)[$_]}

tapi saya lupa saya membutuhkan sub fsehingga solusi berulang menang.

bb94
sumber
2

Dyalog APL, 30 byte

{⍵<3:⍵⌷1 3⋄+/∧/¨4≥2+/¨,⍳1↓⍵/3}

Menggunakan kekuatan kasar. Penjelasan (upaya terbaik saya setidaknya satu):

⍵<3:⍵⌷1 3 - if ⍵ (function arg) is 1 (case 1) or 2 (case 2), return 1 (case 1) or 3 (case 2)
⋄ - separate statements
⍵/3 - otherwise, 3 repeated ⍵ times
1↓ - without the first element
⍳ - the matrix of possible indices of a matrix of that size
,  - ravel, return a list of all the elements of the matrix
2+/¨ - sum of each contiguous pair on each element
4≥ - tests whether each element is less than or equal to 4
∧/¨ - all elements are true, applied to each item.
+/ - Sum.
Zacharý
sumber
1

Dyalog APL, 29 byte

{⍵<4:⍵⌷1 3 6⋄+/2 1 ¯1×∇¨⍵-⍳3}

Bekerja dengan menggunakan definisi rekursif dari urutan bilangan bulat OEIS A006356.

Zacharý
sumber
1

Python dengan Numpy, 62 byte

Saya harus mencobanya, tetapi tampaknya Python murni dan rekursi lebih pendek dari numpy dan eksplisit, perhitungan berbasis matriks pada halaman OEIS.

from numpy import*
lambda n:(mat('1 1 1;1 0 0;1 0 1')**n)[0,0]
Tim Pederick
sumber
1

R, 61 58 55 51 50 byte

Mengambil input dari stdin, menggunakan matriks eksponensial untuk menentukan hasil yang tepat.

el(expm::`%^%`(matrix(!-3:5%in%2^(0:2),3),scan()))

Jika Anda lebih suka solusi rekursif, berikut ini adalah implementasi langsung dari relasi perulangan yang tercantum dalam OEIS, untuk 55 byte .

f=function(n)`if`(n<4,(n*n+n)/2,2*f(n-1)+f(n-2)-f(n-3))
rturnbull
sumber
1

Excel, 123 byte

Menerapkan formula dari OEIS:

=4*(SIN(4*PI()/7)^2*(1+2*COS(2*PI()/7))^A1+SIN(8*PI()/7)^2*(1+2*COS(4*PI()/7))^A1+SIN(2*PI()/7)^2*(1+2*COS(8*PI()/7))^A1)/7

Seperti biasa, masukan A1, rumus di sel lain.

Gali identitas Trig lama untuk melihat apakah bisa membantu. Sekarang kepalaku sakit.

Wernisch
sumber
0

Lithp , 79 byte

#N:(((if(< N 4)((/(+ N(* N N))2))((-(+(* 2(f(- N 1)))(f(- N 2)))(f(- N 3)))))))

Menerapkan urutan bilangan bulat rekursif yang tercantum dalam OEIS.

Implementasi yang mudah dibaca dan test suite.

% alkaline.lithp
% run with: ./run.js alkaline.lithp
(
    (def f #N : ((
        (if (< N 4) (
            (/ (+ N (* N N)) 2)
        ) (else (
            (- (+ (* 2 (f (- N 1))) (f (- N 2))) (f (- N 3)))
        )))
    )))

    % Test cases 1 to 4
    (import lists)
    (each (seq 1 4) #I :: ((print (f I))))
)
Andrakis
sumber