This challenge is about recursion (Cops' thread)

Question

Cops' thread

In this thread, your task is to make a recursion-based program/function to generate any integer series. Robbers will try and find a shorter non-recursive solution over in the Robbers' thread.

Challenge synopsis

In many languages, recursive functions can significantly simplify a programming task. However, the syntax overhead for a proper recursion may limits its usability in code-golf.

The cops will create a program or function taking a single integer n, which will generate the first n entries of an integer series, using only recursion¹. They should also make sure there is a shorter nonrecursive way to generate the sequence in order to mark their entry as safe.

The robbers will try to find a shorter program or function in the same language, generating the same integer series, using no recursion².

If the cops' submission is not cracked within ten days (240 hours), the cop will prove it was in fact possible to have a shorter non-recursive approach by revealing their own solution. They may then mark their submission as safe.

The winner of the cops challenge will be the shortest (according to code-golf) recursion-based submission marked safe.

The winner of the robbers challenge will be the robber who cracked the most solutions.

^{1: It only needs to be recursive in syntax; you don't need to worry about for example tail call optimization.}

^{2: Again, non-recursive in syntax; so you can't post a recursive solution and claim its compiled to a loop thanks to tail call optimization.}

Submission requirements

Each submission will take a single integer n (zero- or one-based). The submission will then output or return the first n entries of an integer series of choice. (note that this integer series must not depend on n). The input and output method may differ between the recursive and non-recursive approach. The integer series may be any deterministic series with a length of at least 5. The series should be explained properly.

Your submission does not have to work for arbitrary large n, but should work for at least n=5. The non-recursive approach must be able to work up to at least the same n as the recursive approach, or up to n=2^15-1, whichever is smaller.

Recursion

For the sake of this challenge, recursion is defined as creating the desired sequence using a function (or function-like construct) that calls itself (or calls a sequence of functions that ends up calling itself; this includes constructs like the Y combinator). The recursion depth should go to infinity as n goes to infinity. The non-recursive approach is anything that is not recursive.

For Thyme where for is done by recursive behind, is for recursive or loop? — l4m2, Mar 7, 2018 at 3:27
Can I say a code works for arbitrarily large n if it's theoretically correct, but it cannot be run due to time or memory constraints? — Bubbler, Mar 7, 2018 at 6:39
@l4m2 Not all languages can compete. It seems like this language does not have a native way of not using recursion (unless xfor is available through some kind of import?) so perhaps this language cannot compete. — Sanchises, Mar 7, 2018 at 7:27
A recursive that don't go that much when n go large, is it a recursive? — l4m2, Mar 7, 2018 at 14:21

Bubbler · Accepted Answer · 2018-03-18 23:16:24Z

Python 3, 65 bytes (Safe)

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)

Try it online!

Another try in Python.

The sequence is "the number of ways to fill a 2-by-n board with dominoes in three colors, so that no two same-colored dominoes touch each other". Not on OEIS.

Let's say n=6. The board looks like:

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

and these are valid domino tilings in three colors (1-3 represent a color each):

123123 122331 212332 212121 113311
123123 133221 212112 212121 331133

but these are not (two same-colored dominoes are touching each other):

112323 332333 211113
112323 112311 233223

The sequence counts all possible domino tilings that satisfy the rules for each n.

Intended solution, 58 bytes

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

Try it online!

Unfortunately it looks like no one bothered to simplify the recurrence relation, which was clearly shown in the recursive code. Making a program with the given double recurrence as-is doesn't work since it's Python 3.

Could you give a more detail explain on the sequence please. — tsh, Mar 8, 2018 at 11:27

l4m2 · Accepted Answer · 2018-03-06 15:06:42Z

2

Octave, 47 bytes, cracked by l4m2

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

Try it online!

As an example, here is an Octave entry which generates the first n positive integers, https://oeis.org/A000027.

edited Mar 6, 2018 at 15:06

l4m2

17.1k1 gold badge17 silver badges72 bronze badges

answered Mar 6, 2018 at 10:19

Sanchises

9,4161 gold badge34 silver badges61 bronze badges

\$\begingroup\$ Cracked. +1 for making a recursive anonymous function though... Not often those are used :) \$\endgroup\$
– Stewie Griffin
Mar 6, 2018 at 14:13
\$\begingroup\$ @StewieGriffin I absolutely love golfing recursive anonymous functions in Octave, although they never turn out shorter than their loop-based version. The reverse of this challenge would definitely be a challenge in Octave for the cops. \$\endgroup\$
– Sanchises
Mar 6, 2018 at 14:23
\$\begingroup\$ @StewieGriffin Not sure if the ping in chat worked, by the way, but l4m2 beat you to it. \$\endgroup\$
– Sanchises
Mar 6, 2018 at 14:40

Add a comment |

Bubbler · Accepted Answer · 2018-03-07 07:40:48Z

2

Python 3, 75 bytes, cracked by 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}))

Try it online!

The famous Hamming numbers, a.k.a. 5-smooth numbers (A051037).

Cracked solution, 51 bytes

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

Try it online!

Intended solution, 74 bytes

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

Try it online!

edited Mar 7, 2018 at 7:40

answered Mar 7, 2018 at 6:53

Bubbler

70.3k5 gold badges139 silver badges428 bronze badges

\$\begingroup\$ Cracked? \$\endgroup\$
– xnor
Mar 7, 2018 at 7:26

Add a comment |

mbomb007 · Accepted Answer · 2018-03-12 16:45:22Z

2

Forth (gforth), 39 bytes, cracked by NieDzejkob

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

Try it online!

edited Mar 12, 2018 at 16:45

mbomb007

23.2k6 gold badges60 silver badges134 bronze badges

answered Mar 6, 2018 at 14:05

jmarkmurphy

1712 silver badges6 bronze badges

1

\$\begingroup\$ You're allowed different integer series than [1,2,...,n], you know that right? \$\endgroup\$
– Sanchises
Mar 6, 2018 at 15:19
\$\begingroup\$ Cracked \$\endgroup\$
– Maya
Mar 6, 2018 at 16:47
\$\begingroup\$ I thought about that because the crack is just a google search away for counted loops using forth. But really whatever is inside the function can be easily recreated inside the loop anyway. \$\endgroup\$
– jmarkmurphy
Mar 6, 2018 at 18:55

Add a comment |

fergusq · Accepted Answer · 2018-03-13 09:02:36Z

Röda, 40 bytes

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

Try it online!

This function gives the following finite sequence (the 90 first Fibonacci numbers):

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

I know it can generate more Fibonacci numbers, but for purposes of this challenge it is enough to produce these numbers.

Shieru Asakoto · Accepted Answer · 2018-03-06 15:07:58Z

1

JavaScript (Node.js), 91 bytes, Cracked by 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]

Try it online!

Prints the first n terms of the OEIS sequence A022559 (starting from i=1).

l4m2 fit 3 for loops into 74 72 bytes and cracked my cop post:

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

However, my intended answer actually has only 2 for loops:

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

Try it online!

edited Mar 6, 2018 at 15:07

answered Mar 6, 2018 at 12:15

Shieru Asakoto

6,12813 silver badges40 bronze badges

\$\begingroup\$ hacked \$\endgroup\$
– l4m2
Mar 6, 2018 at 14:24
\$\begingroup\$ @l4m2 Actually I have a 73-byte one ;) Anyway congrats \$\endgroup\$
– Shieru Asakoto
Mar 6, 2018 at 14:29
\$\begingroup\$ Go on golfing guy It's now 72 @user71546 \$\endgroup\$
– l4m2
Mar 6, 2018 at 14:55

Add a comment |

l4m2 · Accepted Answer · 2018-03-11 03:51:17Z

1

x86 .COM function, 12 bytes, Cracked by 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

Input DX, Output [DI] ~ [DI+2*DX-1]

Cracker's solution:

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

Intended solution:

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

edited Mar 11, 2018 at 3:51

answered Mar 6, 2018 at 14:42

l4m2

17.1k1 gold badge17 silver badges72 bronze badges

\$\begingroup\$ Cracked \$\endgroup\$
– Maya
Mar 6, 2018 at 16:41
\$\begingroup\$ I've changed the output method. Can you look? \$\endgroup\$
– Maya
Mar 10, 2018 at 20:57

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

Python 3, 62 bytes, Cracked by mwchase

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

Try it online!

I feel like this one is going to be too easy...

The sequence is the Fibonacci sequence f(n) = f(n-1) + f(n-2) with f(0) = f(1) = 1

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Mar 9, 2018 at 19:49

PunPun1000

9834 silver badges7 bronze badges

\$\begingroup\$ You can switch to an inline ternary statement made out of boolean operators, which puts it in one statement, which can then go directly after the colon. Saves eight bytes, at least. \$\endgroup\$
– mwchase
Mar 9, 2018 at 21:13
\$\begingroup\$ Switching to lambda saves two (EDIT: four) more. \$\endgroup\$
– mwchase
Mar 9, 2018 at 23:12
2

\$\begingroup\$ @mwchase while I appreciate your suggestions and will keep them in mind for future python code golf submissions, I will not be golfing a cops and robbers submission for a couple of reasons. First if I continue to golf it then it sets a moving target for the robber, which is not desired in this type of post. Second golfing this would mean I would need to golf my iterative version as well, which I might not be able to do to the same extent \$\endgroup\$
– PunPun1000
Mar 9, 2018 at 23:15
\$\begingroup\$ cracked \$\endgroup\$
– mwchase
Mar 10, 2018 at 3:21

Add a comment |

Jo King · Accepted Answer · 2018-03-12 21:44:01Z

1

Gol><>, 15 bytes, cracked by mbomb007

I1AZZ;
M:K:?ZNB

Try it online!

The series is 0,1,2,3,4,5 but each element is followed by that many 0s.

For example, the first few values are:

 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.

edited Mar 12, 2018 at 21:44

answered Mar 9, 2018 at 1:17

Jo King♦

46.8k5 gold badges122 silver badges183 bronze badges

\$\begingroup\$ Cracked \$\endgroup\$
– mbomb007
Mar 12, 2018 at 19:14

Add a comment |

Steadybox · Accepted Answer · 2018-03-11 11:24:43Z

0

JavaScript, 63 bytes, Cracked

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

Try it online!

Returns the first n elements in a reversed array

edited Mar 11, 2018 at 11:24

Steadybox

16.4k5 gold badges39 silver badges83 bronze badges

answered Mar 10, 2018 at 22:26

fəˈnɛtɪk

4,1942 gold badges13 silver badges40 bronze badges

\$\begingroup\$ Cracked \$\endgroup\$
– l4m2
Mar 11, 2018 at 7:11
\$\begingroup\$ Also reversed array returning seem currently not allowed \$\endgroup\$
– l4m2
Mar 11, 2018 at 7:48

Add a comment |

l4m2 · Accepted Answer · 2018-03-12 18:22:08Z

0

Windows .BAT, 80 Bytes

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

Usage:

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

The loop version can assume in the current dictionary, but have to init or reset

edited Mar 12, 2018 at 18:22

answered Mar 11, 2018 at 7:06

l4m2

17.1k1 gold badge17 silver badges72 bronze badges

Add a comment |

agtoever · Accepted Answer · 2018-03-14 10:39:06Z

0

Python, 82 bytes; cracked

This is a recursive Python implementation of OEIS sequence A004001 in 82 bytes. More background on this series can be found on Wolfram's 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]]

The first 30 numbers in this sequence are:

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

edited Mar 14, 2018 at 10:39

answered Mar 14, 2018 at 8:18

agtoever

2,88111 silver badges32 bronze badges

\$\begingroup\$ Cracked \$\endgroup\$
– l4m2
Mar 14, 2018 at 9:14

Add a comment |

Stack Exchange Network

This challenge is about recursion (Cops' thread)

Cops' thread

Challenge synopsis

Submission requirements

Recursion

12 Answers 12

Python 3, 65 bytes (Safe)

Intended solution, 58 bytes

Octave, 47 bytes, cracked by l4m2

Python 3, 75 bytes, cracked by xnor

Cracked solution, 51 bytes

Intended solution, 74 bytes

Forth (gforth), 39 bytes, cracked by NieDzejkob

Röda, 40 bytes

JavaScript (Node.js), 91 bytes, Cracked by l4m2

x86 .COM function, 12 bytes, Cracked by NieDzejkob

Python 3, 62 bytes, Cracked by mwchase

Gol><>, 15 bytes, cracked by mbomb007

JavaScript, 63 bytes, Cracked

Windows .BAT, 80 Bytes

Python, 82 bytes; cracked

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
sequence
cops-and-robbers
or ask your own question.

Linked

Hot Network Questions

This challenge is about recursion (Cops' thread)

Cops' thread

Challenge synopsis

Submission requirements

Recursion

12 Answers 12

Python 3, 65 bytes (Safe)

Intended solution, 58 bytes

Octave, 47 bytes, cracked by l4m2

Python 3, 75 bytes, cracked by xnor

Cracked solution, 51 bytes

Intended solution, 74 bytes

Forth (gforth), 39 bytes, cracked by NieDzejkob

Röda, 40 bytes

JavaScript (Node.js), 91 bytes, Cracked by l4m2

x86 .COM function, 12 bytes, Cracked by NieDzejkob

Python 3, 62 bytes, Cracked by mwchase

Gol><>, 15 bytes, cracked by mbomb007

JavaScript, 63 bytes, Cracked

Windows .BAT, 80 Bytes

Python, 82 bytes; cracked

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfsequencecops-and-robbers or ask your own question.

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
sequence
cops-and-robbers
or ask your own question.