Czasami, kiedy jestem naprawdę znudzony ( naprawdę znudzony), lubię rysować odcinek linii i rysować na nim punkty.

Najpierw rysuję odcinek linii o określonym rozmiarze, który dla pewnej wartości N. wynosi 2 ^ N. Linia będzie reprezentowana przez ciąg .znaków.

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

Następnie rysuję punkt na lewym końcu. Punkty będą reprezentowane przez Xpostacie.

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

Następnie podążam za wzorem. Zaczynając od ostatnio narysowanego punktu (który nazywam A), przechodzę do następnego narysowanego punktu (B) na linii (owijając się w razie potrzeby). Następnie przechodzę do następnego wykreślonego punktu na linii (C). Następnie wykreślam nowy punkt w połowie drogi między tym trzecim punktem (C) a następnym już wykreślonym punktem (D).

Ilekroć owijamy się wokół linii, „środek” jest określany w sposób zawijający. Nowo narysowany punkt znajduje się zawsze po prawej stronie C.

Powiedzmy, że następujący wiersz był moją bieżącą linią. Oto, jak wykreśliłbym następne dwa punkty. W tym przykładzie oznaczę każdy ważny punkt literą.

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

Wracając do poprzedniego przykładu, następny punkt zostanie narysowany na środku linii.

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

Być może jest to trochę szczególny przypadek: przejście do następnego punktu po prostu pozostawia początek. Jedynym użytecznym punktem w połowie jest „cykliczny” punkt w połowie (punkt w połowie linii), w przeciwieństwie do kreślenia punktu na sobie.

Poniżej znajduje się seria punktów, które chciałbym narysować na linii od tego miejsca do końca.

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

Nie ma już miejsca na wykreślanie następnego punktu, ponieważ musiałby on zostać wciśnięty między dwa sąsiednie punkty, więc osiągnąłem maksymalną głębokość dla podanej wartości N = 4. Ostatni wiersz na powyższej liście jest „ukończony . ”

Wyzwanie

Celem jest napisanie najkrótszego programu / nazwanej funkcji, która wypisze / zwróci wypełniony wiersz dla danej wartości N. Powyższe pokazuje N = 4.

Wejście

Wejście będzie pojedynczą nieujemną liczbą całkowitą N. Długość wygenerowanej linii wyniesie wówczas 2 ^ N.

Wynik

Wyjście będzie zakończoną linią o długości 2 ^ N, utworzoną przez .i Xznaki. Końcowy znak nowej linii nie ma znaczenia.

Przykład I / O

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

Całkiem proste.

Pyth, 49

Mniej więcej tłumaczenie. Główną różnicą jest to, że nie używam listy reprezentującej linię, używam łańcucha.

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

Wypróbuj online .

                         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

Klip , 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 bajtów)

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

Wymagana liczba iteracji pętli to A061419 , ale pętla do jest krótsza niż jej obliczenie. Divmod zapisałby znak wewnątrz pętli do. Najbardziej marnotrawstwem jest konwersja wyjściowa, ale nie wiem, jak ją poprawić.

CJam, 55 53 51 50 bajtów

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

Coś na początek.

Wypróbuj online tutaj

Java, 209 207 195 191 bajtów

Jestem zaskoczony, że udało mi się to tak krótko. Prawdopodobnie jest jeszcze miejsce na poprawę. Jak zwykle sugestie będą mile widziane :)

Zwraca a char[]. Zadzwoń za pomocą 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;}

Zębaty:

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 bajtów dzięki Peter :)
4 bajty dzięki TNT;)

Haskell, 182 bajty

(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

Zastosowanie: f 5. Wyjście: X.X.X...X...X...X.XXX.XXX........

Niestety Haskell nie ma funkcji scalania w standardowych bibliotekach, więc muszę podać własną (-> %). Na szczęście muszę scalać tylko nieskończone listy, więc nie muszę obejmować podstawowych przypadków, tj. Pustych list. Nadal kosztuje 40 bajtów.

Jak to działa: zamiast ustawiać Xs bezpośrednio w tablicy, trzymam listę pozycji, w których się znajdują. Co więcej, nie owijam się w, 2^Nale ciągle zwiększam pozycje w kierunku nieskończoności (np. Dla N = 2 ze znakiem Xz przodu wygląda lista pozycji [0,4,8,12,16,20,…]). Biorę trzeci i czwarty element ( ci d), obliczam nową pozycję (c+d)/2, zachowuję ją dla listy wyników, łączę starą listę pozycji od pozycji 4 (the d) z nową, zaczynając od (c+d)/2i powtarzając. Zatrzymuję się, kiedy się (c+d)/2równa c. Na koniec dodaję a 0do listy wyników i drukuję Xw podanych pozycjach i .gdzie indziej.

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