Asterisks viral

Question

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 randomly¹ 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 code-golf, 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.}

Answer 1

CJam, 58 51 bytes

[TT]{_2_m*\f.+{:-},mR}ri*]ee{~\)S*\{'*t}/}%::a:.+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 * at indices given by the corresponding pair in the original array and spaces everywhere else.

["*"
 "**"
 "* *"
 "* * "
 " * * "]

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 resulting lines:

[ "**** "
  "*  *"
  "** "
  " *"
  ""     ]

Answer 2

Charcoal, 31 24 bytes

Ｆ²«Ｊ⁰¦⁰Ｆ⊕θ«¿ι*↓*≔‽²ι¿ＫＫ↗

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:

Ｆ²«

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

Ｊ⁰¦⁰

Jump to the origin of the canvas.

Ｆ⊕θ«

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.

¿ＫＫ↗

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

Answer 3

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
}

Answer 4

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!

Answer 5

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!

Answer 6

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!

Answer 7

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.

Answer 8

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
]

Answer 9

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þ`Ɗ.

Answer 10

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.

Answer 11

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

Answer 12

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