9
\$\begingroup\$

Given a positive integer N ("virality"), your program should create an ASCII-art drawing of a tree with two branches of length N extending downwards and/or rightwards from the top-left corner.

The direction taken by each branch after the first asterisk can be either rightwards or downwards, and this choice should be made randomly1 at every next step.

For example, given an input of 5, the output might look like:

***
* ***
**
 **

The two branches are allowed to touch (be on adjacent cells), but not overlap (be on the same cell), so the following would not be allowed:

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

Examples

For input 1, the only possible output is:

**
*

(This will be present in all valid outputs, since having the two branches take the same path would cause them to overlap.)

Possible outputs for an input of 3 include:

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

For input 7:

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

For input 10:

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

This is , so the shortest valid answer (in bytes) wins.

1. This should uniformly random (i.e. a 50/50 chance of each direction), or as close to uniformly random as you can get on normal hardware.

\$\endgroup\$
  • \$\begingroup\$ Please comment if you're having any problems with consuming my long post - maybe I can shorten something (I'll try then). \$\endgroup\$ – nicael Apr 1 '18 at 20:21
  • 3
    \$\begingroup\$ Just learn to expect that. Sometimes it's busy as all heck. Other times it's quiet like it is now. Don't forget, it's also Easter. \$\endgroup\$ – Zacharý Apr 1 '18 at 21:06
  • \$\begingroup\$ I am not really sure what is wrong with my post. Would the one who downvoted be so kind to explain, please? \$\endgroup\$ – nicael Apr 1 '18 at 22:15
  • 1
    \$\begingroup\$ IMO N is better described as time :P \$\endgroup\$ – ASCII-only Apr 2 '18 at 12:14
  • 1
    \$\begingroup\$ Can we return a matrix of 0s and 1s instead of spaces and asterisks? \$\endgroup\$ – dylnan Apr 5 '18 at 20:14

12 Answers 12

5
\$\begingroup\$

CJam, 58 bytes

1a[TT]{2,ff+:m*{:-},mRT))0a*1${1t}/\}rifT;]::a:.+" *"ff=N*

Try it online!

The basic idea is that we start with [0 0] and then repeatedly add either 0 or 1 to each element (making sure that they are never equal except at the start to avoid overlap), collecting all intermediate results.

[[0 0] [0 1] [0 2] [0 2] [1 3]]

We then create a large array of arrays where each subarray contains 1s at indices given by the corresponding pair in the original array and 0s everywhere else.

[    [1]
    [1 1]
   [1 0 1]
  [1 0 1 0]
 [0 1 0 1 0] ]

This yields diagonal slices of the output matrix (where moving left to right corresponds to moving top-right to bottom-left in the actual matrix).

We can then use ::a:.+ to "de-diagonalize" and get the actual matrix (well, it's not really a matrix, but the other elements would be 0 anyways).

[ [1 1 1 1 0]
  [1 0 0 1]
  [1 1 0]
  [0 1]
  [0]        ]

Let 1 represent * and 0 represent , and join on newlines, and we get:

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

Charcoal, 31 24 bytes

F²«J⁰¦⁰F⊕θ«¿ι*↓*≔‽²ι¿KK↗

Try it online! Link is to verbose version of code. Originally I thought it would be easier to make the first step random but it turned out to be golfier to make the first branch predictable. Explanation:

F²«

Loop twice, using index variable i. (This actually iterates over an implicit list, so it's safe to mutate i inside the loop.)

J⁰¦⁰

Jump to the origin of the canvas.

F⊕θ«

Loop N+1 times.

¿ι*↓*

Print a *, but leave the cursor either to the right or below the cursor depending on the value of i.

‽²ι

Randomise the value of i for the next iteration of the inner loop.

¿KK↗

If the current character is a *, this means that we're the second branch and we went down instead of right, so move up right to correct that. (The first branch always starts downwards so the second branch will always be above it, meaning that we only need to check for a vertical collision.)

\$\endgroup\$
  • \$\begingroup\$ It's almost correct, however it prints not N-sized branches, but N-1 sized :) \$\endgroup\$ – nicael Apr 2 '18 at 9:36
  • \$\begingroup\$ @nicael Sorry, fixed. \$\endgroup\$ – Neil Apr 2 '18 at 10:05
  • \$\begingroup\$ You've probably already seen this too many times, but: 23 bytes \$\endgroup\$ – ASCII-only Apr 2 '18 at 11:29
3
\$\begingroup\$

Java 10, 273 272 268 239 bytes

n->{var c=new char[++n][n];for(var d:c)java.util.Arrays.fill(d,' ');for(int i=0,j=0,k=0,l=0,r=0,s=0,t=0,u=0;n-->0;){c[i+=r][j+=s]=c[k+=t][l+=u]=42;do{r=t=2;r*=Math.random();t*=Math.random();s=r^1;u=t^1;}while(i+r==k+t&j+s==l+u);}return c;}

Try it online here.

Thanks to Kevin Cruijssen for golfing 29 bytes.

Ungolfed version:

n -> { // lambda taking an int as argument
    var c = new char[++n][n]; // the output; increment the virality since the root does not count
    for(var d : c) // for every line
        java.util.Arrays.fill(d,' '); // initialize it with spaces
    for(int i = 0, j = 0, // coordinates of the first branch
            k = 0, l = 0, // coordinates of the second branch
            r = 0, s = 0, // offsets for the first branch, one will be 0 and the other 1 always except for the first '*' where the two branches overlap
            t = 0, u = 0; // offsets for the second branch, one will be 0 and the other 1 always except for the first '*' where the two branches overlap
        n-- > 0; ) { // decrement virality and repeat as many times
        c[i+=r][j+=s] = c[k+=t][l+=u] = 42; // move according to offsets and place an '*' for each branch, 42 is ASCII code
        do { // randomly pick offsets for both branches
            r = t = 2; // Math.random() provides results in [0,1)
            r *= Math.random(); // flip a coin for the first branch
            t *= Math.random(); // flip another coin for the second
            s = r^1; // set s to 0 if r=1, to 1 if r=0
            u = t^1; // set u to 0 if t=1, to 1 if t=0
        } while(i+r==k+t&j+s==l+u); // repeat if the branches overlap
    }
    return c; // return the output
}
\$\endgroup\$
  • \$\begingroup\$ 239 bytes (I've only changed the things inside the do{} a bit (and placed the ints in the first part of the for-loop). PS: In your initial answer the 0.5 could have been golfed to .5 as well. \$\endgroup\$ – Kevin Cruijssen Apr 3 '18 at 7:21
  • \$\begingroup\$ @KevinCruijssen looks like I need to work on my math. thanks :-) \$\endgroup\$ – O.O.Balance Apr 3 '18 at 9:01
3
\$\begingroup\$

Perl 5, 208 124 122 118 bytes

118 bytes without newlines, indentation and comments. Takes N from stdin:

@b=1..2;                            #number of branches is 2
for(1..<>){                         #add length <> (the input) to each branch
  ($x,$y)=@$_                       #get where current branch has its tip now
 ,.5>rand?$x++:$y++                 #increase either x or y
 ,$o[$y][$x]++&&redo                #try again if that place is already occupied
 ,$_=[$x,$y]                        #register new tip of current branch
   for@b                            #...and do all that for each branch 
}
say map$_||!$i++?'*':$",@$_ for@o;  #output the branches

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Nice, but it prints the branches 1 asterisk shorter than they should be :) \$\endgroup\$ – nicael Apr 2 '18 at 9:41
  • \$\begingroup\$ Please see the examples in my questions again :) \$\endgroup\$ – nicael Apr 2 '18 at 9:41
  • \$\begingroup\$ Oh, I've changed 2..$N to 1..shift now and also shaved off a few bytes. \$\endgroup\$ – Kjetil S. Apr 2 '18 at 9:47
  • 1
    \$\begingroup\$ Good answer! You can save a few bytes using <> and input instead of shift and arguments as well as re-orderinf you call to rand to avoid the parens. You shouldn't need to wrap your assignment to @o either. I tried using @b=([],[]); which appears to work, but I didn't experiment too much so I might've missed an edge case there. Hope they help a little! \$\endgroup\$ – Dom Hastings Apr 2 '18 at 10:54
  • 1
    \$\begingroup\$ The tips for golfing in Perl page has some good advice, be sure to check it out! Good luck and have fun! \$\endgroup\$ – Dom Hastings Apr 2 '18 at 13:03
2
\$\begingroup\$

Python 2, 204 bytes

from random import*
N=input()
s=eval(`[[' ']*-~N]*-~N`)
s[0][0]='*'
I=x,y=1,0
J=X,Y=0,1
exec"s[y][x]=s[Y][X]='*';i,j,k,l=choice((J+I,I+I,I+J,J+J)[x-2<X:]);x+=i;y+=j;X+=k;Y+=l;"*N
for i in s:print`i`[2::5]

Try it online!

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

Perl 5 -a, 97 96 93 92 bytes

Has no right, down or off diagonal bias.

#!/usr/bin/perl -a
@;=[1];map{$x=$y=0;map++(.5<rand?$x:$y)*$;[$y][$x]++&&redo,1.."@F"}1,2;say+($","*")[@$_]for@

Try it online!

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

PHP, 118 bytes

for($r="*",$w=$argn+2;$argn--;$r[$q+=rand(0,$r[$q+1]<"*")?:$w]=$r)$r[$p+=rand(!$i++,1)?:$w]=$r;echo wordwrap($r,$w-1);

requires PHP 5.4 or later for the Elvis operator. Replace ?: with ?1: for older PHP.

Run as pipe with -nR or try it online.

\$\endgroup\$
  • 1
    \$\begingroup\$ How do I check with different input there? \$\endgroup\$ – nicael Apr 2 '18 at 9:41
  • \$\begingroup\$ @nicael: You can change the argument on the line $argBak=$argn= \$\endgroup\$ – Galen Ivanov Apr 2 '18 at 10:52
  • \$\begingroup\$ Ok! Not sure whether this is a nice way or not to "accept" input this way, but let the community decide by voting \$\endgroup\$ – nicael Apr 2 '18 at 10:55
  • \$\begingroup\$ @nicael In the TiO, simply replace the value for $argn. In a real environment, $argn comes from STDIN if you run it as a pipe with -R. It will then execute the code for each line of input (but I am pretty certain PHP does not unset the variables inbetween; so explicit consecutive runs are more likely to avoid bad surprises.) \$\endgroup\$ – Titus Apr 2 '18 at 11:16
0
\$\begingroup\$

Red, 195 190 bytes

func[n][g: func[s][i: 0 d: s while[i < n][b/(d): #"*"until[r: 1 if 1 = random 2[r: n + 1]b/(d + r) =#" "]d: d + r
i: i + 1]]b:""loop n[loop n[append b" "]append b"^/"]b/1: #"*"g n + 2 g 2 b]

Try it online!

Readable:

f: func[n][
    g: func[s][
        i: 0
        d: s
        while[i < n][
            b/(d): #"*"
            until[
                r: 1 if 1 = random 2[r: n + 1]
                b/(d + r) = #" "
            ]
            d: d + r
            i: i + 1
        ]
    ]
    b: ""
    loop n[loop n[append b " "]append b "^/"]
    b/1: #"*"
    g n + 2
    g 2
    b
]
\$\endgroup\$
0
\$\begingroup\$

Jelly, 50 43 41 bytes

2ḶẊ⁸С+\‘Ṗ
⁸ÇU;Ǥ⁻Q$¿
‘,þ`⁼€þÇS+»þ`Ị$ị⁾* 

Try it online!

This was a really fun one to write. There could be some much more optimal method. There is probably some golfing to do within this method as well.

Right after I posted this I realized I could use ,þ` instead of aþ,""oþ`Ɗ.

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

R, 148 142 bytes

n=scan();`~`=sample;o=r=k=1;l=c(1,n);for(i in 1:n){r=r+l~1;t=l~1;k=k+"if"(k+t-r,t,l[l!=t]);o=c(o,r,k)};write(c(" ","*")[1:n^2%in%o+1],1,n,,"")

Try it online!

Additionally, although it won't meet the output spec, you can distinguish the two branches: Try it online!

Explanation:

Starting from index 1, we randomly select a right or left move for branch r by adding n or 1, respectively. Then we select another right or left move for branch k, and if it would intersect where r is going, we select the other direction. Then we use r and k as indices into m, setting those values as "*". Iterating n-1 times, we then print the result.

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

Jelly, 39 38 bytes

ḣ2+\€Ẏ
2Rd¤ṗẊÇ⁻Q$$¿Ç0,0ṭ‘Ṭ€×þ/$€Sị⁾* Y

Try it online!

Although seemingly unrelated, d is useful here to save a byte (over my previous approach).

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

Python 2, 191 187 176 bytes

from random import*
n=input()
p,q=c=1,1j;s={p,q,0}
exec'z=choice(c);q,p=p+[z,1+1j-z][p+z in s],q;s|={q};'*2*~-n
R=range(n+1)
for y in R:print''.join(' *'[y+x*1jin s]for x in R)

Try it online!

Python has native support for complex numbers of the form a+bj; this makes some 2-D problems a bit more tractable...

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