# Create a binary ruler

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.

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

# 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

• Is the ~ is -1 or +1? – Stan Strum Sep 8 '17 at 1:58
• Never mind, it's (-x) - 1 – Stan Strum Sep 8 '17 at 1:59

# 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!

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

# 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

• I'm not entirely sure, but I think you can remove the |. – Kritixi Lithos Jun 13 '17 at 17:56
• @KritixiLithos Aha! In hindsight, it's so obvious! Thanks for the tip. :) – DJMcMayhem Jun 13 '17 at 18:03

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

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

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

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

# Octave, 45 bytes

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


Try it on Octave Online!

Instead of '#' prints '!'.

# 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!

# 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",""]
ç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"]

• 20 bytes – Shaggy Jun 13 '17 at 17:46
• @Shaggy Actually, you don't even need the l – ETHproductions Jun 13 '17 at 17:55
• @ETHproductions: yep, just figured that out. 18 bytes – Shaggy Jun 13 '17 at 18:02
• 17 bytes – Shaggy Jun 13 '17 at 18:08
• 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... – ETHproductions Jun 13 '17 at 18:41

# 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) {
putchar('\n');
}
}


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

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

# 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

• @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. – KarlKastor Jun 14 '17 at 17:21

# Python 2, 47 bytes

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


Try it online!

# 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()))

• @RickHitchcock Fixed. – darrylyeo Jun 13 '17 at 18:19

# Mathematica, 69 bytes

Rotate[Grid["#"~Table~#&/@(IntegerExponent[2*#,2]&/@Range[#])],Pi/2]&


## (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

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


Try it online! Example usage: f 10.

# k, 33 bytes

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


This only seems to work 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}


## 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!

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

# Charcoal, 27 23 bytes

↶Ｆ…·¹Ｎ«Ｊι⁰#Ｗ¬﹪ι²«Ａ÷ι²ι#


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

• It's still absolute, just now it's called JumpTo (sorry) – ASCII-only Jun 17 '17 at 4:42
• @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...) – Neil Jun 17 '17 at 11:00
• @ASCII-only Huh, I should have remembered that from codegolf.stackexchange.com/a/119904 ... – Neil Jun 17 '17 at 11:03
• Do you have a GitHub account? – ASCII-only Jun 17 '17 at 11:04
• @ASCII-only I have two... I can't decide which one is more appropriate... – Neil Jun 17 '17 at 11:11

# J, 38 bytes

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


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

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

# 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)
}


## CJam, 34 bytes

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


Meh.

# 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!

• Suggest n+~x instead of n^x+1 – ceilingcat Jan 31 '19 at 20:29

# 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!