language-agnostic - コードゴルフ：ウラムスパイラル

Question

チャレンジ

ユーザー入力によって指定されたスパイラル サイズでウラムのスパイラルを出力するための、文字数別の最短コード。

ウラムのらせんは、素数をマッピングする方法の 1 つです。らせんは、中心にある数字 1 から始まり (1 は素数ではありません)、その周りにらせんを生成し、すべての素数を文字 ' *' としてマークします。非素数はスペース ' ' として出力されます。

代替テキスト http://liranuna.com/junk/ulam.gif

テストケース

Input:
    2
Output:
    * *
      *
    *  
    
Input:
    3
Output:
    *   *
     * * 
    *  **
     *   
      *  
      
Input:
    5
Output:
        * *  
     *     * 
    * *   *  
       * * * 
      *  ** *
     * *     
    *   *    
     *   *   
    *     *  

コード カウントには、入力/出力 (つまり、完全なプログラム) が含まれます。

Answer 1

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

仕組み
アイデアは、「*」として出力する必要のあるx、y座標でAを埋めることです
。アルゴリズムは2に対応するセルから開始するため、素数性について1をテストする特殊なケースは回避されます。
x、yは対象のセル
j、kは次のセルに到達するためにxまたはyをincまたはdecする必要があるかどうかを追跡し
ますsは次のコーナーでのiの値です
tはsへの増分を追跡します

all（i％d for d in R（2、i））は素数性チェックを行います

最後の行はかなり不器用です。すべてのセルを繰り返し処理し、スペースまたはアスタリスクのどちらを配置するかを決定します

Answer 2

MATLAB: 182 167 156 文字

スクリプト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
    * *  
 *     * 
* *   *  
   * * * 
  *  ** *
 * *     
*   *    
 *   *   
*     *  

Answer 3

Golfscript - 92 文字

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

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

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

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

101文字
~:S.(+,{S(-}%:R{~):v;R{:$v>:d;' *'1/[v$.v]2/v~)$< !d^=~:$;:y.*4*$-y-)2d*$y-*+.1=3*+:$,2>{$\%!},!=}%n} %

Answer 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?' ':'*');
        }
}

これは、グリッドの座標を適切な数値に変換してから、蛇のような方法で描画する代わりに、素数テストを実行することによって機能します。4 つの「象限」のさまざまな方程式は、x と y を入れ替えて 1 つにまとめることができ、「後方カウント」の項を追加できます。

Answer 5

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

Answer 6

Ruby 1.8.7、194 文字

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}

Answer 7

MATLAB、56 文字

@gnoviceソリューションに基づいており、MATLAB のスパイラル関数を使用して改善されています :)

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

Answer 8

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

Answer 9

ルビー - 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

Answer 10

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 のものに似ています) 残念ながら、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)

Answer 11

初めてのコードゴルフ！

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

Answer 12

Python 2.x、220C 213C 207C 204C 201C 198C 196C188C

Freenodeに関するヒントを提供してくれたgnibblerに感謝します。出力には、先頭と末尾の改行が含まれます。#stackoverflow

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 /

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

Answer 14

前の C エントリほど美しくはありませんが、これが私のものです。

注：主に、以前のものとは異なるアプローチを取るため、投稿しています

• 座標の再マッピングはありません
• テストと同じ結果が得られます

• 入力> 9（2桁--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.cosx で動作

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

と debian レニー。

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

Answer 15

パイソン - 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
文字列を使用すると「結合」を回避できますが、文字列は不変であるため、1 バイト長くなります

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

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

Answer 17

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

使用法

13巻線：

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

Answer 18

ルア、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:

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

Answer 19

パイソン284 266 256 243 242240文字

再帰を試してみたかったのですが、大幅に短縮される可能性があると確信しています:

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)

コメントの提案の下で編集