Text auf einem Kreis

19

Schreiben Sie ein Programm oder eine Funktion, die eine Eingabezeichenfolge um den diskreten Kreis mit dem kleinstmöglichen Radius druckt. Für die Eingabe This is an examplesollte Ihr Programm beispielsweise Folgendes ausgeben:

  a si   
 n     s 
        i
e       h
x       T
a        
m        
 p       
  le     

Kreiserzeugung

Sie müssen den Mittelpunktkreis-Algorithmus verwenden , um die Koordinaten jedes Punkts des diskreten Kreises zu berechnen. Beispiele zur Implementierung dieses Algorithmus finden Sie auf dieser Wikipedia-Seite .

Hier ist der Pseudocode des Algorithmus (basierend auf dem C-Beispiel von Wikipedia):

integer x = radius
integer y = 0
int decisionCriterion = 1 - x

while y <= x 
    point at coordinates (x,y) belongs to the circle   // Octant 1
    point at coordinates (y,x) belongs to the circle   // Octant 2
    point at coordinates (-x,y) belongs to the circle  // Octant 4
    point at coordinates (-y,x) belongs to the circle  // Octant 3
    point at coordinates (-x,-y) belongs to the circle // Octant 5
    point at coordinates (-y,-x) belongs to the circle // Octant 6
    point at coordinates (x,-y) belongs to the circle  // Octant 7
    point at coordinates (y,-x) belongs to the circle  // Octant 8

    y++
    if decisionCriterion <= 0
        decisionCriterion += 2 * y + 1
    else
        x--
        decisionCriterion += 2 * (y - x) + 1
end while

Sie können genau dann einen anderen Algorithmus verwenden, wenn er für alle Radien genau dieselben Kreise erzeugt wie der Mittelpunktkreis-Algorithmus .

Der Kreis muss den kleinstmöglichen Radius haben , mit dem noch alle Buchstaben der Eingabe geschrieben werden können.

Wenn der Kreis mehr Punkte als die Anzahl der Zeichen in der Zeichenfolge enthält, sind die letzten Füllzeichen Leerzeichen .

Das erste Zeichen der Eingabe muss mit Koordinaten auf den Punkt gedruckt werden (Radius,0). Die nachfolgenden Zeichen werden gegen den Uhrzeigersinn gedruckt.

Eingänge

Die Eingabe ist eine Zeichenfolge aus beliebigen ASCII-Zeichen zwischen dem Leerzeichen (32) und der Tilde ~(126).

Sie können davon ausgehen, dass die Eingabe immer gültig ist, kürzer als 256 Zeichen und mindestens 5 Zeichen lang.

Die Eingabe kann von STDIN oder als Funktionsparameter oder ähnliches erfolgen.

Ausgänge

Sie können das Ergebnis entweder an STDOUT ausgeben oder es als Zeichenfolge von einer Funktion zurückgeben.

Möglicherweise haben Sie nachgestellte Leerzeichen, vorausgesetzt, die Zeile überschreitet nicht die längste Zeile (die mittlere) (als solche darf die mittlere Zeile keine nachgestellten Leerzeichen enthalten).

Eine abschließende neue Zeile ist zulässig.

Testfälle

Input: Hello, World!
Output:
  ,ol  
     l 
W     e
o     H
r      
 l     
  d!   


Input: 4 8 15 16 23 42
Output:
  51   
     8 
1      
6     4

 2   2 
  3 4  


Input: Programming Puzzles & Code golf
Output:
     gnim    
  uP     ma  
 z         r 
 z         g 
l           o
e           r
s           P

&            

 C           
  od     f   
    e Gol    


Input: Ash nazg durbatuluk, ash nazg gimbatul, ash nazg thrakatuluk agh burzum-ishi krimpatul.
Output:
            zan hsa ,           
           g         ku          
        ig             lu        
      bm                 ta      
     a                     b     
    t                       r    
   u                         u   
   l                         d   
  ,                              
                              g  
 a                             z 
 s                             a 
h                               n

n                               h
a                               s
z                               A
g                                

t                                
h                                
 r                               
 a                             . 
  k                           l  
  a                           u  
   t                         t   
   u                         a   
    l                       p    
     u                     m     
      k                  ri      
        ag              k        
          h          hi          
            burzum-is            

Wertung

Das ist , also gewinnt die kürzeste Antwort in Bytes.

Tödlich
quelle

Antworten:

1

Mathematica, 359 357 354

(L=Length;T=Tuples;c=Characters@#;For[r=1,L[p=RotateRight[SortBy[#,ArcTan@@N@#&]+r+1,L@#/4+1]&@(f=1-r;X=1;Y=-2r;x=0;y=r;q={{0,r},{0,-r},{r,0},{-r,0}};While[x<y,If[f>0,y--;f+=Y+=2];x++;f+=X+=2;q=Join[q,T@{{x,-x},{y,-y}},T@{{y,-y},{x,-x}}]];Union@q)]<L@c,r++];R=2r+1;s="";Do[s=s<>({u,v}/.Thread[p~Take~L@c->c]/.{_,_}->" ")<>If[v==R,"\n",""],{u,R},{v,R}];s)&

Ungolfed:

(
  L = Length;
  T = Tuples;
  c = Characters@#;
  For[r = 1,
   L[
     p = RotateRight[
         SortBy[#, ArcTan @@ N@# &] + r + 1, L@#/4 + 1
         ] &@(
        f = 1 - r;
        X = 1;
        Y = -2 r;
        x = 0;
        y = r;
        q = {{0, r}, {0, -r}, {r, 0}, {-r, 0}};
        While[x < y,
         If[f > 0,
          y--;
          f += Y += 2
          ];
         x++;
         f += X += 2;
         q = Join[q, T@{{x, -x}, {y, -y}}, T@{{y, -y}, {x, -x}}]
         ];
        Union@q
        )] < L@c,
   r++];
  R = 2 r + 1;
  s = "";
  Do[s = s <> ({u, v} /. Thread[p ~ Take ~ L@c -> c] /. {_, _} -> " ") <>
      If[v == R, "\n", ""],
   {u, R}, {v, R}];
  s
  ) &
shrx
quelle
3

C 367 Bytes

#include<math.h>
main(){char*m="12345678",b[9999];int p,i,n,q,c,l=strlen(m),r=1,d,f=0;float o,s;for(;!f;r++){f=0;q=r*r;c=r/4;o=6.3,s=o/99.;memset(b,0,q);for(i=0;i<l;i++){p=1;f=0;while(p&&o>0){d=(c-1+(int)(sin(o)*c))*r+c-1+(int)(cos(o)*c);f+=p=b[d];if(!p)b[d]=m[i];o-=s;}}if(f){for(n=p=0;n<q;n++){p+=c=b[n];putchar(c?c:32);if(n%r==r-1){if(!p)n=q;putchar(10);p=0;}}}}}

Hier testen

Ich bin sicher, es kann noch viel weiter golfen werden, aber es fängt an, mir Kopfschmerzen zu bereiten.

C 324 Bytes

Kleinerer Code, aber die Ergebnisse stimmen nicht mit denen von OP überein

#include<math.h>
main(){char*m="12345678",b[9999];int q,c,l=strlen(m),r=1,d,i=0;float o;for(;i<l;r++){i=0;c=r/2;q=r*r;memset(b,0,q);for(o=6.28;o>=0&&i<l;o-=0.001){d=(c-1+(int)(sin(o)*c))*r+c-1+(int)(cos(o)*c);if(!b[d]){b[d]=m[i++];}}}for(d=i=0,--r;d<q;d++){i+=c=b[d];putchar(c?c:32);if(d%r==r-1){putchar(10);d=i?d:q;i=0;}}}

       an hsa ,k
      gz       ulu
    ig           ta
   bm             br
  ta               ud
 lu                  g
 ,                   z
a                    an
s
h                     h
                      s
n                     A
a
z
g                     l
 t                   tu
 h                   a
 ra                 mp
  ka               ri
   tu              k
    lu           hi
     k a       -is
       gh burzum
Johan du Toit
quelle
3
Sie können die voidfür 5 Bytes löschen und einige der Ganzzahlen im globalen Bereich für einige weitere Bytes deklarieren, da Variablen im globalen Bereich ohne Typ angenommen intund automatisch auf initialisiert werden 0.
Mego
1
Anscheinend haben Sie eine anonyme Bearbeitung vorgenommen, während Sie abgemeldet waren. Ich habe es genehmigt, aber im Allgemeinen sollten Sie sich anmelden, um Ihre Änderungen vorzunehmen. ;)
Alex A.
1

C 494 Bytes

Dieser verwendet den tatsächlichen Mittelpunktkreis-Algorithmus:

void main(){char s[]="12345678";int a[9999],b[9999],f=0,c,h,x,y,e,q,t,u,v,g,i,d,l,r=0,k=strlen(s);for(;f<k;r++){c=r;e=r*2+1;q=e*e;memset(b,0,q*4);f=0;l=0;for(i=0;i<8;i++){x=r;y=0;d=1-x;for(x=r,y=0,d=1-x;y<=x;y++,d+=2*d>0?y- --x:y+1){t=(i+1)%4>1;u=t?y:x;v=t?x:y;h=(c+v*(i>3?1:-1))*e+(c+u*(i>1&&i<6?-1:1));if(!b[h])b[h]=f<k?s[f]:0,a[f]=h,f++;}if(i%2){for(g=0;g<(f-l)/2;g++)t=b[a[l+g]],b[a[l+g]]=b[a[f-1-g]],b[a[f-1-g]]=t;}l=f;}}for(i=0;i<q;i++){c=b[i];putchar(c?c:32);if(i%e==e-1)putchar(10);}}

Golf Code:

void main() {
    char text[]="Ash nazg durbatuluk, ash nazg gimbatul, ash nazg thrakatuluk agh burzum-ishi krimpatul.";

    char points[9999];
    int pos[9999];

    int sl = strlen(text);
    int r = 0;
    int pc = 0; // point count
    int lc = 0; // last count

    int c, h, x, y, e, q, t, u, v, g, i, d;

    // increase radius until number of points => strlen(text)
    for(; pc<sl; r++) {
        c = r;
        e = r * 2 + 1;
        q = e * e;
        memset(points,0,q);
        pc = 0;
        lc = 0;

        // loop through the octants
        for(i=0; i<8; i++) {

            // midpoint loop
            x = r;
            y = 0;
            d = 1 - x;
            while (y <= x) {

                // calc index of point
                t = (i + 1) % 4 > 1;
                u = t ? y : x;
                v = t ? x : y;
                h = (c + v * (i > 3 ? 1 : -1)) * e + (c + u * (i > 1 && i < 6 ? -1 : 1)); 

                // add point if space is empty
                if(!points[h]) { 
                    points[h] = pc < sl ? text[pc] : 0;
                    pos[pc] = h;
                    pc++;
                }

                y++;
                d += 2 * d > 0 ? y- --x : y + 1;
            }

            if(i % 2) {
                // reverse point order for odd octants
                for(g=0; g<(pc-lc)/2; g++)
                {
                    t = points[pos[lc + g]];
                    points[pos[lc + g]] = points[pos[pc - 1 - g]];
                    points[pos[pc - 1 - g]] = t;
                }
            }
            lc = pc;
        }
    }

    // write output
    for(i=0;i<q;i++)
    {
        c = points[i];
        putchar(c ? c : 32);
        if(i % e == e - 1)
            putchar(10);
    }
}
Johan du Toit
quelle