Wątek gliniarzy

W tym wątku Twoim zadaniem jest utworzenie programu / funkcji opartej na rekurencji w celu wygenerowania dowolnej liczby całkowitej. Rabusie spróbują znaleźć krótsze nierekurencyjne rozwiązanie w wątku Rabusiów .

Wyzwanie streszczenie

W wielu językach funkcje rekurencyjne mogą znacznie uprościć zadanie programowania. Jednak narzut składni dla prawidłowej rekurencji może ograniczyć jego użyteczność w golfowym kodzie.

Te gliny tworzy program lub funkcję biorąc jedną liczbę całkowitą n, która generuje na pierwszej npozycji z roztworów o całkowitą, przy użyciu tylko rekursji ¹ . Powinny również upewnić się, że istnieje krótszy nierekurencyjny sposób generowania sekwencji, aby oznaczyć ich wpis jako bezpieczny.

W rabusie spróbuje znaleźć krótszy program lub funkcję w tym samym języku, tworząc taką samą serię całkowitą, używając żadnych rekursji ² .

Jeśli oświadczenie gliniarzy nie zostanie złamane w ciągu dziesięciu dni (240 godzin), gliniarz udowodni, że w rzeczywistości możliwe było zastosowanie krótszego nierekurencyjnego podejścia, ujawniając własne rozwiązanie. Następnie mogą oznaczyć swoje zgłoszenie jako bezpieczne .

Zwycięzca wyzwania gliniarzy będzie najkrótszy (według code-golfa) ) rekursja oparta na rekurencji oznaczona jako bezpieczna.

Zwycięzcą wyzwania rabusiów będzie rabuś, który złamał najwięcej rozwiązań.

^{1: Trzeba tylko rekurencyjnie składni; nie musisz się martwić, na przykład, optymalizacją ogona.}

^{2: Ponownie, brak rekurencji w składni; więc nie możesz opublikować rozwiązania rekurencyjnego i twierdzić, że jest ono skompilowane w pętli dzięki optymalizacji wywołania ogona.}

Wymagania dotyczące przedłożenia

Każde przesłanie zajmie jedną liczbę całkowitą n(zero lub jeden). Przesłanie spowoduje następnie wygenerowanie lub zwrócenie pierwszych nwpisów z wybranej liczby całkowitej. (zauważ, że ta seria liczb całkowitych nie może zależećn ). Metoda wejścia i wyjścia może różnić się między podejściem rekurencyjnym i nierekurencyjnym. Szereg całkowity może być dowolną serią deterministyczną o długości co najmniej 5. Szereg ten należy odpowiednio wyjaśnić.

Twoje zgłoszenie nie musi działać dla dowolnych dużych n, ale powinno działać przynajmniej n=5. Podejście nierekurencyjne musi być w stanie działać co najmniej tak samo njak podejście rekurencyjne lub do n=2^15-1, w zależności od tego, które jest mniejsze.

Rekurencja

Ze względu na to wyzwanie rekurencję definiuje się jako tworzenie pożądanej sekwencji przy użyciu funkcji (lub konstruktu podobnego do funkcji), który wywołuje siebie (lub wywołuje sekwencję funkcji, która ostatecznie wywołuje samą siebie; obejmuje to konstrukty takie jak kombinator Y). Głębokość rekurencji powinna osiągnąć nieskończoność, podobnie jak nnieskończoność. Podejście nierekurencyjne to wszystko, co nie jest rekurencyjne.

Python 3 , 65 bajtów (bezpieczny)

f=lambda n,a=3,b=0,c=6,d=6:n*[1]and[a+b]+f(n-1,c,d,2*c+d,2*a+3*b)

Wypróbuj online!

Kolejna próba w Pythonie.

Sekwencja jest „liczbą sposobów na wypełnienie planszy 2 na n domino w trzech kolorach, tak aby żadne dwa domino tego samego koloru nie stykały się ze sobą”. Nie w OEIS.

Powiedzmy Chodźmy n=6. Tablica wygląda następująco:

######
######

i są to prawidłowe domino w trzech kolorach ( 1-3każdy reprezentuje kolor):

123123 122331 212332 212121 113311
123123 133221 212112 212121 331133

ale tak nie jest (dotykają się dwa domino tego samego koloru):

112323 332333 211113
112323 112311 233223

Sekwencja zlicza wszystkie możliwe nachylenia domina, które spełniają reguły dla każdego z nich n.

Zamierzone rozwiązanie, 58 bajtów

n=int(input());a=3;b=12
for _ in[0]*n:print(a);a,b=b,a*4+b

Wypróbuj online!

Niestety wygląda na to, że nikt nie zadał sobie trudu, aby uprościć relację powtarzalności, co wyraźnie pokazano w kodzie rekurencyjnym. Tworzenie programu z podaną podwójną powtarzalnością w stanie „jak jest” nie działa, ponieważ jest to Python 3.

Oktawa , 47 bajtów, pęknięta przez 14m2

@(n)(f=@(r,m){@()[r(r,m-1),m],[]}{~m+1}())(f,n)

Wypróbuj online!

Jako przykład podajemy wpis Octave, który generuje pierwsze ndodatnie liczby całkowite, https://oeis.org/A000027 .

Python 3 , 75 bajtów, spakowany przez xnor

f=lambda n,a=[1]:a*n and[a[0]]+f(n-1,sorted({*a[1:],a[0]*2,a[0]*3,a[0]*5}))

Wypróbuj online!

Słynne liczby Hamminga, czyli 5-gładkie liczby ( A051037 ).

Pęknięty roztwór, 51 bajtów

lambda n:[k for k in range(1,2**n)if 60**k%k<1][:n]

Wypróbuj online!

Zamierzone rozwiązanie, 74 bajty

lambda n:sorted(2**(i%n)*3**(i//n%n)*5**(i//n**2)for i in range(n**3))[:n]

Wypróbuj online!

Dalej (gforth) , 39 bajtów, złamany przez NieDzejkob

: | dup 1 > if dup 1 - recurse then . ;

Wypróbuj online!

Röda , 40 bajtów

f x,a=1,b=2{[a];f x-1,a=b,b=a+b if[x>1]}

Wypróbuj online!

Ta funkcja daje następującą skończoną sekwencję (90 pierwszych liczb Fibonacciego):

1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
1836311903
2971215073
4807526976
7778742049
12586269025
20365011074
32951280099
53316291173
86267571272
139583862445
225851433717
365435296162
591286729879
956722026041
1548008755920
2504730781961
4052739537881
6557470319842
10610209857723
17167680177565
27777890035288
44945570212853
72723460248141
117669030460994
190392490709135
308061521170129
498454011879264
806515533049393
1304969544928657
2111485077978050
3416454622906707
5527939700884757
8944394323791464
14472334024676221
23416728348467685
37889062373143906
61305790721611591
99194853094755497
160500643816367088
259695496911122585
420196140727489673
679891637638612258
1100087778366101931
1779979416004714189
2880067194370816120
4660046610375530309

Wiem, że może generować więcej liczb Fibonacciego, ale na potrzeby tego wyzwania wystarczy wygenerować te liczby.

JavaScript (Node.js) , 91 bajtów, Pęknięty przez l4m2

f=x=>[w=~-x&&(g=(n,y=2)=>~-n&&(n<y?1:n%y?g(n,y+1):1+g(n/y,y)))(x)+f(x-1),console.log(w)][0]

Wypróbuj online!

Drukuje pierwsze n wyrażeń sekwencji OEIS A022559 (zaczynając od i = 1).

l4m2 pasuje 3 dla pętli do 74 72 bajtów i złamał mój post gliniarza:

n=>{for(i=s=0;j=i++<n;console.log(s))for(x=i;j++<i;)for(;x%j<1;x/=j)s++}

Jednak moja zamierzona odpowiedź ma w rzeczywistości tylko 2 pętle:

n=>{for(i=c=0;i++<n;console.log(c))for(p=2,z=i;p<=z;z%p?p++:(z/=p,c++));}

Wypróbuj online!

Funkcja x86 .COM, 12 bajtów, Cracked przez NieDzejkob

0000 52                     push dx
0001 4A                     dec dx
0002 7403                   je 0007
0004 E8F9FF                 call 0000
0007 58                     pop ax
0008 F7E0                   mul ax
000A AB                     stosw


000B C3                     ret

Wejście DX, Wyjście [DI] ~ [DI + 2 * DX-1]

Rozwiązanie krakersa:

0: 31 C0    xor ax, ax
2: BF 01 00 mov di, 1
5: 01 F8    add ax, di
7: AB       stosw
8: E2 FB    loop 5
A: C3       ret

Zamierzone rozwiązanie:

  xor bx,bx
c:inc bx
  mov ax,bx
  mul ax
  stosw
  loop c
  ret

Python 3 , 62 bajty, Cracked przez mwchase

def f(x):
 if(x<1):return[1]
 return f(x-1)+[sum(f(x-1)[-2:])]

Wypróbuj online!

Myślę, że ten będzie zbyt łatwy ...

Sekwencja jest sekwencją Fibonacciego f(n) = f(n-1) + f(n-2)zf(0) = f(1) = 1

Gol> <> , 15 bajtów, złamane przez mbomb007

I1AZZ;
M:K:?ZNB

Wypróbuj online!

Seria jest 0,1,2,3,4,5 ale po każdym elemencie występuje tyle zer.

Na przykład pierwsze kilka wartości to:

 1: 0  First element, followed by 0 zeroes
 2: 1  Followed by 1 zero
 3: 0
 4: 2  Followed by 2 zeroes
 5: 0
 6: 0
 7: 3  Followed by 3 zeroes
 8: 0
 9: 0
10: 0
    etc.

JavaScript, 63 bajty, pęknięty

f=x=>(x?[f(x-1)[0]&&1?3*f(x-1)[0]+1:f(x-1)[0]/2,...f(x-1)]:[7])

Wypróbuj online!

Zwraca pierwsze n elementów w odwróconej tablicy

Windows .BAT, 80 bajtów

@set /a n=%1-1
@echo 8%3
@if 0 neq %n% @call %0 %n% 2%3 6%2%3

Stosowanie:

CD <PATH>
<FILENAME> <N_1>
<FILENAME> <N_2>
<FILENAME> <N_3>

Wersja pętli może przyjmować w bieżącym słowniku, ale musi zostać zainicjowana lub zresetowana

Python, 82 bajty; pęknięty

Jest to rekurencyjna implementacja w Pythonie sekwencji OEIS A004001 w 82 bajtach. Więcej informacji na temat tej serii można znaleźć w Mathworld Wolframa .

def A(n):
 if n in[1,2]:return[1]*n
 S=A(n-1);return S+[S[S[n-2]-1]+S[n-S[n-2]-1]]

Pierwsze 30 liczb w tej sekwencji to:

1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, 10, 11, 12, 12, 13, 14, 14, 15, 15, 15, 16, 16, 16