Code Golf: Ulam Spiral
https://stackoverflow.com/questions/1805796
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
The Challenge
The shortest code by character count to output Ulam's spiral with a spiral size given by user input.
Ulam's spiral is one method to map prime numbers. The spiral starts from the number 1 being in the center (1 is not a prime) and generating a spiral around it, marking all prime numbers as the character '*'. A non prime will be printed as a space ''.
alt text http://liranuna.com/junk/ulam.gif
Test cases
Input:
2
Output:
* *
*
*
Input:
3
Output:
* *
* *
* **
*
*
Input:
5
Output:
* *
* *
* * *
* * *
* ** *
* *
* *
* *
* *
Code count includes input/output (i.e full program).
Solution
Golfscript - 92 Characters
~.(:S+,:R{S\-:|;R{S-:$|>' *'1/[|$.|]2/@:d|~)$<!^=~:$;:y.*4*$-y-)2d*$y-*+:$,{)$\%!},,2==}%n}%
97 characters
~.(:S+,:R{S\-:|;R{S-:$|>' *'1/[|$.|]2/@:d|~)$<!^=~:$;:y.*4*$-y-)2d*$y-*+.1=3*+:$,2>{$\%!},!=}%n}%
99 characters
~.(:S+,{S-}%:R{~):|;R{:$|>' *'1/[|$.|]2/@:d|~)$<!^=~:$;:y.*4*$-y-)2d*$y-*+.1=3*+:$,2>{$\%!},!=}%n}%
100 characters
~:S.(+,{S(-}%:R{~):|;R{:$|>' *'1/[|$.|]2/@:d|~)$<!^=~:$;:y.*4*$-y-)2d*$y-*+.1=3*+:$,2>{$\%!},!=}%n}%
101 characters
~:S.(+,{S(-}%:R{~):v;R{:$v>:d;' *'1/[v$.v]2/v~)$<!d^=~:$;:y.*4*$-y-)2d*$y-*+.1=3*+:$,2>{$\%!},!=}%n}%
OTHER TIPS
Python - 203 Characters
_________________________________________________________
/x=input();y=x-1;w=x+y;A=[];R=range;k,j,s,t=R(4) \
| for i in R(2,w*w): |
| A+=[(x,y)]*all(i%d for d in R(2,i)) |
| if i==s:j,k,s,t=k,-j,s+t/2,t+1 |
| x+=j;y+=k |
| for y in R(w):print"".join(" *"[(x,y)in A]for x in R(w)) |
\_________________________________________________________/
\ ^__^
\ (oo)\_______
(__)\ )\/\
||----w |
|| ||
x=input();y=x-1;w=x+y
A=[];R=range;k,j,s,t=R(4)
for i in R(2,w*w):
A+=[(x,y)]*all(i%d for d in R(2,i))
if i==s:j,k=k,-j;s,t=s+t/2,t+1
x+=j;y+=k
for y in R(w):print"".join(" *"[(x,y)in A]for x in R(w))
How it works
The idea is to fill A with x,y coords that need to be printed as '*'
The algorithm starts at the cell corresponding to 2, so the special case of testing 1 for primality is avoided.
x,y is the cell of interest
j,k keep track of whether we need to inc or dec x or y to get to the next cell
s is the value of i at the next corner
t keeps track of the increment to s
all(i%d for d in R(2,i)) does the primality check
The last line is rather clumsy. It iterates over all the cells and decides whether to place a space or an asterisk
MATLAB: 182 167 156 characters
Script ulam.m:
A=1;b=ones(1,4);for i=0:(input('')-2),c=b(4);b=b+i*8+(2:2:8);A=[b(2):-1:b(1);(b(2)+1:b(3)-1)' A (b(1)-1:-1:c+1)';b(3):b(4)];end;disp(char(isprime(A)*10+32))
And formatted a little nicer:
A = 1;
b = ones(1,4);
for i = 0:(input('')-2),
c = b(4);
b = b+i*8+(2:2:8);
A = [b(2):-1:b(1); (b(2)+1:b(3)-1)' A (b(1)-1:-1:c+1)'; b(3):b(4)];
end;
disp(char(isprime(A)*10+32))
Test cases:
>> ulam
2
* *
*
*
>> ulam
3
* *
* *
* **
*
*
>> ulam
5
* *
* *
* * *
* * *
* ** *
* *
* *
* *
* *
C, 208 206 201 200 199 196 194 193 194 193 188 185 183 180 176 Bytes
(if newlines are removed):
main(int u,char**b){
for(int v,x,y,S=v=**++b-48;--v>-S;putchar(10))
for(u=-S;++u<S;){
x=u;y=v;v>-u^v<u?:(x=v,y=u);
x=4*y*y-x-y+1+2*(v<u)*(x-y);
for(y=1;x%++y;);
putchar(y^x?32:42);}}
Compiled with
> gcc -std=c99 -o ulam ulam.c
Warning. This program is slow, because is does a trial division up to 2^31. But is does produce the required output:
* *
* *
* * *
* * *
* ** *
* *
* *
* *
* *
In nicely formatted C and with redundant #includes:
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char** argv) {
int u,v,x,y,d,S = atoi(argv[1]);
/* v is the y coordinate of grid */
for (v=S; v>=-S; --v)
/* u is the x coordinate. The second operand (!putchar...) of the boolean or
* is only ececuted a a end of a x line and it prints a newline (10) */
for (u=-S; u<=S || !putchar(10); ++u) {
/* x,y are u,v after "normalizing" the coordintes to quadrant 0
normalizing is done with the two comparisions, swapping and and
an additional term later */
d = v<u;
x=u;
y=v;
if (v<=-u ^ d) {
x=v;
y=u;
}
/* reuse x, x is now the number at grid (u,v) */
x = 4*y*y -x-y+1 +2*d*(x-y);
/* primality test, y resused as loop variable, won't win a speed contest */
for (y=2; y<x && x%y; ++y)
;
putchar(y!=x?' ':'*');
}
}
It works by transforming the coordinates of the grid to the appropriate number and then performing the primality test, intead of drawing in a snake-like manner. The different equations for the four "quadrants" can be collapsed into one with swapping x and y and an additional term for "backward counting".
Ruby 1.8.7, 194 chars
n=2*gets.to_i-1
r=n**2
l,c=[nil]*r,r/2
r.times{|i|l[c]=i+1;c=i==0||l[c-n]&&!l[c+1]?c+1:l[c-1]&&!l[c-n]?c-n:l[c+n]?c-1:c+n}
r.times{|i|print"1"*l[i]!~/^1?$|^(11+?)\1+$/?'*':' ',i%n==n-1?"\n":''}
For some reason, ruby1.9 wants another space on line 4:
r.times{|i|l[c]=i+1;c=i==0||l[c-n]&&!l[c+1]?c+1:l[c-1]&&!l[c-n]?c-n :l[c+n]?c-1:c+n}
Python - 171
drhirsch's C ported to python.
S=input();R=range(-S+1,S)
for w in R:
p="";v=-w
for u in R:d=v<u;x,y=[(u,v),(v,u)][(w>=u)^d];x=4*y*y-x-y+1+2*d*(x-y);p+=" *"[(x>1)*all(x%f for f in range(2,x))]
print p
echo 20 |python ulam.py
* * * * * *
* * * * * *
* * * * *
* * * * * *
* * * *
* * * * * *
* * * * * *
* * * * * * *
* * * * * * *
* * * * *
* * * * * * * *
* * * * * * *
* * * * *
* * * * * *
* * * * * * * * *
* * *
* * * * * * * * * *
* * * * * * * * * *
* * * *
* * ** * * * * * *
* * * *
* *
* * * * * * * * * * *
* * * * * * * *
* *
* * * * * * * *
* * * * * * *
* * * * *
* * * * * *
* * * * * * * * *
* * * *
* * * * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * *
* * * * * *
* *
* * * * * *
MATLAB, 56 characters
based on @gnovice solution, improved by using MATLAB's spiral function :)
disp(char(isprime(flipud(spiral(2*input('')-1)))*10+32))
Test Cases:
>> disp(char(isprime(flipud(spiral(2*input('')-1)))*10+32))
2
* *
*
*
>> disp(char(isprime(flipud(spiral(2*input('')-1)))*10+32))
3
* *
* *
* **
*
*
>> disp(char(isprime(flipud(spiral(2*input('')-1)))*10+32))
5
* *
* *
* * *
* * *
* ** *
* *
* *
* *
* *
J solution: 197 173 165 161 bytes (so far)
this does not use the method mentioned in the comments to the OP
p=:j./<.-:$g=:1$~(,])n=:<:+:".1!:1]3
d=:j.r=:1
(m=:3 :'if.y<*:n do.if.0=t=:<:t do.d=:d*0j1[t=:<.r=:r+0.5 end.m>:y[g=:y(<+.p=:p+d)}g end.')t=:2
1!:2&2(1 p:g){' *'
My first code golf!
Ruby, 309 301 283 271 265 characters
s=gets.to_i;d=s*2-1;a=Array.new(d){' '*d}
e=d**2;p='*'*e;2.upto(e){|i|2.upto(e/i){|j|p[i*j-1]=' '}};p[0]=' '
s.times{|i|k=s-i-1;l=2*i;m=l+1;o=l-1
m.times{|j|n=j+k;a[k][n]=p[l**2-j];a[n][k]=p[l**2+j];a[k+l][n]=p[m**2-m+j]}
l.times{|j|a[j+k][k+l]=p[o**2+o-j]}}
puts a
Python 2.x, 220C 213C 207C 204C 201C 198C 196C 188C
Special thanks to gnibbler for some hints in #stackoverflow on Freenode. Output includes a leading and trailing newline.
import math
v=input()*2
w=v-1
a=['\n']*w*v
p=w*v/2
for c in range(1,w*w):a[p]=' *'[(c>1)*all(c%d for d in range(2,c))];x=int(math.sqrt(c-1));p+=(-1)**x*((x*x<c<=x*x+x)*w+1)
print''.join(a)
(Python 3 compatibility would require extra chars; this uses input, the print statement and / for integer division.)
Ruby - 158 Characters
Same algorithm as this one, just the prime test is different
p=(v=(w=gets.to_i*2)-1)*w/2-1
a='
'*v*w
d=0
(v*v).times{|i|a[p]="1"*(i+1)!~/^1?$|^(11+?)\1+$/?42:32;d=(a[p+(z=[w,-1,-w,1])[d-1]]<32)?(d-1):d%4;p+=z[d]}
puts a
Haskell - 224 characters
(%)=zipWith(++)
r x=[x]
l 1=r[1]
l n=r[a,a-1..b]++(m r[a+1..]%l s%m r[b-1,b-2..])++r[d-s*2..d]where{d=(n*2-1)^2;b=d-s*6;a=d-s*4;s=n-1}
p[_]='*'
p _=' '
i n=p[x|x<-[2..n],n`mod`x==0]
m=map
main=interact$unlines.m(m i).l.read
i'm not the best at haskell so there is probably some more shrinkage that can occur here
output from echo 6 | runghc ulam.hs
* *
* *
* * * *
* * *
* * *
* ** *
* * *
* *
* * * *
* *
*
this is a different algorithm (similar to @drhirsch's) unfortunately i cannot seem to get it below 239 characters
p[_]='*'
p _=' '
main=interact$unlines.u.read
i n=p[x|x<-[2..n],n`mod`x==0]
u(n+1)=map(map(i.f.o).zip[-n..n].replicate((n+1)*2-1))[n,n-1..(-n)]
f(x,y,z)=4*y*y-x-y+1+if z then 2*(x-y)else 0
o(u,v)=if(v> -u)==(v<u)then(v,u,v<u)else(u,v,v<u)
First post! (oh wait, this isn't SlashDot?)
My entry for Team Clojure, 685 528 characters.
(defn ulam[n] (let [z (atom [1 0 0 {[0 0] " "}])
m [[0 1 1 0][2 -1 0 -1][2 0 -1 0][2 0 0 1][2 0 1 0]]
p (fn [x] (if (some #(zero? (rem x %)) (range 2 x)) " " "*"))]
(doseq [r (range 1 (inc n)) q (range (count m)) [a b dx dy] [(m q)]
s (range (+ (* a r) b))]
(let [i (inc (first @z)) x (+ dx (@z 1)) y (+ dy (@z 2))]
(reset! z [i x y (assoc (last @z) [x y] (p i))])))
(doseq [y (range (- n) (inc n))] (doseq [x (range (- n) (inc n))]
(print ((last @z) [x y]))) (println))))
(ulam (dec (.nextInt (java.util.Scanner. System/in))))---
Input:
5
Output:
* *
* *
* * *
* * *
* ** *
* *
* *
* *
* *
Input:
10
Output:
* * * *
* * *
* * *
* * *
* * * *
* * *
* * * * * *
* * * * *
* * *
* * ** * * *
* * *
* *
* * * * * *
* * * *
* *
* * * * *
* *
* * *
* * * *
Not as beautiful as the previous C entry, but here's mine.
note: I'm posting because it takes a different approach than the previous one, mainly
- there's no coordinate remapping
- it gives the same results as the tests
it works with input > 9 (two digits - no
-47trick)enum directions_e { dx, up, sx, dn } direction; int main (int argc, char **argv) { int len = atoi(argv[1]); int offset = 2*len-1; int size = offset*offset; char *matrix = malloc(size); int startfrom = 2*len*(len-1); matrix[startfrom] = 1; int next = startfrom; int count = 1; int i, step = 1; direction = dx ; for (;; step++ ) do { for ( i = 0 ; i < step ; i++ ) { switch ( direction ) { case dx: next++; break; case up: next = next - offset; break; case sx: next--; break; case dn: next = next + offset; } int div = ++count; do { div--; } while ( count % div ); if ( div > 1 ) { matrix[next] = ' '; } else { matrix[next] = '*'; } if (count >= size) goto dontusegoto; } direction = ++direction % 4; } while ( direction %2); dontusegoto: for ( i = 0 ; i < size ; i++ ) { putchar(matrix[i]); if ( !((i+1) % offset) ) putchar('\n'); } return 0; }
which, adequately translated in unreadable C, becomes 339 chars.
compile with: gcc -o ulam_compr ulam_compr.c works on osx
i686-apple-darwin9-gcc-4.0.1 (GCC) 4.0.1 (Apple Inc. build 5465)
and debian Lenny.
main(int a,char**v){
int l=atoi(v[1]),o=2*l-1,z=o*o,n=2*l*(l-1),c=1,i,s=1,d;
char*m=malloc(z);
m[n]=1;
for(;;s++)do{
for(i=0;i<s;i++){
if(d==0)n++;
else if(d==1)n-=o;
else if(d==2)n--;
else n+=o;
int j=++c;
while(c%--j);
if(j>1)m[n]=' ';else m[n]='*';
if(c>=z)goto g;
}d=++d%4;}while(d%2);
g:for(i=0;i<z;i++){
putchar(m[i]);
if(!((i+1)%o))putchar('\n');
}
}
Here is some output:
$ ./ulam_compr 3
* *
* *
* **
*
*
$ ./ulam_compr 5
* *
* *
* * *
* * *
* ** *
* *
* *
* *
* *
Python - 176
This one starts with a big long list of newline characters and replaces all of them except for the ones that are needed at the end of the lines.
Starting at the centre, the algorithm peeps around the lefthand corner at each step. If there is a newline character there, turn left otherwise keep going forward.
w=input()*2;v=w-1;a=['\n']*v*w;p=w/2*v-1;d=0;z=[w,-1,-w,1]
for i in range(v*v):a[p]=' *'[i and all((i+1)%f for f in range(2,i))];d=d%4-(a[p+z[d-1]]<' ');p+=z[d]
print"".join(a)
Python - 177
Using a string avoids "join" but ends up one byte longer since the string is immutable
w=input()*2;v=w-1;a='\n'*v*w;p=w/2*v-1;d=0;z=[w,-1,-w,1]
for i in range(v*v):a=a[:p]+' *'[i and all((i+1)%f for f in range(2,i))]+a[p+1:];d=d%4-(a[p+z[d-1]]<' ');p+=z[d]
print a
Python, 299 characters:
from sys import *
def t(n):
if n==1:return ' '
for i in range(2,n):
if n%i==0:return ' '
return '*'
i=int(stdin.readline())
s=i*2-1
o=['\n']*(s+1)*s
c=1
g=2
d=0
p=(s+2)*(i-1)
for n in range(s**2):
o[p]=t(n+1);p+=[1,-s-1,-1,s+1][d%4];g-=1
if g==c:d+=1
if g==0:d+=1;c+=1;g=2*c
print ''.join(o)
Lua, 302 characters
s=...t={" "}n=2 function p()for j=2,n-1 do if n%j==0 then n=n+1 return" "end
end n=n+1 return"*"end for i=2,s do for k=#t,1,-1 do t[k+1]=t[k]..p()end
t[1]=""for k=1,i*2-1 do t[1]=p()..t[1]end for k=2,#t do t[k]=p()..t[k]end
t[#t+1]=""for k=1,i*2-1 do t[#t]=t[#t]..p()end end print(table.concat(t,"\n"))
Output from lua ulam.lua 6:
* *
* *
* * * *
* * *
* * *
* ** *
* * *
* *
* * * *
* *
*
Python 284 266 256 243 242 240 char
I wanted to try recursion, I'm sure it may be heavily shortened:
r=range
def f(n):
if n<2:return[[4]]
s=2*n-1;z=s*s;c=[r(z-2*s+2,z-3*s+2,-1)];e=1
for i in f(n-1):c+=[[c[0][0]+e]+i+[c[0][-1]-e]];e+=1
c+=[r(z-s+1,z+1)];return c
for l in f(input()):print''.join(' *'[all(x%f for f in r(2,x))]for x in l)
edited under suggestion in comments
Mathematica 243
l = Length; t = Table; f = Flatten;
h@m_ := With[{x = l@m[[1]], y = l@m}, f[{{Reverse@t[w + y + (x y), {w, x + 2}]},
t[f[{(x y) + x + y + 2 + w, m[[w]], (x y) + y - w + 1}], {w, y}],
{t[2 + y + x + y + w + (x y), {w, x + 2}]}}, 1]];
m_~g~z_ := Nest[h, m, z] /. {_?PrimeQ -> "\[Bullet]", _Integer -> ""};
Grid[{{1}}~g~#, Frame -> All] &
Usage
13 windings:
Grid[{{1}}~g~#, Frame -> All] &[13]
