22
\$\begingroup\$

Given a number n, generate the first n columns of this pattern:

                               #
               #               #
       #       #       #       #
   #   #   #   #   #   #   #   #
 # # # # # # # # # # # # # # # #
################################ ...

The height of the column at (1-indexed) n is the number of trailing 0 bits in n's binary representation, plus one. As a result, the bottom layer has every column filled in, the second layer every second column, the third layer every fourth column, etc.

Rules

  • You may input and output through any standard method.
  • You may assume the input is an integer between 1 and 999, inclusive.
  • The output may contain any amount of whitespace, as long as the pattern is intact.
  • The pattern must be 1-indexed, and in the same format as shown here.
  • You may use any single non-whitespace character in place of #, but you may not change the space character.

Test cases

1
#

2
 #
##

3
 # 
###

4
   #
 # #
####

5
   # 
 # # 
#####

7
   #   
 # # # 
#######

32
                               #
               #               #
       #       #       #       #
   #   #   #   #   #   #   #   #
 # # # # # # # # # # # # # # # #
################################

A few larger test cases can be found here.

Scoring

This is , so the shortest code in bytes in each language wins.

\$\endgroup\$
  • 2
    \$\begingroup\$ Related. \$\endgroup\$ – ETHproductions Jun 13 '17 at 17:06
  • \$\begingroup\$ Now I can measure distance in binary! Oh wait... \$\endgroup\$ – Okx Jun 13 '17 at 17:08
  • 2
    \$\begingroup\$ 1. Does the ruler have to be horizontal? 2. Do the markings have to be #? \$\endgroup\$ – Jonathan Allan Jun 13 '17 at 17:24
  • 1
    \$\begingroup\$ @JonathanAllan 1. Yes, and 2. No, they can be any single non-space character. I've added this to the rules. \$\endgroup\$ – ETHproductions Jun 13 '17 at 17:25
  • \$\begingroup\$ The sequence at OEIS: A001511 \$\endgroup\$ – Not a tree Jun 13 '17 at 23:00

24 Answers 24

11
\$\begingroup\$

Python 2, 54 bytes

i=n=input()
while i:i-=1;print((' '*~-2**i+'#')*n)[:n]

Try it online!

Prints with lots of leading whitespace. Each row i counting down from n repeats a pattern of 2**i-1 spaces followed by a #. This pattern is repeated up to the width of the ruler, which is the input n. This is done by multiplying the pattern string by n and taking the first n characters with [:n].

The pattern can be made by string formatting for an equal length alternative.

i=n=input()
while i:i-=1;print('%%%ds'%2**i%'#'*n)[:n]

A cute slicing method is longer.

n=input();s=~-2**n*' '+'#'
exec"s=s[1::2]*2;print s[:n];"*n
\$\endgroup\$
  • \$\begingroup\$ Is the ~ is -1 or +1? \$\endgroup\$ – Stan Strum Sep 8 '17 at 1:58
  • \$\begingroup\$ Never mind, it's (-x) - 1 \$\endgroup\$ – Stan Strum Sep 8 '17 at 1:59
10
\$\begingroup\$

Python 3, 74 bytes

n=int(input())
a=1
while a<n:a*=2
while a:print(("%%%dd"%a%4*n)[:n]);a//=2

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Wow, it took me a while to figure out how the rows are generated. Well done. \$\endgroup\$ – ETHproductions Jun 13 '17 at 17:29
  • 2
    \$\begingroup\$ a=2**len(bin(n)) for 72 bytes \$\endgroup\$ – ovs Jun 13 '17 at 17:50
  • 2
    \$\begingroup\$ It will hit memory errors quickly, and print a bunch of extra white space (allowed) - but you can do 54 using Python 2. \$\endgroup\$ – Jonathan Allan Jun 13 '17 at 18:20
9
\$\begingroup\$

V, 17, 16 bytes

é#Àñä}Är {ñÎÀlD

Try it online!

Hexdump:

00000000: e923 c0f1 e416 7dc4 7220 7bf1 cec0 6c44  .#....}.r {...lD

Thanks to @KritixiLithos for saving one byte!

This algorithm is horribly inefficient, but it should work in theory for any size input.

It works by generating the first n iterations of the following pattern:

#

 #
##

   #
 # #
####

       #
   #   #
 # # # #
########

               #
       #       #
   #   #   #   #
 # # # # # # # #
################

                               #
               #               #
       #       #       #       #
   #   #   #   #   #   #   #   #
 # # # # # # # # # # # # # # # #
################################

And then chopping off all but the first n columns. As such, this will produce a ton of leading whitespace, but the OP said:

The output may contain any amount of whitespace, as long as the pattern is intact

Explanation:

é#                      " Insert an '#'
  Àñ           ñ        " 'N' times:
    ä<C-v>}             "   Duplicate every line blockwise (duplicating horizontally instead of vertically)
           Ä            "   Duplicate the top line. This conveniently puts us on the first non-whitespace character (that is, '#')
            r           "   Replace this character with a space
              {         "   Move to the beginning of the buffer
                Î       " On every line:
                 Àl     "   Move 'N' characters to the right ('l' for right, makes sense, right?)
                   D    "   And delete everything after the cursor
\$\endgroup\$
  • \$\begingroup\$ I'm not entirely sure, but I think you can remove the |. \$\endgroup\$ – Kritixi Lithos Jun 13 '17 at 17:56
  • \$\begingroup\$ @KritixiLithos Aha! In hindsight, it's so obvious! Thanks for the tip. :) \$\endgroup\$ – DJMcMayhem Jun 13 '17 at 18:03
5
\$\begingroup\$

JavaScript (ES6), 61 58 bytes

f=(n,c=n,s='')=>c?f(n,c>>1,s+s+' ')+`
`+(s+1).repeat(c):''

Saved 1 byte thanks to @ETHProductions, then 2 more bytes when I saw that any character could be used.

A recursive solution.

Test cases:

f=(n,c=n,s='')=>c?f(n,c>>1,s+s+' ')+`
`+(s+1).repeat(c):''

console.log(f(32));
console.log(f(1));  
console.log(f(5));  
console.log(f(7));  

Animation:

f=(n,c=n,s='')=>c?f(n,c>>1,s+s+' ')+`
`+(s+1).repeat(c):''

for(let i = 1 ; i < 64 ; i++) {
  setTimeout(_=>document.querySelector('pre').textContent=f(i), i*40);
}
<pre>

\$\endgroup\$
  • 1
    \$\begingroup\$ Well done. You can change c/2|0 to c>>1 to save a byte. \$\endgroup\$ – ETHproductions Jun 13 '17 at 19:06
  • \$\begingroup\$ Nice, I need to brush up on my bitwise operators. \$\endgroup\$ – Rick Hitchcock Jun 13 '17 at 19:09
4
\$\begingroup\$

APL (Dyalog), 21 bytes

'# '[1+⊖0⍪∨⍀⊖2⊥⍣¯1⍳⎕]

Try it online!

'# '[…`] index the string with

 get input

 that many integers

2⊥⍣¯1 convert to binary, using as many digits as needed (one number in each column)

 flip upside down

∨⍀ vertical cumulative OR reduction

0⍪ concatenate zeros on top

 flip upside down (i.e. back up again)

1+ add one (for 1-based indexing)

\$\endgroup\$
3
\$\begingroup\$

Jelly, 11 10 bytes

Rọ2‘4ẋz⁶ṚY

Try it online!

1 byte saved after the OP added a relaxation that the character doesn't have to be #.

\$\endgroup\$
2
\$\begingroup\$

Octave, 45 bytes

@(n)[[sort(cummin(de2bi(g=0:n)'));g|1]+32 '']

Try it on Octave Online!

Instead of '#' prints '!'.

\$\endgroup\$
2
\$\begingroup\$

PHP, 139 bytes

for($f=array_fill(0,$l=1+log($a=$argn,2)," ");$n++<$a;)for($h=1+strspn(strrev(decbin($n)),$i=0);$i<$h;)$f[$l-++$i][$n]=3;echo join("
",$f);

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Japt, 20 17 bytes

Saved 3 bytes thanks to @Shaggy and @ETHproductions

õ_¤q1 o Ä ço÷z w

Try it online!

Explanation:

Input: 5

õ_¤q1 o Ä ço÷z w
õ           Ã       // Create a range [1...Input] [1,2,3,4,5]
 _                  // Map; At each item:
  ¤                 //   Convert to binary        ["1","10","11","100","101"]
   q1               //   Split on "1"             [["",""],["","0"],["","",""],["","00"],["","0",""]]
      o             //   Get the last item        ["","0","","00",""]
        Ä           //   Add 1                    [["1","01","1","001","1"]]
          ço        //   Fill with "o"            ["o","oo","o","ooo","o"]
             ·      // Join with new-lines        ["o\noo\no\nooo\no"]
              z     // Rotate 90 degrees          ["ooooo\n o o \n o   "]
                w   // Reverse                    ["   o \n o o \nooooo"]
\$\endgroup\$
  • \$\begingroup\$ 20 bytes \$\endgroup\$ – Shaggy Jun 13 '17 at 17:46
  • \$\begingroup\$ @Shaggy Actually, you don't even need the l \$\endgroup\$ – ETHproductions Jun 13 '17 at 17:55
  • \$\begingroup\$ @ETHproductions: yep, just figured that out. 18 bytes \$\endgroup\$ – Shaggy Jun 13 '17 at 18:02
  • \$\begingroup\$ 17 bytes \$\endgroup\$ – Shaggy Jun 13 '17 at 18:08
  • \$\begingroup\$ A cool trick with bitwise operators is to do n&-n to capture only the final 1 and all trailing 0s in n. Not sure if this will help, but it's worth a shot... \$\endgroup\$ – ETHproductions Jun 13 '17 at 18:41
2
\$\begingroup\$

C, 84 74 bytes

f(i,l,m){putchar(32+3*!(i&m));i<l?f(i+1,l,m):m?putchar(10),f(1,l,m>>1):1;}

Ungolfed:

void f(int counter, int length, int mask) {
    putchar((counter&mask) ? ' ' : '#');
    if(counter<length) {
        f(counter+1, length, mask);
    } else if(mask) {
        putchar('\n');
        f(1, length, mask>>1);
    }
}

Test with:

int main() {
    f(1, 32, 1023);
    putchar('\n');
    f(1, 1, 1023);
    putchar('\n');
    f(1, 999, 1023);
    putchar('\n');
}

Explanation

Once again, recursion takes less characters in C than iteration, so the two loops are expressed as the two recursional invocations.

Also, C is a great language for playing tricks with boolean expressions, allowing the decision of whether to put a blank or a # to be expressed by the expression 32+3*!(i&m). A space has the ASCII value of 32, the # is ASCII 35, so we get a blank if any of the bits in the mask is set in i.

\$\endgroup\$
  • \$\begingroup\$ Do you even need the int i,l,m? \$\endgroup\$ – Zacharý Jun 14 '17 at 15:07
  • \$\begingroup\$ @ZacharyT No, turns out I didn't. Thanks for saving those 10 bytes :-) \$\endgroup\$ – cmaster Jun 14 '17 at 15:18
2
\$\begingroup\$

Pyth, 15 Bytes

j_.tm*Nhx_.Bd1S

Try it!

explanation

j_.tm*Nhx_.Bd1S
    m         SQ   # map over the numbers from 0 to the implicit input (lambda variable: d)
          .Bd      # Convert d to a binary string: (12 -> 1100)
         _         # reverse: (1100 -> 0011)
        x    1     # get the location of the first 1 ( 2 )
     *Nh           # make one more than that " quotation marks (""")
 _.t               # transpose the list of quotation mark strings and reverse it
j                  # join on newline
\$\endgroup\$
  • \$\begingroup\$ @JasonS It's a golfing language based on Python! I now linked pyth's github. I thought the Try it! link to the online Executor would be sufficient. \$\endgroup\$ – KarlKastor Jun 14 '17 at 17:21
2
\$\begingroup\$

Python 2, 47 bytes

f=lambda n:n and' '.join(f(n/2))+'\n'+n*'#'or''

Try it online!

\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES8), 71 bytes

The padStart() function was introduced in ECMAScript 2017!

N=>eval(`for(s='',n=1;n<=N;n*=2)s='\\n'+'#'.padStart(n).repeat(N/n)+s`)

f=
N=>eval(`for(s='',n=1;n<=N;n*=2)s='\\n'+'#'.padStart(n).repeat(N/n)+s`)

console.log(f(+prompt()))


JavaScript (ES6), 77 bytes

N=>eval(`for(s='',n=1;n<=N;n*=2)s='\\n'+(' '.repeat(n-1)+'#').repeat(N/n)+s`)

f=
N=>eval(`for(s='',n=1;n<=N;n*=2)s='\\n'+(' '.repeat(n-1)+'#').repeat(N/n)+s`)

console.log(f(+prompt()))

\$\endgroup\$
  • 1
    \$\begingroup\$ @RickHitchcock Fixed. \$\endgroup\$ – darrylyeo Jun 13 '17 at 18:19
1
\$\begingroup\$

Mathematica, 69 bytes

Rotate[Grid["#"~Table~#&/@(IntegerExponent[2*#,2]&/@Range[#])],Pi/2]&
\$\endgroup\$
1
\$\begingroup\$

(WESRRMICGSE): 237 bytes

IF(ROW()<=FLOOR(LOG(COUNTA(R1C:R[-1]C,R[1]C:R[1024]C)+1,2),1)+2,LEFT(REPT(REPT(" ",FLOOR(POWER(2,LOG(COUNTA(R1C:R[-1]C,R[1]C:R[1024]C)+1,2)-ROW()+2),1)-1) &"#",COUNTA(R1C:R[-1]C,R[1]C:R[1024]C)+1),COUNTA(R1C:R[-1]C,R[1]C:R[1024]C)+1),"")

Alright. 'splaining time.

First off, replace every COUNTA(R1C:R[-1]C,R[1]C:R[1024]C)+1 with simply [i], for input. the token counts the number of cells, not including itself, that contain a formula, and then adds one, to include itself. Since WESRRMICGSE drags a formula according to the input you give it, this token always results in the input.

we have:

IF(ROW()<=FLOOR(LOG([i],2),1)+3,LEFT(REPT(REPT(" ",FLOOR(POWER(2,LOG([i],2)-ROW()+2),1)-1) &"#",[i]),[i]),"")

This is much more readable. You're going to see the FLOOR(LOG([i],2),1) token a lot, which simply means take the nearest power of 2 which is less than the input ([i]) number. eg: 4->4, 5->4, 6->4, 7->4, 8->8 ...etc. I'll replace that with GS[[i]]

IF(ROW()<=GS[[i]]+3,LEFT(REPT(REPT(" ",,FLOOR(POWER(2,LOG([i],2)-ROW()+2),1),1)-1) &"#",[i]),[i]),"")

better. breaking down the if clause, we're testing if the row is less than or equal to GS[[i]]+3, because all rulers' height is equal to the GS[[i]]+1, this selects the rows which are equal to the height of the ruler. +1 for 1-indexing rows, and +1 again for WESRRMICGSE offset.

The FALSE result yields an empty cell (""), and a true result yields LEFT(REPT(REPT(" ",,FLOOR(POWER(2,LOG([i],2)-ROW()+2),1),1)-1) &"#",[i]),[i])

currently still editing, stay tuned

\$\endgroup\$
1
\$\begingroup\$

Haskell, 64 62 bytes

l m=([2..2^m]>>" ")++'#':l m
f n=unlines$take n.l<$>[n,n-1..0]

Try it online! Example usage: f 10.

\$\endgroup\$
1
\$\begingroup\$

k, 33 bytes

`0:|" #"{(1+!x){~y!x}/:(x>)(2*)\1}

This only seems to work in AW's interpreter.

Example of it working in AW's interpreter.

The oK version (which you can try online) seems to have a bug, requiring a slight change to make it work:

`0:|" #"{(1+!x){~y!x}/:{x>y}[x](2*)\1}
\$\endgroup\$
1
\$\begingroup\$

C#, 174 bytes

This method has two parameters, an input for the ruler length, and an output which is the ruler as string.

Golfed:

void R(int n,out string s){var l=new int[++n];int i,x=n,y=0;for(s="";x-->1;)for(i=0;0==(l[x]=(x>>i++&1)*i);y=y<i?i:y);for(y++;y-->0;s+='\n')for(x=0;++x<n;s+=y<l[x]?'#':' ');}

Indented:

void R(int n,out string s){                       // Return the result in an out parameter.
    var l=new int[++n];                           // Use a 1-based array.
    int i,x=n,y=0;                                //
    for(s="";x-->1;)                              // For each number x on the ruler
        for(i=0;0==(l[x]=(x>>i++&1)*i);y=y<i?i:y) // ... find lowest set bit of x, counting the maximum value.
            ;                                     //
    for(y++;y-->0;s+='\n')                        // Count down each line.
        for(x=0;++x<n;s+=y<l[x]?'#':' ')          // Output # for numbers that are tall enough.
            ;                                     //
}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Would converting to a Func<int, string> save you some bytes? \$\endgroup\$ – TheLethalCoder Jun 14 '17 at 15:20
1
\$\begingroup\$

Charcoal, 27 23 bytes

↶F…·¹N«Jι⁰#W¬﹪鲫A÷ι²ι#

Try it online! Link is to verbose version of code. Edit: Saved 4 bytes by switching to JumpTo.

\$\endgroup\$
  • \$\begingroup\$ It's still absolute, just now it's called JumpTo (sorry) \$\endgroup\$ – ASCII-only Jun 17 '17 at 4:42
  • \$\begingroup\$ @ASCII-only Ah, the wiki could do with an update. (Or I assume I could do it should you want to give me edit permission...) \$\endgroup\$ – Neil Jun 17 '17 at 11:00
  • \$\begingroup\$ @ASCII-only Huh, I should have remembered that from codegolf.stackexchange.com/a/119904 ... \$\endgroup\$ – Neil Jun 17 '17 at 11:03
  • \$\begingroup\$ Do you have a GitHub account? \$\endgroup\$ – ASCII-only Jun 17 '17 at 11:04
  • \$\begingroup\$ @ASCII-only I have two... I can't decide which one is more appropriate... \$\endgroup\$ – Neil Jun 17 '17 at 11:11
1
\$\begingroup\$

J, 38 bytes

3 :'|.|:''#''#~,.(1+|.i.1:)@#:"0>:i.y'

Not great. Lmk if the byte count is off -- I'm on my phone.

\$\endgroup\$
  • \$\begingroup\$ Looks like 38 to me, unless the 3 at the beginning is input... \$\endgroup\$ – ETHproductions Sep 9 '17 at 0:54
  • \$\begingroup\$ @ETHproductions thanks, shame switching from a tacit definition didn't save any bytes... \$\endgroup\$ – cole Sep 9 '17 at 2:07
  • 1
    \$\begingroup\$ 28 bytes with 0|.@|:'#'#"0~1#.2~:/\i.#:@,] \$\endgroup\$ – miles Sep 15 '17 at 11:35
0
\$\begingroup\$

Java (OpenJDK 8), 91 bytes

n->{int i=10,j;String s="";for(;i-->0;s+="\n")for(j=0;j++<n;)s+=j>>i<<i<j?' ':35;return s;}

Try it online!

Ungolfed:

n->{
    int i=10,j; // Since we are allowed extra whitespace, set columns always to 10
    String s = "";
    for(;i-->0;s+="\n")      // Every iteration add a newline, i=9..0
        for(j=0;j++<n;)      // j=1..n+1
            s+= j>>i<<i<j    // if j has less than i trailing 0s in binary form
                ?' '         // add a space else
                :35          // # (java handles ternary return types weirdly)
}
\$\endgroup\$
0
\$\begingroup\$

CJam, 34 bytes

ri{2bW%0+0#)}%_'#f*\:e>f{Se]}zW%N*

Meh.

\$\endgroup\$
0
\$\begingroup\$

C (gcc), 70 bytes

f(x,l,n){for(l=512;l/=2;)for(n=0;n++<=x;)putchar(n^x+1?n%l?32:35:10);}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Suggest n+~x instead of n^x+1 \$\endgroup\$ – ceilingcat Jan 31 at 20:29
0
\$\begingroup\$

Perl 5, 60 + 1 (-n) = 61 bytes

$n=0|1+(log)/log 2;say(($"x(2**$n-1),X)x($_/2**$n))while$n--

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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