A Bird Revenge

'''
Created on 16 sept. 2013

@author: Adil OURIDA.
@contact: [email protected]

===========
Algorithm :
===========

Let's take this example :
50
0 5 10
1 3 5
3 7 12
6 11 20
14 17 8
19 24 14
21 22 2

I think that one of the solutions is to delimit the whole list into
independent lists so to calculate the optimum energy unit for each one.
And the global energy unit is the sum.

 ______10______      ____20____
|              |    |          |
0    1    3    5    6    7    11
     |_5__|_______12_____| 

=> optimum is 80 : 10 + 50 + 20

 ___8__    
|      |
14    17

=> 14 - 11 is the distance between the two sequential lists.
=> optimum is 8

 _________14_______
|                  |
19    21    22    24
       |__2__|
       
=> 19 - 17 is the distance between the two sequential lists.
=> optimum is 14

=> The global is : 80 + 3*50 + 8 + 2*50 + 14 = 352

'''
class Model:
    '''
    class docs
    '''
    def __repr__(self):
        return repr((self.x, self.y, self.eu))


# Energy Unit
eu_normal = 0;


def delimitList(models):
    """ 
    
    """
    retModels = list();
    retModels.append(models[0])
    comp = models[0].y
    i = 0
    for model in models:
        if i != 0: 
            if model.x < comp:
                # add 
                retModels.append(model)
                if model.y > comp :
                    comp = model.y
            else:
                # stopList
                break
        i = i + 1
    return retModels

def getOptimumValue(models, diffList):
    optimumValue_ = 0
    tuples_ = []
    i = 0
    for model in models:
        tuples = [(model.x,model.y)]
        opt = 0
        opt = opt + (model.x - diffList) * eu_normal
        opt = opt + model.eu
        comp = model.y
        for model2 in models:
            if model2.x >= comp:
                # add
                opt = opt + (model2.x - model.y) * eu_normal
                opt = opt + model2.eu
                comp = model2.y
                tuples.append((model2.x,model2.y))
        
        
        sortedY = sorted(models, key=lambda model: model.y)
        opt = opt + (sortedY[-1].y - comp) * eu_normal
        
        if i != 0:
            if opt < optimumValue_:
                optimumValue_ = opt
                tuples_ = tuples
                
        else:
            optimumValue_ = opt
            tuples_ = tuples
        i = i + 1
        
    return optimumValue_,tuples_

f = open('in', 'r')
i = 0;

models = list()
for line in f:
    if i == 0 :
        eu_normal = int(line)
    else:
        split = line.split(" ")
        model = Model();
        model.x = int(split[0])
        model.y = int(split[1])
        model.eu = int(split[2])
        models.append(model)
    i = i + 1
# print(eu_normal)
models = sorted(models, key=lambda model: model.x)
# print(models)
f.close()

hasNext = True
diffList = 0
optimumValue = 0
tuples = []
while hasNext:
    if not models:
        hasNext = False
    else:
        
        result = delimitList(models);
        
        value = getOptimumValue(result, diffList)
        
        optimumValue = optimumValue + value[0] 

        for t in value[1]:
            tuples.append(t)
        
        diffList = result[-1].y
        
        for model in result:
            models.remove(model)
            
print(optimumValue)
print(tuples)