Optimizing my Diet with Code

Finally, a quick way to find perfectly nutritious diets.

Why search for perfect diets?

A healthy diet is essential for one’s well-being. With a balanced diet, one thinks more clearly, has more energy, is more resistant to disease, and will likely live longer. On the other hand, a poor diet can lead to brain-fog, fatigue, and disease. So to seize the benefits of healthy eating whilst avoiding the drawbacks of malnutrition, it is vital to plan one’s diet carefully¹.

Yet planning a diet is difficult. There are dozens of different vitamins and minerals that humans need, and a “perfect” diet would provide sufficient levels of all of them. Additionally, there are hundreds of different foods to choose from, with each providing different amount of these nutrients. This makes it challenging to find a combination of foods that provides all vitamins and minerals.

And existing diet planning tools are all lacking in some capacity. Many use AI, which makes them inherently unreliable. Other tools hide their implementation from users, and so provide little faith that they aren’t just using AI as well. And some tools are paid services, which some people be unable to afford.

So I wrote a free, open-source, non-AI program to generate “perfect” diets. The key insight is that we can find a perfect diet by just trying all combinations of foods until finding one that satisfies all our daily recommended intake of vitamins and minerals. In fact, the only thing stopping people from doing by this by hand is the sheer number of combinations one would need to try. But computers are perfect for this sort of task, being designed to process large amounts of data. And the technique of solving problems by simply exhausting all possible solutions already has a name: backtracking.

Finding “perfect” diets with backtracking

Backtracking is a well-studied category of algorithms which dates back to the 1950s. A backtracking algorithm is one which incrementally builds its way to a solution that satisfies a given set of constraints, by exploring each “path” to the solution one at a time. If the algorithm explores a path that would prevent the solution from satisfying the problem’s constraints, then the algorithm abandons that potential solution, “backtracks” to the most recent solution that would still be able to satisfy the constraints, and explores a different path to the solution instead. To make things more clear, let’s see how we can use backtracking to solve our problem of creating a “perfect” diet, one which provides 100% of one’s daily recommended intake of all vitamins and minerals.

Minimal example

To keep the example simple, let’s focus on a diet providing 100% of your daily recommended intake of just one vitamin, B12, and one mineral, iron. And to make this example even simpler, we’ll restrict ourselves to only eating eggs and toast for breakfast² The diet should also include no more than 2 servings of eggs or bread, because we’ll assume you prefer to eat a light breakfast. Backtracking can solve this problem by trying all possible combinations of servings of eggs and toast with these requirements. This is illustrated in the following diagram:

Notice that we only explore combinations with at most 2 servings of egg or toast, and avoid wasting time exploring combinations involving more than 2 servings of eggs or toast.

Now that we have all combinations of eggs and toast, we need a way to check which combinations actually satisfy 100% of our daily recommended intake of iron and B12. To do this, we first need to know how much iron and B12 one serving of eggs and toast each provide. For the sake of example, let’s pretend eggs and toast provide the following nutrients:

Armed with this information, let’s return to the previous diagram, coloring in green those combinations of eggs and toast which achieve 100% of our recommended daily intake of both iron and B12.

From this diagram, we can see that there are two possible unique combinations of eggs and toast that satisfy our intake requirements for iron and B12: 2 eggs with 1 piece of toast (for 100% iron and B12), and 2 eggs with 2 pieces of toast (for 150% iron and 100% B12). This illustrates the big idea of the algorithm: just try all possible combinations of foods, and emit any that satisfy at least 100% of our daily recommended intake of all vitamin and minerals.

But although this algorithm works, in practice it would be horribly slow, because we would want to explore many more combinations of foods with a greater a maximum number of servings per food. So now let’s see how we can speed it up.

Optimizations

Stopping once we find a solution

One easy way to optimize this algorithm would be to simply stop exploring the search space once we reach our first solution. For instance, let’s assume we explore each node in the search tree by trying that node’s combination first, then its left subtree’s combinations, and finally its right subtree’s combinations (this would be an in-order tree traversal, a kind of depth-first search). With this approach we would avoid exploring much of the tree. The following diagram illustrates this idea, with the green node signifying our solution, and gray nodes signifying combinations that we skip checking.

We skipped checking 15 of 19 possible solutions; quite the speedup.

Avoiding redundant work with memoization

We were able to greatly accelerate our algorithm by stopping once we found a single solution, but eating the same thing everyday can become boring. So is there a way we can optimize our approach to go faster while still finding all (or at least, more than one) solution? In fact, there is! If we take a second look at the diagram, we’ll notice that we explore some combinations more than once (in the following diagram these combinations are red).

To make make our algorithm faster, we can keep track of the combinations we’ve already explored, and skip re-evaluating them if we encounter them again. For the above example, this would result in the following search space, with solutions in green, and skipped combinations in gray.

With this optimization, we skip checking 10/19 combinations. This isn’t quite as fast as returning after the first solution (that would have skipped 15 combinations), but the upside is that we now obtain all solutions. This technique of remembering prior inputs to avoid redundant computation is called memoization, and our usage of it makes our algorithm an example of top-down dynamic programming.

Try it!

You can check out my implementation of this approach on GitHub. Here’s some sample output, a diet which satisfies all your daily vitamin and mineral needs!³:

Diet 1
  Bell pepper             400 grams    80.0 calories
  Carrot                  400 grams    164.0 calories
  Chicken                 200 grams    478.0 calories
  Peanut butter           100 grams    598.0 calories
  Salmon                  200 grams    412.0 calories
  Spinach                 100 grams    23.0 calories
  Tofu                    100 grams    144.0 calories
  Total                   4300 grams    1899.0 calories

You can even customize the tool to generate diets from different lists of foods, and change the maximum number of servings and calories that you want each diet to provide. I encourage you to try it out :)

Notes