12
\$\begingroup\$

Sometimes, when I'm really bored (really bored), I like to draw a line segment and draw points on it.

First, I draw a line segment of a certain size, which is 2^N for some value of N. The line will be represented by a series of . characters.

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

Then, I plot a point at the left end. Points will be represented by X characters.

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

Then, I follow a pattern. Starting at the most recently plotted point (which I'll call A), I advance to the next plotted point (B) on the line (wrapping around as necessary). Then, I advance to the next plotted point on the line (C). Then, I plot a new point half-way in between this third point (C) and the next already plotted point (D).

Whenever you wrap around the line, the "middle" is determined in wrapping manner. The newly plotted point is always to the right of C.

Let's say that the following line was my current line. Here is how I would plot the next two points. For this example, I'll label each important point with a letter.

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

Returning to the previous example, the next point will be plotted in the middle of the line.

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

This is perhaps a little bit of a special case: advancing to the next point simply leaves you where you started. The only useful halfway point is the "cyclic" halfway point (the halfway point on the line), as opposed plotting a point on top of itself.

Below is the series of points that I would plot on the line from here to the end.

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

There is no longer any room to plot the next point, as it would have to be wedged between two adjacent points, so I have reached the maximum depth for the given value of N = 4. The last line in the above list is "complete."

The Challenge

The goal is to write the shortest program/named function that will print/return the completed line for a given value of N. The above shows N = 4.

Input

Input will be a single non-negative integer N. The length of the generated line will then be 2^N.

Output

Output will be the completed line of length 2^N, formed by . and X characters. A trailing newline doesn't matter.

Example 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.......
Improve this question
\$\endgroup\$

7 Answers 7

Reset to default
4
\$\begingroup\$

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

Quite straightforward.

Pyth, 49

More or less a translation. Main difference is that I don't use a list representing the line, I use a string. 

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

Try it 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
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

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}
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

GolfScript (61 bytes)

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

The number of loop iterations required seems to be A061419, but the do-loop is shorter than calculating that. A divmod would save a char inside the do loop. The part which feels most wasteful is the output conversion, but I don't see how to improve it.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

CJam, 55 53 51 50 bytes

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

Something to start with.

Try it online here

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Java, 209 207 195 191 bytes

I'm surprised I was able to get it this short. There is probably still room for improvement. As usual, suggestions will be appreciated :)

This returns a char[]. Call using 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;}

Indented:

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 bytes thanks to Peter :)
4 bytes thanks to TNT ;)

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ (c%b+b)%b? Are you expecting c to be negative? \$\endgroup\$
    – Peter Taylor
    Commented Mar 12, 2015 at 21:18
  • \$\begingroup\$ c=0 and d=0 can be shortened to just c and d. int types defined at the class level are automatically initialized to 0. \$\endgroup\$
    – TNT
    Commented Mar 13, 2015 at 13:35
1
\$\begingroup\$

Haskell, 182 bytes

(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

Usage: f 5. Output: X.X.X...X...X...X.XXX.XXX........

Unfortunately Haskell doesn’t have a merge function in the standard libraries, so I have to provide my own (-> %). Fortunately I have to merge only infinite lists, so I don’t have to cover the base cases, i.e. empty lists. It still costs 40 bytes.

How it works: instead of setting the Xs directly in an array, I keep a list of positions where they are. Furthermore I do not wrap around at 2^N but keep on increasing the positions towards infinity (e.g. for N=2 with an X at the front, the position list looks like [0,4,8,12,16,20,…]). I take the 3rd and 4th element (c and d), calculate the new position (c+d)/2, keep it for the output list, merge the old position list from position 4 (the d) on with a new one starting with (c+d)/2 and recur. I stop when (c+d)/2 equals c. Finally I add a 0 to the output list and print Xs at the given positions and . elsewhere.

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
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.