We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Linux Shell
  3. Bash
  4. Functions and Fractals - Recursive Trees - Bash!
  5. Discussions

Functions and Fractals - Recursive Trees - Bash!

Sort by

recency

|

149 Discussions

|

  • jnordwick
     + 0 comments

    I looked at the top few, and most basically hardcoded the tree. That's weak.

    I was happy with my fairly unique answer. I can be cleaned up better, but I've already spent a few hours on this.

    The basic idea was to form each tree based on a base row. At first the tree function was done in 3 parts - trunk, branch left, and branch right - but I was able to roll them into the same loop after I had all three working independantly.

    From the base row, the trunk just copies the previous row (if there was a 1 at "base, col)" then you put a 1 at "trunkcur,col"). For the branches you look at the base row plus the offset so "base, col +/- i" (where i is the row difference from branchcur to base) to put a 1 in "branchcur, col +/- (base - branchcur)".

    You add an additional 64th row that is just a 1 at "64,50" and now the trees can be built off that single starting point. frac() takes the number of iterations, starting line, and depth of the tree (starting line is always 63 and depth always starts at 16). Each recursive call decreaments iteration number (base case of 0 where nothing is printed at it returns), calculates a new starting row (decrementing 2 * length of last tree), and sets the next tree length to half the previous. So frac 5 63 16 calls frac 4 31 8 which calls frac 3 15 4 ...

    Yes, this can all be done iteratively, but I was just too lazy to refactor it for such a small n. The nice thing about this approach is that all the constants are easily adjustable to make it work on any size board with any length trees and any number of branches even.

    When the table is printed at the end, just remeber to leave off the 64th starting base row and you're good.

    declare -A tab

for r in {1..64}; do
    for c in {1..100}; do
        tab["$r,$c"]="_"
    done
done

tab["64,50"]="1"

function prtab {
    for r in {1..63}; do
        for c in {1..100}; do
            echo -n ${tab["$r,$c"]}
        done
    echo
    done
}

function tree {
    line=$1
    len=$2
    base=$(($line + 1))
    for i in $(seq 0  $(($len - 1))); do
        trunkcur=$(($line - $i))
        branchcur=$(($line - $len - $i))
        for c in {1..100}; do
            # trunk
            if test "1" = ${tab["$base,$c"]-_}; then
                tab["$trunkcur,$c"]="1"
            fi
            # left branch
            right=$(($c + $i + 1))
            if test "1" = ${tab["$base,$right"]-_}; then
                tab["$branchcur,$c"]="1"
            fi
            # right branch
            left=$(($c - $i - 1))
            if test "1" = ${tab["$base,$left"]-_}; then
                tab["$branchcur,$c"]="1"
            fi
        done
    done
}

function frac {
    iter=$1
    start=$2
    len=$3
    
    if [ $iter -eq 0 ]; then
        return
    fi

    tree $start $len
    frac $((iter - 1)) $((start - len * 2)) $((len / 2))
}

read n
frac $n 63 16

prtab

  • dhruvflare
     + 0 comments

    as a bash noob, this was tough, but some brute-force algos always work lol

    declare -A mat
rows=63
cols=100
read n
f=16
for ((i=0; i<$rows; ++i)) do
    for ((j=0; j<$cols; ++j)) do
        mat[$i,$j]="_"
    done
done

pow(){
    local v=1
    for((i=1; i<$1; ++i)) do
        v=$(($v*2))
    done
    echo $v
}

it() { # mid, iteration, row
    local nums=$(($f/$(pow $2)))
    local a=$3
    local b=$(($3+$nums))

    for((i=$a; i<$b; ++i)) do
        mat[$i,$1]=1
    done

    local ml=$1
    local mr=$1

    a=$b
    b=$(($b+$nums))
    for((i=$a; i<$b; ++i)) do
        ml=$(($ml-1))
        mat[$i,$ml]=1
    done    

    for((i=$a; i<$b; ++i)) do
        mr=$(($mr+1))
        mat[$i,$mr]=1
    done
    local x=$(($2+1))
    if (( $x <= $n )) then
        it $ml $x $b;
        it $mr $x $b;
    fi
};

it 49 1 0;

for ((i=$(($rows-1)); i>=0; --i)) do
    for ((j=0; j<$cols; ++j)) do
        echo -n ${mat[$i,$j]}
    done
    echo
done

  • nguyenducnam2509
     + 0 comments

    EZ

    #!/bin/bash
base_str="____________________________________________________________________________________________________"
str_arr=()
read level
draw_fractal() {
    local current_level=$1
    local row_no=$2
    local pos=$3
    local row_current=$4
    if [ $current_level -eq $level ]; then
        return
    fi
    for ((i = 1; i <= $row_no; i++)); do
       str_arr[$row_current]="${str_arr[$row_current]:0:$pos}1${str_arr[$row_current]:$(($pos + 1))}"
       row_current=$(($row_current + 1))
    done
    for ((i = 1; i <= $row_no; i++)); do
       str_arr[$row_current]="${str_arr[$row_current]:0:$(($pos + $i))}1${str_arr[$row_current]:$(($pos + $i + 1))}"
       str_arr[$row_current]="${str_arr[$row_current]:0:$(($pos - $i))}1${str_arr[$row_current]:$(($pos - $i + 1))}"
       row_current=$(($row_current + 1))
    done
    draw_fractal $(($current_level + 1)) $(($row_no / 2)) $(($pos - $row_no )) $row_current
    draw_fractal $(($current_level + 1)) $(($row_no / 2)) $(($pos + $row_no )) $row_current
}
for (( i=1; i<=64; i++ )); do
    str_arr[i]=$base_str
done

draw_fractal 0 16 49 1

length=${#str_arr[@]}
for (( i=length-1; i>=0; i-- )); do
    echo "${str_arr[i]}"
doner_arr[i]}"
done

  • Madophs
     + 0 comments
    #!/bin/bash
#Usage script [branch_size] [depth]
#example ./script 10 4 ./script 77 7
pad=$(printf "_%.0s" {1..500})

create_fractal_pattern() {
    local left_length=${1}
    local right_length=${2}
    local branch_size=${3}
    local depth=${4}

    if [[ ${depth} == 0 ]]
    then
        return
    fi

    paste -d "" <( create_fractal_pattern $(( left_length - branch_size )) ${branch_size} $(( branch_size / 2 )) $(( depth - 1 )) ) \
        <( create_fractal_pattern $(( branch_size - 1 )) $(( right_length - branch_size )) $(( branch_size / 2 )) $(( depth - 1 )) )

    for (( i=${branch_size}-1; i>=0; i-=1 ))
    do
        printf "%s1%s1%s\n" "${pad:1:left_length-i-1}" "${pad:1:i*2+1}" "${pad:1:right_length-i-1}"
    done

    for (( i=0; i<${branch_size}; i+=1 ))
    do
        printf "%s1%s\n" ${pad:1:left_length} ${pad:1:right_length}
    done
}

compute_max_width() {
    local branch_size=${1}
    local depth=${2}
    local res=0
    for (( i=0; i<depth; ++i ))
    do
        res=$(( res + branch_size ))
        branch_size=$(( branch_size / 2 ))
    done
    echo $(( res * 2 + 7 ))
}

draw_fractal() {
    local branch_size=${1}
    local depth=${2}
    local width=$(compute_max_width ${branch_size} ${depth})
    local left_bound=$(( (width + 1) / 2 -1 ))
    local right_bound=$(( width / 2 ))
    printf "%s\n" ${pad:1:width}
    create_fractal_pattern ${left_bound} ${right_bound} ${branch_size} ${depth}
}

draw_fractal ${1} ${2} | tr ' ' '\n'

  • Madophs
     + 0 comments
    pad=$(printf "_%.0s" {1..100})

create_fractal_pattern() {
    local left_length=${1}
    local right_length=${2}
    local branch_size=${3}
    local depth=${4}

    if [[ ${depth} == 0 ]]
    then
        return
    fi

    local left_child=( $(create_fractal_pattern $(( left_length - branch_size )) ${branch_size} $(( branch_size / 2 )) $(( depth - 1 ))) )
    local right_child=( $(create_fractal_pattern $(( branch_size - 1 )) $(( right_length - branch_size )) $(( branch_size / 2 )) $(( depth - 1 ))) )

    declare -a tree
    for (( i=0; i<${#left_child[@]}; i+=1 ))
    do
        tree[${i}]="${left_child[${i}]}${right_child[${i}]}"
    done
    echo "${tree[@]}"

    for (( i=${branch_size}-1; i>=0; i-=1 ))
    do
        printf "%s1%s1%s\n" "${pad:1:left_length-i-1}" "${pad:1:i*2+1}" "${pad:1:right_length-i-1}"
    done

    for (( i=0; i<${branch_size}; i+=1 ))
    do
        printf "%s1%s\n" ${pad:1:left_length} ${pad:1:right_length}
    done
}

draw_fractal() {
    local width=${1}
    local branch_size=${2}
    local depth=${3}
    local left_bound=$(( (width + 1) / 2 -1 ))
    local right_bound=$(( width / 2 ))
    local upper_bound=$(( 63 - ( 64 - (2 ** (6 - depth)) ) ))
    for (( i=0; i<${upper_bound}; i+=1 ))
    do
        printf "%s\n" ${pad}
    done
    
    create_fractal_pattern ${left_bound} ${right_bound} ${branch_size} ${depth}
}

read N

fractal=$(draw_fractal 100 16 ${N})
echo ${fractal} | tr ' ' '\n'