Everybody loves pizza. In group settings, it can be challenging to come up with the right number and combination of pizzas so that everyone is able to enjoy a slice, while also trying to minimize the waste. If only we could write a program to help us...
Write a program that will determine the minimum pizza order that will allow all members of a group to eat something they will enjoy. The program works like this:
- Available toppings are divided into three broad categories:
- There may be "specialty" pizzas:
- Supreme (has all or almost all of the toppings)
- Meat Lover's
- You will have a pre-configured file representing the toppings and specialty pizzas available from your favorite pizza place, organized by category. An example file is shown below.
- You will either have the user input "least favorite toppings" for each person, or load that data from another text file (or files) -- this is your choice.
- Assume that every person will be happy with at least one topping.
- You may make your own assumption about the number of slices in a single pizza. 8 is a common number, but this is your choice.
- Assume that your options are either to get a specialty pizza or to get up to three toppings on a "custom" pizza. You should always prefer specialty pizzas when possible; then prefer 3 toppings over 2, and 2 over 1 (more toppings are "better").
Your program should take the information available about the toppings (and their categories) and each individual's preferences, and produce an order for the minimum number of pizzas (with a preference for specialty pizzas) that will satisfy the entire group.
Example Pizza Place
Let's say you are ordering from Wolf's Pizzaria, whose menu looks like this:
Cheeses: Mozzarella, Provolone, Feta, Ricotta, Cheddar, Swiss, American.
Meats: Pepperoni, Bacon, Beef, Salami, Italian Sausage, Canadian Bacon, Ham, Turkey, Roast Beef.
Gourmet: BBQ Chicken Breast, Garlic, Jalapenos, Black Olives, Green olives, Green Chilies, Artichoke Hearts, Sun dried Tomatoes, Banana Peppers, Pineapple and Mandarin Oranges.
Farm Fresh Vegetables: Spinach, Green and Red Bell Peppers, Mushrooms, Tomatoes, Red and White Onion.
Supreme: Smothered with cheese, Canadian bacon, beef, Italian sausage, pepperoni, fresh mushrooms, black olives, green & red peppers, white & red onion and tomatoes.
Meat Grande: Pepperoni, Italian sausage, ham, beef, bacon and Canadian bacon.
Four Cheese: Smothered with mozzarella, Swiss, cheddar and provolone.
Cheese: A simple classic, smothered with fresh mozzarella.
Garden: A vegetable pizza with red and white onions, green and red bell peppers, black olives, fresh mushrooms, tomatoes and mozzarella cheese on a whole wheat dough.
This menu was inspired by Pizza Chef in Jonesboro, AR; some descriptions are from their menu.
There are eight people in your group: Angelina, Corwin, Kaleb, Hasan, Christian, Elicia, Sundar, and Jess. If we assume that a single large pizza has 8 slices, then in theory one pizza would be plenty to feed everyone one slice. But not everyone will agree on toppings. Everyone is asked for the things they will not eat:
- won't eat american cheese, ham, or salami
- won't eat meat or pineapple
- will eat anything
- won't eat meat
- won't eat green peppers
- won't eat pepperoni
- won't eat meat
- won't eat cheese or any kind of olive
We would prefer to order Specialty pizzas since we can get the most toppings that way; for this problem, we will assume that more toppings are better. Because several of the group won't eat meat, the Specialty Pizzas options are:
- Four Cheese (no good for Angelino)
- Cheese (only one topping)
- Garden (no good for Christian and Jess)
Now notice that the Garden pizza has more toppings (prefer more toppings); Christian and Jess won't eat it, but they would both eat a Meat Grande.
So, we can maximize the group's ability to eat by ordering a Meat Grande and a Garden pizza. Everyone eats, and we got a lot of toppings (8 + 6 = 14 total).
Taking the ingredients and specialty pizzas from the example above, we could produce a "menu" file like this:
meat: pepperoni, bacon, beef, salami, italian_sausage, canadian_bacon, ham, turkey, roast_beef, bbq_chicken_breast vegetables: spinach, green_pepper, red_pepper, mushroom, tomato, red_onion, white_onion, garlic, jalapeno, black_olive, green_olive, green_chili, artichoke_heart, sun_dried_tomato, banana_pepper, pineapple, mandarin_orange cheese: mozzarella, provolone, feta, ricotta, cheddar, swiss, american supreme meat: canadian_bacon, beef, italian_sausage, pepperoni vegetables: mushroom, black_olive, green_pepper, red_pepper, white_onion, red_onion, tomato cheese: mozzarella meat_grande meat: pepperoni, italian_sausage, ham, beef, bacon, canadian_bacon vegetables: cheese: four_cheese meat: vegetables: cheese: mozzarella, swiss, cheddar, provolone cheese meat: vegetables: cheese: mozzarella garden meat: vegetables: red_onion, white_onion, green_pepper, red_pepper, black_olive, mushroom, tomato cheese: mozzarella
Notice that for ease of processing, everything can be lowercase, singular word forms, and items that are more than one word can be joined with underscores. This file format should be relatively easy to read.
Now, the information about user's dislikes can be entered (you choose how).
Based on that information, you want to try to create an order where every person can eat at least one kind of pizza, everyone gets at least one slice, and the total number of toppings on each pizza is maximized. (You may think of this as maximizing the average number of toppings per pizza.)
You can do this in any language you like, with whatever user interface you think is interesting. Be creative!