Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

The trees we are growing have some rules that define how they grow:

Growth Rules:

  1. Trees consist only of branches.
  2. Branches are made up of a combination of the following symbols: _, \, |, /, & _
  3. A tree starts as a single vertical branch/trunk (|) on the ground (_):

    __________________|___________________

  4. The food for branch growth comes from light.

    • Light starts at an intensity of 2 at each point in the sky and travels straight down.
    • Each branch is able to eat half the light available to it and the rest passes through to lower branches.
    • Thus, a branch with no other branches above it will get 1 unit of light-food each season, a branch with 1 branch above it will get .5 units of food each season, and in general a branch with n branches over it will get 1/(2^n) units of food each season.
  5. At the end of each season, the food is totaled starting with the trunk and moving up and converted into new branches and fruit (apply the following rules until the branch turns into fruit or has less than 1 unit of food remaining):
    • If a branch has less than 1 unit of food at the end of a season, all the food for that branch is stored in that branch until the next season.
    • If a branch has greater than or equal to 1 unit of food and has room to grow, it randomly grows a new branch using the available growth patterns (see below) and stores the remaining food for the next season.
    • If a branch has >= 1 unit of food, nowhere to grow, and has offshoot branches, it evenly distributes the food to its offshoot branches
    • If a branch has >= 1 unit of food, nowhere to grow, and no offshoot branches, it becomes fruit (represented by O)
  6. Here are the possible growth configurations

Growth Configurations:

_    \     |     /   _      _   \   |    /   \    |   /   _ 
 |    |    |    |   |        \   \   \   \   /   /   /   /     __   \_   |_   _|  _/  __
--- Vertical Branches ---      --- Diagonal Branches ---      --- Horizontal Branches ---


Example potential tree:

                \  
                /   /
              \/O  |___//
            \_/  \//O\_/ 
              \__/|\|_/
                 \|/
__________________|__________________

Input:

Your program should be able to take as input a list of which snapshots of the tree you would like to see. For example [10,20,50] would mean you'd like to see the tree after 10 seasons, 20 seasons, and 50 seasons.

Output:

For each input season, your program should output the season and then a picture of the tree in that season. If it helps, you can define a maximum age for the tree, such as 60, so that the maximum height for a tree would be 61, and the maximum width would be 121, and then always show the tree on that scale. Otherwise, feel free to scale your image to any sized tree. For example, if the input was [0,1,2,3], your output might be:

Season 0:
_|_

Season 1:
 \
__|__

Season 2:
 _
  \| 
___|___

Season 3:

 |_/ _
   \| 
____|___


Winner

Each solution must post the output of the coder's favorite run of their program with input of [10,40], along with their source code. Also, ALL the above criteria must be met in order to qualify.

The winner will be the qualifier with the highest number of votes.

Good luck and merry planting!!!

share|improve this question
    
"Room to grow" doesn't seem to be defined. –  Peter Taylor Sep 20 '11 at 22:32
    
I think the tags "code-challenge" and "code-golf" do not fit together ("objective criterion other than code size" vs. "fewest bytes of source code"). –  Howard Sep 21 '11 at 12:03
    
@Peter Taylor: To see if there is room to grow, you must first check the growth configurations for that branch type (e.g. vertical branches can go up-left, up, and up-right), and then see if any of those spaces are empty. If so, there is room for growth. –  Briguy37 Sep 21 '11 at 13:09
    
@Howard: Yeah, I was thinking the same thing, but wasn't sure. I think this is definitely more challenging than most problems I've seen on here, so I definitely wanted "code-challenge". However, if there are multiple solutions, I wanted a way to determine a clear winner. The scoring calculation above favors voting over atomic-code-golf scoring, so the atomic-code-golf score is really mainly a tie-breaker. I'll leave it up to the people: The golf requirements will be waved if Howard's comment gets more up-votes than this one. –  Briguy37 Sep 21 '11 at 13:21
    
With the present scoring mechanism, it isn't a code-golf. It's not really a atomic-code-golf either. –  Peter Taylor Sep 21 '11 at 14:28

3 Answers 3

Javascript

Here is not the most beautiful code on javascript. May be later would be some improvements. Code on JSFiddle

var branch = function(food, direction){
    var directionChars = ["_", "\\", "|", "/"];
    var frootChar = "0";
    this.food = food || 0;
    this.char = directionChars[direction];
    this.direction = direction;
    this.is_froot = false;
    this.child_branches = [];

    //return [x,y,[possible dirs of new branch]]`s of theoretically possible directions
    this.getPossibleDirections = function(){
        if(this.direction == 0)
        {
            return [
                    [-1, 0, [0,1,2]],
                    [+1, 0, [2,3,0]]
                ];
        }
        if(this.direction == 1)
        {
            return [
                    [-1, +1, [0,1,2]],
                    [0, +1, [3]]
                ];
        }
        if(this.direction == 2){
            return [
                    [-1, +1, [0,1]],
                    [0, +1, [2]],
                    [+1, +1, [3,0]]
                ];
        }
        if(this.direction == 3){
            return [
                    [+1 ,+1 , [0,2,3]],
                    [0 ,+1 , [1]]
                ];
        }
    };

    this.setAsFroot = function(){
        this.is_froot = true;
        this.char = frootChar;
    };

    this.getHtml = function(){
        var color = "brown";
        var bgColor = "00CCFF";

        if(this.is_froot)
            color = "red";

        return "<span style=\"color: " + color + "; background-color: " + bgColor + "\">" + this.char + "</span>";
    };
};

var ground = function(){
    this.char = "_";

    this.getHtml = function(){
        var color = "black";
        var bgColor = "00CCFF";

        return "<span style=\"color: " + color + "; background-color: " + bgColor + "\">" + this.char + "</span>";
    };
}

var air = function(){
    this.char = " ";

    this.getHtml = function(){
        var color = "blue";
        var bgColor = "00CCFF";

        return "<span style=\"color: " + color + "; background-color: " + bgColor + "\">" + this.char + "</span>";
    };
}

var tree = function(){
    var me = this;

    this.treeMatrix = [];

    this.calculateFood = function(){
        //console.log(this.treeMatrix);
        var width = this.treeMatrix[0].length;

        for(var i in this.treeMatrix[0]){
            var food = 2;

            for(var j in this.treeMatrix){
                if(this.treeMatrix[this.treeMatrix.length - 1 - j][i] instanceof branch){
                    this.treeMatrix[this.treeMatrix.length -1 - j][i].food += food;
                    food /= 2;
                }
            }
        }
    };

    this.expandMatrix = function(){
        var expandLeft = false;
        var expandRight = false;
        var expandTop = false;

        this.treeMatrix[this.treeMatrix.length - 1].forEach(function(el){
            if(el instanceof branch)
                expandTop = true;
        });

        if(expandTop)
            this.treeMatrix.push(this.treeMatrix[0].map(function(){return new air();}));


        for(var i in this.treeMatrix){
            if(this.treeMatrix[i][0] instanceof branch){
                expandLeft = true;
            }
            if(this.treeMatrix[i][this.treeMatrix.length - 1] instanceof branch){
                expandRight = true;
            }
        }

        this.treeMatrix = this.treeMatrix.map(function(row){
            if(expandLeft)
                row.unshift((row[0] instanceof ground ? new ground() : new air()));
            if(expandRight)
                row.push((row[0] instanceof ground ? new ground() : new air()));

            return row;
        });
    }

    this.calculateNewMatrix = function(){
        if(this.treeMatrix.length == 0){
            this.treeMatrix.push([new ground(), new branch(0,2), new ground()]);
        }

        this.expandMatrix();
        this.calculateFood();

        for(var i in this.treeMatrix){
            for(var j in this.treeMatrix[i]){
                var element = this.treeMatrix[i][j];

                // grow a branch/distribute food/set froot or just store food of not(do nothing)
                if(element instanceof branch
                    && !element.is_froot
                    && element.food >= 1
                ){
                    //console.log("branch coordinates", i, j);
                    var directions = element.getPossibleDirections();
                    var tm = this.treeMatrix;

                    var freeDirections = directions.filter(function(directionArr){
                        if(tm[parseInt(i) + directionArr[1]][parseInt(j) + directionArr[0]] instanceof branch)
                            return false;
                        else
                            return true;
                    });

                    if(freeDirections.length){
                        var newCell = freeDirections.length > 1
                            ? freeDirections[Math.floor(Math.random() * freeDirections.length)]
                            : freeDirections[0];

                        this.treeMatrix[parseInt(i) + newCell[1]][parseInt(j) + newCell[0]] = new branch(0, newCell[2][Math.floor(Math.random() * newCell[2].length)]);
                        element.child_branches.push(this.treeMatrix[parseInt(i) + newCell[1]][parseInt(j) + newCell[0]]);
                    }
                    else if(!freeDirections.length && !element.child_branches.length){
                        element.setAsFroot();
                    }
                    else if(!freeDirections.length && element.child_branches.length){
                        element.child_branches.forEach(function(child){
                            child.food += element.food/element.child_branches.length;
                        });

                        element.food = 0;
                    }
                }
            }
        }
    };

    this.getTreeString = function(){
        //return this.treeMatrix.map(function(row){return row.map(function(el){ return el.char}).join('')}).join("\n");
        return this.treeMatrix.reduceRight(function(prev, next){
                return (
                typeof prev == "string"
                    ? prev
                    : prev.map(function(el){ return el.char}).join('')
                ) + "\n" + next.map(function(el){ return el.char}).join('');
                 })
    };

    this.getTreeHtml = function(){
        return "<pre>" + this.treeMatrix.reduceRight(function(prev, next){
                return (
                typeof prev == "string"
                    ? prev
                    : prev.map(function(el){ return el.getHtml()}).join('')
                ) + "<br/>" + next.map(function(el){ return el.getHtml()}).join('');
                 }) + "</pre>";
    };
};


var seasonsTotal = 50;
var seasonsCounter = 0;
var showAt = [1,5,10,15,20,25,30,35,40,45,50,55,60,65,70,75,80,85,90,95,100];
var pageTree = new tree();

var season = function(){
    pageTree.calculateNewMatrix();
    seasonsCounter++;
    if(showAt.indexOf(seasonsCounter) >= 0){console.log(pageTree.getTreeString()); document.body.innerHTML = pageTree.getTreeHtml();}
};

window.onload = function(){
        var intervalId = setInterval(function(){
                season();
                if(seasonsCounter >= seasonsTotal)
                    clearInterval(intervalId);
                }, 100);
};

Some examples: @10 season:

       \/          
    \ |/\_/_       
  |  \/\/|/0/_ _   
  |/  \/0||/|_//   
 / \0_/0/\|0|_|    
 \_/00\0\/|_|      
   \_|/00\|        
     |__|/         
________|__________

@25 season:

                    |  _ \__                   
                    |/ |\/|_//                 
             /\0|0| |__|/\|_0\_     /          
           \/\/  \|0/\_0\//00/    \|_          
      \   \||/\_0/00\|\0/ \/|   \\/|0|/        
     _ |_0/0_\/0|/|00|/\\0//0\_0/ \|/|\_/      
  __/\|_0\\00|\/0\| \|\0\||_0|||000|/_/        
   \\/0/|/0|00\\|/\0/0/0/0|_/0||/|0|/          
    \\/  \/  \/0|\/ \0\0\//0__||_|0|\          
   \_|\__/000/\0|_\0/ 0|/ \/ 0/ 0|/0/   |      
  \ \|\00\/00\0\|0||\00|00/   \0//  \___|      
   \0|/0\0\_|/0/|/0|//\|| \_0_//|___/          
 | |\|_/0\_0|/|_0\0|/0//0_/_00|0|              
 |_|/00\_|0\|00|\/0|\/ \/0|0|0|/               
   |/0|_||__|\/|/\/|/\0/_/0/ \|                
    \/0_|   |_\|00\0\/|/0/0\0/                 
     \/       \|/  \/0||/|_//                  
      \_______/ \0_/0/\|0|_|                   
              \_/00\0\/|_|                     
                \_|/00\|                       
                  |__|/                        
_____________________|_________________________
share|improve this answer

Python, 673 chars

Here's a golfed version:

import random
Z='|_\/O'
T={60:0}
F={60:0}
C={60:[]}
B=[((1j-1,1),(1j-1,2),(1j,0),(1j+1,3),(1j+1,1)),((-1,1),(-1,2),(-1,0),(1,0),(1,3),(1,1)),((1j-1,1),(1j-1,2),(1\
j-1,0),(1j,3)),((1j,2),(1j+1,0),(1j+1,3),(1j+1,1)),()]
S=input()
for s in range(61):
 if s in S:
  for y in range(60,0,-1):print''.join(Z[T[x+y*1j]]if x+y*1j in T else' 'for x in range(121))
  print'_'*60+'|'+'_'*60
 for p in T:F[p]+=.5**sum(q.real==p.real and q.imag>p.imag and T[q]<4for q in T)
 for p in[q for q in T if F[q]>=1]:
  D=[p+d,c for d,c in B[T[p]]if p+d not in T]
  if D:q,c=random.choice(D);F[p]-=1;T[q]=c;F[q]=0;C[q]=[];C[p]+=[q]
  elif C[p]:
   for q in C[p]:F[q]+=F[p]/len(C[p])
  else:T[p]=4

sample @10 (truncated to the interesting part):

           |  |_   
       |_|/\_\ \|  
 |   \\/\|\/__|/   
 |/   \\O|O\__|    
  \___/O|/\/       
      \/O\/        
       \|/         
________|__________

sample @40:

             _  _        \_ _ / _|                        
        // _|/\|_\||_\___/ \_|_|/|/|_ |  _    //          
/     _|\\|_/\/|\/_/\/O|O\OO\|\|OO\|  \\/  |/|/|_/|       
\/\|OOO|//OO\O\|//OO/O_|O||\O|/|/|/OOO/ \OOO\/\| \||_|  | 
 \_|/|_O\\|\O\/|/O/O\_O|/  \\|O|O|/OO\\_/\O\|\/OO/\|O_|\| 
   |_|OO/O|/O/\|\/\O|O||_OOO|\\|/ \/O_|O\/OO|/O_|\/|OO|/  
     |/|\O|\|\/OO\O\|_|OO\|||// \OO\_O|O/  |||/_O/O|__|   
      \|O\O\|/\O\/\O|O|O\/O||/O_/|OO/\| \OO/\|/  \_|      
       |_/ O|\/O/\/\O\|\|\O|/\/OO|/ \/OO/\O\O\\__/        
         \_/O/\||/\O|\|O|O\\\/O_| \O/|/ \/O/_//     
           \O\/  \O\|_|O/\// \/OOOO|\|OO/|/|_|   
            |/\OO/O/  |O\/|\O/\O\|\O\|_|\|_|     
             \/OO\_\O__\|\|O|\/OO|/OO|___|       
              \|OOO\|O \\\|O|/|OO|OO\|          
               |/ \O|\_O\\|O|\|OO|O|/       
                \_/O|/O_//|O|/OO\|\|    
                  \_|OO \\O\|\/O_|/    
                    |/   \\O|O\__|    
                     \___/O|/\/     
                         \/O\/     
                          \|/    
___________________________|______________________________
share|improve this answer
    
Interesting... your tree looks very flat on top, whereas mine look rounded. I wonder if one of us has a bug, or it's that I shuffle children to randomize what order they spawn grandchildren in. Also, I notice that your fruit doesn't capture light... I wasn't sure if I should do that or not. –  boothby Sep 23 '11 at 6:45

Python

I took a little liberty with this:

  1. I allow multiple trees
  2. Fruit is preceded by flower -- once a flower has 1 food, it turns into a fruit.
  3. Fruit turns ripe when it has 3 food. It then falls off of the tree, and turns back into a flower.
  4. If fruit falls at least 4 places from any given trunk, it buds into a new tree. Since it doesn't get much light, I seed it with as much food as was in the fruit.

Sample Output, 2 trees

                            / 
     \/\_ |  /             |  
 _  _/\|\|_\/             /|/ 
  |/ \/|/|O/              \|/ 
   \_/O|@|/               /|_ 
     \_|_|                \|  
_______|___________________|__

                       _      \                                   
                _/ _ \/\___/\|/                  \                
             /|\|\O@|/\/|__\/ \__/_\|/\\|  _ |/| _||/\\ /         
             \|_|@|\|@/O|@@/O_/@O|@/ \//\   \|\||@||@///          
           \_ \_|\|/@\\O|@||/OO//O\\O/ \@|@\||/@|\/\/|/   | / _   
        ___/    |/|/O//O|O||\\/|/O// \_O\|__| \O|/\/O|   _/\\|    
         / \_O@@_\/\O\\@|/O|/O\@\O\\@/OO/|O_@O/O|\/\/     \//|/__ 
     _|/|_|  \\|O\\/O/O||_@|\O|\/O//|O|@\|/O_O\@|/O/\_@O__//_||   
    | \\|____// |O|\O\O|/\@|/ |/O/ \|O|OO|\/@_/O|_O\/O//O_//O/    
    |_O\\@O\/\\OO\|/|/\O\O\|__@\|O@/|/O|O|/\OO\/|_O/  \\|OO\/     
   /  \\||_|\|||_O|\|@/OO\//OOO/|/@\|OO|\|\@|O \|\|O@O//  \/\     
 _/\_/@\|\@|/  \_||/ \\@|/\\\||/ \//O|O|/|/@|\@/|/O/OO\\__/  \||/ 
  \||/  |_|O\__@ |O\O/O||\///@|O_//|/OO|@|OO|/O\|O/OO|// /|\|/\|  
   ||___O@|_/  |__\/||_||/|\\/OO/|@|O|/ \|_O||_/O/O/O|/_|\/\|_/   
    \_OO\\_O\@_|/|_\|_O|/\|//\/|/@|O\|@_O|O_O\/||\/O/|/_|/|O|     
      \_|\@\@|_|\|OO|O|/\//O\/\O\@|_/|_@\|/\O/\||/\|/|@@|@|/      
       /|//|\|O|_|O\O\O\/|O\/|@|/_|\OO@\/ \/|O/_|O//@|@/\_|       
       \O\\|/|_OO|OO\O|/\|@@\|O|/ @//|_@\_/\|//O_/|O/  \/         
        \O\|O_/|/ \|O|O\/|/OO|O|O_/ \|    \/|/|/@ |/\__/          
         |O|_O\|\O/|_|O/\|\//|/   \_/     /\@\| \_/\/             
          \OO\O|/ \ _|@\/O||@|\___/       \/|/    \/              
           |__|O\__|OO\/\@||/\/            \|O____/               
              |____|/@/\|\|O\/            _/|/O                   
                   |/ \/|/|@/              \|/                    
                    \_/O|@|/              |/|__                   
            \|/       \_|_|  \|_      \|/  \|    \|/  _|_         
_____________|__________|_____|________|____|_____|____|__________

Source

from random import choice, shuffle
format = '_\|/_@O'
directions = [(-1,0),(-1,1),(0,1),(1,1),(1,0)]
placement = [[[],[0,1,2],[]],[[],[0,1,2],[3]],[[0,1],[2],[3,4]],[[1],[2,3,4],[]],[[],[2,3,4],[]]]

def shine():
    for x in ymax:
        light = 2.
        for y in range(ymax[x],-1,-1):
            if (x,y) in tree:
                tree[x,y][1] += light/2
                light        /= 2


def grow((x,y)=(0,0),flow=0):
    type,store,children = tree[x,y]
    food = store + flow
    if type == 5:
        if food > 1:
           tree[x,y][0] = 6
           tree[x,y][1] = food-1
        return
    elif type == 6:
        if food > 3:
            tree[x,y]=[5,0,[]]
            if min(abs(x-xi) for xi in roots) > 4:
                tree[x,0] = [2,food,[]]
                roots.append(x)
        else:
            tree[x,y][1]=food
        return

    if food < 1:
        shuffle(children)
        for c in children:
            grow(c)
        return

    sites = []
    x0 = x+directions[type][0]-1
    y0 = y+directions[type][1]
    for i,t in enumerate(placement[type]):
        if t and (x0+i,y0) not in tree:
            sites.append((t,x0+i,y0))

    if sites:
        t,x1,y1 = choice(sites)
        t1 = choice(t)
        children.append((x1,y1))
        tree[x,y][1]=food-1
        tree[x1,y1]= [t1,0,[]]
        ymax[x1] = max(ymax.get(x1,0),y1)
    elif children:
        shuffle(children)
        for c in children:
            grow(c,food/len(children))
        tree[x,y][1]=0
    else:
        tree[x,y][0]=5

def output():
    X = range(min(ymax.keys())-1,max(ymax.keys())+2)
    for y in range(max(ymax.values()),-1,-1):
        s = ''
        for x in X:
            s += format[tree[x,y][0]] if (x,y) in tree else '_ '[y>0]
        print s


roots = [0,20]
seasons = [10,40]
tree = {}
ymax = {}
for r in roots:
    tree[r,0] = [2,0,[]]
    ymax[r]=0

for season in range(max(seasons)):
    shine()
    shuffle(roots)
    for r in roots:
        grow((r,0))
    if season+1 in seasons:
        output()
        print

I'm curious to see a golfed solution.

share|improve this answer
    
I like the flowers turning into fruits and seeds idea! One suggestion: add a space rule to keep trees separate. For example, maybe branches cannot sprout on any space adjacent to a branch from another tree. –  Briguy37 Sep 21 '11 at 21:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.