For an integer n that satisfies n > 0, write its value as a right-descending path based on its binary representation.

Rules

  • The first (most significant) set bit is always in the top-left corner.
  • When the next bit is set (a 1), draw a character ("filled") on the next line in the same column as the previous character drawn. Try to use spaces ("empty") to fill, but any character will do as long as it's always the same.
  • When the next bit is unset (a 0), draw a character ("filled") on the same line immediately to the the right of the previous character drawn.
  • Your code must support numbers with at least 20 significant bits.
  • Write a full program, a function, a lambda, etc. but no snippet.
  • No leading spaces (or "empty" char) / lines allowed
  • Any number of trailing spaces (or "empty" char) / lines allowed
  • Any kind of 1D input is accepted: number, string, array of booleans, etc. Keep the order of bits untouched though.
  • Any kind of visual 2D output is accepted: on stdout, a string (with any two distinct values representing "filled" and "empty"), you can even output a matrix if you want. A list of numbers seems hard to reconcile with the "no heading spaces" rule, but I'm open to it if you find a way to use it. Note: if you chose to print or return a string, the characters used must be ASCII characters in the codepoints range [32-126].
  • Standard loopholes are banned.
  • This is codegolf so the shortest code wins.

Examples

Input: 1

*

Input: 2

**

Input: 3

*
*

Input: 4

***

Input: 5

**
 *

Input: 6

*
**

Input: 7

*
*
*

Input: 25

*
***
  *

Input: 699050

**
 **
  **
   **
    **
     **
      **
       **
        **
         **

Input: 1047552

*
*
*
*
*
*
*
*
*
***********

Input: 525311

**********
         *
         *
         *
         *
         *
         *
         *
         *
         *
         *
  • Sandbox – Olivier Grégoire 2 days ago
  • Does "allowed input array of booleans" mean that taking the input in the form of the number's binary representation as an array is allowed? – Nit yesterday
  • 3
    @Nit Any kind of 1D input. So if the number is 5, you may have an input array similar to [1,0,1], yes. – Olivier Grégoire yesterday
  • So how free is that format really ? I'd like to take a number as the binary digits with the first 1 moved to the end, so since 9 is 1001 I'd like my input to be 0011. Is that OK? – Ton Hospel yesterday
  • Having the first bit being 1 first is part of the challenge, and (re-)moving that bit would be trivializing the challenge so I'm afraid I'll have to say you no, @TonHospel . You can remove it from your input in the program, though. – Olivier Grégoire yesterday

24 Answers 24

MATL, 14 bytes

J_iB^YsJ+'o-'&XG

Produces graphical output as a path starting at coordinates (0,0). Try it at MATL Online! Or see some offline examples below:

  • Input 7:

    enter image description here

    Output:

    enter image description here

  • Input 699050:

    enter image description here

    Output:

    enter image description here

If you prefer, you can see the path as complex coordinates for 9 bytes:

J_iB^YsJ+

Try it online!

Explanation

J_      % Push -1j (minus imaginary unit)
i       % Push input number
B       % Convert to binary. Gives an array of 0 and 1 digits
^       % Power, element-wise. A 0 digit gives 1, a 1 digit gives -1j
Ys      % Cumulative sum. Produces the path in the complex plane
J+      % Add 1j, element-wise. This makes the complex path start at 0
'o-'    % Push this string, which defines plot makers
&XG     % Plot

MATL, 10 bytes

YsG~YsQ1Z?

Inputs an array of binary digits. Outputs a matrix.

Try it online!

Explanation

Ys    % Implicit input: array of binary digits. Cumulative sum. This gives the
      % row coordinates
G     % Push input again
~     % Negate: change 0 to 1 and 1 to 0
Ys    % Cumulative sum
Q     % Add 1. This gives the column coordinates
1Z?   % Matrix containing 1 at those row and column coordinates and 0 otherwise.
      % Implicit display

C# (.NET Core), 155 123 120 113 101 bytes

Saved 32 bytes due to input being able to be received as an array of bits.
Saved 7 bytes thanks to @auhmaan.
Saved 10 bytes thanks to @KevinCruijssen.

n=>{var m="";for(int i=0,c=1;i<n.Length;)m+=n[i++]<1?c++%1+"":(i>1?"\n":"")+"0".PadLeft(c);return m;}

Try it online!

  • Can't you change the +new string(' ',c)+"*" to +"*".PadLeft(c) ( saves 7 bytes ) ? – auhmaan yesterday
  • @auhmaan You're right, thanks! – Ian H. yesterday
  • -4 bytes by printing 0 instead of *: if(n[i++]<1){m+="*";c++;} to if(n[i++]<1)m+=c++%1; and "*".PadLeft(c); to "0".PadLeft(c); – Kevin Cruijssen yesterday
  • Correction, it's actually -12 bytes because m+= can now be a ternary-if: m+=n[i++]<1?c++%1+"":(i>1?"\n":"")+"0".PadLeft(c); – Kevin Cruijssen yesterday
  • 1
    @KevinCruijssen Thanks, using 0's and the use of the ternary operator is really smart! I also fixed the case for 699060, by simply setting c to one the beginning, I kinda missed that while checking the test cases. – Ian H. yesterday

Python 2, 100 99 81 78 73 66 bytes

a='';x=0
for c in input():a+=('\n'+' '*x)*c+'*';x+=1-c
print a[1:]

Try it online!

Recursive version:

Python 2, 71 69 67 bytes

f=lambda n,x=0:n and('\n'[:x]+' '*x)*n[0]+'*'+f(n[1:],x+1-n[0])or''

Try it online!

05AB1E, 18 17 14 bytes

γ€gć¸s>«1IÔ·ÌΛ

Try it online!

Explanation

γ€g             # Push the input as the array as chuncks of consecutive elements, map with length
   ć¸s>«        # Increment each value except the first one
        1I      # Push 1 and the input       
          Ô     # Push connected uniquified input (first elements of each chunck of consecutive elements in the input)
           ·Ì   # Map each with 2 * a + 2
             Λ  # Draw canvas :-)
  • 3 bytes thanks to @Emigna

05AB1E canvas's explanation

  • 1
    γ€gć¸s>«1IÔ·ÌΛ should save 4 bytes. – Emigna yesterday
  • @Emigna Brilliant, thanks ! Totally forgot that there was an a+2 builtin o: – Kaldo yesterday

Charcoal, 22 20 19 11 10 bytes

F⮌S¿Iι↑*←*

Only my second Charcoal answer thus far.

Takes the input as binary-String (i.e. 699050 as 10101010101010101010).

-9 bytes thanks to @Neil suggesting to loop backwards.

Try it online.

Explanation:

Read STDIN as string in reversed order:

Reverse(InputString())
⮌S

Loop over its binary digits as strings ι:

For(Reverse(InputString()))
F⮌S

If ι casted back to a number is 1, print the * upwards, else print the * towards the left.

If(Cast(i)) Print(:Up,"*"); Else Print(:Left,"*");
¿Iι↑*←*
  • 1
    This would be half as long if you printed the string in reverse, starting at the end and working up and left. – Neil yesterday
  • @Neil Ok, now it should be fixed. Thanks! -8 bytes – Kevin Cruijssen yesterday
  • 1
    Save another byte by removing the {}s. – Neil yesterday
  • @Neil Ah, I had hoped the verbose converter would be smart enough to golf those kind of things itself. ;) Including Assign(InputString(), a); to InputString(a); or Print(:Right, "*"); to Print("*");. Thanks! I still have a lot to learn, but it's an amazing language for sure! – Kevin Cruijssen yesterday
  • 1
    Base only costs 1 byte as you don't need the Cast at all: F⮌↨N²¿ι↑*←*. – Neil yesterday

Jelly, 8 bytes

¬œṗ+\Ṭz0

A monadic link accepting a number as a list of ones and zeros (e.g. 13 is [1,1,0,1]) returning a list of lists of ones and zeros where the first list is the first row.

Try it online! or see a formatted test-suite

How?

¬œṗ+\Ṭz0 - Link: list L           e.g. [1,1,0,0,1,1,0,1] (i.e. 205)
¬        - logical NOT L               [0,0,1,1,0,0,1,0]
    \    - cumulative reduce L by:
   +     -   addition                  [1,2,2,2,3,4,4,5]
 œṗ      - partition @ truthy indices  [[1,2],[2],[2,3,4],[4,5]]
     Ṭ   - un-truth (vectorises)       [[1,1],[0,1],[0,1,1,1],[0,0,0,1,1]]
      z0 - transpose with filler 0     [[1,0,0,0],[1,1,1,0],[0,0,1,0],[0,0,1,1],[0,0,0,1]]
         -                        i.e.  1000
                                        1110
                                        0010
                                        0011
                                        0001

Haskell, 74 70 67 bytes

tail.f
f(x:r)|h:t<-f r=[""|x]++('*':h):map([' '|not x]++)t
f[]=[""]

Try it online! Takes a list of Booleans as input and returns a list of lines.

Japt, 19 17 bytes

Ë?R+Tî +Q:°T©Qìx
Ë?                 // Map over the input and if the current value is 1:
  R+               // Return a new line and
    Tî +           // a space repeated T (with initial value 0) times and
        Q          // a \".
         :         // If the current value is 0:
          °T       // Increment T
            ©Q     // and return \".
              Ã    // When all of that is done,
               ¬   // turn the array into a string
                x  // and trim it, removing the excess new line at the start.

Takes input as an array of bits, for example [1,0,1], outputs " instead of *.
Shaved two bytes off thanks to Oliver.

Try it online!

  • Nice one. You can replace SpT with - î is similar to p, except it defaults to " ". Also, there's a shortcut for q : ¬ – Oliver yesterday
  • @Oliver Thanks, I didn't know about î, certainly very handy. I often check for chances to use the shortcuts, but I still always miss some of them, thanks a lot for your help. – Nit yesterday

Haskell, 126 bytes

(#)n=maximum.map(!!n)
f l|s<-scanl1(zipWith(+))$(\a->[1-a,a])<$>l=unlines[[last$' ':['#'|elem[x,y]s]|x<-[0..0#s]]|y<-[1..1#s]]

Input as a list of zeroes and ones. Transforms number into offset by x↦[1-x,x] and calculates the partial sums. Final output is done with two nested list comprehensions.

Try it online!

JavaScript (ES6), 48 bytes

Same I/O format and same logic as the recursive version below.

a=>a.map((n,i)=>n?i&&p+0:+(p+=' '),p=`
`).join``

Try it online!

Or 42 bytes if this format is acceptable.


Recursive version, 56 bytes

Takes input as an array of integers (0 or 1). Uses 0 for filled and space for empty.

f=([n,...a],p=`
`,x=0)=>1/n?(n?x+0:+(p+=' '))+f(a,p,p):a

Try it online!

Commented

f = (               // f = recursive function taking:
  [n, ...a],        //   n = current bit; a[] = remaining bits
  p = `\n`,         //   p = padding string, initialized to a linefeed
  x = 0             //   x = 0 on the 1st iteration / equal to p after that
) =>                //
  1 / n ?           // if n is defined:
    ( n ?           //   if n = 1:
        x + 0       //     append x + 0 --> either the integer 0 on the first iteration
                    //                      or the padding string followed by a '0'
      :             //   else:
        +(          //     append the integer 0 (whitespace coerced to a number)
          p += ' '  //     and append a space to the padding string
        )           //
    ) + f(a, p, p)  //   append the result of a recursive call with x = p
  :                 // else:
    a               //   append the empty array a[], forcing coercion to a string

R, 59 bytes

function(n,x=sum(n|1))matrix(1:x^2%in%cumsum((n-1)%%x+1),x)

Try it online!

Takes input as an array of bits.

Returns a boolean matrix of TRUE and FALSE representing a * and a , respectively.

Also has some stuff in the footer to print a matrix corresponding to the specs above, for ease of testing.

APL+WIN, 65 or 46 bytes

Prompts for input of the integer

n←+/i←((1+⌊2⍟n)⍴2)⊤n←⎕⋄m←(n,n)⍴' '⋄m[⊂[2](+\i),[1.1]1++\~i]←'*'⋄m

or for numerical vector of the binary representation of the integer

m←(2⍴+/n←⎕)⍴' '⋄m[⊂[2](+\i),[1.1]1++\~i]←'*'⋄m

assuming I have read the comments to certain answers correctly and the latter input is allowed.

Pyth, 23 bytes

p\*VtQINp+b*Zd.?=hZ)p\*

Try it here

Explanation

p\*VtQINp+b*Zd.?=hZ)p\*
p\*                       Print the leading *.
   VtQ                    For each bit (excluding the leading 1)...
      IN      .?   )      ... If the bit is set...
        p+b*Zd            ... Print a newline and a bunch of spaces...
                =hZ       ... Otherwise, increase the count of spaces...
                    p\*   ... Then print the next *.

Perl 5 -p, 54 36 bytes

s/./$&?"
".$"x$i.1:++$i&&1/ge;s/.//s

Try it online!

Cut it way down after I realized that the input could be a bit string.

Bash + GNU utilities, 38

dc -e?2op|sed 's/\B1/^K^H*/g;s/[10]/*/g'

Here ^K and ^H are literal vertical-tab and backspace control characters. These don't render well on browsers, so this script may be recreated as follows:

base64 -d <<< ZGMgLWU/Mm9wfHNlZCAncy9cQjEvCwgqL2c7cy9bMTBdLyovZyc= > binpath.sh

Run in a terminal. Input is via STDIN.

This answer may stretch the specifications too far - there are in fact no leading characters on each line of output - all positioning is done with control characters. If this is too much of a stretch, then the output may be piped to |col -x|tac for an extra 11 bytes.

SmileBASIC, 64 59 57 bytes

INPUT N@L
GPSET X,Y
B=N<0X=X+B
Y=Y+(X>B)N=N<<1ON!N GOTO@L

The highest bit (sign bit) is checked, and if it's 1, the X position increases. If the sign bit is less than the X position (that is, the sign bit is 0 and X is not 0) the Y position increases.

The first movement will always be horizontally, so Y movement is blocked until after the first X movement. This ensures that the Y position doesn't increase during the leading 0 bits.

Then N is shifted left, and this repeats until N reaches 0.

Ruby, 63 bytes

->n{s=""
n.to_s(2).gsub(/./){$&==?1?"
"+s+?*:(s+=" ";?*)}[1,n]}

Try it online!

Batch, 113 bytes

@set s=
:l
@shift
@if %1.==0. set s=%s%+&goto l
@echo %s%+
@if not %s%.==. set s=%s:+= %
@if %1.==1. goto l

Takes a list of bits as command-line arguments. Uses + instead of * because * has a special meaning inside %s:...=...% expansions.

Python 2, 59 bytes

s=p='\n'
for x in input():s+=p*x+'*';p+=' '[x:]
print s[2:]

Try it online!

Based off TFeld's solution.

Java 10, 100 106 bytes

b->{var s="";int i=0,j;for(var c:b){if(c)for(s+="\n",j=i;j-->0;)s+=0;else++i;s+=1;}return s.substring(1);}

Takes an array of booleans and returns a String (0s are empty, 1s are filled). Try it online here.

Thanks to Olivier Grégoire for helping me golf it a bit more and alerting me to the fact that my output format was not up to the spec.

Ungolfed version:

b -> { // lambda taking an array of booleans as argument
    var s = ""; // the output String
    int i = 0,  // the number of "empty" characters to output
    j;          // iterator variable for outputting the "empty" characters
    for(var c : b) { // iterate over the boolean array (the binary digits)
        if(c) // if it's a '1'
            for(s += "\n", // output a newline
            j = i; j-- > 0;) s += 0; // output the "empty" characters
        else // if it's a '0'
            ++i; // move one to the right on the next line
        s += 1; // output the "filled" character
    }
    return s.substring(1); // output the constructed String, minus the leading newline
}
  • I golfed 5 bytes: {if(c){s+="\n";for(j=i;j-->0;)s+=0;}else++i;s+=1;} – Olivier Grégoire yesterday
  • Even further: {if(c)for(s+="\n",j=i;j-->0;)s+=0;else++i;s+=1;} – Olivier Grégoire yesterday
  • Though, you don't print on the first line but on the second one. From the challenge: "No leading spaces (or "empty" char) / lines allowed" – Olivier Grégoire yesterday
  • @OlivierGrégoire Thanks. I have edited. – O.O.Balance yesterday

Python 2, 113 Bytes

def f(a):
 o='*';r=[o]
 for i in bin(a)[3:]:
  if'0'<i:r+=[' '*len(r[-1][1:])]
  r[-1]+=o
 print'\n'.join(r)

Not sure if this one counts (it outputs an array of each of the lines), but if so then I'll change my byte count to 103:

def f(a):
 o='*';r=[o]
 for i in bin(a)[3:]:
  if'0'<i:r+=[' '*len(r[-1][1:])]
  r[-1]+=o
 print r

Java (JDK 10), 83 bytes

a->{int m[][]=new int[20][20],r=0,i=0;for(int b:a)m[r+=i<1?0:b][i++-r]=1;return m;}

Try it online!

  • Supports at most 20 bits.
  • Input as int[]
  • Output as int[][]

TI-Basic (TI-84 Plus CE), 85 bytes

Prompt L
1→X
1→Y
DelVar [A]
sum(LL
{Ans,1-Ans+dim(LL→dim([A]
1→[A](Y,X
For(I,2,dim(LL
Y+LL(I→Y
X+not(LL(I→X
1→[A](Y,X
End
[A]

Prompts for a boolean list, returns a matrix of 0 and 1.

Goes through the list, incrementing X if the next 'bit' is 0, changing Y otherwise, then adding a 1 to the matrix at that location, and returns the matrix at the end.

TI-Basic is a tokenized lanugage.

  • 1 byte: Prompt , L*6, (newline)*12, 1*5, *7, X*5, Y*5, sum(, L*5, {, Ans*2, ,*5, -, +*3, dim(*3, (*4, For(, I*3, 2, not(, End = 73 bytes
  • 2 bytes: Delvar , [A]*5 = 12 bytes
  • Total: 85 bytes

TI-Basic (TI-84 Plus CE), 56 bytes

Prompt L
1→X
1→Y
Output(Y,X,"*
For(I,2,dim(LL
Y+LL(I→Y
X+not(LL(I→X
Output(Y,X,"*
End

Same processs as above, but using graphical output (limited by screen size: 10 rows, 26 columns, so max 10 1s and 25 0s) as it goes, instead of adding to a matrix.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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