Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Implement better algorithm optimizing the drink combinations #31

Open
nhaef opened this issue Mar 24, 2021 · 3 comments
Open

Implement better algorithm optimizing the drink combinations #31

nhaef opened this issue Mar 24, 2021 · 3 comments
Labels
backend Addresses the backend performance

Comments

@nhaef
Copy link
Collaborator

nhaef commented Mar 24, 2021

The current implementation is brute-forcing every combination of drinks for up to 3 drinks.

@nhaef nhaef added backend Addresses the backend performance labels Mar 24, 2021
@Quaffel
Copy link
Owner

Quaffel commented Mar 24, 2021

Potential solution is proposed in #27.

@Jonasdoubleyou
Copy link
Collaborator

Jonasdoubleyou commented Mar 24, 2021

Maybe we can also do something like this instead:

const drinksByMostAlc = drinks.sort((a, b) => b.alcohol - a.alcohol); // most heave ones first

function* getDrinksByMostAlc(skip, targetAlc) {
  let sum = 0;
  for(const drink of drinksByMostAlc) {
    if(skip(drink)) continue; // insert e.g. a randomizer here to pick different drinks each time
    if(sum + drink.alcohol > targetAlc) continue; // gets the person more dizzy than wanted, skip
    yield drink;
    sum += drink.alcohol;
  }

  if(sum < targetAlc) 
    // not quite reached, do we get closer if we add the last one?
}

@nhaef
Copy link
Collaborator Author

nhaef commented Mar 25, 2021

Potential solution is proposed in #27.

I think this is only about searching for which drinks are available given a set of ingredients, not searching for the best combination while optimizing the alcohol. While #27 is definetly worth implementing, it's not a necessary performance improvement since looping trough 150-ish drinks is okay. However, looping trough 150 * 150 * 150 combinations as in the current implementation of the alcohol optimization IS a performance problem.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
backend Addresses the backend performance
Projects
None yet
Development

No branches or pull requests

3 participants