6
\$\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\$
12
  • \$\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\$ Commented Apr 15, 2012 at 15:05
  • \$\begingroup\$ What about conditionals, Boolean negation, etc? \$\endgroup\$ Commented Apr 15, 2012 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\$ Commented Apr 15, 2012 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
    Commented Dec 19, 2016 at 22:07
  • 1
    \$\begingroup\$ @HatWizard in little endian. ... not a bad point. \$\endgroup\$
    – DELETE_ME
    Commented Jun 7, 2018 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
  • 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\$ Commented Apr 12, 2018 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\$
7
  • \$\begingroup\$ By using a(n){return(n-n/2*2)*(2-n+n/4*4);} you can shave off two characters. \$\endgroup\$
    – Superbest
    Commented May 2, 2012 at 22:10
  • \$\begingroup\$ @Superbest, this gives the series shifted by one position. Close, but not it. \$\endgroup\$
    – ugoren
    Commented May 3, 2012 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
    Commented May 3, 2012 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
    Commented May 3, 2012 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
    Commented May 3, 2012 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\$
3
  • \$\begingroup\$ I think that operator .real is not supported by the rules. You may use (j**n+(-j)**n)/2 instead. \$\endgroup\$
    – Howard
    Commented Apr 16, 2012 at 4:04
  • 1
    \$\begingroup\$ Should be 1j**-n. \$\endgroup\$
    – lirtosiast
    Commented Aug 8, 2015 at 4:31
  • \$\begingroup\$ 1j**-n instead of (-1j)**n saves 2 bytes. \$\endgroup\$
    – Dennis
    Commented Mar 30, 2018 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\$
2
  • \$\begingroup\$ I think you should spend a semicolon after your code. Otherwise it interferes with the input to your program. \$\endgroup\$
    – Howard
    Commented Apr 16, 2012 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\$ Commented Apr 16, 2012 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\$
1
  • \$\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
    Commented Dec 19, 2016 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.