Код Гольф: Улама Спираль

Задача

Самый короткий код по количеству символов для вывода спирали Улама со спиральным размером, заданным пользователем.

Спираль Улама - один из способов сопоставления простых чисел. Спираль начинается от числа 1, находящегося в центре (1 не является простым) и создает вокруг него спираль, обозначая все простые числа как символ "*". Нечетное число будет напечатано как пробел ''.

alt text http://liranuna.com/junk/ulam.gif

Тестовые примеры

Input:
    2
Output:
    * *
      *
    *  

Input:
    3
Output:
    *   *
     * * 
    *  **
     *   
      *  

Input:
    5
Output:
        * *  
     *     * 
    * *   *  
       * * * 
      *  ** *
     * *     
    *   *    
     *   *   
    *     *

Количество кодов включает ввод/вывод (т.е. полную программу).

Ответ 1

Golfscript - 92 символа

~. (: S +,: R {S\-: |; R {S -: $| > '*' 1/[| $. |] 2/@: d | ~) $<! ^ = ~: $;: у * 4 * $- y-) 2d * $у - * +:. ${!) $\%}, 2 ==}% п}%

97 символов
~: (: S +,: R {S\-: |; R {S -: $| > '*' 1/[| $. |] 2/@: d | ~) $<! ^ = ~: $;: у * 4 * $- у-) 2d * $у - * + 1 = 3 * +:..! $, 2 > {! $\%}, =}% п}%

99 символов
~. (: S +, {S -}%: R {~): |; R {: $| > '*' 1/[| $. |] 2/@: d | ~) $<! ^ = ~:..! $у *;: 4 * $- y-) 2d * $у - * + 1 = 3 * +: $, 2 > {! $\%} =}% п}%р >

100 символов
~: S. (+, {S (-}%: R {~): |; R {: $| > '*' 1/[| $. |] 2/@: d | ~) $<! ^ = ~:. $;: у * 4 * $- y-) 2d * $у - * + 1 = 3 * +: $, 2 > {$ \%!}, =}% п}% <.!/p >

101 символ
~: S. (+, {S (-}%: R (~): v; R {: $v > : d; '*' 1/[v $.v] 2/v ~) $<! d ^ = ~:..! $у *;: 4 * $- y-) 2d * $у - * + 1 = 3 * +: $, 2 > {! $\%} =}% п}%

Ответ 2

Python - 203 символов

  _________________________________________________________
 /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))

Как это работает
Идея состоит в том, чтобы заполнить A координатами x, y, которые должны быть напечатаны как "*"
Алгоритм начинается в ячейке, соответствующей 2, поэтому исключается частный случай тестирования 1 для примитивности.
x, y - интересующая ячейка j, k отслеживать, нужно ли нам вводить или dec x или y, чтобы перейти к следующей ячейке
s - значение я в следующем углу
t отслеживает прирост до s

all (i% d для d в R (2, i)) проверяет ли первичность

Последняя строка довольно неуклюжая. Он выполняет итерацию по всем ячейкам и решает, следует ли разместить пробел или звездочку

Ответ 3

MATLAB: ~~182~~ ~~167~~ 156 символов

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

И отформатирован немного лучше:

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

Тестовые случаи:

>> ulam
2
* *
  *
*  
>> ulam
3
*   *
 * * 
*  **
 *   
  *  
>> ulam
5
    * *  
 *     * 
* *   *  
   * * * 
  *  ** *
 * *     
*   *    
 *   *   
*     *

Ответ 4

C, 208 206 201 200 199 196 194 193 194 193 188 185 183 180 176 байтов

(если новые строки удалены):

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);}}

Скомпилирован с

> gcc -std=c99 -o ulam ulam.c

Предупреждение. Эта программа медленная, потому что она выполняет пробное деление до 2 ^ 31. Но выводит требуемый результат:

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

В хорошо отформатированном C и с избыточным #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?' ':'*');
        }
}

Он работает, преобразуя координаты сетки в соответствующее число, а затем выполнив тест примитивности, используя рисунок в виде змеи. Различные уравнения для четырех "квадрантов" могут быть свернуты в одну с заменой x и y и дополнительным термином для "обратного счета".

Ответ 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":''}

По какой-то причине ruby1.9 хочет другое пространство в строке 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 C, перенесенный на 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 символов

на основе решения @gnovice, улучшенного с помощью функции MATLAB spiral:)

disp(char(isprime(flipud(spiral(2*input('')-1)))*10+32))

Тестовые случаи:

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

Мой первый гольф для гольфа!

Ruby, 309 301 283 271 265 символов

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

Ответ 9

Haskell - 224 символа

(%)=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

Я не лучший в haskell, поэтому, возможно, здесь будет еще больше усадки.

вывод из echo 6 | runghc ulam.hs

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

это другой алгоритм (похожий на @drhirsch's), к сожалению, я не могу получить его ниже 239 символов

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)

Ответ 10

Python 2.x, 220C 213C 207C 204C 201C 198C 196C 188C

Особая благодарность gnibbler за некоторые подсказки в #stackoverflow на Freenode. Выход включает в себя ведущую и конечную новую строку.

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 потребует дополнительных символов, в ней используется input, print и / для целочисленного деления.)

Ответ 11

J решение: ~~197 173 165~~ 161 байт (до сих пор)
это не использует метод, упомянутый в комментариях к 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){' *'

Ответ 12

Ruby - 158 Персонажи

Тот же алгоритм, что и этот, просто первый тест отличается

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

Ответ 13

Первое сообщение! (о, подождите, это не SlashDot?)

Моя запись для команды Clojure, ~~685~~ 528 символов.

(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

Не так красиво, как предыдущая запись C, но здесь моя.

Примечание: я публикую, потому что он использует другой подход, чем предыдущий, главным образом

нет переназначения координат
он дает те же результаты, что и тесты

он работает с вводом > 9 (два знака - нет -47 трюк)

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

который, надлежащим образом переведенный в нечитаемый C, становится 339 символов.

скомпилировать с помощью: gcc -o ulam_compr ulam_compr.c работает в osx

i686-apple-darwin9-gcc-4.0.1 (GCC) 4.0.1 (Apple Inc. build 5465)

и 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');
    }
}

Вот несколько результатов:

    $ ./ulam_compr 3
*   *
 * * 
* **
 *   
  *  

    $ ./ulam_compr 5
    * *  
 *     * 
* *   *  
   * * * 
  * ** *
 * *     
*   *    
 *   *   
*     *

Ответ 15

Python - 176

Это начинается с большого длинного списка символов новой строки и заменяет все из них, за исключением тех, которые необходимы в конце строк.

Начиная с центра, алгоритм просматривает левый угол на каждом шаге. Если там есть символ новой строки, поверните налево, иначе продолжайте движение вперед.

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
Использование строки позволяет избежать "join", но заканчивается на один байт дольше, поскольку строка неизменна

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 символов:

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 символа

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

Выход из lua ulam.lua 6:

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

Ответ 18

Python 284 266 256 243 242 240 char

Я хотел попробовать рекурсию, я уверен, что это может быть сильно сокращено:

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)

отредактировано под предложением в комментариях

Ответ 19

Mathematica 243

l = Length; t = Table; f = Flatten;
[email protected]_ := With[{x = [email protected][[1]], y = [email protected]}, f[{{[email protected][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] &

Использование

13 обмоток:

Grid[{{1}}~g~#, Frame -> All] &[13]