Polizistenthread

In diesem Thread besteht Ihre Aufgabe darin, ein rekursionsbasiertes Programm / eine rekursionsbasierte Funktion zum Generieren beliebiger ganzzahliger Reihen zu erstellen. Räuber werden versuchen, eine kürzere nicht-rekursive Lösung im Räuber-Thread zu finden .

Inhaltsangabe der Challenge

In vielen Sprachen können rekursive Funktionen eine Programmieraufgabe erheblich vereinfachen. Der Syntax-Overhead für eine ordnungsgemäße Rekursion kann jedoch die Verwendbarkeit in Code-Golf einschränken.

Die Cops erstellen ein Programm oder eine Funktion, die eine einzelne Ganzzahl verwendet nund die ersten nEinträge einer Ganzzahlserie generiert , wobei nur die Rekursion ^{1 verwendet wird} . Sie sollten auch sicherstellen, dass es eine kürzere nicht-rekursive Möglichkeit gibt, die Sequenz zu generieren, um ihren Eintrag als sicher zu kennzeichnen.

Die Räuber werden versuchen, ein kürzeres Programm oder eine kürzere Funktion in derselben Sprache zu finden und dabei dieselbe Ganzzahlserie ohne Rekursion ^{2 zu} erzeugen .

Wenn die Vorlage der Polizei nicht innerhalb von zehn Tagen (240 Stunden) geknackt wird, wird der Polizist nachweisen, dass es tatsächlich möglich war, einen kürzeren nicht-rekursiven Ansatz zu verfolgen, indem er seine eigene Lösung enthüllt. Sie können dann ihre Einreichung als sicher markieren .

Der Gewinner der Cops Challenge ist die kürzeste (laut Code-Golf ) rekursionsbasierte Einsendung, die als sicher eingestuft wird.

Der Gewinner der Räuberherausforderung wird der Räuber sein, der die meisten Lösungen geknackt hat.

^{1: Es muss nur in der Syntax rekursiv sein; Sie müssen sich zum Beispiel keine Gedanken über die Optimierung von Tail Calls machen.}

^{2: Wieder nicht rekursiv in der Syntax; Sie können also dank der Tail-Call-Optimierung keine rekursive Lösung veröffentlichen und behaupten, dass sie zu einer Schleife kompiliert wurde.}

Anforderungen für die Vorlage

Für jede Übermittlung wird eine einzelne Ganzzahl n(null- oder einsbasiert) verwendet. Die Übermittlung wird dann die ersten nEinträge einer ganzzahligen Reihe der Wahl ausgeben oder zurückgeben . (Beachten Sie, dass diese Ganzzahlserie nicht davon abhängen darf n). Die Eingabe- und Ausgabemethode kann sich zwischen dem rekursiven und dem nicht rekursiven Ansatz unterscheiden. Die ganzzahlige Reihe kann jede deterministische Reihe mit einer Länge von mindestens 5 sein. Die Reihe sollte richtig erklärt werden.

Ihre Einreichung muss nicht für beliebig große nfunktionieren, sollte aber zumindest funktionieren n=5. Der nicht-rekursive Ansatz muss in der Lage sein, mindestens den gleichen Wert nwie der rekursive Ansatz oder den n=2^15-1kleineren zu erreichen.

Rekursion

Um dieser Herausforderung willen wird Rekursion so definiert, dass die gewünschte Sequenz mit einer Funktion (oder einem funktionsähnlichen Konstrukt) erstellt wird, die sich selbst aufruft (oder eine Folge von Funktionen aufruft, die sich letztendlich selbst aufruft; dazu gehören Konstrukte wie der Y-Kombinator). Die Rekursionstiefe sollte unendlich sein, ebenso nwie unendlich. Der nicht rekursive Ansatz ist alles, was nicht rekursiv ist.

Python 3 , 65 Bytes (sicher)

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)

Probieren Sie es online!

Ein weiterer Versuch in Python.

Die Folge ist "die Anzahl der Möglichkeiten, eine 2-mal-n-Tafel mit Dominosteinen in drei Farben zu füllen, so dass sich keine zwei gleichfarbigen Dominosteine ​​berühren". Nicht bei OEIS.

Sagen wir mal n=6. Das Board sieht aus wie:

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

und dies sind gültige Dominokacheln in drei Farben ( 1-3stellen jeweils eine Farbe dar):

123123 122331 212332 212121 113311
123123 133221 212112 212121 331133

aber das sind nicht (zwei gleichfarbige Dominosteine ​​berühren sich):

112323 332333 211113
112323 112311 233223

Die Sequenz zählt alle möglichen Dominokacheln, die den jeweiligen Regeln entsprechen n.

Geplante Lösung, 58 Bytes

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

Probieren Sie es online!

Leider hat sich anscheinend niemand die Mühe gemacht, die Wiederholungsbeziehung zu vereinfachen, was im rekursiven Code deutlich gezeigt wurde. Das Erstellen eines Programms mit der angegebenen doppelten Wiederholung funktioniert nicht, da es sich um Python 3 handelt.

Oktave , 47 Bytes, geknackt von l4m2

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

Probieren Sie es online!

Hier ist als Beispiel ein Octave-Eintrag, der die ersten npositiven Ganzzahlen generiert : https://oeis.org/A000027 .

Python 3 , 75 Bytes, geknackt von 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}))

Probieren Sie es online!

Die berühmten Hamming-Zahlen, auch bekannt als 5-glatte Zahlen ( A051037 ).

Gebrochene Lösung, 51 Bytes

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

Probieren Sie es online!

Geplante Lösung, 74 Bytes

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

Probieren Sie es online!

Forth (gforth) , 39 Bytes, geknackt von NieDzejkob

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

Probieren Sie es online!

Röda , 40 Bytes

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

Probieren Sie es online!

Diese Funktion liefert die folgende endliche Folge (die 90 ersten Fibonacci-Zahlen):

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

Ich weiß, dass es mehr Fibonacci-Zahlen erzeugen kann, aber für diese Herausforderung reicht es aus, diese Zahlen zu produzieren.

JavaScript (Node.js) , 91 Byte, Gebrochen von 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]

Probieren Sie es online!

Gibt die ersten n Terme der OEIS-Sequenz aus A022559 aus (beginnend mit i = 1).

l4m2 hat 3 for loops in 74 72 bytes gepasst und meinen cop post geknackt:

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

Meine beabsichtigte Antwort enthält jedoch nur 2 for-Schleifen:

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

Probieren Sie es online!

x86 .COM Funktion, 12 Bytes, Cracked von 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

Eingang DX, Ausgang [DI] ~ [DI + 2 * DX-1]

Crackers Lösung:

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

Beabsichtigte Lösung:

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

Python 3 , 62 Bytes, Cracked von mwchase

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

Probieren Sie es online!

Ich fühle mich wie dieses wird zu einfach sein ...

Die Sequenz ist die Fibonacci-Sequenz f(n) = f(n-1) + f(n-2)mitf(0) = f(1) = 1

Gol> <> , 15 Bytes, geknackt von mbomb007

I1AZZ;
M:K:?ZNB

Probieren Sie es online!

Die Serie ist 0,1,2,3,4,5 aber auf jedes Element folgen so viele Nullen.

Die ersten Werte sind beispielsweise:

 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 Bytes, Gebrochen

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

Probieren Sie es online!

Gibt die ersten n Elemente in einem umgekehrten Array zurück

Windows .BAT, 80 Bytes

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

Verwendung:

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

Die Schleifenversion kann im aktuellen Wörterbuch annehmen, muss aber initialisiert oder zurückgesetzt werden

Python, 82 Bytes; geknackt

Dies ist eine rekursive Python-Implementierung der OEIS-Sequenz A004001 in 82 Bytes. Weitere Hintergrundinformationen zu dieser Serie finden Sie in Wolframs Mathworld .

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

Die ersten 30 Zahlen in dieser Reihenfolge sind:

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