Kenko, A Personalized Meal Planner

Kenko was a project I was brought in to by my friend Mark. Kenko was based on a simple idea: people think that eating healthy is expensive but it’s not.

In this blog post I’ll be writing more about the technical challenges in trying to generate customized meal plans. Ultimately this project was put on hold and I don’t currently have plans to open source the meal plan generating portion.

What makes a meal plan?

We know we want to have three to five meals a day over a week. Breakfast, lunch, dinner, and optionally one to two snacks.

The way we can think about a meal is as an object that has a bunch of attributes: nutritional information, a taste profile, cost, and the amount of time required to prepare the meal. Ideally we want to have a nutritionally balanced meal plan, meaning over the course of a given day we should hit match the USDA’s recommendations and adjust for different calorie requirements.

So we define a meal roughly as follows:

{
 vitamin_c: int,
 vitamin_d: int, 
 vitamin_b12: int,
 iron: int,
 ... 
 sugar: int,
 protein: int,
 fat: int,
 calories: int,
 piquancy: int,
 sweetness: int,
 savouriness: int, 
 ingredients: [],
 time_required: int,
 type: BREAKFAST|LUNCH|DINNER|SNACK
}

Optimizing a Meal Plan

We know we have objects with different attributes and we’re trying to get as close to (or slightly above) target values without going over a certain price point. Optimizing a meal plan is just a fancy way of saying “what is the maximum value of items we fit in a knapsack without going over a target weight”. This is a bit of a simplification of the problem — in actuality the value of a given meal is a function of the difference of the nutrient’s target value and the current value for that nutrient given our other meals for the day.

The value function I used during my testing was essentially:

def meal_value(attribute_name, target_nutrition, knapsack, meal):
    return (target_nutrition[attribute_name] - knapsack.value(attribute_name)) * meal[attribute_name] * WEIGHTS[attribute_name]

Where attribute_name is some attribute of a meal, target_nutrition is the amount of each attribute we’re aiming to have, knapsack is the meals for the day, meal is the meal we’re looking at, and WEIGHTS is a lookup table of how important each attribute is. WEIGHTS allows us to normalize values from different attributes and change how important something is to maximize, a modified version could have a positive and negative version of a weight so we can penalize heavily if we overshoot an attribute.

So we’ve framed a meal planner as an optimization problem with a bunch of known good solutions, unfortunately there is no good solution (that I’ve found or written) when the value of an item is a function of what is already in the knapsack. So what can we do?

A 90% Solution

It turns out that even if we did find the perfect solution it would lead to boring meal plans, everyone who entered the same price limit would always end up with the same meal plan! What we’re actually going to do is create a bunch of possible meal plans knowing we can’t find the perfect solution then pick the best one from all our possibilities.

We were pulling our meals from a database with millions of recipes, finding the perfect solution would scale poorly on that large of a data set but we can creating randomized meal plans can be done quickly.

In order to pick out the best meal plan from our set we need to define a scoring function, a simple one would be taking the absolute difference between each attribute of the knapsack and of the target_nutrition. We would then pick the meal plan that has a score closest to zero. The pseudo code for this would look like:

def knapsack_score(knapsack, target_nutrition):
    score = 0
    for each attribute:
        score += abs(target_nutrition[attribute] - knapsack[attribute])

The Full Algorithm

def get_optimal_meal_plan(target_calories, max_cost):
    meal_plans = []
    victory_threshold = 10 # If we randomize a meal plan with a score less than 10 we stop and just return that
    target_nutrition = TargetNutrition(target_calories) # Scales the USDA's nutrition target based on calories
    for i from 1 to 100000:
        current = generate_meal_plan(max_cost)
        if knapsack_score(current, target_nutrition) <= victory_threshold:
            return current
        meal_plans.append(current)
    return meal_plan from meal_plans with lowest knapsack_score

I purposefully skimmed over the price part — we really just want to discard any meal plans that exceed max cost, in the pseudo code I handwaved that away inside a hypothetical generate_meal_plan function that accounts for only max_cost.

The other big question with Kenko is how can we get the price of a meal. If you want to talk to me more about this project feel free to contact me, I’d love to chat.