# Asterisks viral

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.

• Please comment if you're having any problems with consuming my long post - maybe I can shorten something (I'll try then). Apr 1, 2018 at 20:21
• 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. Apr 1, 2018 at 21:06
• I am not really sure what is wrong with my post. Would the one who downvoted be so kind to explain, please? Apr 1, 2018 at 22:15
• IMO N is better described as time :P Apr 2, 2018 at 12:14
• Can we return a matrix of 0s and 1s instead of spaces and asterisks? Apr 5, 2018 at 20:14

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

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

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

Ｊ⁰¦⁰

Ｆ⊕θ«

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

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

# Java 10, 273272268 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
}
• 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. Apr 3, 2018 at 7:21
• @KevinCruijssen looks like I need to work on my math. thanks :-) Apr 3, 2018 at 9:01

# Perl 5, 208124122 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! • Nice, but it prints the branches 1 asterisk shorter than they should be :) Apr 2, 2018 at 9:41 • Please see the examples in my questions again :) Apr 2, 2018 at 9:41 • Oh, I've changed 2..$N to 1..shift now and also shaved off a few bytes. Apr 2, 2018 at 9:47
• 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! Apr 2, 2018 at 10:54
• The tips for golfing in Perl page has some good advice, be sure to check it out! Good luck and have fun! Apr 2, 2018 at 13:03

# 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:printi[2::5]

Try it online!

# Perl 5-a, 979693 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! # 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.

• How do I check with different input there? Apr 2, 2018 at 9:41
• @nicael: You can change the argument on the line $argBak=$argn= Apr 2, 2018 at 10:52
• Ok! Not sure whether this is a nice way or not to "accept" input this way, but let the community decide by voting Apr 2, 2018 at 10:55
• @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.) Apr 2, 2018 at 11:16

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

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
]

# Jelly, 5043 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þƊ.

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

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

# Python 2, 191187 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...