title: Plant a tree and watch it grow

text:
# Question
Title: Plant a tree and watch it grow
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!!!

# Answer
> 16 votes
**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.

# Answer
> 7 votes
## 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\/
                          \|/
___________________________|______________________________

```

# Answer
> 2 votes
## Javascript

**UPD:** Added some new rules:

1. if branch can grow it become leaf at first, when leaf have \>= 1 food it became a branch with food = leaf food
2. if branch have nowhere to grow and have food \>= 1 food its turn into flower
3. if flower have more than 1.5 food it become a froot with flower food / 2
4. if froot have more than 1 food it drops on the ground and grows into new tree
5. each season have 10% chance to have rain which gives additional food to the branches on the ground which distributing food to the others.

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

```
var leaf = function(food, branchDirection){
    this.food = food || 0;
    this.branchDirection = branchDirection;
    this.char = 'o';

    this.getHtml = function(){
        var color = "#00FF00";
        var bgColor = "#00BBEE";

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

var branch = function(food, direction){
    var directionChars = ["_", "\\", "|", "/"];

    this.food = food || 0;
    this.char = directionChars[direction];
    this.direction = direction;
    this.child_branches = [];

    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.getHtml = function(){
        var color = "brown";
        var bgColor = "#00BBEE";

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

var froot = function(food){
    this.char = "O";
    this.food = food || 0;

    this.getHtml = function(){
        var color = "#FF0000";
        var bgColor = "#00BBEE";

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

var flower = function(food){
    this.char = "@";
    this.food = food || 0;

    this.getHtml = function(){
        var color = "#FFFF00";
        var bgColor = "#00BBEE";

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

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

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

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

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

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

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

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

    this.treeMatrix = [];

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

        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] instanceof leaf){
                    this.treeMatrix[this.treeMatrix.length -1 - j][i].food += food;
                    food /= 2;
                }
            }

            if(isRainy){
                var rainFood = 5;

                for(var j in this.treeMatrix){
                    if(j == 0 && !(this.treeMatrix[j][i] instanceof branch))
                        continue;

                    if((this.treeMatrix[j][i] instanceof branch
                      || this.treeMatrix[j][i] instanceof leaf)
                      &&
                      (j == 0 || this.treeMatrix[j-1][i] instanceof branch)){
                        this.treeMatrix[j][i].food += food;
                        rainFood /= 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()]);
        }

        var rainySeason = Math.random() > 0.9;

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

        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.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 leaf(element.food/2, 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){
                        this.treeMatrix[i][j] = new flower(element.food/2);
                    }
                    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;
                    }
                }
                if(element instanceof flower
                    && element.food >= 1.5
                  ){
                    this.treeMatrix[i][j] = new froot(element.food/2);
                }
                if(element instanceof froot
                    && element.food >= 1
                  ){
                    this.plantNewTree(j, element.food);
                    this.treeMatrix[i][j] = new air();
                }
                if(element instanceof leaf
                    && element.food >= 1
                  ){
                   this.treeMatrix[i][j] = new branch(element.food, element.branchDirection);
                }
            }
        }
    };

    this.plantNewTree = function(coord, food){
        var canGrow = true;

        for(var i = 0; i <= treeSpace; i++){
            if(!(this.treeMatrix[0][coord + i] instanceof ground)
               || !(this.treeMatrix[0][coord - i] instanceof ground))
                canGrow = false;
        }

        if(canGrow)
            this.treeMatrix[0][coord] = new branch(food*10, 2);
    };

    this.getTreeString = function(){
        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 = 300;
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,300];
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,40,100):

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

     /
   _ \_
    |/\o_| /
o_/  \/ @|/\|
_@\o__\_/|o/
 \|\|\/ \|/
  |/  \_//
   \__/_|
______|__________

                       \ \/\
                 \    |/\/\_|/ |   |  /
              \ \@\/ \/\/\/ |/  \_/ \||_
          _  _\\/@/\/@\/\/   \_//\__/|/\_
           \ /\|\/|/|_o\/  __/o|\/_|_/\/__|
          |@|\_|/_o\|/\|\__o/\\|/\_|\|//|/\__|
       |_||/|_@|\/|\|_/|/|| \/ |\//\/o\\\\_@\|| |_|
       |/|/\|_||/\o\|/_/\/\_/\o|/ \/|_//// \/ \\|
     __@\|\||/\|@/|/o\/\/\/_@_\|\_/\_/|/ \_/__//
     __\/|/_@\O|o\|@|@\/\/\_|o/|/|\|\/|_//_||_/
  \ \ \|\|_/\|\|//|/\|_\/\//_@\/\|/|/\||//|\|o
 / |/ _|_|@|/|/ \\|__|_o\/o\\|o\||\|\/O|/O|/o_|_|
 \_/\|___|_|  \_/_|\/ \\/@|\\|\/||/|/\_|__|@|\|___/ /
|_||/|_@_\@\o_/o|o|/@_/\\/_//o \|/\|\/@|_o__|_|__/|/
  |@\| /|/\_\|\|/\||_/\_|\@|\\_/|\/@/|/|__/O|_/_/_|/
   \||@\|_@_\|/|\@|//o\||//o\||\|/\/||||o___|/ @|_|  _
    |o\/ \|@@|/ /\O\\/\|o\\|/o|/ \/|/\/\/|\@/\_/|/\_/
     \|\o/ \/ \ \/o_|\/|\//|\/o\_/_|O/\//o_|\/@//\/
      \\|\_@\_/_o\_/|o\|/|_|_\|/O|/|/\|||__|/o \\/
       \|/_|@\\/\\_\|/\|\|@\|\|\_|\|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\|_|/_///|@\|\\|/|/@|\/\_|@\|/\\|
                                _ \/\_o_\_/|/ \\\|/|\/ \O\/_@\/\|/|/|_/\\\|_/ \\|\|o_|_\|\|\/|\/\|_|\  /
                              \o_\|\|\_|||\/\_/o\|o|/\_/__\/\/\/\\|o_@\///  \o/o|/|__|\o|/||||/\/|O|/|@\/
                              \|@/|/@\|\/\/o/@\|\|_o\/_/||/\/\o\/O|/|@_\\\__/ \/|\__/|//|\/\|/\/o||@\/\/__|
                               |O\O\|\|/o//o\//|//\|/|o/|O\|\|\|\_|@|/ \\|||\_/\|///O|// @\/O\/|/\\\/\\\/\__|
                                \||/@/|\/\\/|\\o\\ |/|/\|@\|O|/|/ |_|__//_||O\|o|//o_|\\_//\_|\|\/_||//|\/@\|\
                         |   \__@|/\/\|/_/|\|_\|/\\/\/\/| \|_@\/\_|o|/\|_o||o/\\|/@/_o//\@\/\|/|/\o\|\\|/ \/|/
                      o_\|/   \|||\/\||_/\|/|@\|\/\\/\/\|_/|o_|\/o/\o\/|_|/\o\/ \\/|_|/\/_@\/| |__|/|//O\_///\o_
                        \|\|o_/@|\\\||/\|\|o|_@|/o/O\/\_|_/_o_|O\|_/\@\||/  |/\ /|\_/|O/o/|/\|o|/|/\| \|/@/|_/|_|\ _
                  / /\__/|/o__\_|_|\|/\/\/|/|/|_\|\/ \/\|/\@|__o||\|/o_|/\__/\/ \|/@/||o/| \/|_@\|_/___|O|_|@/|_@/|//
                  \/\o_/\| o__|\|@|/\\o\/\|\|_@/\|/_o/o/o\/\\/\\||/|\__|\/|/_/__/ \/\|@\\|\/ @/\/ \|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/|/\/ \\|\\/\/o\/\/\\_|\/ \/_|\\| \|_| \/|//  \/|_o/\__\__
          |   |/ o_o\| o\\_/|@\/ o|/\_|\|@\_o_/|\|/@\/\\_@|\\|/o_/||_/\o//|_|\/__|\/\/ /|/O_/\/\//__/|___/_|@\_o/O|o/@/ \/|_
         \|/o_@\_/|\||_//@_\|_/@__|\/o|/_/\||/| \|_/_\//@\|//o\_o\||/\//\\|_ //_|o/\/\o\|_o\\|\/// @_|\_||@_|/@|\/_/\/\_/_| /
          |\_/|/_|\\|@ \\|o\|o\_o_|@\\|/O_//\\|_o|/\_||_|/| \\/o\/|O\/\\//_/|o\O\/\/|/|/@||//|//@\__/\|__|/\/ \|/|_|/__/||\|
        /_/\|\/\||/ |__@\|/o|_/_|_|\@\|\/  \/ |/_|\/_||o|/|_//\_|\|_|\/O\\/\|o/o/@|\|_|_/o_\\o\\|/_@__|_||\|\_/ \|@|\@|//\\||
        \|\@|/\/\_\_o\|o|\\\|_|o|/\O\_|/\o_/| |_/|/ o\|_|\|o/\/_o/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\|/|_/\\/@|\_|
     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_//o/\|\\_//\/\_/O|/o__/\_|
    \/\_|/o\/\\\/|O\/||_||//@_\_|/o\/@|/@\\//\\/|o\\\/@_\/_/\|\_/|_|_//\|\/\|\|\\\|/||\_//o|\//|O\/O|\||O\/_//O|o/\/O|_|o_|@\/
     \O_|\_|\/\|\|_o\|_/|@\\|__|\\|/\/_\|/|\\o|\|\/@|\__|\/\/ \|\|o|//\/o \O\\|//_|\||/o_\/|/\\|//\_|_||_/\_|\||O\/\_|@/|_|_/
      |_|/_|@\_|_||_O||\|\\||@||/@|\/_|\|\|_|\|/|o\/|/o/|/|/O/o|/ \||\/\\_/_//|/@|\/O|o__|\o\//| \/|/__|o_/\_//@|/ /@@|\__|
     o  |\_|_|_|O|/o/|o\|/ \\\|\\/|/_/\||o|o\\\\o\/\|_/\O\\\/ o|\_//O/\/|\|@|_o\_|/\_|/\\_/\/\\|_/O||/\_||@/_@\/|o|/\_||\/
      |_@\||o|_/\|\/\|\/ \_||\|\|\\\O\o||/o\/ \|\|\//@_/O_\|\_/|/o|_o\ \|/|_|o//_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|/o\\\||/\_o|\|||/|@\|\|\/\_/o\|//@\|\|/\|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__|//__/|/|_//|_|_| \o\||/o/|/@\\|/|_///@/|/\/_||_//_||@|_@___/@__|
  \_|\_/\oo|_/_@\_@\_@\|@/ /o\/@\|\_ \\||_/|o|\@\_/|/ \|\_|_@_\\/\|@__/\/_o\|/|O//_|\|@/||/|@\/\/|/\||@/@/|__|_@//|/
    |__\|\|_o\/\/_|\|\O|/\o\_|\|_|_/| \|o|\|o|/\_o\|\__|/o/_|_o\\/_/|\| \ |//o|/ \|\/|//\|@\\|\/_|\/_|/\/\|/o@/|/_|
       \|_||/ \/\_|_|/o|\/|/ \\|o|_||_/o/  |/ \/ |_|//o|\/_@\/\//  \|_|_/o||/\|\_/@_\|\\_|_/_|/|o\//O///\_|/  \|/
        |_\|\_o\/O|o|_\|@\o\_o\|/|_|_@\|\@_/\_/___o|\\_| \/\o\/ \_@_|@|/ \||_/|/@__O\|//O|_||O\|_||\/ \\/o \__/|
          \|/|\|\|/\\\||\/||\|_|\_O|__/|/ |\__\@|\_o\|\\_/_/_/o_/\/\|_@\_@|/\_|__|\|@|/|_|| |_/|_@|/\_//o\_/ O/
           \\|/  |_// |/\\||O|_|o_|\\o\|\o|/__\||o\|\|/o\\||/\_/\/\_|_|\\|||/@|_o/\|/|_||/_o/\_|@\/\/_||\_@\_/
            \|o___o|_o_\//o|_/\\_||\||@|/|\\_@\|/\/@/|\/|||o\/o//\//|o_///O|\/|/o\o|/|_||__|\/|__|\/|/o|/ \/
             |\|@_\O \|\\\/_@\/_\\|_|/\o\|_|\_/@\o\/  \\| \\/\|\\/ \|/\|\\_|/_|_/_||/|O/|/o|/\|_||/\| \/\_/
              \|/  \__|_||\/\/O|\\|_|o/\/|/@\_\|/|/\_o/ |o_|\/|/ \_/o\_|/|\|__|@_/\|/O/_o\/ \o|__|\/  o\/
               |_____o|_|@\\/_o\\|\@\|\/\|\// \|\|\/_|\_/\|\/\ \_/@_|/o|/ \|____/\//\/|o_/   \|/|_/o__//
                 oooo|_/|@|\\||\||/|/|\\//|\\_o|/|/\/\/\|o|/o/o/@_|||o\|\o/ \|O/o/\\|\|_o\___/|O|oo/ \|
               o__|/\|o\|/|_||/\|/\|_@\|\\|/@\\|\|\|\/o/|_|\/\/\|\_|\\\|/ \_/  \|\/O|/|_|/|_//|/_//__/oo
                  |_//  |_|\//@/ \ |__@|O||\//@|_|/|/\/\|o|/\/\_|/||/ \|o_/Oo__/_/\/|\|/|\|/ \|@_|/ooo|
                    |_____|//@|\_/\|O|_/\||/ \/ \\\/\O\/o\/\/\/ |/ o\_/ \||_/ \| \@\|\|\|/|__/___|/|_/
                       ooo|/ \|@\\_|o_@\/_|@_/__/_\\/o/\/o\/\/o  \_//\__/|/\__/__/_o|/|_|_|__|oooo\|
                     o__|/o\__|_//@|/\\o\o\_o\|\\O\|\/|/|_|\/|___/@|\/_|_/\/__|o_@_||\|_|@/ oo\\/\/
                        |_|\\||@|\|@\/|\\|o|\\|o|\_|/_o\|/\|\__@/\\|/\_|\|//O/|__|/_|/|__|oo \/ \/
                          |/ ||_|/|_@\|/\|\|_||/|_@|\/|\|_/|/|| \/o|\//\/o\\\\_o\||o|_|oo_|__@\_/
                           \_o\\|@|_|_|O/  |/|@\|_||/\o\|/_/\/\_/\o|/ \/|_//// \/ O\| oo\/|/@|/oo
                             \_||@|__@| \__@\|\O|/_|@/|/o\/\/\/_@_\|\_/\_/|/o\_/__// oo|/\|\_|@|_oo
                               |/\\_\_|_@_|\/|/_@\\|o\|@|@\/\/\_|o/|/|\|\/|_//_||_/ooo\|\_|/o_/|_|
                                \@|@|\\|\|\|\|_/\|\|//|/\|_\/\//_@\/\|/|/\||//|\|@|_|//|/O|o_/\|
                                 \|\|/ |/|@|_|@|_|/ \\|__|_o\/o\\|o\||\|\/O|/O|/@_|_| \/\/_o_\/
                                  |_|\_/\|O__|_|  \_/_|\/ \\/@|\\|\/||/|/\_|__|@|\|___/\/|\|_/
                                    |_||/|_@_\@\o_/o|o|/@_/\\/_//o \|/\|\/@|_o__|_|__/|/||/|/
                                      |o\| /|/\_\|\|/\||_/\_|\@|\\_/|\/@/|/|__/O|_/_/_|// \|
                                       \||@\|_@_\|/|\@|//o\||//o\||\|/\/||||o___|/o_|@| \_/
                                        |o\/ \|@@|/ /\O\\/\|o\\|/o|/ \/|/\/\/|_o/\_/|/\_/
                                         \|\o/ \/ \ \/o_|\/|\//|\/o\_/_|O/\//o_|\/@//\/
                                          \\|\_@\_/_o\_/|o\|/|_|_\|/O|/|/\|||__|/o \\/
                                           \|/_|@\\/\\_\|/\|\|@\|\|\_|\|O//O/o_/ \_//
                                            |_@|_/@\/_/\|@_|//o/_/o//@\|/|\//||____|
                                    o________\\/\\|@\/\/__@\\\/|_o/|__|\\|/|/O|
                                             \|\/ |_o\/\o|_////_/|\|_|@/@|_|\/
                                              |_\_o\\/\/\o\|/|/ O|/ O|/\/\|\/
                                                \||/@\/\O\_|\|@_/ \_/|O/@_|/
                                                 |_\|_\O|/o|/ oo\_/@/  \__|
                                                   \|_\|\\_|\_/_|/\|___/
                                                    |/\| \||/ |_|\/|/
                                                     \ |_/@ \/ o|/\|
               oooooooo  ooo           oo             |_o\\_@\_/|@/
              oo|_o\|/oo__|_oo        o_\_o_oo          \|\|\/ \|/
               |/\|/|  \/\|/|_o         |\|_/            |/  \_//
                \_|/    \_|_|            \|/              \__/_|
__________________|_______|_______________|__________________|____________________________________________________________________________________________________

```

---
Tags: popularity-contest, ascii-art
---


title: Mr. Moneybag's Money Piles

text:
# Question
Title: Mr. Moneybag's Money Piles
Mr. Moneybags is a very rich man. He has an assistant Mr. Perfect, who one day, got very mad, and shredded some of Mr. Moneybag’s $100 bills! Mr. Moneybags decided to punish Mr. Perfect.

Mr. Moneybags tells Mr. Perfect to stack his money into different piles.

He starts with N (1 \<= N \<= 1,000,000, N odd) empty stacks, numbered 1..N. Mr. Moneybags then gives him a sequence of K instructions (1 \<= K \<= 25,000), each of the form "A B", meaning that Mr. Perfect should add one new bill to the top of each stack in the range A to B, inclusive. For example, if Mr. Perfect is told "11 13", then he should add a bill to each of the stacks 11, 12, and 13.

After Mr. Perfect finishes stacking the money according to his instructions, Mr. Moneybags would like to know the median height of his N stacks -- that is, the height of the middle stack if the stacks were to be arranged in sorted order (N is odd, so this stack is unique). Please write an efficient program to help Mr. Perfect determine the answer to Mr. Moneybag’s question.

INPUT FORMAT:

* Line 1: Two space-separated integers, N K.
* Lines 2..1+K: Each line contains one of Mr. Moneybag’s instructions in the form of two space-separated integers A B (1 \<= A \<= B \<= N).

SAMPLE INPUT:

```
7 4
5 5
2 4
4 6
3 5

```

INPUT DETAILS:

There are N=7 stacks, and Mr. Moneybags issues K=4 instructions. The first instruction is to add a bill to stack 5, the second is to add a bill to each stack from 2..4, etc.

OUTPUT FORMAT:

* Line 1: The median height of a stack after Mr. Perfect completes the instructions.

SAMPLE OUTPUT:

1

The winner is the one with the "most efficient" algorithm. So, if someone posts an O(N) solution, then it will beat any O(N^2). If there is a tie, aka, two or more people who post an O(N) solution, for example, then whoever has is the shortest code (code-golfed) wins.

So, your purpose is to write a efficient algorithm, and to prevent possible ties with other people, try to code-golf it as well.

Another thing, the input is to be read from a file and the output must be written to a file.

**EDIT** Also, the solution must be returned under or equal to 2 seconds. If it is not, you will receive a T. A wrong answer is an X. Which means, if no one can get it under time, then the most efficient algorithm sigh score of T can win.

**EDIT #2** Here are some more samples:

1. http://pastebin.com/x88xAyPA
2. http://pastebin.com/y6Cuxm7W
3. http://pastebin.com/kgbeiQtd

**EDIT #3** Bonus: (subtract 100 chars from total)

Solve this under 2 seconds :)

1. http://pastebin.com/3uT9VSzv

# Answer
# O(K log N), many characters of Python

**Edit:** Improved by replacing merge sort with radix sort.

This is an improvement over my previous answer, but I'm posting it separately because it's a different strategy, and so the post doesn't get super-long.

This is now optimal because simply reading the input can take `2*K*lg N` time in the worst case -- `2*K` numbers each with `lg N` bits.

The goal is to have minimal dependence on `N`. To do this, rather than store counts for each pile index, we realize that all piles in a contiguous cluster unaffected by the endpoints of any interval must have the same counts. So, if we see that an interval starts with `5`, and there's no changes until `15`, then those 10 piles have the same value.

Each change in pile size from a pile to the next one is caused by an interval starting or ending. We call these "events". Each event increases or decreases the current pile size by 1. If, from one event to the next, there's some number of piles, each of those piles has the current size.

We extract the `2*k` events from the intervals, and sort them using a radix sort, taking advantage of the values being `1` through `N`. This take takes `O(K*log(N))` because the numbers have `O(lg N)` bits.

We then run over the events, and for each one, update the list of counts to the previous event, which requires adding a number up to `N` (so `lg N` bits). This takes `O(log(N))` per step, and so `O(K*log(N))`

Finally, having gotten the counts of the pile sizes, it's easy to quickly find the median by computing the cumulative number of piles up to a given size (or, rather, we subtract it from our desired count). This also takes `O(K*log(N))`.

The algorithm does the huge test case in under a second.

The code (ungolfed) is below with comments.

```
# Process input
def get_ints(line):
 vals = line.split()
 return (int(vals[0]),int(vals[1]))

s = input()

lines = s.split("\n")
N,K = get_ints (lines[0])
intervals = [get_ints(line) for line in lines[1:]]

mins,maxes=map(list,zip(*intervals))

#Each event will represent an increase or decrease of a pile from the previous one
#Each min increases the count by 1
#Each max causes the count to decrease by 1, starting with the next pile
events = [(a,1) for a in mins] + [(b+1,-1) for b in maxes]
events.append((N+1,0))

#Do a radix sort on the first element of each pair
#Each number has O(lg N) digits, so this takes O(k lg N)
events.sort()

#Count of the number of piles of each size
#pile_sizes[size] counts the number of piles of that size
pile_sizes = [0]*K
cur_pile = 1
cur_size = 0

#For each event, we track the pile size after the event
#Then, on the next event, we know there were some number of piles of that size
#The number of piles equals the distance between events
#Multiple events on the same pile have zero distance and don't affect the counts
for event in events:
 event_pile = event[0]
 piles_current_size = event_pile - cur_pile
 pile_sizes[cur_size] += piles_current_size
 cur_pile = event_pile
 cur_size += event[1]

#Get the i_th largest pile size from a list of pile size counts
def get_order_stat(counts,i):
 for val in range(len(counts)):
  cur_count = counts[val]
  if i<cur_count:
   return val
  i-=cur_count
 return None

median = get_order_stat(pile_sizes,N//2)

print(median)

```
> 3 votes

# Answer
# O((N + K) * log(N)), many chars of Python

(See my improved solution.)

**Edit:** I realized that I wasn't accounting for operations with numbers taking `log(N)` time. For example, I think the linear time median, despite its name, is actually `N log N` once you take into account the time to compare numbers bit by bit.

**Edit:** Improved sorting. Thanks to isaacg.

The idea is to make a list of the size of each pile `1...N`, and then take the median of this list. The key is to obtain the size of a pile from the size of the pile before by adding the number of intervals that start at that value, and subtracting the number that end at the previous value. By sorting the lists of interval-starts and interval-ends, we can quickly query how many intervals start and end.

See the code for more detailed comments. I didn't golf it.

The code has no problem with the huge test case, taking \<1 second on my machine.

```
# Process input
def get_ints(line):
 vals = line.split()
 return (int(vals[0]),int(vals[1]))

s=input()

lines = s.split("\n")
N,K = get_ints (lines[0])
intervals = [get_ints(line) for line in lines[1:]]

# Separate out the starts and ends of the intervals.
# Sort each, which takes O((K + N) * log(N)) with a counting sort.
mins,maxes=map(list,zip(*intervals))
mins.sort()
maxes.sort()

#Make a running list of the sizes of each pile
size_list = []
cur_size = 0
for i in range(1,N+1):
 #Update the size of the next pile by adding one for each interval that starts here
 #Each number in min can only can one update, so this contributes O(k) total
 while mins and mins[0]==i:
  mins.pop(0)
  cur_size+=1
 #Likewise, subtract one for each interval that ended at the previous number
 while maxes and maxes[0]==i-1:
  maxes.pop(0)
  cur_size-=1
 size_list.append(cur_size)

#Now, we compute the median of size_list
#The naive median algorithm sorts and take the middle element, taking O(N*log(N)) time
#But, there's a linear-time algorithm to select the median (or any order statistic) of    a list
linear_time_median = lambda L: select(L, 0, len(L), len(L)//2)

#I didn't want to write my own linear median algorithm, as it standard but long.
#So, I use the linear median code from https://gist.github.com/boyers/7233877
median = linear_time_median(size_list)

print(median)

```

Here's the code for linear-time-median from https://gist.github.com/boyers/7233877.

```
#### Code credit: https://gist.github.com/boyers/7233877

# partition A[p:r] in place about x, and return the final position of the pivot
def partition(A, p, r, x):
  # find the index of the pivot
  i = -1
  for j in range(p, r):
    if A[j] == x:
      i = j
      break

  # move the pivot to the end
  if i != -1:
    t = A[r - 1]
    A[r - 1] = A[i]
    A[i] = t

  # keep track of the end of the "less than" sublist
  store_index = p

  # iterate
  for j in range(p, r - 1):
    if A[j] < x:
      t = A[j]
      A[j] = A[store_index]
      A[store_index] = t
      store_index += 1

  # put the pivot in its final place
  if i != -1:
    t = A[r - 1]
    A[r - 1] = A[store_index]
    A[store_index] = t

  # return the store index
  return store_index

# find the ith biggest element in A[p:r]
def select(A, p, r, i):
  # make a copy of the array
  A = A[:]

  # divide the n elements of A into n / 5 groups
  groups = [[]] * (((r - p) + 4) // 5)
  for x in range(p, r):
    groups[(x - p) // 5] = groups[(x - p) // 5] + [A[x]]

  # find the median of each group
  medians = [sorted(l)[(len(l) - 1) // 2] for l in groups]

  # find the median of medians
  if len(medians) == 1:
    median_to_rule_them_all = medians[0]
  else:
    median_to_rule_them_all = select(medians, 0, len(medians), (len(medians) - 1) // 2)

  # partition A around the median of medians
  partition_index = partition(A, p, r, median_to_rule_them_all)

  # base case
  if p + i < partition_index:
    return select(A, p, partition_index, i)
  if p + i > partition_index:
    return select(A, partition_index + 1, r, p + i - partition_index - 1)
  return A[p + i]

```
> 2 votes

# Answer
# C#

~~307~~ ~~273~~ ~~281~~ 283 characters. ~~A complexity of O(K)~~ I'm not sure but could be O(K\*N).

```
void m()
{
    var r = new StreamReader("in.txt");
    var m = new int[int.Parse(r.ReadLine().Split(' ')[0]) + 1];
    string l;
    while ((l = r.ReadLine()) != null)
    {
        var t = l.Split(' ');
        for (var i = int.Parse(t[0]); i <= int.Parse(t[1]); i++)
        {
            m[i]++;
        }
    }
    Array.Sort(m);
    File.WriteAllText("out.txt", m[m.Length / 2].ToString());
}

```

The character count is after deleting all new lines/unnecessary whitespaces...

PS: Your input example has an even amount of stacks, which violates your rule.

PPS: I answered the wrong question in my first try.

Second version little bit bigger but faster. If compiled without debug symbols (ctrl + f5 in visual studio 2013) 2.5 seconds for the last example.

But 318 characters...

```
void m()
{
    var r=new StreamReader("in.txt");
    var m=new int[int.Parse(r.ReadLine().Split(' ')[0])];
    string l;
    while((l=r.ReadLine())!=null)
    {
        var t = l.Split(' ');
        var e=Array.ConvertAll(t,int.Parse);
        m=m.Select((c,i)=>i>=e[0]&i<=e[1]?++m[i]:m[i]).ToArray();
    }
    Array.Sort(m);
    File.WriteAllText("out.txt",m[m.Length/2].ToString());
}

```
> 1 votes

# Answer
# C# - 374 Characters

Shamelessly lifted from Armin, and probably possible to micro-optimize even further. However, I saw his post and thought "Low hanging fruit" so hey, may as well.

```
void Main(){var r=new StreamReader("i");var m=new int[f(r.ReadLine())[0]];string l;while((l=r.ReadLine())!=null){var t=f(l);for(var i=t[0];i<=t[1];i++){m[i]++;}}Array.Sort(m);File.WriteAllText("o",m[m.Length/2].ToString());}static int[]f(string n){int[]b=new int[2];int r=0;for(int i=0;i<n.Length;i++){char c=n[i];if(c!=32){r=10*r+(c-48);}else{b[0]=r;r=0;}}b[1]=r;return b;}

```

## Ungolfed

```
void Main()
{
    var r = new StreamReader("i");
    var m = new int[f(r.ReadLine())[0]];
    string l;
    while ((l = r.ReadLine()) != null)
    {
        var t = f(l);
        for (var i = t[0]; i <= t[1]; i++)
        {
            m[i]++;
        }
    }
    Array.Sort(m);
    File.WriteAllText("o", m[m.Length/2].ToString());
}
static int[] f(string n)
{
    int[] b = new int[2];
    int r = 0;
    for (int i = 0; i < n.Length; i++)
    {
        char c = n[i];
        if (c != 32)
        {
            r = 10 * r + (c - 48);
        }
        else
        {
            b[0] = r;
            r=0;
        }
    }
    b[1] = r;
    return b;
}

```

Using LinqPad and the third pastebin link from the op, running a GC/warmup, and taking the average of 10 runs I get the following comparison times:

* Armin first answer: 3229ms average
* Armin second answer: 2601ms average
* My answer: 18ms average

First submission so I can't wait to see how badly the more seasoned posters can beat this!

Also, now that the bonus was added I can test mine against that! However, sadly over an average of 10 runs on my computer it takes 4293ms to come up with 9314. So I have quite a ways to go yet.
> 1 votes

# Answer
# Lua, 247 bytes

The program constructs a frequency table and finds the median from that. I don't know what that would be in the complexity notation. For the sake of code-golfing, the output is appended to the end of the input file. If that's a problem, I'll change it.

```
s="*n"f=io.open(--[[FILE NAME--]],"a+")t,i=f:read(s,s)b={}c={}d={}for x=1,i do
y,z=f:read(s,s)for w=y,z do
q=b[w]or 0
if c[q]then
c[q]=c[q]-1
end
b[w]=q+1
c[q+1]=1+(c[q+1]or 0)end
end
n=0
for _,i in pairs(c)do
for w=1,i do
d[n]=_
n=n+1
end
end
f:write(d[#d/2])f:flush()

```

**Ungolfed**

```
s="*n"
f=io.open("input.txt")
t,i=f:read(s,s)
b={}
c={}
d={}
for x=1,i do
  y,z=f:read(s,s)
  for w=y,z do
    q=b[w]or 0
    if c[q]then
      c[q]=c[q]-1
    end
    b[w]=q+1
    c[q+1]=1+(c[q+1]or 0)
  end
end
n=0
for _,i in pairs(c)do
  for w=1,i do
    d[n]=_
    n=n+1
  end
end
f:write(d[#d/2])
f:flush()

```
> 0 votes

---
Tags: code-golf, fastest-algorithm
---


# Question
Title: Recursive Mathematical Puzzle from a high school contest
The problem appeared on the 2013 SJCNY High School Programming Contest. It was the last question in the set of problems and no team produced a correct answer during the 2.5 hours they had to work on it. Shortest solution that can handle the full range of inputs with a reasonable run time (say under 2 minutes on a Pentium i5) wins.

**Vases**

Ryan’s mom gave him a vase with a cherished inscription on it, which he often places on his window ledge. He is moving into a high rise apartment complex and wants to make sure that if the vase falls off the ledge, it won’t break. So he plans to purchase several identical vases and drop them out of the window to determine the highest floor he can live on without the vase breaking should it fall off the window ledge. Time is short, so Ryan would like to minimize the number of drops he has to make.

Suppose that one vase was purchased and the building was 100 stories. If it was dropped out of the first floor window and broke, Ryan would live on the first floor. However if it did not break, it would have to be dropped from all subsequent floors until it broke. So the worst case minimum number of drops for one vase (V=1) and an N story building is always N drops. It turns out that if Ryan’s drop scheme is used, the worst case minimum number of drops falls off rapidly as the number of vases increases. For example, only 14 drops are required (worst case) for a 100 story building if two (V = 2) vases are used, and the worst case number of drops decreases to 9 if three vases are used.

Your task is to discover the optimum drop algorithm, and then code it into a program to determine the minimum number of drops (worst case) given the number of vases Ryan purchased, V, and the number of floors in the building, N. Assume that if a vase is dropped and it does not break, it can be reused.

Inputs: (from a text file) The first line of input contains the number of cases to consider. This will be followed by one line of input per case. Each line will contain two integers: the number of vases Ryan purchased, **V**, followed by the number of stories in the building, **N**. **N** \< 1500 and **V** \< 200

Output: (to console) There will be one line of output per case, which will contain the minimum number of drops, worst case.

**Sample Input**

```
   5
   2 10
   2 100
   3 100
   25 900
   5 100

```

**Sample Output** (1 for each input)

```
    4
    14
    9
    10
    7

```

# Answer
I solved this in excel, as my work machine doesn't have any languages on it. obviously the input/output part doesn't quite match the question... so psuedocode answer :

Setup

```
Array Heights[200][1500]

for v = 1 to 200
  Heights[v][1] = 1
for d = 1 to 1500
  Heights[1][d] = d
for d = 2 to 200
  for d = 2 to 1500
    Heights[v][d] = Heights[v-1][d-1] + Heights[v][d-1] + 1

```

'Heights' now contains all the answers within range. (sort of)

Solutions

```
for each input (V,N) :
d = 1
while (d <= 1500) and (Heights[V][d] < N)
  d++
print d

```

A few notes:

* if speed is vital the search in the 'solution' part can be replaced with a binary search
* because of the 1500 limit on floors, you never need to consider more than 11 vases. (in fact if V \> log2(N+1), then answer is just round up log2(N+1) ) ((ie binary vase drop search))
* There is slight ambiguity in the question regarding the first floor. It says 'if it breaks on the 1st floor, he will live on the 1st floor' which leads to 'if it breaks on the 2nd floor, he will live on the 1st floor regardless of whether or not it breaks on the 1st'...
> 2 votes

---
Tags: code-golf, math
---


title: The Mouse's Tale

text:
# Question
Title: The Mouse's Tale
Write a program that outputs Lewis Carroll's poem The Mouse's Tale from Alice in Wonderland, drawn in its distinctive tail-like shape.

Plain text of the poem:

> Fury said to a mouse, That he met in the house, 'Let us both go to law: I will prosecute you.— Come, I'll take no denial; We must have a trial: For really this morning I've nothing to do.' Said the mouse to the cur, 'Such a trial, dear sir, With no jury or judge, would be wasting our breath.' 'I'll be judge, I'll be jury,' Said cunning old Fury; 'I'll try the whole cause, and condemn you to death.'

Your output could be ASCII art or an image or an animation or a webpage or pretty much anything that follows the rules. The point of course is to be artistic and original.

**The highest voted answer will win in approximately one week.**

## Rules

* Your representation of the poem must exactly match the quoted text above.
* Your representation must be legible. Any literate person with decent eyesight should be able to decipher it and not have to zoom in.
* The tail must be vertically oriented, taking roughly 2 to 3 times more vertical space than horizontal space.
* The tail must be thicker at the top and grow thinner as it gets to the bottom.
* There must be at least 3 distinct curves or turns in the shape of the tail. (I count 5 above.)
* You may not use existing images/layouts of the poem as your output or in your code.
* You must actually write a program that generates your output. You cannot simply arrange some text in Photoshop.

# Answer
# JavaScript, animated edition

## Live Demo

**HTML**

```
<div id='wrapper'>
    <p id='intro'>
        "It is a long tail, certainly," said Alice, looking down with wonder at the Mouse's tail; "but why do you call it sad?" And she kept on puzzling about it while the Mouse was speaking, so that her idea of the tale was something like this:—"
    </p>
    <div id='tail'></div>
</div>

```

**CSS**

```
#wrapper { width: 300px; font: 16px serif; text-align: justify; }
p { margin: 0; padding: 0; }
p.wordEl { position: relative; }

```

**JS**

```
var poem = "Fury said to a mouse, That he met in the house, 'Let us both go to law: I will prosecute you.- Come, I'll take no denial; We must have a trial: For really this morning I've nothing to do.' Said the mouse to the cur, 'Such a trial, dear sir, With no jury or judge, would be wasting our breath.' 'I'll be judge, I'll be jury,' Said cunning old Fury; 'I'll try the whole cause, and condemn you to death.'\" ",
    words = poem.match(/.{0,15}[ ]/g),
    wordEls = [],
    tail = document.getElementById('tail'),
    startFontSize = 16,
    endFontSize = 8;

for (var i = 0; i < words.length; ++i) {
    var word = words[i].slice(0, words[i].length - 1);

    var wordEl = document.createElement('p');
    wordEl.className = 'wordEl';
    wordEl.innerText = word;
    wordEl.style.setProperty('font-size', (Math.round(((words.length - i) / words.length) * (startFontSize - endFontSize)) + endFontSize) + 'px');
    wordEls.push(wordEl);

    tail.appendChild(wordEl);
}

var counter = 0;
setInterval(function() {
    ++counter;
    for (var i = 0; i < wordEls.length; ++i) {
        var sn = Math.sin((i*2 + counter) / 5) * 150; // sn = result of math.SiN
        var wsn = sn * (i / wordEls.length); // weighted sn
        wordEls[i].style.setProperty('left', (wsn + 150) + 'px');
    }
}, 50);

```
> 16 votes

---
Tags: popularity-contest, ascii-art, graphical-output
---