Htydjtk

I've created the following code to try and find the optimum "diet" from a game called Eco. The maximum amount of calories you can have is 3000, as shown with MAXCALORIES.

Is there any way to make this code faster, since the time predicted for this code to compute 3000 calories is well over a few hundred years.

Note: I am trying to find the highest SP (skill points) you get from a diet, the optimum diet. To find this, I must go through every combination of diets and check how many skill points you receive through using it. The order of food does not matter, and I feel this is something that is slowing this program down.

import itertools

import sys

import time



sys.setrecursionlimit(10000000)



#["Name/Carbs/Protein/Fat/Vitamins/Calories"]

available = ['Fiddleheads/3/1/0/3/80', 'Fireweed Shoots/3/0/0/4/150', 'Prickly Pear Fruit/2/1/1/3/190', 'Huckleberries/2/0/0/6/80', 'Rice/7/1/0/0/90', 'Camas Bulb/1/2/5/0/120', 'Beans/1/4/3/0/120', 'Wheat/6/2/0/0/130', 'Crimini Mushrooms/3/3/1/1/200', 'Corn/5/2/0/1/230', 'Beet/3/1/1/3/230', 'Tomato/4/1/0/3/240', 'Raw Fish/0/3/7/0/200', 'Raw Meat/0/7/3/0/250', 'Tallow/0/0/8/0/200', 'Scrap Meat/0/5/5/0/50', 'Prepared Meat/0/4/6/0/600', 'Raw Roast/0/6/5/0/800', 'Raw Sausage/0/4/8/0/500', 'Raw Bacon/0/3/9/0/600', 'Prime Cut/0/9/4/0/600', 'Cereal Germ/5/0/7/3/20', 'Bean Paste/3/5/7/0/40', 'Flour/15/0/0/0/50', 'Sugar/15/0/0/0/50', 'Camas Paste/3/2/10/0/60', 'Cornmeal/9/3/3/0/60', 'Huckleberry Extract/0/0/0/15/60', 'Yeast/0/8/0/7/60', 'Oil/0/0/15/0/120', 'Infused Oil/0/0/12/3/120', 'Simple Syrup/12/0/3/0/400', 'Rice Sludge/10/1/0/2/450', 'Charred Beet/3/0/3/7/470', 'Camas Mash/1/2/9/1/500', 'Campfire Beans/1/9/3/0/500', 'Wilted Fiddleheads/4/1/0/8/500', 'Boiled Shoots/3/0/1/9/510', 'Charred Camas Bulb/2/3/7/1/510', 'Charred Tomato/8/1/0/4/510', 'Charred Corn/8/1/0/4/530', 'Charred Fish/0/9/4/0/550', 'Charred Meat/0/10/10/0/550', 'Wheat Porridge/10/4/0/10/510', 'Charred Sausage/0/11/15/0/500', 'Fried Tomatoes/12/3/9/2/560', 'Bannock/15/3/8/0/600', 'Fiddlehead Salad/6/6/0/14/970', 'Campfire Roast/0/16/12/0/1000', 'Campfire Stew/5/12/9/4/1200', 'Wild Stew/8/5/5/12/1200', 'Fruit Salad/8/2/2/10/900', 'Meat Stock/5/8/9/3/700', 'Vegetable Stock/11/1/2/11/700', 'Camas Bulb Bake/12/7/5/4/400', 'Flatbread/17/8/3/0/500', 'Huckleberry Muffin/10/5/4/11/450', 'Baked Meat/0/13/17/0/600', 'Baked Roast/4/13/8/7/900', 'Huckleberry Pie/9/5/4/16/1300', 'Meat Pie/7/11/11/5/1300', 'Basic Salad/13/6/6/13/800', 'Simmered Meat/6/18/13/5/900', 'Vegetable Medley/9/5/8/20/900', 'Vegetable Soup/12/4/7/19/1200', 'Crispy Bacon/0/18/26/0/600', 'Stuffed Turkey/9/16/12/7/1500']



global AllSP, AllNames

AllSP = 

AllNames = 



def findcombs(totalNames, totalCarbs, totalProtein, totalFat, totalVitamins, totalNutrients, totalCalories, MAXCALORIES):

    doneit = False

    for each in available:

        each = each.split("/")

        name = each[0]

        carbs = float(each[1])

        protein = float(each[2])

        fat = float(each[3])

        vitamins = float(each[4])

        nutrients = carbs+protein+fat+vitamins

        calories = float(each[5])

#        print(totalNames, totalCalories, calories, each)

        if sum(totalCalories)+calories <= MAXCALORIES:

            doneit = True

            totalNames2 = totalNames[::]

            totalCarbs2 = totalCarbs[::]

            totalProtein2 = totalProtein[::]

            totalFat2 = totalFat[::]

            totalVitamins2 = totalVitamins[::]

            totalCalories2 = totalCalories[::]

            totalNutrients2 = totalNutrients[::]



            totalNames2.append(name)

            totalCarbs2.append(carbs)

            totalProtein2.append(protein)

            totalFat2.append(fat)

            totalVitamins2.append(vitamins)

            totalCalories2.append(calories)

            totalNutrients2.append(nutrients)

#            print("    ", totalNames2, totalCarbs2, totalProtein2, totalFat2, totalVitamins2, totalNutrients2, totalCalories2)

            findcombs(totalNames2, totalCarbs2, totalProtein2, totalFat2, totalVitamins2, totalNutrients2, totalCalories2, MAXCALORIES)

        else:

            #find SP

            try:

                carbs    = sum([x * y for x, y in zip(totalCalories, totalCarbs)])    / sum(totalCalories)

                protein  = sum([x * y for x, y in zip(totalCalories, totalProtein)])  / sum(totalCalories)

                fat      = sum([x * y for x, y in zip(totalCalories, totalFat)])      / sum(totalCalories)

                vitamins = sum([x * y for x, y in zip(totalCalories, totalVitamins)]) / sum(totalCalories)

                balance  = (carbs+protein+fat+vitamins)/(2*max([carbs,protein,fat,vitamins]))

                thisSP   = sum([x * y for x, y in zip(totalCalories, totalNutrients)]) / sum(totalCalories) * balance + 12

            except:

                thisSP = 0

            #add SP and names to two lists

            AllSP.append(thisSP)

            AllNames.append(totalNames)



def main(MAXCALORIES):

    findcombs(, , , , , , , MAXCALORIES)

    index = AllSP.index(max(AllSP))

    print()

    print(AllSP[index], "  ", AllNames[index])



for i in range(100, 3000, 10):

    start = time.time()

    main(i)

    print("Calories:", i, ">>> Time:", time.time()-start)

Edit: On request, here is the formula for calculating the SP

Carbs = (amount1*calories1*carbs1 + ...) / (amount1*calories1 + ...)



          (N1*C1) + (N2*C2)

SP =     ----------------    x Balance + Base Gain

                C1+C2



^^ Where N is the nutrients of the food (carbs+protein+fat+vitamins), and C is the calories of the food



Base Gain = 12 (Always 12)



Balance = Sum Nutrients / (2 * highest nutrition)

1. 
   

   Global variables are bad. Don't use them. I have to spend a long while looking at your code to tell what uses them and when. When your code becomes hundreds of lines long this is tedious and unmaintainable.

   
   
   

   If you need to use recursion and add to something not in the recursive function use a closure.

   
   



2. You should load available into an object, rather than extract the information from it each and every time you use it.



3. Using the above you can simplify all your totalNames, totalCarbs into one list.


4. Rather than using AllSP and AllNames you can add a tuple to one list.


5. You should put all your code into a main so that you reduce the amount of variables in the global scope. This goes hand in hand with (1).


6. Rather than copying and pasting the same line multiple times you can create a function.

All this gets the following. Which should be easier for you to increase the performance from:

import itertools

import sys

import time

import collections



sys.setrecursionlimit(10000000)



_Food = collections.namedtuple('Food', 'name carbs protein fat vitamins calories')



class Food(_Food):

    @property

    def nutrients(self):

        return sum(self[1:5])





def read_foods(foods):

    for food in foods:

        name, *other = food.split('/')

        yield Food(name, *[float(v) for v in other])





def tot_avg(food, attr):

    return (

        sum(f.calories * getattr(f, attr) for f in food)

        / sum(f.calories for f in food)

    )





def find_combs(available, MAXCALORIES):

    all_combinations = 

    def inner(total):

        for food in available:

            total_calories = [f.calories for f in total]

            if sum(total_calories) + food.calories <= MAXCALORIES:

                inner(total[:] + [food], MAXCALORIES)

            else:

                nutrients = [

                    tot_avg(total, 'carbs'),

                    tot_avg(total, 'protein'),

                    tot_avg(total, 'fat'),

                    tot_avg(total, 'vitamins')

                ]

                balance = sum(nutrients) / 2 / max(nutrients)

                sp = tot_avg(total, 'nutrients') * balance + 12

                all_combinations.append((sp, total))

    inner()

    return all_combinations





def main(available):

    for MAXCALORIES in range(100, 3000, 10):

        start = time.time()

        all_ = findcombs(available, MAXCALORIES)

        amount, foods = max(all_, key=lambda i: i[0])

        print(amount, '  ', [f.name for f in foods])

        print('Calories:', i, '>>> Time:', time.time()-start)





if __name__ == '__main__':

    available = ['Fiddleheads/3/1/0/3/80', 'Fireweed Shoots/3/0/0/4/150', 'Prickly Pear Fruit/2/1/1/3/190', 'Huckleberries/2/0/0/6/80', 'Rice/7/1/0/0/90', 'Camas Bulb/1/2/5/0/120', 'Beans/1/4/3/0/120', 'Wheat/6/2/0/0/130', 'Crimini Mushrooms/3/3/1/1/200', 'Corn/5/2/0/1/230', 'Beet/3/1/1/3/230', 'Tomato/4/1/0/3/240', 'Raw Fish/0/3/7/0/200', 'Raw Meat/0/7/3/0/250', 'Tallow/0/0/8/0/200', 'Scrap Meat/0/5/5/0/50', 'Prepared Meat/0/4/6/0/600', 'Raw Roast/0/6/5/0/800', 'Raw Sausage/0/4/8/0/500', 'Raw Bacon/0/3/9/0/600', 'Prime Cut/0/9/4/0/600', 'Cereal Germ/5/0/7/3/20', 'Bean Paste/3/5/7/0/40', 'Flour/15/0/0/0/50', 'Sugar/15/0/0/0/50', 'Camas Paste/3/2/10/0/60', 'Cornmeal/9/3/3/0/60', 'Huckleberry Extract/0/0/0/15/60', 'Yeast/0/8/0/7/60', 'Oil/0/0/15/0/120', 'Infused Oil/0/0/12/3/120', 'Simple Syrup/12/0/3/0/400', 'Rice Sludge/10/1/0/2/450', 'Charred Beet/3/0/3/7/470', 'Camas Mash/1/2/9/1/500', 'Campfire Beans/1/9/3/0/500', 'Wilted Fiddleheads/4/1/0/8/500', 'Boiled Shoots/3/0/1/9/510', 'Charred Camas Bulb/2/3/7/1/510', 'Charred Tomato/8/1/0/4/510', 'Charred Corn/8/1/0/4/530', 'Charred Fish/0/9/4/0/550', 'Charred Meat/0/10/10/0/550', 'Wheat Porridge/10/4/0/10/510', 'Charred Sausage/0/11/15/0/500', 'Fried Tomatoes/12/3/9/2/560', 'Bannock/15/3/8/0/600', 'Fiddlehead Salad/6/6/0/14/970', 'Campfire Roast/0/16/12/0/1000', 'Campfire Stew/5/12/9/4/1200', 'Wild Stew/8/5/5/12/1200', 'Fruit Salad/8/2/2/10/900', 'Meat Stock/5/8/9/3/700', 'Vegetable Stock/11/1/2/11/700', 'Camas Bulb Bake/12/7/5/4/400', 'Flatbread/17/8/3/0/500', 'Huckleberry Muffin/10/5/4/11/450', 'Baked Meat/0/13/17/0/600', 'Baked Roast/4/13/8/7/900', 'Huckleberry Pie/9/5/4/16/1300', 'Meat Pie/7/11/11/5/1300', 'Basic Salad/13/6/6/13/800', 'Simmered Meat/6/18/13/5/900', 'Vegetable Medley/9/5/8/20/900', 'Vegetable Soup/12/4/7/19/1200', 'Crispy Bacon/0/18/26/0/600', 'Stuffed Turkey/9/16/12/7/1500']

    main(list(read_foods(available)))

Data representation

Your choice of data representation is curious. It's a middle ground between a fully-serialized text format and a fully-deserialized in-memory format (such as nested tuples or dictionaries). I'd offer that it's not as good as either of the above. If you're going for micro-optimization, you need to do "pre-deserialized" literal variable initialization that doesn't require parsing at all. The best option would probably be named tuples or even plain tuples, i.e.

available = (

    ('Fiddleheads', 3, 1, 0, 3, 80),

    # ...

)

But this won't yield any noticeable benefit, and it's not as maintainable as the alternative: just write a CSV file.

main isn't main

You've written a main function that isn't actually top-level code. This is not advisable. Rename it to something else, and put your top-level code in an actual main function, called from global scope with a standard if __name__ == '__main__' check.

list duplication

This:

totalNames[::]

should simply be

list(totalNames)

snake_case

Your names should follow the format total_names, rather than totalNames.

Also, variables in global scope (i.e. AllSP) should be all-caps; and you shouldn't need to declare them global.

I'm going to do some reading and see what you're doing in terms of algorithm and submit a second answer to suggest a saner one.