Code Friday/Challenge 7: Pizza Order

Background

Everybody loves pizza[citation needed]. 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...

Challenge

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:
    • Meat
    • Vegetables
    • Cheese
  • There may be "specialty" pizzas:
    • Supreme (has all or almost all of the toppings)
    • Cheese
    • Meat Lover's
    • etc.
  • 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:


Toppings:

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.


Specialty Pizzas:

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.

Example Order

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:

Angelino
won't eat american cheese, ham, or salami
Corwin
won't eat meat or pineapple
Kaleb
will eat anything
Hasan
won't eat meat
Christian
won't eat green peppers
Elicia
won't eat pepperoni
Sundar
won't eat meat
Jess
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).

Example Data

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.)

Parting Thoughts

You can do this in any language you like, with whatever user interface you think is interesting. Be creative!

Have fun!