4
\$\begingroup\$

Robbers thread

In this thread, your task is to find a non-recursive solution which produces the same integer series of a submission not marked as 'safe' in the Cops' 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.1.

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

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 ) 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.

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 the same integer series as the cops' entry. The input and output method may differ between the recursive and non-recursive approach.

Your robbers' entry must be strictly shorter in byte-count than the recursive solution. It must work for at least the same n, 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). The recursion depth should go to infinity as n goes to infinity. The non-recursive approach is anything that is not recursive.

\$\endgroup\$

10 Answers 10

3
\$\begingroup\$

Octave, by Sanchises 27 bytes

There are so many, many ways to do this in a loopy-way. For instance this one, if an explicit loop is needed:

for i=1:input('')disp(i)end

Try it online!

Or, if you want to create a vector (I haven't golfed this terribly well, since using a loop like this is kinda pointless):

x=0;for i=1:input(''),x(i)=i;end,x

Or 7 bytes if it's OK to not use a loop at all:

@(n)1:n
\$\endgroup\$
3
\$\begingroup\$

Python 3, 75 bytes by Bubbler

Python 3, 51 bytes

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

Try it online!

Tests for 5-smoothness of k with 60**k%k<1.

\$\endgroup\$
  • \$\begingroup\$ You may have missed my comment, but I consider using the Y combinator a recursive solution. \$\endgroup\$ – Sanchises Mar 7 '18 at 7:28
  • \$\begingroup\$ The robber's solution should be shorter than the cop's, so Y combinator doesn't work in general anyway. \$\endgroup\$ – Bubbler Mar 7 '18 at 7:29
  • \$\begingroup\$ @Sanchises I only saw your comment after posting this. I think this is non-recursive by all definitions I've seen, so I think you should define what it means more cleanly. But I had missed that the new solution needs to be shorter, so the Y combinator method shouldn't work in general. \$\endgroup\$ – xnor Mar 7 '18 at 7:31
  • \$\begingroup\$ But the second solution looks good though the current upper bound doesn't work at n>=1000 or so; you can throw in 2**n for correctness, then I'll mark my solution as cracked. \$\endgroup\$ – Bubbler Mar 7 '18 at 7:33
  • \$\begingroup\$ @xnor Interesting, I would've never considered that non-recursive. Any ideas for a good definition which really encompasses the "nested function"-ness that is typical of recursion, whether true recursion or via a helper function? \$\endgroup\$ – Sanchises Mar 7 '18 at 7:43
1
\$\begingroup\$

JavaScript (Node.js), by user71546, 74 72 Bytes

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

Gol><> by Jo King, 12 bytes iterative

I:FL:R0|rRN;

Try it online

Makes good use of R, the repeat command. Once I thought of this method, I knew it would be shorter than trying to use a for loop within a while loop.

Explanation:

I:              Input and duplicate (will be used at the end to print). 
  F             For loop input times. 
   L:           Push and duplicate loop counter (leaving one on the stack). 
     R0         Pop counter and push that many zeros. 
       |        End of loop. 
        r       Reverse the stack. 
         RN;    Print input times and halt.

List of language commands (D debug is useful for understanding what is going on)

Golfish

\$\endgroup\$
1
\$\begingroup\$

https://codegolf.stackexchange.com/a/158075/76323, 78 Bytes

def A(n):
 x=[1]*n
 for i in range(2,n):x[i]=x[x[i-1]-1]+x[i-x[i-1]]
 return x
\$\endgroup\$
0
\$\begingroup\$

https://codegolf.stackexchange.com/a/157397/76323, 7 bytes assuming it's not recursive

@(n)1:n

or if use for,

function o=f(n);for i=1:n;disp(i);end;end;
\$\endgroup\$
0
\$\begingroup\$

Forth (gforth), by jmarkmurphy, 22 bytes iterative

: | 0 do i 1+ . loop ;

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Python 3 by PunPun1000, 59 bytes iterative

def f(x):
 l=[1]
 while x>0:l+=[sum(l[-2:])];x-=1
 return l

I tried my hardest to do a closed-form one-liner, but I only got as low as the original submission.

\$\endgroup\$
  • \$\begingroup\$ Couldn’t you just do while x: rather than x>0? \$\endgroup\$ – Jo King Mar 10 '18 at 4:07
  • \$\begingroup\$ @JoKing Probably. I was basing this off the original code, and I wasn't sure what some of the intent was. \$\endgroup\$ – mwchase Mar 10 '18 at 15:59
0
\$\begingroup\$

COM function, by l4m2, 11 bytes iterative

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

Input CX, output [ES:1] ~ [ES:2*CX] (inclusive)

\$\endgroup\$
  • \$\begingroup\$ Is backward array allowed? \$\endgroup\$ – l4m2 Mar 6 '18 at 16:52
  • \$\begingroup\$ @l4m2 I don't see a reason for it to be not allowed, but if you insist, std is one byte. \$\endgroup\$ – NieDzejkob Mar 6 '18 at 17:13
  • \$\begingroup\$ Asked about that on meta \$\endgroup\$ – l4m2 Mar 6 '18 at 17:18
  • \$\begingroup\$ meta leads to Default for Code Golf: Input/Output methods where only codegolf.meta.stackexchange.com/a/13262/76323 matters \$\endgroup\$ – l4m2 Mar 6 '18 at 20:05
0
\$\begingroup\$

JavaScript (Node.js), 45 bytes

x=>[...Array(x)].map(_=>h=h&1?3*h+1:h/2,h=14)

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.