### Lyrics...

Pyramids are amazing! Both in architectural and mathematical sense. If you have a computer, you can mess with pyramids even if you are not in Egypt at the time. For example, let's consider the following problem. Imagine that you have a pyramid built of numbers, like this one here:

```
   /3/
  \7\ 4 
 2 \4\ 6 
8 5 \9\ 3
```

### Here comes the task...

Let's say that the *'slide down'* is the maximum sum of consecutive numbers from the top to the bottom of the pyramid. As you can see, the longest *'slide down'* is `3 + 7 + 4 + 9 = 23`

Your task is to write a function `longestSlideDown` (in ruby: `longest_slide_down`) that takes a pyramid representation as argument and returns its' __largest__ *'slide down'*. For example,

```python
longestSlideDown([[3], [7, 4], [2, 4, 6], [8, 5, 9, 3]]) => 23
```

### By the way...

My tests include some extraordinarily high pyramids so as you can guess, brute-force method is a bad idea unless you have a few centuries to waste. You must come up with something more clever than that.

(c) This task is a lyrical version of the __Problem 18__ and/or __Problem 67__ on [ProjectEuler](https://projecteuler.net).

Difficulty: interview

Starter code:

def longest_slide_down(pyramid):
	

Solutions:
def longest_slide_down(p):
    res = p.pop()
    while p:
        tmp = p.pop()
        res = [tmp[i] + max(res[i],res[i+1])  for i in range(len(tmp))] 
    return res.pop()

def longest_slide_down(pyr):
    for row in range(len(pyr)-1, 0, -1):
        for col in range(0, row):
            pyr[row-1][col] += max(pyr[row][col], pyr[row][col+1])
    return pyr[0][0]

def longest_slide_down(pyramid):
    l = len(pyramid)
    for i in range(l-2,-1,-1):
        for j in range(i+1):
            pyramid[i][j] = max([pyramid[i+1][j],pyramid[i+1][j+1]])+pyramid[i][j]
    return pyramid[0][0]


def longest_slide_down(pyramid):
    i = len(pyramid) - 2
    while i > - 1:
        for j in range(len(pyramid[i])):
            pyramid[i][j] += max(pyramid[i+1][j], pyramid[i+1][j+1])
        i -= 1
    return pyramid[0][0]

class Tree(object):
    value = summ = None
    left = right = None
    
    def __init__(self, value):
        self.value = value


def iter_pairs(level):
    it = iter(level)
    a, b = Tree(next(it)), Tree(next(it))
    while b.value is not None:
        yield a, b
        a, b = b, Tree(next(it, None))


def build_tree(pyramid):
    it = iter(pyramid)
    root = Tree(next(iter(next(it))))
    prev_level = iter([root])
    for level in it:
        tree_level = []
        parent = next(prev_level)
        
        for left_tree, right_tree in iter_pairs(level):
            tree_level.append(left_tree)

            parent.left = left_tree
            parent.right = right_tree
            parent = next(prev_level, None)
            
        tree_level.append(right_tree)
        prev_level = iter(tree_level)

    return root


def calc_max_sums(root):
    if root is None:
        return 0

    if root.summ is not None:
        return root.summ

    root.summ = root.value + max(calc_max_sums(root.left), calc_max_sums(root.right))
    return root.summ


def find_max_slide(root):
    if root is None:
        return 0

    if not (root.left and root.right):
        return root.value

    if root.left.summ >= root.right.summ:
        return root.value + find_max_slide(root.left)
    
    if root.left.summ < root.right.summ:
        return root.value + find_max_slide(root.right)


def longest_slide_down(pyramid):
    tree = build_tree(pyramid)
    calc_max_sums(tree)
    return find_max_slide(tree)

def longest_slide_down(a):
    a = a[::-1]
    for j in range(1,len(a)):
        a[j] = [a[j][i]+max(a[j-1][i],a[j-1][i+1]) for i in range(len(a[j]))]
    return a[-1][0]


def longest_slide_down(pyramid):
    if len(pyramid) == 1:
        return pyramid[0][0]
    left, current = pyramid[:-1], pyramid[-1]
    pair_sum_g = map(max, zip(current[:-1], current[1:]))
    for i, x in enumerate(pair_sum_g):
        left[-1][i] += x
    return longest_slide_down(left)