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 $text{SP} :$

$$
begin{align}
text{Carbs} & {~=~} frac{text{amount}_1 times text{calories}_1 times text{carbs}_1 + cdots}{text{amount}_1 times text{calories}_1 + cdots} \[5px]
text{SP} & {~=~} frac{N_1 C_1 + N_2 C_2}{C_1 + C_2} times text{Balance} + text{Base Gain}
end{align}
$$
where:

• $N$ is the nutrients of the food (carbs+protein+fat+vitamins);




• $C$ is the calories of the food;




• $text{Base Gain} = 12$ (in all cases);




• $text{Balance} = frac{text{Sum Nutrients}}{2 times text{highest nutrition}} .$

Readability is #1

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])

            else:

                try:

                    nutrients = [

                        tot_avg(total, 'carbs'),

                        tot_avg(total, 'protein'),

                        tot_avg(total, 'fat'),

                        tot_avg(total, 'vitamins')

                    ]

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

                except ZeroDivisionError:

                    continue

                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_ = find_combs(available, MAXCALORIES)

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

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

        print('Calories:', amount, '>>> 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)))

How to optimizing the algorithm

Firstly the equations are:

$$g(f, a) = frac{Sigma(f_{a_i} times f_{text{calories}_i})}{Sigma(f_{text{calories}_i})}$$
$$n = {g(f, text{carbs}), g(f, text{protein}), g(f, text{fat}), g(f, text{vitimins})}$$
$$text{SP} = g(f, text{nutrients}) times frac{Sigma n}{2max(n)} + text{Base gain}$$

From here we have to find the maximums.

1. 
   

   What's the maximum and minimum that $frac{Sigma n}{2max(n)}$ can be?

   
   
   

   $$ frac{n + n + n + n}{2 times n} = frac{4n}{2n} = 2$$
   $$ frac{n + 0 + 0 + 0}{2 times n} = frac{n}{2n} = 0.5$$

   
   
   

   This means all we need to do is ensure the calorie average of all the different nutrients are the same. It doesn't matter what value this average is, only that all have the same.

   
   


2. 
   

   What's the maximum that $g(f, text{nutrients})$ can be?

   
   
   

   Firstly taking into account:

   
   
   

   $$frac{Sigma(a_i times b_i)}{Sigma(b_i)} = Sigma(a_i times frac{b_i}{Sigma(b_i)})$$

   
   
   

   We know that these are the calorie average of the foods nutritional value. To maximize this you just want the foods with the highest nutritional value.

   
   

Lets work through an example lets say we have the following five foods:

• a/10/0/0/0/1


• b/0/10/0/0/1


• c/0/0/10/0/1


• d/0/0/0/10/1


• e/1/1/1/1/4

What's the way to maximize SP?

Eating 1 e would give you $4 times 2 = 8$.

Eating 4 a would give you $10 times 0.5 = 5$.

Eating 1 a, b, c and d would give you $10 times 2 = 20$.

And so from here we have deduced eating a, b, c and d in ratios of 1:1:1:1 give the most SP.

This means the rough solution is to find the foods that have the same calorie average for their individual nutrients where you select foods with a bias for ones with high total nutrients.

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.

Suggested

This doesn't at all tackle the main issue of algorithmic complexity, only Python usage. It isn't a good implementation, it's just to illustrate some stylistic improvements.

Note a few things:

• Having a shebang at the top is very important to indicate to the shell and other programmers what's being executed


• Use csv


• Use tuple unpacking in your loops where possible


• Abbreviate the formation of new lists by doing appends inline


• Never except:; at a minimum except Exception: although even this should be more specific


• Use f-strings where appropriate


• Drop inner lists in list comprehensions when you don't need them

foods.csv

name,carbs,protein,fat,vitamins,calories

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

Python

#!/usr/bin/env python3



import csv

from time import time



ALL_SP = 

ALL_NAMES = 





def read(fn):

    with open('foods.csv') as f:

        reader = csv.reader(f, newline='')

        next(reader)  # ignore title

        return tuple(

            (name, float(carbs), float(protein), float(fat), float(vitamins), float(calories))

            for name, carbs, protein, fat, vitamins, calories in reader

        )





AVAILABLE = read('foods.csv')





def find_combs(total_names, total_carbs, total_protein, total_fat, total_vitamins, total_nutrients,

               total_calories, max_calories):

    for name, carbs, protein, fat, vitamins, calories in AVAILABLE:

        nutrients = carbs+protein+fat+vitamins



        if sum(total_calories) + calories <= max_calories:

            find_combs(total_names + [name],

                       total_carbs + [carbs],

                       total_protein + [protein],

                       total_fat + [fat],

                       total_vitamins + [vitamins],

                       total_nutrients + [nutrients],

                       total_calories + [calories],

                       max_calories)

        else:

            # find SP

            try:

                carbs    = sum(x * y for x, y in zip(total_calories, total_carbs)) / sum(total_calories)

                protein  = sum(x * y for x, y in zip(total_calories, total_protein)) / sum(total_calories)

                fat      = sum(x * y for x, y in zip(total_calories, total_fat)) / sum(total_calories)

                vitamins = sum(x * y for x, y in zip(total_calories, total_vitamins)) / sum(total_calories)

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

                thisSP   = sum(x * y for x, y in zip(total_calories, total_nutrients)) / sum(total_calories) * balance + 12

            except Exception:

                thisSP = 0



            # add SP and names to two lists

            ALL_SP.append(thisSP)

            ALL_NAMES.append(total_names)





def calc(max_calories):

    find_combs(, , , , , , , max_calories)

    index = ALL_SP.index(max(ALL_SP))

    print()

    print(f'{ALL_SP[index]:.2f} {ALL_NAMES[index]}')





def main():

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

        start = time()

        calc(i)

        print(f'Calories: {i} >>> Time: {time()-start:.3f}')





if __name__ == '__main__':

    main()

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.