Vous pouvez écrire un programme ou une fonction qui reçoit un entier positif impair, n où n >= 3, comme argument de fonction, arguments de ligne de commande, ou sur STDIN (ou équivalent pour votre système), et imprime sur STDOUT (ou équivalent de système) une spirale ASCII qui tourne vers l'intérieur dans le sens horaire où le bord supérieur est exactement nlong. Le premier bord droit doit être n+1long, évidemment. Par exemple,

Contribution:

11

Production:

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

Les captures:

• Votre programme ne doit utiliser que de la O(log n)mémoire .
• Votre programme peut uniquement imprimer les caractères *(ASCII 42), (ASCII 32), <CR>(ASCII 13) et <LF>(ASCII 10).
• Votre programme doit imprimer la chaîne, pas la renvoyer de la fonction.
• La restriction Big-O est uniquement sur la mémoire , il n'y a aucune restriction sur l' exécution .
• Une nouvelle ligne de fin est facultative.
• Si votre langue ne prend pas en charge les grands types entiers, vous n'avez pas à prendre en charge plus haut que ce qu'elle prend en charge, mais vous ne pouvez pas utiliser cela comme une astuce pour dire "oh, eh bien, je n'ai pas à prendre en charge au-dessus de X, donc je peut simplement faire un énorme tableau de la taille maximale à chaque fois "

Les failles standard sont interdites, comme d'habitude.

C, 125 121 octets

Version golfée Cela n'a pas de variable k. La variable kest utilisée dans la version non golfée juste pour faciliter la lisibilité. Les forconditions de boucle sont également réarrangées et un ensemble d'éléments inutiles {}supprimés. Un autre ensemble de {}peut être supprimé en migrant puts("")à l'intérieur des crochets de la jboucle dans la position d'initialisation, mais cela signifierait une nouvelle ligne au début de la sortie, donc je ne l'ai pas fait.

f(n){int i,j;n/=2;for(i=-n-2;i++-n-1;){if(i){for(j=-n-1;j++-n;)putchar(32+10*(n+(j*j<i*i?i:j+(i!=j|i>0))&1));puts("");}}}

Imprime une nlarge par n+1haute spirale comme l'exemple.

Explication

Fondamentalement , je réduire de moitié la valeur de n(arrondi vers le bas) et exécuter deux boucles: une extérieure ide -n/2-1la n/2+1pour imprimer les lignes ( i=0est supprimée si nous obtenons des n+1lignes) et un un intérieur jde ( -n/2à n/2Nous utilisons pour imprimer les caractères.) expression & 1Pour imprimer des bandes , et la condition j*j<i*ipour décider d'imprimer des bandes verticales ou horizontales (verticales sur les côtés où la magnitude absolue de iest plus grande, et horizontale en haut et en bas.) Un ajustement +nest nécessaire pour aider à la terminaison correcte selon qu'il n/2est impair ou même.

kest normalement 1, et fournit un ajustement pour le fait que les valeurs absolues de la iplage de 1 à n/2+1tandis que les valeurs absolues de la jplage de 0 à n/2. Si kétait toujours 1, nous obtiendrions des rectangles concentriques, mais il est inversé à 0 lorsque de i==j&i<=0sorte qu'une rangée diagonale de cellules est inversée, produisant la spirale.

non golfé dans le programme de test

f(n){
  int i,j,k;
  n/=2;
  for(i=-n-1;i<=n+1;i++){
    if(i){
       for(j=-n;j<=n;j++){
           k=i!=j|i>0;
           putchar(32+10*(n+(j*j<i*i?i:k+j)&1));
         }
       puts("");
     }
  }
} 

int m;
main(){
  scanf("%d",&m);
  f(m);
}

Production

11
***********
          *
********* *
*       * *
* ***** * *
* *   * * *
* * * * * *
* * *** * *
* *     * *
* ******* *
*         *
***********

9
*********
        *
******* *
*     * *
* *** * *
* * * * *
* *   * *
* ***** *
*       *
*********

3
***
  *
* *
***

1
*
*

C, 118 octets

m,p,x,y,d;f(n){for(m=n++/2;p<n*n;x=p%n-m,y=p++/n-m,d=y==x+1&x<0,y-=y>0,d+=x*x>y*y?x:y,putchar(x>m?10:(d+m)%2?32:42));}

Code avant le golf final:

#include <stdio.h>

int m, p, x, y, d;

int f(int n) {
    for (m = n++ / 2; p < n * n; ) {
        x = p % n - m;
        y = p++ / n - m;
        d = y == x + 1 && x < 0;
        y -= y > 0;
        d += x * x > y * y ? x : y;
        if (x > m) {
            putchar(10);
        } else if ((d + m) % 2) {
            putchar(32);
        } else {
            putchar(42);
        }
    }

    return 0;
}

L'observation clé est que le motif est presque une série de carrés concentriques. Avec quelques rides légères:

• La taille y est une plus grande que la taille x. Ceci est corrigé en soustrayant 1 de y pour la moitié inférieure, qui répète essentiellement la ligne du milieu.
• Pour transformer les rectangles en spirale, les pixels le long de la y = x + 1diagonale doivent être inversés jusqu'au milieu de la forme.

Pour le reste, le code fait simplement une boucle sur toutes les positions, calcule la distance de Tchebychev du centre pour chaque position et émet l'un des deux caractères selon que la distance est paire ou impaire. Et émettre une nouvelle ligne pour la dernière position de chaque ligne.

Puisqu'il n'y a que quelques variables scalaires et que les caractères sont émis un par un, l'utilisation de la mémoire est évidemment constante.

C ++, 926 octets

#include<iostream>
#include<string>
#include<math.h>
#define S string
using namespace std;S N(S x,int y){S z="";for(int q=0;q<y;q++){z+=x;}return z;}int main(){int n=0,t=0,g=0,fi=1;cin>>n;int t1[]={0,0,n,0};int t2[]={0,n-2,n-2,1};for(int k=0;k<n+1;k++){if((k>(n-2)/2)&&(k<(n+5)/2)){if(g==0){S d,e;if(!((n+1)%4)){cout<<N("* ",t2[0])<<"  *"<<N(" *",t2[0])<<endl<<N("* ",(n+1)/2)<<endl<<N("* ",t2[0])<<"***"<<N(" *",t2[0])<<endl;t2[2]=n-8-(n-11);t1[2]=n-4-(n-11);t1[0]--;t2[3]--;t1[3]-=2;}else{cout<<N("* ",t1[0])<<"***"<<N(" *",t2[0])<<endl<<N("* ",(n+1)/2)<<endl<<N("* ",t1[0])<<"*  "<<N(" *",t2[0])<<endl;t2[0]--;t1[2]+=2;t2[2]+=6;t1[3]--;t2[1]-=2;t2[3]-=2;}fi=0;}g=5;}else{t=1-t;int*tR;tR=t?t1:t2;cout<<N("* ",tR[0])<<N(t?"*":" ",tR[2])<<N(" *",tR[3])<<endl;if(fi){if(t){t1[0]+=k==0?0:1;t1[2]-=k==0?2:4;t1[3]++;}else{t2[0]++;t2[2]-=4;t2[3]++;}}else{if(t){t1[0]--;t1[2]+=4;t1[3]--;}else{t2[0]--;t2[2]+=4;t2[3]--;}}}}return 0;}

Ce n'est pas élégant, mais cela ne prend pas beaucoup de mémoire pour les grands n. De plus, il y a (presque certainement) environ 20 personnages qui peuvent être joués plus loin, mais je ne supporte plus de le regarder.

Brève explication:

Cela divise les lignes dans les spirales en deux types: celles avec ****** au milieu et celles avec \ s \ s \ s \ s \ s au milieu. Ensuite, il est clair que chaque ligne est composée de plusieurs "*", le milieu et quelques "*". Déterminer exactement combien de chaque chose est simple si vous regardez le motif assez longtemps. La chose délicate était d'imprimer le centre de la spirale que j'ai codé en dur à l'aide d'un conditionnel. Cela a fini par être utile parce que les lignes *** et \ s \ s \ s sont impaires / paires.

Tests:

Entrée: 55 (je pense que les grands sont les plus cool)

Production:

************************************************** *****
                                                      *
************************************************** *** *
* * *
* ************************************************* * *
* * * * *
* * ********************************************* * * *
* * * * * * *
* * * ***************************************** * * * *
* * * * * * * * * *
* * * * ************************************* * * * * *
* * * * * * * * * * *
* * * * * ********************************* * * * * * *
* * * * * * * * * * * * *
* * * * * * ***************************** * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * ************************* * * * * * * * *
* * * * * * * * * * * * * * * * *
* * * * * * * * ********************* * * * * * * * * *
* * * * * * * * * * * * * * * * * * *
* * * * * * * * * ***************** * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * ************* * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * ********* * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * ***** * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * {- mon programme ajoute un espace ici btw
* * * * * * * * * * * * * *** * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * ******* * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * *********** * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * *************** * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * *
* * * * * * * * * ******************* * * * * * * * * *
* * * * * * * * * * * * * * * * * *
* * * * * * * * *********************** * * * * * * * *
* * * * * * * * * * * * * * * * *
* * * * * * * *************************** * * * * * * *
* * * * * * * * * * * * * * *
* * * * * * ******************************* * * * * * *
* * * * * * * * * * * *
* * * * * *********************************** * * * * *
* * * * * * * * * *
* * * * *************************************** * * * *
* * * * * * * * *
* * * ******************************************* * * *
* * * * * *
* * *********************************************** * *
* * * *
* ************************************************* ** *
* *
************************************************** *****

Contribution: 3

Production:

***
  *
* * 
***

Remarque: Je ne suis pas un informaticien / étudiant CS, et je ne sais pas comment prouver que cela utilise la mémoire O (log n). Je ne peux que savoir quoi faire en fonction des liens dans la question. Je vous serais reconnaissant de bien vouloir confirmer / infirmer si cette réponse est valide. Ma logique pour la validité de cette réponse est qu'elle ne stocke jamais aucune variable de taille basée sur n, sauf l'entrée elle-même. Au lieu de cela, une boucle for qui s'exécute n fois calcule des valeurs entières basées sur n. Il y a le même nombre de ces valeurs quelle que soit l'entrée.

Note2: Cela ne fonctionne pas pour n = 1 en raison de ma méthode de traitement avec le milieu. Ce serait facile à corriger avec les conditions, donc si quelqu'un se trouve à quelques caractères de ma réponse, je le corrigerai;)

Jouez avec lui sur ideone.

Haskell, 151 octets

(#)=mod
f n=[[if y<= -(abs$x+1)||y>abs x then r$y#2/=n#2 else r$x#2==n#2|x<-[-n..n]]|y<-[-n-1..n+1],y/=0]
r b|b='*'|1<2=' '
p=putStr.unlines.f.(`div`2)

Exemple d'utilisation:

*Main> p 9
*********
        *
******* *
*     * *
* *** * *
* * * * *
* *   * *
* ***** *
*       *
*********

*Main> p 11
***********
          *
********* *
*       * *
* ***** * *
* *   * * *
* * * * * *
* * *** * *
* *     * *
* ******* *
*         *
***********

Grâce à la paresse de Haskell, cela fonctionne dans la mémoire constante. Il utilise l'approche évidente, à savoir boucler yet xet choisir entre *et , selon

• si la position actuelle est supérieure ou inférieure à une diagonale
• xresp. yest pair ou impair
• n/2 est pair ou impair

Lisp commun - 346

(lambda(n &aux(d 0))(tagbody $ #6=(#7=dotimes(i n)#4=(princ"*"))#2=(#7#(i d)#5=(princ" ")#4#)#3=(terpri)#1=(#7#(i d)#4##5#)(when(> n 0)(#7#(i(1- n))#5#)#4#)#2##3#(when(> n 3)#1##4##4#(incf d)(decf n 4)(go $))(go /)@(decf d)(incf n 4)(when(> n 3)#2##5##4##3#)/ #1#(when(> n 0)#4#)(when(> n 1)(#7#(i(- n 2))#5#)#4#)#2##3##1##6#(when(> d 0)(go @))))

Solution itérative avec utilisation constante de la mémoire. Ce qui précède fait un usage intensif des variables #n=et des #n#lecteurs. Même s'il existe des approches plus directes, j'ai commencé avec une fonction récursive et l'ai modifiée pour simuler la récursivité avec des gotoinstructions: c'est probablement illisible.

Sortie pour toutes les valeurs d'entrée de 0 à 59 .

Version récursive originale, avec informations de débogage

(note: terprisignifie newline)

(defun spiral (n &optional (d 0) )
  (flet ((prefix ()
           (format t "~4d~4d | " n d)
           (dotimes (i d)
             (princ "a ")))
         (postfix ()
           (dotimes (i d)
             (princ " b"))))
    (when (= d 0) (prefix))
    (dotimes (i n) (princ "c"))
    (postfix)
    (terpri)

    (prefix)
    (when (> n 0)
      (dotimes (i (1- n)) (princ " "))
      (princ "d"))
    (postfix)
    (terpri)

    (when (> n 3)
      (prefix)
      (princ "**")
      (spiral (- n 4) (1+ d))
      (postfix)
      (princ " f")
      (terpri))

    (prefix)
    (when (> n 0)
      (princ "g"))

    (when (> n 1)
      (dotimes (i (- n 2)) (princ " "))
      (princ "h"))
    (postfix)
    (terpri)

    (prefix)
    (dotimes (i n) (princ "i"))
    ))

Par exemple:

(spiral 8)

   8   0 | cccccccc
   8   0 |        d
   8   0 | **cccc b
   4   1 | a    d b
   4   1 | a ** b b
   0   2 | a a  b b
   0   2 | a a  b b
   0   2 | a a  b f
   4   1 | a g  h b
   4   1 | a iiii f
   8   0 | g      h
   8   0 | iiiiiiii

Voir aussi cette pâte avec tous les résultats de 0 à 59 (pas le même que ci-dessus, celui-ci est plus verbeux).

Version itérative, avec informations de débogage

(defun spiral (n &aux (d 0) )
  (flet ((prefix ()
           (format t "~4d~4d | " n d)
           (dotimes (i d)
             (princ "a ")))
         (postfix ()
           (dotimes (i d)
             (princ " b"))))
    (tagbody
     step-in
       (when (= d 0) (prefix))
       (dotimes (i n) (princ "c"))
       (postfix)
       (terpri)

       (prefix)
       (when (> n 0)
         (dotimes (i (1- n)) (princ " "))
         (princ "d"))
       (postfix)
       (terpri)

       (when (> n 3)
         (prefix)
         (princ "**")

         (incf d)
         (decf n 4)
         (go step-in))

       (go skip)

     step-out
       (decf d)
       (incf n 4)
       (when (> n 3)
         (postfix)
         (princ " f")
         (terpri))

     skip
       (prefix)
       (when (> n 0)
         (princ "g"))

       (when (> n 1)
         (dotimes (i (- n 2)) (princ " "))
         (princ "h"))
       (postfix)
       (terpri)

       (prefix)
       (dotimes (i n) (princ "i"))
       (when(> d 0)(go step-out)))))

CJam, 72 octets

li_2/:M;)__*{1$mdM-\M-_2$)=2$0<*@_*@_0>-_*e>mQ_M>2*@@+M+2%+'#S+N+N+=o}/;

Il s'agit d'une conversion assez directe de ma solution C en CJam. Pas aussi court que ce que vous attendez normalement d'une solution CJam, mais celle-ci souffre vraiment de la restriction de mémoire. Les avantages courants de la création de résultats sur la pile qui est automatiquement vidée à la fin et de l'utilisation d'opérations de liste / chaîne fantaisie, disparaissent tous de la fenêtre. Cela génère et génère la solution un caractère à la fois. La pile ne contient que quelques entiers au moment de l'exécution et est vide à la fin.

Même si ce n'est pas un bon moyen d'utiliser un langage de golf, il est encore beaucoup plus court que le code C simplement parce que la notation est plus compacte.

Explication:

li    Get input n.
_2/   Calculate n/2.
:M;   Store it in variable M
)__*  Calculate (n+1)*(n+1), which is the total number of output characters.
      Also keep a copy of n+1 on the stack.
{     Start loop over output character positions.
  1$md  Calculate divmod of position with n+1. This gives y and x of position.
  M-    Subtract M from x.
  \M-   Subtract M from y.
  _     Copy y.
  2$)   Calculate x+1.
  =     Check if y == x+1
  2$0<  Check if x < 0.
  *     Multiply the two check results. This is the result of the flip
        condition for the top-left diagonal to turn the rectangles into a spiral.
  @_*   Calculate x*x.
  @_    Get y to top of stack, and copy it.
  0>-   Subtract 1 from y if it is in the bottom half.
  _*    Calculate y*y.
  e>    Take maximum of x*x and y*y...
  mQ    ... and calculate the square root. This is the absolute value of the
        larger of the two.
  _M>   Check if the value is greater M, which means that this is the
        position of a line end.
  2*    Multiply by 2 so that we can add another condition to it later.
  @     Get result of diagonal flip condition to the stack top.
  @     Get max(x,y) to the top.
  +M+   Add the two, and add M to the whole thing. This value being even/odd
        determines if the output is a # or a space.
  2%    Check if value is odd.
  +     Add to line end condition to get a single ternary condition result.
  '#S+N+N+
        Build string "# \n\n".
  =     Use the condition result to pick the output character out of the string.
  o     Output the character.
}/    End loop over output characters.
;     Pop n+1 value off stack, to leave it empty.