Parfois, quand je m'ennuie vraiment ( vraiment m'ennuie), j'aime dessiner un segment de ligne et y dessiner des points.

Tout d'abord, je dessine un segment de ligne d'une certaine taille, qui est 2 ^ N pour une certaine valeur de N. La ligne sera représentée par une série de .caractères.

................

Ensuite, je trace un point à l'extrémité gauche. Les points seront représentés par des Xcaractères.

X...............

Ensuite, je suis un schéma. En partant du dernier point tracé (que j'appellerai A), j'avance jusqu'au prochain point tracé (B) sur la ligne (en faisant le tour si nécessaire). Ensuite, je passe au prochain point tracé sur la ligne (C). Ensuite, je trace un nouveau point à mi-chemin entre ce troisième point (C) et le prochain point déjà tracé (D).

Chaque fois que vous vous enroulez autour de la ligne, le "milieu" est déterminé de manière enveloppante. Le point nouvellement tracé est toujours à droite de C.

Disons que la ligne suivante était ma ligne actuelle. Voici comment je tracerais les deux points suivants. Pour cet exemple, je vais étiqueter chaque point important avec une lettre.

X...A...X.X...X.
    ^

X...A...B.X...X.
        ^

X...A...B.C...X.
          ^

X...A...B.C...D.
            ^

X...X...X.X.A.X.
            ^

X...X...X.X.A.B.
              ^

C...X...X.X.A.B.
^

C...D...X.X.A.B.
  ^

X.A.X...X.X.X.X.
  ^

Pour revenir à l'exemple précédent, le point suivant sera tracé au milieu de la ligne.

X.......X.......

C'est peut-être un petit cas particulier: passer au point suivant vous laisse simplement là où vous avez commencé. Le seul point à mi-chemin utile est le point à mi-chemin «cyclique» (le point à mi-chemin sur la ligne), par opposition au tracé d'un point au-dessus de lui-même.

Ci-dessous se trouve la série de points que je tracerais sur la ligne d'ici à la fin.

X.......X.......
X.......X...X...
X.......X.X.X...
X...X...X.X.X...
X...X...X.XXX...
X.X.X...X.XXX...
X.X.X...XXXXX...

Il n'y a plus de place pour tracer le point suivant, car il devrait être coincé entre deux points adjacents, j'ai donc atteint la profondeur maximale pour la valeur donnée de N = 4. La dernière ligne de la liste ci-dessus est "complète" . "

Le défi

Le but est d'écrire le programme le plus court / la fonction nommée qui imprimera / retournera la ligne complétée pour une valeur donnée de N. Ce qui précède montre N = 4.

Contribution

L'entrée sera un seul entier non négatif N. La longueur de la ligne générée sera alors de 2 ^ N.

Production

La sortie sera la ligne complète de longueur 2 ^ N, formée par les caractères .et X. Une nouvelle ligne de fin n'a pas d'importance.

Exemple d'E / S

0
X

1
XX

2
X.XX

3
X.X.XXX.

4
X.X.X...XXXXX...

5
X.X.X...X...X...X.XXX.XXX.......

Python 2, 137

n=input()
l=[0]*2**n;i=0
while~i%2:i=i/2%2**n;l[i]=1;i=sum([k for k,v in enumerate(l*4)if(k>i)*v][1:3])
print''.join(['.X'[x]for x in l])

Assez simple.

Pyth, 49

Plus ou moins une traduction. La principale différence est que je n'utilise pas de liste représentant la ligne, j'utilise une chaîne.

J*\.^2QW!%Z2K%/Z2lJ=JXJK\X=Zs<tf&q\X@JT>TKU*4J2)J

Essayez-le en ligne .

                         Q=input(); Z=0 #implicit
J*\.^2Q                  J = "."*(2^Q)
W!%Z2                    while !(Z%2):
  K%/Z2lJ                  K=(Z/2)%(len(J))
  =JXJK\X                  change J, the point at index K is changed to a "X"
       f          U*4J     filter all elements T in [0, 1, 2, ..., 4*len(J)-1]:
        &q\X@JT>TK           where J[T]=='X' and T>K
     <t               2    only us the second and third element
  =Zs                      and store the sum to Z
)J                       end while and print J

Clip , 95

[z?zF#2(z*2*:(#2(z'.'X]'X]]n[Fa[b[q[j[r?=rirFrsrb'X]b]][t[u+*<ut*Blb/+tu2]]g+2jqg+3jq]#qa]%b'X}

GolfScript (61 octets)

~2\?,[]0{.@|$4*.@?2+1$>2<.+~<!4$,*++.2/\1&!}do;`{&!'X.'1/=}+%

Le nombre d'itérations de boucle nécessaires semble être A061419 , mais la boucle do est plus courte que le calcul. Un divmod enregistrerait un caractère dans la boucle do. La partie qui semble la plus inutile est la conversion de sortie, mais je ne vois pas comment l'améliorer.

CJam, 55 53 51 50 octets

2ri#:N'.*0aN{):U+__Nf++$_U#))>2<1bNe|2/N%|}*{'Xt}/

Quelque chose pour commencer.

Essayez-le en ligne ici

Java, 209 207 195 191 octets

Je suis surpris d'avoir pu l'obtenir aussi court. Il y a probablement encore place à amélioration. Comme d'habitude, les suggestions seront appréciées :)

Cela renvoie a char[]. Appelez en utilisant a(n).

char[]a;int b,c,d,e=2;char[]a(int f){java.util.Arrays.fill(a=new char[b=1<<f],'.');for(a[0]=88;d+1<e;c=(d+e)/2,a[c%b]=88)e=b(d=b(b(c)));return a;}int b(int f){for(;;)if(a[++f%b]>87)return f;}

Dentelé:

char[] a;
int b, c, d, e = 2;

char[] a(int f){
    java.util.Arrays.fill(
            a = new char[
                    b = 1 << f
                    ]
            , '.'
    );
    for(
            a[0] = 88;
            d + 1 < e;
                c = (d + e) / 2,
                a[c % b] = 88
        )
        e = b(
                d = b(
                        b(c)
                )
        );
    return a;
}

int b(int f){
    for (;;)
        if (a[++f % b] > 87)
            return f;
}

12 octets grâce à Peter :)
4 octets grâce à TNT;)

Haskell, 182 octets

(a:b)%(c:d)|a<c=a:b%(c:d)|1<2=c:(a:b)%d
f i=putStr$map(!(0:g[0,n..]))[0..n-1]where n=2^i;e!l|e`elem`l='X'|1<2='.';g(_:_:c:d:r)|m==c=[]|1<2=mod m n:g((d:r)%[m,m+n..])where m=div(c+d)2

Utilisation: f 5. Sortie: X.X.X...X...X...X.XXX.XXX........

Malheureusement, Haskell n'a pas de fonction de fusion dans les bibliothèques standard, je dois donc fournir la mienne (-> %). Heureusement, je ne dois fusionner que des listes infinies, donc je n'ai pas à couvrir les cas de base, c'est-à-dire les listes vides. Il en coûte encore 40 octets.

Comment ça marche: au lieu de mettre les Xs directement dans un tableau, je garde une liste des positions où ils se trouvent. De plus je ne fais pas le tour 2^Nmais continue d'augmenter les positions vers l'infini (par exemple pour N = 2 avec un Xà l'avant, la liste des positions ressemble [0,4,8,12,16,20,…]). Je prends les 3e et 4e éléments ( cet d), calcule la nouvelle position (c+d)/2, la conserve pour la liste de sortie, fusionne l'ancienne liste de positions de la position 4 (la d) avec une nouvelle commençant par (c+d)/2et récidivant. Je m'arrête à (c+d)/2égalité c. Enfin, j'ajoute un 0à la liste de sortie et j'imprime des Xs aux positions données et .ailleurs.

step by step example, N=2

step  position list       (c+d)/2  output     lists to merge (pos. list for next round)
                                   list       old list from d on / new list from (c+d)/2

  #1  [0,4,8,12,16,…]       10     [10]          [12,16,20,24,…] / [10,14,18,22,…]
  #2  [10,12,14,16,18,…]    15     [10,15]       [16,18,20,22,…] / [15,19,23,27,…]
  #3  [15,16,18,19,20,…]    18

stop here, because c equals (c+d)/2

add 0 to the output list: [0,10,15]
take all elements modulo 2^N: [0,2,3]
print X at position 0, 2 and 3 

Mathematica, 110 102 112 108

a=Array["."&,n=2^Input[]];a[[Mod[Round@{n/2,n}//.{x_,y_,z___}/;y-x>1:>{z,x+n,(x+y)/2+n,y+n},n]+1]]="X";""<>a