5
\$\begingroup\$

In the spirit of a question on math.se: given an integer n, return the integer in position n of the sequence [1, 0, -1, 0, 1, 0, -1, 0, ...]. Assume n >= 0.

Rules:

  1. You may only use the operations -x, x+y, x-y, x*y, x/y, and xy, whatever their representations are in the language you choose.
  2. Your function must be called a.
  3. Your function must run in constant time for all n.

Example:

a=lambda n:((-1)**(n*n-n)//2)+(-1)**(n*n+n)//2))//2

Non-example (uses list subscripting operation and modulo operator):

a=lambda n:[1,0,-1,0][n%4]

Non-example (uses cos operation):

from math import *;a=lambda n:int(cos(n*pi/2))

Non-example (does not run in constant time and uses if operation):

a=lambda n:-a(n-2) if n>1 else 0 if n>0 else 1

Clarifications: Both integer and float division are allowed. Your solution may return either an integer or a float (or complex number, I suppose, since some answers already used it). If your solution returns a float: your solution should, if it were to theoretically be carried out to infinite precision, give the exact answer.

\$\endgroup\$

closed as unclear what you're asking by user202729, Nissa, Sriotchilism O'Zaic, wastl, Stewie Griffin Jun 7 '18 at 8:41

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ Is the allowed x/y any kind of division (including div) or always floating point division? — Certainly, "Your function must run in constant time for all n" is limited to some reasonable limit, no need to work for bigInts? \$\endgroup\$ – ceased to turn counterclockwis Apr 15 '12 at 15:05
  • \$\begingroup\$ What about conditionals, Boolean negation, etc? \$\endgroup\$ – Peter Taylor Apr 15 '12 at 22:07
  • \$\begingroup\$ Your example uses ** and // but you didn't allow them. a) What does ** and // mean, and why can you use them? \$\endgroup\$ – user unknown Apr 15 '12 at 23:25
  • 3
    \$\begingroup\$ How does the restriction on the name of the function work in languages where functions can't be named, or where a isn't a valid function name? \$\endgroup\$ – user62131 Dec 19 '16 at 22:07
  • 1
    \$\begingroup\$ @HatWizard in little endian. ... not a bad point. \$\endgroup\$ – user202729 Jun 7 '18 at 2:54

13 Answers 13

5
\$\begingroup\$

Ruby, 26 characters

a=->n{1-(k=n-n/4*4)+k/3*2}

Example:

> p (0..10).map{|n| a[n]}
[1, 0, -1, 0, 1, 0, -1, 0, 1, 0, -1]

Note: This solution assumes that integer division / is an allowed operation.

\$\endgroup\$
  • 1
    \$\begingroup\$ I know it's been 6 years (lol..), but it can be golfed by 1 byte by reusing n instead of using a new variable k: a=->n{1-(n-=n/4*4)+n/3*2}. Try it online 25 bytes. \$\endgroup\$ – Kevin Cruijssen Apr 12 '18 at 12:53
3
\$\begingroup\$

C, 36 chars

a(n){return(1-n+n/2*2)*(1-n+n/4*4);}

The same function used by Peter Taylor.

\$\endgroup\$
  • \$\begingroup\$ By using a(n){return(n-n/2*2)*(2-n+n/4*4);} you can shave off two characters. \$\endgroup\$ – Superbest May 2 '12 at 22:10
  • \$\begingroup\$ @Superbest, this gives the series shifted by one position. Close, but not it. \$\endgroup\$ – ugoren May 3 '12 at 7:49
  • \$\begingroup\$ According to codepad.org/sO0mFkhI output from your function is 0, -1, 0, 1, 0, -1, 0, 1, 0, .... Output from mine is 1, 0, -1, 0, 1, 0, -1, 0, 1. The original question gives the example output 1, 0, -1, 0, 1, 0, -1, 0, .... \$\endgroup\$ – Superbest May 3 '12 at 9:57
  • \$\begingroup\$ @Superbest, you seem to start with n=1, I start with n=0. All examples (except the first, which gives a syntax error), give a(0)=1, like my answer. You can say your suggestion is valid, because it gives the same series starting from another position, but I'll stick with my version. \$\endgroup\$ – ugoren May 3 '12 at 13:00
  • \$\begingroup\$ Ah, that's right. I'm not sure why I thought the first one was 1 not 0. Sorry. \$\endgroup\$ – Superbest May 3 '12 at 13:14
3
\$\begingroup\$

Python, 29 chars

a=lambda n:(1j**n+(-1j)**n)/2

Kind of cheating, but fun.

Edit:

Now that we can return complex numbers, this is competitive and no longer cheating (with Howard's suggestion).

\$\endgroup\$
  • \$\begingroup\$ I think that operator .real is not supported by the rules. You may use (j**n+(-j)**n)/2 instead. \$\endgroup\$ – Howard Apr 16 '12 at 4:04
  • 1
    \$\begingroup\$ Should be 1j**-n. \$\endgroup\$ – lirtosiast Aug 8 '15 at 4:31
  • \$\begingroup\$ 1j**-n instead of (-1j)**n saves 2 bytes. \$\endgroup\$ – Dennis Mar 30 '18 at 14:35
2
\$\begingroup\$

Python, 36 chars

a=lambda n:(-1)**(n/2)*(1+(-1)**n)/2
\$\endgroup\$
2
\$\begingroup\$

J, 18 characters

a=:[:{.[:+._1^2%~]

Works, but is probably cheating by the rules set out above.

Calculates -1 to the power of the given integer divided by 2 which gives 0j1 for any odd number. The {. and the +. return the real part so that the odd numbers give 0.

Usage:

   a 1
0
   a 6
_1

Edit: After feeling a bit smug about this I've just looked properly at Keith's answers and realized I've done essentially the same thing.

\$\endgroup\$
2
\$\begingroup\$

GolfScript (20 19 chars)

{.4/4*-.3/2*)\-}:a;

This is a port of Howard's solution.

If, in addition to division, the remainder operation were permitted, this could be improved substantially (by 6 5 chars):

{.2%(\4%(*}:b;

Mathematically that's

x => (x%2 - 1) (x%4 - 1)

I can't see any logic behind excluding remainder, since it's defined in terms of permitted operations.

\$\endgroup\$
  • \$\begingroup\$ I think you should spend a semicolon after your code. Otherwise it interferes with the input to your program. \$\endgroup\$ – Howard Apr 16 '12 at 11:06
  • \$\begingroup\$ @Howard, I see your point. I think it's arguable, because the spec's badly worded, but on balance I think the leave-it-off position is weaker. \$\endgroup\$ – Peter Taylor Apr 16 '12 at 11:14
1
\$\begingroup\$

Python, 34 chars

Poor man's modulus... saves a whopping 2 chars over Keith Randall's solution. Take that! ;)

a=lambda n:(n-1-n/2*2)*(n-1-n/4*4)

edit: on reading others' solutions, this is the same as Peter Taylor's

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

bc: 28 chars

echo 'a=4;(1-a+a/2*2)*(1-a+a/4*4)' | bc
\$\endgroup\$
0
\$\begingroup\$

Python, 49 chars

a=lambda n:(lambda x:(x**3-3*x*x-x+3)/3)(n-n/4*4)

Note: In Python3 you'll have to replace n/4 with n//4 at the end.

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

8086 Assembler (14 bytes of machine code):

 ; ax holds the index into the sequence
 ; returns the sequence value in ax
 a: inc al
    shl al,6
    sar al,6
    cbw
    xor al,ah
    add al,ah
    cbw                     
    ret        
\$\endgroup\$
  • \$\begingroup\$ But in machine code, it isn't named a. The name's only used by the assembler and by the linker, so you'd have to count the length of the assembly code or the object code (unless the OP clarifies that it's ok for the function to be named 0 instead, which would be the closest analogue to the name of a function in machine code). \$\endgroup\$ – user62131 Dec 19 '16 at 22:10
0
\$\begingroup\$

TI-Basic, 12 bytes

i^Ans+i^-Ans
Ans/2

Store in prgmA and run with 5:prgmA, with the input in place of 5.

TI-Basic implicitly returns the last evaluated value.

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

Python 2, 28 bytes

a=lambda n:(n/2*2-n+1)*1j**n

Try it online!

Proof of validity for those who don't know Python:

The expression is (n/2*2-n+1)*1j**n. If you add parentheses, it becomes ((((n/2)*2)-n)+1)*(1j**n). / is integer division, since both n and 2 are integers in this case, * is multiplication, - is subtraction, + is addition and ** is exponentiation.

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

Java 8, 21 bytes

n->1-(n-=n/4*4)+n/3*2

Port of @Howard's Ruby answer.

Try it online.

\$\endgroup\$

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