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 $textSP :$

$$
beginalign
textCarbs & ~=~ fractextamount_1 times textcalories_1 times textcarbs_1 + cdotstextamount_1 times textcalories_1 + cdots \[5px]
textSP & ~=~ fracN_1 C_1 + N_2 C_2C_1 + C_2 times textBalance + textBase Gain
endalign
$$
where:

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




• $C$ is the calories of the food;




• $textBase Gain = 12$ (in all cases);




• $textBalance = fractextSum Nutrients2 times texthighest 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)))

I want speed and I want it now!

To speed up your program you can return early. Knowing if sum(total_calories) + food.calories <= MAXCALORIES: then you should return if the inverse is true when food is the food with the lowest amount of calories.

def test_early_leaf(available, MAXCALORIES):
 all_combinations = []
 min_calories = min(a.calories for a in available)

 def find_sp(total):
 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:
 return None
 return tot_avg(total, 'nutrients') * balance + 12

 def inner(total):
 if sum(f.calories for f in total) + min_calories > MAXCALORIES:
 sp = find_sp(total)
 if sp is not None:
 all_combinations.append((sp, total))
 else:
 for food in available:
 total_calories = [f.calories for f in total]
 if sum(total_calories) + food.calories <= MAXCALORIES:
 inner(total[:] + [food])

 inner([])
 return max(all_combinations, key=lambda i: i[0])

I added another function that performs memoization via an LRU cache with an unbound size. However it seemed to slow the process.

How to optimizing the algorithm

Firstly the equations are:

$$g(f, a) = fracSigma(f_a_i times f_textcalories_i)Sigma(f_textcalories_i)$$
$$n = g(f, textcarbs), g(f, textprotein), g(f, textfat), g(f, textvitimins)$$
$$textSP = g(f, textnutrients) times fracSigma n2max(n) + textBase gain$$

From here we have to find the maximums.

1. 
   

   What's the maximum and minimum that $fracSigma n2max(n)$ can be?

   
   
   

   $$ fracn + n + n + n2 times n = frac4n2n = 2$$
   $$ fracn + 0 + 0 + 02 times n = fracn2n = 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, textnutrients)$ can be?

   
   
   

   Firstly taking into account:

   
   
   

   $$fracSigma(a_i times b_i)Sigma(b_i) = Sigma(a_i times fracb_iSigma(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.