11
\$\begingroup\$

The goal is to calculate all the squares up to x with addition and subtraction.

Rules:

  1. The code must be a function which takes the total number of squares to generate, and returns an array containing all those squares.
  2. You can not use strings, structures, multiplication, division, or built-in functions for calculating squares.
  3. You can only use arrays, integers (whole numbers), addition, subtraction. No other operators allowed!

This is a question, so the shortest code in bytes wins!

\$\endgroup\$
  • \$\begingroup\$ This is essentially Most optimized algorithm for incrementing squares - or, at least, will get pretty much identical answers. \$\endgroup\$ – Peter Taylor Feb 22 '14 at 20:24
  • 2
    \$\begingroup\$ @PeterTaylor No, it's not the same, as that's for the most optimised algorithm for incrementing squares, but my question asks for only addition and subtraction. \$\endgroup\$ – Toothbrush Feb 22 '14 at 20:29
  • \$\begingroup\$ Which is the same thing. As witness: the present answer to this question does exactly the same as the vast majority of answers to the previous question. \$\endgroup\$ – Peter Taylor Feb 22 '14 at 20:36
  • \$\begingroup\$ @PeterTaylor I might be biased, but I really don't think it's at all the same. \$\endgroup\$ – Toothbrush Feb 22 '14 at 20:37
  • 3
    \$\begingroup\$ This question may already have answers elsewhere, but that does not make the question a duplicate of the other question. \$\endgroup\$ – Blacklight Shining Feb 23 '14 at 14:06

23 Answers 23

6
\$\begingroup\$

APL - 10

{+\1++⍨⍳⍵}

Example usage:

{+\1++⍨⍳⍵}10
1 4 9 16 25 36 49 64 81 100

ngn APL demo

\$\endgroup\$
  • \$\begingroup\$ Save three bytes: +\1+⍳+⍳ \$\endgroup\$ – Adám Jun 12 '17 at 19:43
6
\$\begingroup\$

C, 55 52 bytes

int s(int n,int*r){for(int i=0,j=-1;n--;*r++=i+=j+=2);}

simply sums odd numbers

  • n: number of squares to compute
  • r: output array for storing the results
  • j: takes the successive values 1, 3, 5, 7, ...
  • i: is incremented by j on each iteration

Edit

4 chars can be saved using the implicit int declaration (>C99), but this costs 1 char because for initializers cannot contain a declaration in >C99. Then the code becomes

s(int n,int*r){int i=0,j=-1;for(;n--;*r++=i+=j+=2);}

Usage

void main() {
    int r[20];
    s(20, r);
    for (int i = 0; i < 20 ; ++i) printf("%d\n", r[i]);
}  

Output

1
4
9
16
25
36
49
(...)
361
400
\$\endgroup\$
  • 1
    \$\begingroup\$ that logic is Excellent! you deserve +1 \$\endgroup\$ – Mukul Kumar Feb 25 '14 at 16:53
5
\$\begingroup\$

GolfScript, 17 characters

{[,{.+(1$+}*]}:F;

Usage (see also examples online):

10 F     # => [0 1 4 9 16 25 36 49 64 81]

Note: * is a loop and not the multiplication operator.

\$\endgroup\$
  • \$\begingroup\$ OK; how does it work? \$\endgroup\$ – Toothbrush Feb 23 '14 at 21:10
  • \$\begingroup\$ @toothbrush , takes the input and converts it to the array [0 1 ... n-1]. Then * injects the given code-block into the array. This block first doubles the current item (.+) subtracts one (() and then adds the previous result 1$+ (in other words, add 2j-1 to the previous square number). [] encloses everything in order to return a new array. \$\endgroup\$ – Howard Feb 24 '14 at 9:18
  • \$\begingroup\$ Great! I don't know GolfScript, so I wondered how it worked. \$\endgroup\$ – Toothbrush Feb 24 '14 at 9:41
5
\$\begingroup\$

Windows Batch, 115 bytes

setlocal enabledelayedexpansion&for /l %%i in (1 1 %1)do (set a=&for /l %%j in (1 1 %%i)do set /a a+=%%i
echo.!a!)

This should be placed in a batch file instead of being run from cmd, and it outputs the list to the console. It takes the number of squares to create from the first command-line argument. For the most part it uses & instead of newlines, one is still needed however and it counts as two bytes.

It needs delayed variable expansion enabled, this can be done with cmd /v:on. Assuming it's not, an extra setlocal enabledelayedexpansion& was needed at the start (without it the script is 83 bytes).

\$\endgroup\$
4
\$\begingroup\$

Haskell - 30

f n=scanl1(\x y->x+y+y-1)[1..n]

This uses the fact that (n+1)^2=n^2+2n+1

\$\endgroup\$
4
\$\begingroup\$

Perl, 27 bytes

sub{map{$a+=$_+$_-1}1..pop}

Math:

Math

Script for calling the function to print 10 squares:

#!/usr/bin/env perl
$square = sub{map{$a+=$_+$_-1}1..pop};
use Data::Dumper;
@result = &$square(10);
print Dumper \@result;

Result:

$VAR1 = [
          1,
          4,
          9,
          16,
          25,
          36,
          49,
          64,
          81,
          100
        ];

Edits:

\$\endgroup\$
  • \$\begingroup\$ I see no reason why you need to name your sub. IOW "sub{map{$a+=$_+$_-1}1..shift}" seems legit to me, and saves you two chars. \$\endgroup\$ – skibrianski Mar 19 '14 at 18:14
  • \$\begingroup\$ @skibrianski: An anonymous function is also a function. The downside is that the calling of the function is a little more cumbersome. \$\endgroup\$ – Heiko Oberdiek Mar 21 '14 at 12:05
  • \$\begingroup\$ Right, but that's on the caller. There are entries in other languages that define anonymous subs, so I think you're safe =) \$\endgroup\$ – skibrianski Mar 21 '14 at 16:57
  • \$\begingroup\$ And you can save another 2 chars by using pop() instead of shift() since there's only one argument. \$\endgroup\$ – skibrianski Mar 21 '14 at 17:00
  • \$\begingroup\$ @skibrianski: Right, thanks. \$\endgroup\$ – Heiko Oberdiek Mar 21 '14 at 17:26
4
\$\begingroup\$

JavaScript - 32 Characters

for(a=[k=i=0];i<x;)a[i]=k+=i+++i

Assumes a variable x exists and creates an array a of squares for values 1..x.

ECMAScript 6 - 27 Characters

b=[f=i=>b[i]=i&&i+--i+f(i)]

Calling f(x) will populate the array b with the squares for values 0..x.

\$\endgroup\$
  • \$\begingroup\$ I have to ask... the i+++i at the end...? \$\endgroup\$ – WallyWest Mar 3 '14 at 11:53
  • 2
    \$\begingroup\$ k+=i+++i is the same as k += i + (++i) which is the same as k+=i+i+1 followed by i=i+1 \$\endgroup\$ – MT0 Mar 3 '14 at 18:20
  • \$\begingroup\$ Oh that is genius... I've gotta implement that in my next codegolf if needed! :) \$\endgroup\$ – WallyWest Mar 3 '14 at 23:18
  • \$\begingroup\$ You can save one character by moving the function declaration to inside the array (e.g. b=[f=i=>b[i]=i&&i+--i+f(i)]). \$\endgroup\$ – Toothbrush Apr 1 '14 at 8:27
  • \$\begingroup\$ Thanks - saved one character on the top answer too by moving things round to remove a semi-colon. \$\endgroup\$ – MT0 Apr 1 '14 at 8:48
4
\$\begingroup\$

Julia - 33

Any square number can be written by a summation of odd numbers:

julia> f(x,s=0)=[s+=i for i=1:2:(x+x-1)];f(5)
5-element Array{Int64,1}:
  1
  4
  9
 16
 25
\$\endgroup\$
  • \$\begingroup\$ Hi, and welcome to CG.se! Nice, succinct answer. Never heard of Julia, but it looks intriguing. \$\endgroup\$ – Jonathan Van Matre Feb 28 '14 at 21:18
  • \$\begingroup\$ Isn't "2x" a multiplication in Julia? You could say x+x instead, which will cost you just one byte. \$\endgroup\$ – Glenn Randers-Pehrson Feb 28 '14 at 22:06
  • \$\begingroup\$ You are right (didnt notice), edited. \$\endgroup\$ – CCP Feb 28 '14 at 22:07
  • \$\begingroup\$ I'm not familiar (yet) with julia, but looked it up in the online manual at docs.julialang.org/en/release-0.2 and found "Numeric Literal Coefficients: To make common numeric formulas and expressions clearer, Julia allows variables to be immediately preceded by a numeric literal, implying multiplication." So yeah, 2x is a multiplication. \$\endgroup\$ – Glenn Randers-Pehrson Feb 28 '14 at 22:17
2
\$\begingroup\$

C++ 99 81 78 80 78

int* f(int x){int a[x],i=1;a[0]=1;while(i<x)a[i++]=a[--i]+(++i)+i+1;return a;}  

my first try in code-golf

this code is based on
a = 2 x n - 1
where n is term count and a is n th term in the following series
1, 3, 5, 9, 11, 13, .....
sum of first 2 terms = 2 squared

sum of first 3 terms = 3 squared
and so on...

\$\endgroup\$
  • 2
    \$\begingroup\$ I think you can remove the braces {} after the for loop, since there is only one statement. This can reduce your char count by 2 \$\endgroup\$ – ace_HongKongIndependence Feb 23 '14 at 11:14
  • 1
    \$\begingroup\$ If you declare arrays of non-constant size in some function other than main() then it's acceptable \$\endgroup\$ – Mukul Kumar Feb 23 '14 at 18:04
  • 1
    \$\begingroup\$ This code has undefined behaviour. \$\endgroup\$ – Kerrek SB Feb 25 '14 at 9:13
  • 1
    \$\begingroup\$ and returns pointer to data on stack destroyed during the return. \$\endgroup\$ – V-X Feb 25 '14 at 14:42
  • 1
    \$\begingroup\$ @MukulKumar addition, subtraction, I'm only using those \$\endgroup\$ – mniip Feb 27 '14 at 17:05
2
\$\begingroup\$

DCPU-16 Assembly (90 bytes)

I wrote this in assembly for a fictional processor, because why not?

:l
ADD I,1
SET B,0
SET J,0
:m
ADD J,1
ADD B,I
IFL J,I
SET PC,m
SET PUSH,B
IFL I,X
SET PC,l

The number is expected to be in the X register, and other registers are expected to be 0. Results are pushed to the stack, it will break once it reaches 65535 due to the 16 bit architecture. You may want to add a SUB PC, 1 to the end to test it. Compiled, the program should be 20 bytes (10 words).

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

Haskell

f x=take x [iterate (+y) 0 !! y | y<- [0..]]

This basically invents multiplication, uses it own itself, and maps it over all numbers. f 10 = [0,1,4,9,16,25,36,49,64,81]. Also f 91 = [0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400,441,484,529,576,625,676,729,784,841,900,961,1024,1089,1156,1225,1296,1369,1444,1521,1600,1681,1764,1849,1936,2025,2116,2209,2304,2401,2500,2601,2704,2809,2916,3025,3136,3249,3364,3481,3600,3721,3844,3969,4096,4225,4356,4489,4624,4761,4900,5041,5184,5329,5476,5625,5776,5929,6084,6241,6400,6561,6724,6889,7056,7225,7396,7569,7744,7921,8100].

\$\endgroup\$
  • \$\begingroup\$ Can you extend the demo to a little larger than 10? \$\endgroup\$ – Glenn Randers-Pehrson Mar 2 '14 at 22:43
2
\$\begingroup\$

Haskell, 34 / 23

n#m=m+n:(n+2)#(m+n)
f n=take n$1#0

or, if imports are okay:

f n=scanl1(+)[1,3..n+n]

Output:

λ> f 8
[1,4,9,16,25,36,49,64]
\$\endgroup\$
1
\$\begingroup\$

Javascript 47

function f(n,a){return a[n]=n?f(n-1,a)+n+n-1:0}

r=[];f(12,r);console.log(r) returns :
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144]

\$\endgroup\$
  • \$\begingroup\$ Great! In EcmaScript 6: f=(n,a)=>a[n]=n?f(n-1,a)+n+n-1:0. \$\endgroup\$ – Toothbrush Feb 22 '14 at 21:12
  • 1
    \$\begingroup\$ I really can't wait for ECMAScript 6 to really enter mainstream use. That would be the perfect excuse to learn it. \$\endgroup\$ – Isiah Meadows Feb 23 '14 at 8:20
  • 1
    \$\begingroup\$ The Arrow Function part of the ECMAScript 6 specification has been in FireFox since version 22. \$\endgroup\$ – MT0 Feb 28 '14 at 22:50
1
\$\begingroup\$

Smalltalk, 52

f:=[:n||s|(s:=1)to:n collect:[:i|x:=s.s:=s+i+i+1.x]]

Returns a new array (i.e. does not fill or add to an existing one).

call:

f value:10

-> #(1 4 9 16 25 36 49 64 81 100)

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

python - 39

a=0
for i in range(5):a+=i+i+1;print(a)

Replace 5 with any value. Any suggestions?

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

Bash - 92 85 62 61 59 57

declare -i k=1;for((i=0;i++<$1;k+=i+i+1));do echo $k;done

Result:

$ ./squares.sh 10
1
4
9
16
25
36
49
64
81
100

Edit: I replaced the inner loop with the algorithm from @mniip's Haskell solution.

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

Same method as above, in APL and J:

APL: F←{+\1+V+V←¯1+⍳⍵} (17 characters) works with most APL variants (try it here)

and even less (only 14 characters) with NGN APL: F←{+\1+V+V←⍳⍵} (see here)

J: f=:+/\@(>:@+:@:i.) (18 characters)

edit: better solution in APL: F←{+\¯1+V+V←⍳⍵} (15 characters)

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

C# (82)

int[] s(int n){int i,p=0;var r=new int[n];while(i<n){p+=i+i+1;r[i++]=p;}return r;}
\$\endgroup\$
1
\$\begingroup\$

C# - 93

int[]s(int l){int[]w=new int[l];while(l>=0){int i=0;while(i<l){w[l-1]+=l;i++;}l--;}return w;}

When called from another method of the same class, will return the array - [1,4,9,16,25,36...], up to lth element.

\$\endgroup\$
  • \$\begingroup\$ did you try removing the spaces between int[] and sq? I don't know C#, but I think it should work. \$\endgroup\$ – ace_HongKongIndependence Feb 25 '14 at 8:18
  • \$\begingroup\$ No, that wont work. First int[] is the return type of method "sq". I can reduce the method name to may be just "s" :) \$\endgroup\$ – Rajesh Feb 25 '14 at 9:16
  • \$\begingroup\$ I mean using int[]sq instead of int[] sq and int[]res instead of int[] res. This helps you save two chars, and I didn't get any compilation errors with that. Also you should use single character identifiers for sq and res as you suggested. \$\endgroup\$ – ace_HongKongIndependence Feb 25 '14 at 11:07
  • \$\begingroup\$ seems like there's something wrong with your answer \$\endgroup\$ – ace_HongKongIndependence Feb 26 '14 at 8:03
  • \$\begingroup\$ Indent code with 4 spaces to put it in a code-block with monospace font. \$\endgroup\$ – luser droog Mar 1 '14 at 10:41
1
\$\begingroup\$

Fortran II|IV|66|77, 134 122 109 105

  SUBROUTINES(N,M)
  INTEGERM(N)
  K=0
  DO1I=1,N
  K=K+I+I-1
1 M(I)=K
  END

Edit: removed inner loop and used @mniip's Haskell algorithm instead.

Edit: Verified that the subroutine and driver are valid Fortran II and IV

Driver:

  INTEGER M(100)
  READ(5,3)N
  IF(N)5,5,1
1 IF(N-100)2,2,5
2 CALLS(N,M)
  WRITE(6,4)(M(I),I=1,N)
3 FORMAT(I3)
4 FORMAT(10I6)
  STOP  
5 STOP1
  END

Result:

$ echo 20 | ./a.out
   1     4     9    16    25    36    49    64    81   100
 121   144   169   196   225   256   289   324   361   400
\$\endgroup\$
  • \$\begingroup\$ @mniip, thanks, I replaced my inner loop with your code. \$\endgroup\$ – Glenn Randers-Pehrson Feb 25 '14 at 20:59
1
\$\begingroup\$

Python - 51

Here I'm defining a function as requested by the rules.

Using sum of odd numbers:

f=lambda n:[sum(range(1,i+i+3,2))for i in range(n)]

This only uses sum (a builtin which performs addition) and range (a builtin which creates arrays using addition). If you object to sum, we can do this with reduce:

def g(n):v=[];reduce(lambda x,y:v.append(x) or x+y,range(1,i+i+3,2));return v
\$\endgroup\$
1
\$\begingroup\$

PHP, 92 bytes

This needs to have the "short tags" option enabled, of course (to shave off 3 bytes at the start).

<? $x=100;$a=1;$r=0;while($r<=$x){if($r){echo"$r ";}for($i=0,$r=0;$i<$a;$i++){$r+=$a;}$a++;}

Output:

1 4 9 16 25 36 49 64 81 100 
\$\endgroup\$
1
\$\begingroup\$

Forth - 48 bytes

: f 1+ 0 do i 0 i 0 do over + loop . drop loop ;

Usage:

7 f

Output:

0 1 4 9 16 25 36 49
\$\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.