Have a bit of a story problem. I'll try and explain it like a homework question:
A list of products in an ecommerce shopping cart must be validated for products that require other products to be in a cart. These products can require one matching product to exist from a variety of products. For example, a Medium Bike Frame might require a set of Small Wheels, Medium Wheels, or Large Wheels to be in the cart. Wheels do not require a Bike Frame to be in the cart. You can have multiple of the same Bike Frame in the cart, and they all need a matching set of wheels. If a Bike Frame does not have a matching set of wheels, the Bike Frame needs to be highlighted, and checkout disabled.
The tricky part is highlighted in this example: Say Small Bike Frames require a set of Small Bike Wheels to be in the cart. Small Bike Wheels are also compatible with Medium Bike Frames.
If your cart consists of 2 Medium Bike Frames, 1 Small Bike Frame, 2 Medium Bike Wheels, and 1 Small Bike Wheels, you have to be sure to connect the small wheels with the small frame. It's possible that you evaluate the 2 Medium Bike Frames first, pair them up with the Small Bike Wheels and 1 of the Medium Bike Wheels, and then the Small Bike Frame has no matching wheels in the cart, and gets highlighted and disables Checkout.
What is an efficient way I can programmatically verify this cart? A friend of mine came up with a recursive function that is not very efficient, and more or less brute forces all possible combinations before finalizing the validation. I'm looking for something a bit more performant, and I feel like there must be some clever algorithm to determine this faster.
I tried to come up with some stuff to do with only picking the most-desired item from the options in the cart, but I was easily able to break my solutions with variations on what is in the cart and what their requirements/quantities are, and what their order of evaluation is.
I cannot reprogram this old software I'm working with to do things like persistently remember a bundle of items added to the cart at a different time (for example, requiring you to pick a set of wheels when you add a bike frame to the cart, and mapping those two together indefinitely in the cart). It just needs to verify a cart on a page, with no info other than the Product ID, its quantity, and a list of Product IDs from which there must be a matching pair for each item in its quantity, and that list of Product IDs is optional/doesn't exist for all products.
I'll be writing this in Javascript, but really the solution could even be pseudocode. Just looking for an efficient strategy here to tackle this. Thanks for any ideas.