JavaScript prevent infinite loop - possibily with dynamic recognition pattern?

Question

first of here is the commented pseudo-code:

// TODO:
// Person A (80kg) nutrition intake requirements are:
// nutrient     ||  Unit(g)
// Vitamin A    :   30,
// Vitamin B1   :   2,
// Vitamin C    :   300,
// Vitamin D    :   3000,
// Protein      :   100,
// Calcium      :   30

var nutrient_requirements = {
    vita: {min: 30 ,max: 38},
  vitb1: {min:2, max:4},
  vitc: {min:300, max: 800},
  vitd: {min: 300, max:3000},
  protein: {min:100, max:200},
  calcium: {min:30, max:50}
}

// The calculated estimate amount of food
// the person eats on a daily base is around 900(g)
// The amount will be distributed among the terms
// with a predefined pattern

var food_amount = {
    fruits:[200,200],
  meat: [500]
}

// START (usefull anchor for this pseudocode)

var calculated_nutrition = {
    vita: 0,
  vitb1: 0,
  vitc: 0,
  vitd: 0,
  protein: 0,
  calcium: 0
}

// The daily nutrition intake of this person
// needs to be achieved by the following terms:
// apple, banana, chicken breast
// Term nutrient values per gramm
var terms = {
    fruits:[
    apple:{
        vita: 0.02,
        vitc: 0.30,
        vitd: 0.01,
        protein: 0.08,
        calcium: 0
    },
    banana:{
        vita: 0.1,
        vitc: 0.09,
        vitd: 0.00,
        protein: 0.1,
        calcium: 0.2
    }
  ],
  meat:[
    chicken_breast:{
        vita: 0.07,
        vitc: 0.08,
        vitd: 0.03,
        protein: 0.4,
        calcium: 0.2
    }
  ]
}

// Now we want to see if the normal amount and distribution
// of the food covers the required amount
// To do that we need to multiply the matching food amount
// with the matching food / term and sum up all values

for(let prop in terms){
    for(let i = 0; i < terms[prop].length; i++){
    for(let propb in terms[prop][i]){
        calculated_nutrition[propb] = terms[prop][i][propb] * food_amount[prop][i];
    }
  }
}

// After that is done, we can compare calculated_nutrition to
// nutrient_requirements to see whether something is too much
// or too little

for(let propa in nutrient_requirements){
    if(nutrient_requirements[propa].min > calculated_nutrition[propa]){
    // this nutrient level is too little
    // now we need to increase some food / term
    // in order to achieve the required minimum
    // of this nutrient
    alter_amount(propa, "up");
    return;
  }else if(nutrient_requirements[propa].max < calculated_nutrition[propa]){
    // this nutrient level is too high
    // now we need to decrease some food / term
    // in order to achieve the required minimum
    alter_amount(propa, "down");
    return;
  }else{
    // this nutrient level is ok
    return;
  }
}

function alter_amount(prop, direction){
    // here we look in terms which food
  // has the highest amount of prop

  switch(direction){
    case "down":
        // here we decrease the amount of
      // the matching term in the amount object
            // and re-run this whole calculation from
      // point START
      break;
    case "up":
        // here we increase the amount of
      // the matching term in the amount object
            // and re-run this whole calculation from
      // point START
    break;
  }
}

Let me briefly explain this example.

The computed expected result is that, the person needs to eat an X amount of apples, an Y amount of bananas and an Z amount of chicken breast per day to achieve the daily nutrition goal.

In my pseudo code I have written down the basic functionality of my program and the current problem I am facing is, that IF a specific food happens to be the perfect fit for an increase in amount in one loop and then happens to be the perfect fit for a decrease in amount in another loop - I end up in an endless loop.

Based on my minimalistic example I could hardcode that if apple amount got increased, it shouldn't get decreased in the next loop - but in my real world program I am working with a greater ingredient stack with a lot of more properties. So the complexity to cover that up raises extremely.

I am looking for a way to recognize the pattern, that leads to no result and tell the program to pick the 2nd best food for increase or decrease in order to not end in an endless loop.

That something like this gets avoided:

apple ++
apple ++
banana ++
apple ++
banana ++
meat --

apple --
apple --
banana --
apple --
banana --
meat ++

apple ++
apple ++
banana ++
apple ++
banana ++
meat --

apple --
apple --
banana --
apple --
banana --
meat ++
...

EDIT

The answer given below promoting some hashing and storing system leads to the same outcome which I experience with my custom blacklisting method.

My blacklisting method works as following:

Apple amount has been altered (decrement / increment) -> save that to blacklist array.

blacklist = [{product: "apple", altered: "down/up"},...]

Now every at every loop before choosing the food to increment or decrement the blacklist is scanned. If the perfect fit is in the array, then the second best fit will be chosen and so on.

There are some additional restrictions like: f.e. Apples may not be more than x % of the total amount. Or apples may not be less than x % of the total amount.

In combination of the restrictions + the blacklisted products my program ends in a state where it has no more different foods to increment or decrement and simply alters nothing and ends in an endless loop without progression

I don't even know if there is a way to fix that issue programmatically - or if I just have to say "hey, that problem isn't solvable".

All I can think of is a way to implement a functionality, that the program recognizes that it's "stuck" -> remembers the pattern that lead to the stucked state and tries over again with a different approach. But that might be an overkill in thoughts.

Answer 1

A solution is to remember the set of all states you visited before and avoid entering a state twice (mark it as a "taboo").

If the state change is small (i.e. if you only mutate a few values) then a useful trick is to use "zobrist hashing" so that an hash code for the next state can be computed in O(n) where n is the number of changes, not the number of variables.

Answer 2

Based on your description, I think you are dealing with a classic (Unbounded) Knapsack Problem, of which the aim is to find the best combination of items (food types) to achieve a given measurement (sum of nutritions). Your pseudo-code cannot solve this problem right.

There are various parameters to this problem, which was not mentioned in the question, for example:

• What is the weight of each nutrition?
• Can one nutrition exceeding a little to achieve better results?
• How do you decide which combo is better? (How to reduce a combo to a score?)
• When there are several combos considered equally good, how do you decide which one to go?

You will get less than ideal results if these questions are not answered. When things gone bad, you get stuck in the algorithm.

I wrote a snippet to demonstrate a bruteforce solution to the problem, using my personal thoughts as answers to questions above, with 2 nutritions and 2 food types.

While the problem space get complicated really quickly when adding nutritions/food type, you can always give it various tweaks to make sure it can run within reasonable timeframe on a modern browser.

See JSFiddle. (You may want to turn off line wrapping.)