Liczba

16

Biorąc pod uwagę liczbę dodatnią , znajdź liczbę alkanów o atomach węgla, ignorując stereoizomery ; lub równoważnie, liczba nieoznakowanych drzew z węzłami, tak że każdy węzeł ma stopień .nnn4

Jest to sekwencja OEIS A000602 .

Zobacz także: Parafiny - kod Rosetty

Przykład

Dla odpowiedź wynosi , ponieważ heptan ma dziewięć izomerów :n=79

  • Heptan :H.3)do-doH.2)-doH.2)-doH.2)-doH.2)-doH.2)-doH.3)

Heptan

  • 2-metyloheksan :H.3)do-doH.(doH.3))-doH.2)-doH.2)-doH.2)-doH.3)

2-metyloheksan

  • 3-metyloheksan :H.3)do-doH.2)-doH.(doH.3))-doH.2)-doH.2)-doH.3)

3-metyloheksan

  • 2,2-dimetylopentan :H.3)do-do(doH.3))2)-doH.2)-doH.2)-doH.3)

2,2-dimetylopentan

  • 2,3-dimetylopentan :H.3)do-doH.(doH.3))-doH.(doH.3))-doH.2)-doH.3)

2,3-dimetylopentan

  • 2,4-dimetylopentan : H.3)do-doH.(doH.3))-doH.2)-doH.(doH.3))-doH.3)

2,4-dimetylopentan

  • H.3)do-doH.2)-do(doH.3))2)-doH.2)-doH.3)

3,3-dimetylopentan

  • H.3)do-doH.2)-do(doH.2)doH.3))-doH.2)-doH.3)

3-etylopentan

  • H.3)do-do(doH.3))2)-doH.(doH.3))-doH.3)

2,2,3-trimetylobutan

Należy zauważyć, że 3-metyloheksan i 2,3-dimetylopentan są chiralne , ale tutaj ignorujemy stereoizomery.

Przypadki testowe

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
źródło
3
Byłbym pod wrażeniem, gdyby komuś udało się napisać rozwiązanie w Alchemist !
ბიმო
@PeterTaylor Well Może wypisywać za każdym razem cyfrę
l4m2
@ l4m2: Użyłem go wcześniej do wyzwania sekwencji i niektórych wyzwań liczbowych , możesz także użyć jednoargumentowego wyniku, który najprawdopodobniej jest łatwiejszy. I tak, najprawdopodobniej jest to TC ( używa bignum ), ale formalnie tego nie udowodniłem.
ბიმო
@BMO Wygląda na to, że można po prostu symulować CM
l4m2

Odpowiedzi:

11

CJam ( 100 98 91 89 83 bajtów)

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

Pobiera dane wejściowe ze standardowego wejścia, a wyjściowe na standardowe wyjście. Zauważ, że wykorzystuje to licencję do nieobsługiwania danych wejściowych w 0celu zaoszczędzenia dwóch bajtów poprzez wstawienie definicji Ci D. Demo online

Uwaga: jest to bardzo wolne i nieefektywne pod względem pamięci. Przycinanie tablic pozwala uzyskać znacznie szybszą wersję (3 bajty więcej). Demo online .

Sekcja

ZA000598(x)=1+xZ(S.3);ZA000598(x))ZA000678(x)=xZ(S.4;ZA000598(x))ZA000599(x)=Z(S.2);ZA000598(x)-1)ZA000602(x)=ZA000678(x)-ZA000599(x)+ZA000598(x2))
Z(S.n;fa(x))S.nfa(x)

Zmanipulowałem to do rozkładu nieco bardziej golfistycznego, a następnie przejrzałem sekwencje pośrednie i odkryłem, że są one również w OEIS:

ZA000642(x)=Z(S.2),ZA000598(x))ZA000631(x)=Z(S.2),ZA000642(x))ZA000602(x)=ZA000642(x)+xZA000642(x2))-xZA000631(x)

Wcześniejsze wersje ponownie wykorzystywały blok C(zwijają dwa wielomiany) z tej odpowiedzi . Znalazłem o wiele krótszy, ale nie mogę zaktualizować tej odpowiedzi, ponieważ pochodzi ona z łańcuchowego pytania.

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
źródło
5

Node.js 11.6.0 ,  229 223 221  218 bajtów

Pochodzi z implementacji Java sugerowanej w kodzie Rosetta .

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)

Wypróbuj online!

Arnauld
źródło
5

Alchemik (1547 bajtów)

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

Demo online .

Uwaga: jest to dość powolne. Jeśli testowanie za pomocą interpretera, który obsługuje wielokrotne stosowanie reguły jednocześnie (np. Mojej - chociaż upewnij się, że masz najnowszą wersję, która naprawia błąd w parserze), możesz uzyskać znaczne przyspieszenie, dodając dwie reguły:

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

które wyznaczają trasę według istniejących reguł

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

Częściowe rozwarstwienie

Na wysokim poziomie używa tego samego podejścia, co moja odpowiedź CJam.

Model obliczeniowy Alchemist jest zasadniczo maszyną rejestru Minsky'ego . Jednak Alchemist bardzo ładnie ujawnia równoważność kodu i danych, a pozwalając skutecznie na wiele tokenów po lewej stronie reguły produkcji, stan nie jest ograniczony do reprezentowania przez jeden atom: możemy użyć krotki atomów, a to zezwala na (nierekurencyjne) podprogramy. Jest to bardzo przydatne w golfa. Jedyne, czego tak naprawdę brakuje, to makra i możliwość debuggowania.

0xZA(2)ZA+1)2)xPebnbebtded

a, b = b, 0

rozwija się do co najmniej 17 bajtów:

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

gdzie Sjest obecny stan i Tnastępny. Nieniszcząca „kopia” jest jeszcze droższa, ponieważ musi być wykonana jako „ruch” z ado bi pomocniczy tmp, a następnie „ruch” z tmppowrotem do a.

Zaciemnianie

Zróżnicowałem różne zmienne i wyeliminowałem około 60 stanów w trakcie gry w golfa w programie, a wiele z nich i tak nie miało szczególnie znaczących nazw, ale aby w pełni zagrać w golfa, napisałem minimiser, więc nazwy są teraz całkowicie nieczytelne. Powodzenia inżynieria odwrotna! Oto minimalizator (w CJam), który przyjmuje kilka założeń dotyczących kodu, ale można go dostosować w celu zminimalizowania innych programów 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
źródło
Zaraz ... czy ten tłumacz działa? AFAICT ... wybierasz losową regułę, a następnie zastanawiasz się, ile razy można ją zastosować. Czy to w ogóle działa poprawnie?
Tylko ASCII,
Hmm Jak byś poprawił debuggowanie
tylko ASCII
@ Tylko ASCII, to by działało, ale tak naprawdę nie działa. Najpierw wybiera regułę, która ma zastosowanie, a następnie sprawdza, ile razy można ją zastosować. Debugowanie jest trudne. Jednym z moich pomysłów na projekt pracy dyplomowej był edytor GUI RM z debuggerem wstecznym.
Peter Taylor,
ale ... kolejność wykonywania reguł wpływa na kolejność programów, prawda
tylko ASCII
@ Tylko ASCII, tak. Dlatego jest tak wiele zmiennych. Tylko około 16 z nich to dane: reszta to stan. Użyłem niedeterminizmu do gry w golfa, skutecznie paralelizując niezależne operacje „ruchów”.
Peter Taylor,