Code Golf: Ulam Spiral

问题:

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

回答1:

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}%

回答2:

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

回答3:

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
    * *  
 *     * 
* *   *  
   * * * 
  *  ** *
 * *     
*   *    
 *   *   
*     *  

回答4:

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

回答5:

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}

回答6:

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 
      *     *   * *   *             *  
 *     * *     *   * *                 
*     * *                     *     *  
       * *     *   *           *     * 
                  *   * *   *          
 *               *   *       *   * *   
*     *   *           * *     *        
 *   * *     * *     *     *           
* *           *           *   *     * *
   *     *   *       *     *           
    *   *         *   * *   * * *      
 * *       *     *         * *   *     
      *     *   * *               *    
                   * *     *   *   * * 
*   *   *   * *   *       *   * *      
                   * *   *             
  *       *   * *     * * *     * * *  
   * * * * * * * *   *       *         
                  * * *           *    
             *   *  ** * * *   * * *   
      *       * * *                    
               *   *                   
    *   * *   * *   *   * *   *   * *  
 *     *   *   *     *     * *   *     
                *           *          
 *         * *     *   *   *       * * 
* *     *   *           *       *     *
   *     *     *   * *                 
              * *   *     *   *     *  
   * * * *         * *     *     * *   
      *   *           * *              
 *   * *     *     *   * *           * 
  * *       *         *       *     *  
             * *   * *         *     * 
          *   *     *     *         * *
       * *     *                 *     
*   *       *           *   *     *    
                             *     *   
*   * *   *     *           *          

回答7:

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
    * *  
 *     * 
* *   *  
   * * * 
  *  ** *
 * *     
*   *    
 *   *   
*     *  

回答8:

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){' *'

回答9:

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

回答10:

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

回答11:

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

回答12:

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)

回答13:

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:
        *   * *   *
 *     *         * 
  *   * *          
         * *     * 
  * *   *       *  
         * *   *   
*   * *     * * *  
 * * * *   *       
        * * *      
   *   *  ** * * * 
    * * *          
     *   *         
*   * *   *   * *  
 *   *     *     * 
      *           *
 * *     *   *   * 
  *           *    
     *   * *       
    * *   *     *  

回答14:

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 -47 trick)

  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
    * *  
 *     * 
* *   *  
   * * * 
  * ** *
 * *     
*   *    
 *   *   
*     *  

回答15:

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

回答16:

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)

回答17:

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:

*   *      
     * *   
* *     * *
 * *   *   
    * * *  
   *  ** * 
* * *      
 *   *     
* *   *   *
 *     *   
  *        

回答18:

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

回答19:

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]