You are responsible for ordering a large pizza for you and your friends. Each of them has told you what he wants on a pizza and what he does not; of course they all understand that since there is only going to be one pizza, no one is likely to have all their requirements satisfied. Can you order a pizza that will satisfy at least one request from all your friends?

The pizza parlor you are calling offers the following pizza toppings; you can include or omit any of them in a pizza:

Your friends provide you with a line of text that describes their pizza preferences. For example, the line

+O-H+P;

reveals that someone will accept a pizza with onion, or without ham, or with pepperoni, and the line

-E-I-D+A+J;

indicates that someone else will accept a pizza that omits extra cheese, or Italian sausage, or diced garlic, or that includes anchovies or jalapenos.

Input Format

The input consists of a series of pizza constraints.

A pizza constraint is a list of 1 to 12 topping constraint lists each on a line by itself followed by a period on a line by itself.

A topping constraint list is a series of topping requests terminated by a single semicolon.

An topping request is a sign character (+/-) and then an uppercase letter from A to P.
 

Required Output Format

For each pizza constraint, provide a description of a pizza that satisfies it. A description is the string "Toppings: " in columns 1 through 10 and then a series of letters, in alphabetical order, listing the toppings on the pizza. So, a pizza with onion, anchovies, fresh broccoli and Canadian bacon would be described by:

Toppings: ACFO

If no combination toppings can be found which satisfies at least one request of every person, your program should print the string

"No pizza can satisfy these requests." on a line by itself starting in column 1.
 

Sample Input

+A+B+C+D-E-F-G-H;
-A-B+C+D-E-F+G+H;
-A+B-C+D-E+F-G+H;
.
+A+B+C+D;
+E+F+F+H;
+A+B-G;
+O+J-F;
+H+I+C;
+P;
+O+M+L;
+M-L+P;
.
+A+B+C+D;
+E+F+F+H;
+A+B-G;
+P-O;
+O+J-F;
+H+I+C;
+P;
+O;
+O+M+L;
-O-P;
+M-L+P;
.

Sample Output

Toppings:
Toppings: CELP
No pizza can satisfy these requests.

Judge's Input

+A-B;
+A+B;
.
+A+B+C+D-E-F-G-H;
-A-B+C+D-E-F+G+H;
-A+B-C+D-E+F-G+H;
.
+A+B+C+D;
+E+F+H;
+A+B-G;
+O+J-F;
+H+I+C;
+P;
+O+M+L;
+M-L+P;
.
+A+B+C+D;
+E+F+H;
+A+B-G;
+P-O;
+O+J-F;
+H+I+C;
+P;
+O+M+L;
+M-L+P;
+O;
-O-P;
.
+A;
+A;
.
+A+B+C+D+E+F+G+H+I+J+K+L+M+N+O+P;
-A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P;
.
+A;
-A;
.
+A;
+B;
+C;
+D;
+E;
+F;
+G;
+H;
+I;
+J;
+K;
+L;
+M;
+N;
+O;
+P;
.
+A-B;
+B-C;
+C-D;
+D-E;
+E-F;
+F-G;
+G-H;
+H-I;
+I-J;
+J-K;
+K-L;
+L-M;
+M-N;
+N-O;
+O-P;
+P-A;
.
+A;
+A+B;
+A+C+;
+A+C+D;
+A+C+E;
+A+C+F;
+A+C+G;
+A+C+H;
+A+C+I;
+A+C+J;
+A+C+K;
+A+C+L;
+A+C+M;
+A+C+N;
+A+C+O;
+A+C+P;
.
+P;
+B-C+G;
-B+C+D-H+K-L+M;
+D-E-F+H-O+P;
-J+K-L+M-N+O;
-C+D+I-K+M+N;
.

Judge's Output

Toppings: A
Toppings:
Toppings: CELP
No pizza can satisfy these requests.
Toppings: A
Toppings: A
No pizza can satisfy these requests.
Toppings: ABCDEFGHIJKLMNOP
Toppings:
Toppings: A
Toppings: P

Judge's Solution

#include <stdio.h>
#define MAX_PEOPLE 16
#define MAX_TOPPINGS 16
 
int main()
{ FILE *infp = fopen("pizza.dat","r");
  FILE *outfp= fopen("pizza.out","w");
 
  int nextChar = getc(infp);
  while (!feof(infp))
    { unsigned long int wants[MAX_PEOPLE];
      unsigned long int hates[MAX_PEOPLE];
      int personId = 0;
      unsigned long int pizzaId;
 
      /* Read pizza constraint */
 
      for (personId = 0; nextChar !='.'; ++personId)
        { wants[personId] = hates[personId] = 0;
          while (nextChar != ';')
            { if (nextChar == '+')
                { nextChar = getc(infp);
                  wants[personId] |= (1LU << (nextChar - 'A'));
                }
              else if (nextChar == '-')
                { nextChar = getc(infp);
                  hates[personId] |= (1LU << (nextChar - 'A'));
                }
              nextChar=getc(infp);
            }
          nextChar = getc(infp);  /* newline after semicolon */
          nextChar = getc(infp);
        }
      nextChar = getc(infp); /* newline after period */
 
      /* Enumerate pizzas */
      { int nPersons = personId;
        pizzaId = 0;
        do
          { for (personId = 0; personId < nPersons; ++personId)
              { if ((pizzaId & wants[personId]) || (~pizzaId & hates[personId]))
                  { /* this person will accept this pizza */ }
                else
                  break;
              }
            if (personId < nPersons)
              { /* pizza was rejected */ }
            else
              /* everyone can accept this pizza */
              break;
          ++pizzaId;
        } while (pizzaId != (1LU << MAX_TOPPINGS));
      }
 
      /* Print selected pizza, or report that none exists */
      if (pizzaId != (1LU << MAX_TOPPINGS))
        { int toppingId;
          fprintf(outfp, "Toppings: ");
          for (toppingId = 0; toppingId < MAX_TOPPINGS; ++toppingId)
            if ((pizzaId >> toppingId) & 1)
              fprintf(outfp, "%c", toppingId + 'A');
          fprintf(outfp, "\n");
        }
      else
        fprintf(outfp, "No pizza can satisfy these requests.\n");
      nextChar = getc(infp);
    }
  fclose(infp);
  fclose(outfp);
  return 0;
}

Comments

The pizza problem is just the conjunctive normal form satisfiability problem (CNF-SAT) hidden behind a thin crust.  It is well-known to be NP-complete, but when N is capped at 16, it becomes feasible.  There were many input sets for which there was more than one satisfying pizza; rather than require the "simplest" or "cheapest", we would accept any solution.  We had the following pizza checking program to help us.

#include <stdio.h>
#define MAX_PEOPLE 16
#define MAX_TOPPINGS 16

char toppings[] = "Toppings: ";
char nopizza[] = "No pizza can satisfy these requests.\n";
 
int main()
{
  FILE *infp = fopen("pizza.dat","r");
  FILE *outfp= fopen("pizza.out","r");
 
  int nextChar = getc(infp);
  while (!feof(infp) && !feof(outfp))
    {
      unsigned long int wants[MAX_PEOPLE];
      unsigned long int hates[MAX_PEOPLE];
      int personId;
      unsigned long int pizzaId;
 
      /* Read pizza constraint */
      for (personId = 0; nextChar != '.'; ++personId)
        {
          wants[personId] = hates[personId] = 0;
          while (nextChar != ';')
            {
              if (nextChar == '+')
                {
                  nextChar = getc(infp);
                  wants[personId] |= (1LU << (nextChar - 'A'));
                }
              else if (nextChar == '-')
                {
                  nextChar = getc(infp);
                  hates[personId] |= (1LU << (nextChar - 'A'));
                }
              nextChar = getc(infp);
            }
          nextChar = getc(infp); /* newline after semicolon */
          nextChar = getc(infp);
        }
      nextChar = getc(infp); /* newline after period */
 
      /* Check answer */
      {
        int nPersons = personId;
        char outputString[100];
        fgets(outputString, sizeof(outputString), outfp);
        if (! strcmp(outputString, nopizza))
          /* enumerate pizzas to verify */
          {
            pizzaId = 0;
            do {
              for (personId = 0; personId < nPersons; ++personId)
                {
                  if (( pizzaId & wants[personId]) ||
                      (~pizzaId & hates[personId]))
                    {/* this person will accept this pizza */}
                  else
                    break;
                }
            } while (personId < nPersons && ++pizzaId != (1LU << MAX_TOPPINGS));
 
            /* Print error if sat pizza exists */
            if (pizzaId != (1LU << MAX_TOPPINGS))
              {
                int toppingId;
                fprintf(stderr,
                        "Error: These toppings satisfy the contraints: ");
                for (toppingId = 0; toppingId < MAX_TOPPINGS; ++toppingId)
                  if ((pizzaId >> toppingId) & 1)
                    fprintf(stderr, "%c", toppingId + 'A');
                fprintf(stderr, "\n");
              }
          }
        else if (! strncmp(outputString, toppings, sizeof(toppings)-1))
          {
            char *tops = outputString + sizeof(toppings) - 1;
            unsigned long pizzaId = 0;
            while (*tops != '\n')
              {
                unsigned long newTopping = 1LU << (*tops - 'A');
                if (pizzaId >= newTopping)
                  {
                    fprintf(stderr,
                            "Error: toppings listed in wrong order: %s\n",
                            outputString);
                    break;
                  }
                pizzaId |= newTopping;
                tops++;
              }
            if (*tops == '\n')
              {
                for (personId = 0; personId < nPersons; ++personId)
                  {
                    if ((pizzaId & wants[personId]) || (~pizzaId & hates[personId]))
                      {/* this person will accept this pizza */}
                    else
                      break;
                  }
                if (personId < nPersons)
                  {
                    fprintf(stderr,
                            "Error: person %d would reject this pizza: %s\n",
                            personId, outputString);
                  }
              }
          }
        else
          fprintf(stderr, "Malformed data in output file: %s\n", outputString);
      }
      nextChar = getc(infp);
      ungetc(getc(outfp), outfp);
    }
  if (!feof(infp) || !feof(outfp))
    {
      if (!feof(infp))
        fprintf(stderr, "Error: output terminated prematurely.\n");
      else
        {
          char outputString[100];
          fprintf(stderr, "Error: extraneous output: ");
          fgets(outputString, sizeof(outputString), outfp);
          fprintf(stderr, "%s\n", outputString);
        }
    }
  fclose(infp);
  fclose(outfp);
  return 0;
}