Учитывая положительное целое число N («виральность»), ваша программа должна создать ASCII-рисунок дерева с двумя ветвями длины N, идущими вниз и / или вправо от верхнего левого угла.

Направление, выбранное каждой ветвью после первой звездочки, может быть как вправо, так и вниз, и этот выбор должен быть сделан случайным образом ¹ на каждом следующем шаге.

Например, если задано значение 5, результат может выглядеть следующим образом:

***
* ***
**
 **

Две ветви могут касаться (находиться в соседних ячейках), но не перекрываться (находиться в одной и той же ячейке), поэтому не допускается следующее:

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

Примеры

Для ввода 1единственно возможный вывод:

**
*

(Это будет присутствовать во всех допустимых выходных данных, так как если две ветви выберут один и тот же путь, они будут перекрываться.)

Возможные выходы для входа 3включают в себя:

***
* *
**

**
***
*
*

Для ввода 7:

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

Для ввода 10:

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

Это Код-гольф, поэтому самый короткий действительный ответ (в байтах) выигрывает.

^{1. Это должно быть равномерно случайным (то есть шанс 50/50 каждого направления), или настолько близко к равномерно случайным, насколько вы можете получить на обычном оборудовании.}

CJam , 58 51 байт

[TT]{_2_m*\f.+{:-},mR}ri*]ee{~\)S*\{'*t}/}%::a:.+N*

Попробуйте онлайн!

Основная идея состоит в том, что мы начинаем с, [0 0]а затем многократно добавляем либо 0, либо 1 к каждому элементу (следя за тем, чтобы они никогда не были равны, кроме как в начале, чтобы избежать дублирования), собирая все промежуточные результаты.

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

Затем мы создаем большой массив массивов, где каждый подмассив содержит *индексы, заданные соответствующей парой в исходном массиве и пробелами везде.

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

Это дает диагональные срезы выходной матрицы (где перемещение слева направо соответствует перемещению сверху вниз справа налево в фактической матрице).

Затем мы можем использовать ::a:.+для «de-diagonalize» и получить результирующие строки:

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

Древесный уголь , 31 24 байта

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

Попробуйте онлайн! Ссылка на подробную версию кода. Первоначально я думал, что будет проще сделать первый шаг случайным, но оказалось, что лучше сделать первую ветку предсказуемой. Объяснение:

Ｆ²«

Цикл дважды, используя индексную переменную i. (Это на самом деле перебирает неявный список, поэтому его можно изменять iвнутри цикла.)

Ｊ⁰¦⁰

Перейти к началу холста.

Ｆ⊕θ«

Цикл N+1раз.

¿ι*↓*

Напечатайте a *, но оставьте курсор вправо или ниже курсора в зависимости от значения i.

‽²ι

Произведите рандомизацию значения iдля следующей итерации внутреннего цикла.

¿ＫＫ↗

Если текущим символом является a *, это означает, что мы вторая ветвь, и мы пошли вниз, а не вправо, поэтому двигайтесь вверх вправо, чтобы исправить это. (Первая ветвь всегда начинается вниз, поэтому вторая ветвь всегда будет над ней, а это означает, что нам нужно только проверять наличие вертикального столкновения.)

Java 10, 273 272 268 239 байт

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;}

Попробуйте это онлайн здесь .

Спасибо Кевину Круйссену за игру в гольф 29 байтов.

Безголовая версия:

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
}

Perl , 5 , 208 124 122 118 байт

118 байт без перевода строки, отступов и комментариев. Берет N из стандартного ввода:

@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

Попробуйте онлайн!

Python 2 , 204 байта

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]

Попробуйте онлайн!

Perl 5 -a , 97 96 93 92 байта

Не имеет права, вниз или вне диагонального смещения.

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

Попробуйте онлайн!

PHP, 118 байт

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

требует PHP 5.4 или более поздней версии для оператора Elvis. Заменить ?:с ?1:для более старых PHP.

Запустите как трубу с -nRили попробуйте онлайн .

Красный , 195 190 байтов

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]

Попробуйте онлайн!

Удобочитаемый:

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
]

Желе , 50 43 41 байт

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

Попробуйте онлайн!

Это было действительно весело, чтобы написать. Там может быть гораздо более оптимальный метод. В этом методе, вероятно, есть и игра в гольф.

Сразу после публикации я понял, что могу использовать ,þ`вместо aþ,""oþ`Ɗ.

R , 148 142 байт

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,,"")

Попробуйте онлайн!

Кроме того, хотя он не будет соответствовать выходной спецификации, вы можете различить две ветви: попробуйте онлайн!

Объяснение:

Начиная с индекса 1, мы произвольно выбираем движение вправо или влево для ветви r, добавляя nили 1, соответственно. Затем мы выбираем другое движение вправо или влево для ветки k, и если оно будет пересекать rнаправление движения, мы выбираем другое направление. Затем мы используем rи в kкачестве индексов m, устанавливая эти значения как "*". Итерируя n-1время, мы затем выводим результат.

Желе , 39 38 байт

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

Попробуйте онлайн!

Хотя, казалось бы, не связано, dздесь полезно сохранить байт (по сравнению с моим предыдущим подходом).

Python 2 , 191 187 176 байт

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)

Попробуйте онлайн!

Python имеет встроенную поддержку для комплексных чисел формы a+bj; это делает некоторые двумерные проблемы более податливыми ...