recursion pitfalls

icecubeflower · 11-23-2009, 10:06 AM

Anybody do topcoder? I'm a rookie. I competed once and solved the 250 point problem. Usually the 500 and 750 point problems are over my head. So now I'm doing practice problems and I'm studying other people's solutions.

Anyway worked on a practice problem today. It was SRM 249, DIV 1. Here is the problem statement:

Code:

Problem Statement
****
Your restaurant has numTables tables to seat customers. The tables are all arranged in a line. If a large party of customers comes in, a group of adjacent tables will be used. Which group of tables is entirely up to the customer. Since you cannot predict this, assume all possible choices occur with equal probability. What you can predict is the size of each group of customers that arrives. Element i of probs gives the probability, in percent, that an entering party will need i+1 tables. Assuming nobody leaves, return the expected number of tables you will use before a party must be turned away. This only occurs if there is no place to seat them.
Definition
****
Class:
TableSeating
Method:
getExpected
Parameters:
int, vector <int>
Returns:
double
Method signature:
double getExpected(int numTables, vector <int> probs)
(be sure your method is public)
****

Notes
-
Return values must be accurate to 1e-9, relative or absolute.
Constraints
-
numTables will be between 1 and 12 inclusive.
-
probs will contain between 1 and 12 elements inclusive.
-
Each element of probs will be between 0 and 100 inclusive.
-
The elements of probs will sum to 100.
Examples
0)

****
4
{100}
Returns: 4.0
Since every party needs only 1 table, you will always fill the restaurant before turning someone away.
1)

****
4
{0,100}
Returns: 3.3333333333333335
Now every party wants 2 tables. One third of the time, the first party will choose the middle 2 tables blocking anyone else from being seated. Two thirds of the time, the first party will choose 2 tables on the end allowing the restaurant to become full. Thus, the returned value is (1/3)*2 + (2/3)*4 = 10/3.
2)

****
5
{0,0,0,0,0,50,50}
Returns: 0.0
You have 5 tables, but every party needs 6 or 7 tables.
3)

****
12
{9,9,9,9,9,9,9,9,9,9,10}
Returns: 7.871087929710551

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

Here is my solution, it uses recursion:

Code:

#include <vector>
#include <iostream>

class TableSeating
{
public:
  double getExpected(int numTables, std::vector<int> probs);
private:
  void Cruncher(int numTables, std::vector<int> probs, double hotpotato_odds);  //recursive thingy
  int *restaurant;	//tables in the restaurant
  double *odds;		//collects odds (0.x/1) for each number of tables filled (0.0,0.0,0.25,0.75) or something
  int level;  //delete this
  int numfilled;
};

int main()
{
  std::vector<int> probs;
  int numTables;
  TableSeating funstuff;

  probs.push_back(9);
  probs.push_back(9);
  probs.push_back(9);
  probs.push_back(9);
  probs.push_back(9);
  probs.push_back(9);
  probs.push_back(9);
  probs.push_back(9);
  probs.push_back(9);
  probs.push_back(9);
  probs.push_back(10);
  numTables=12;

  std::cerr<<"Expected number of filled tables="<<funstuff.getExpected(numTables,probs)<<"\n";

  return 0;
}

double TableSeating::getExpected(int numTables, std::vector<int> probs)
{
  int ix;
  double hotpotato_odds;  //collects current odds, pass recursively and restore
  double returner=0.0;

  restaurant=new int[numTables];
  odds=new double[numTables+1];
  for(ix=0;ix<numTables;ix++)
    restaurant[ix]=0;
  for(ix=0;ix<numTables+1;ix++)
    odds[ix]=0.0;
  hotpotato_odds=0.0;

  level=0;
  numfilled=0;
  Cruncher(numTables,probs,hotpotato_odds);
  std::cerr<<"odds: ";
  for(ix=0;ix<numTables+1;ix++)
  {
    std::cerr<<odds[ix]<<" ";
    returner+=double(ix)*odds[ix];
  }
  std::cerr<<"\n";

  delete[] restaurant;
  delete[] odds;

  return returner;
}

void TableSeating::Cruncher(int numTables, std::vector<int> probs, double hotpotato_odds)
{
  int ir,ix,ij,iz;
  bool fit;
  int numfits;
  double oldodds;

  //go through each element of probs, try all seating arrangements
  for(ir=0;ir<probs.size();ir++)
  {
   if(probs[ir]!=0)
   {
    numfits=0;  //number of possible fits for this element of probs at this point in the recursion
    for(ix=0;ix<numTables-ir;ix++) //check for each possible seating arrangement for this size group
    {
      fit=true;  //assume we can fit at least one group
      for(ij=0;ij<ir+1;ij++)  //check this spot
      {
        if(restaurant[ix+ij]!=0)
          fit=false;  //no we can't!
      }
      if(fit)  //or if we can
      {
        numfits+=1;  //increase number of possible fits
      }
    }
    oldodds=hotpotato_odds;
    //new odds = current odds * probably of getting this size group * 1.0/number of ways we can fit them
    if(hotpotato_odds!=0&&numfits!=0)
      hotpotato_odds=hotpotato_odds*(double(probs[ir])/100.0)*(1.0/double(numfits));
    else if(hotpotato_odds!=0)
      hotpotato_odds=hotpotato_odds*(double(probs[ir])/100.0);
    else if(numfits!=0)
      hotpotato_odds=(double(probs[ir])/100.0)*(1.0/double(numfits));
    else
      hotpotato_odds=(double(probs[ir])/100.0);

    if(numfits>0)  //do it all again now that we have new hotpotato_odds, unless there were no fits
    {
      for(ix=0;ix<numTables-ir;ix++)  //same as above
      {
        fit=true;
        for(ij=0;ij<ir+1;ij++)  //same
        {
          if(restaurant[ix+ij]!=0)
            fit=false;
        }
        if(fit)
        {
          //now actually fill those seats and call this function recursively
          for(ij=0;ij<numTables;ij++)
            std::cerr<<restaurant[ij]<<" ";
          std::cerr<<"\n";
          for(ij=0;ij<ir+1;ij++)
          {
            restaurant[ix+ij]=1;
            numfilled+=1;
          }
          level+=1;
          Cruncher(numTables,probs,hotpotato_odds);
          for(ij=0;ij<ir+1;ij++)  //undo the damage
          {
            restaurant[ix+ij]=0;
            numfilled-=1;
          }
          for(ij=0;ij<numTables;ij++)
            std::cerr<<restaurant[ij]<<" ";
          std::cerr<<"\n";
        }
      }
    }
    else
    {
      //there were no fits, group turned away, add in the odds
      odds[numfilled]+=hotpotato_odds;
      std::cerr<<"odds: ";
      for(iz=0;iz<numTables+1;iz++)
         std::cerr<<odds[iz]<<" ";
      std::cerr<<"\n";
    }
    hotpotato_odds=oldodds;  //reset odds for next ir (element of probs)
   }
  }
  level-=1;
}

I think mine works. I stripped out the std::cerr stuff and of course I removed main and tested the getExpected class. I got correct answers for all their tests except for the last one. On the last one there are twelve tables and 9% chance of there being each of 0 to 9 sized arrivals ad a 10% chance of the arrival size being 11. Of course my program timed out because it needs to finish in under 2 seconds. My recursion method exausts all possibilities and records the odds of that possibility happening. And it could take billions of years to solve this example for all I know. I suppose I could crunch some numbers and figure out exactly how long it would take my program to solve that example but I don't think it matter.

Before I study the better solutions, can anybody tell me how I should have done it instead? I'm about 99% sure trying every possibility and using recursion was the wrong way to go. There must be a simple, mathematical way to get the same answers. But my way was sure fun.

smeezekitty · 11-24-2009, 02:57 AM

WTF are you talking about? i am heading off to google it!

neonsignal · 11-24-2009, 10:06 AM

The recursion is fine, but as you say, takes too long to complete. However, it can be sped up.

The main thing to notice is that even with 12 tables, there are only 4096 arrangements (2^12) - either a table is occupied or it isn't. For any given arrangement (ie, some tables already occupied), it is possible to calculate how many more parties can arrive (on average), ie, there is only one answer for each arrangement.

So as the program recurses through the possibilities (starting with no tables occupied), it will often reach arrangements that have already been seen. If it keeps a cache of these calculations, this can be used to 'snip' later (matching) branches of the recursion without recursing all the way to the bottom.

A possible solution would then be something like this:

Code:

// includes
   #include <vector>
   #include <limits>
   #include <cmath>
   #include <iostream>
   typedef std::vector<int> Probs;
// table seating class
   class TableSeating
   {
   public:
      double getExpected(int numTables, Probs probs);
   private:
      double calculate(unsigned int tableSet);
   private:
      Probs probs;
      int n;
      double *pCache;
   };
// set up parameters and calculate solution
   double TableSeating::getExpected(int numTables, Probs probs0)
   {
   // initialize constants
      n = numTables; probs = probs0;
   // initialize cache
      pCache = new double[1<<n];
      for (size_t i = 0; i < 1<<n; ++i)
        pCache[i] = std::numeric_limits<double>::quiet_NaN();
   // calculate average, starting with empty set of tables
      double average = calculate(0);
   // remove cache
      delete[] pCache;
   // return result
      return average;
   }
// recursively calculate average number of patrons
   double TableSeating::calculate(unsigned int tableSet)
   {
   // if already calculated, then return
      if (!std::isnan(pCache[tableSet]))
        return pCache[tableSet];
   // for each of the party sizes
      double average = 0;
      for (size_t iProb = 0; iProb < probs.size(); ++iProb)
      {
      // for each offset position
        double sum = 0.;
        unsigned int nSum = 0;
        for (size_t iOff = 0; iOff+iProb < n; ++iOff)
        {
        // allocate tables to the party
          unsigned int party = (1<<iProb+1)-1<<iOff;
        // if party can be placed here
          if ((tableSet & party) == 0)
          {
          // add to the sum
            sum += calculate(tableSet|party);
            ++nSum;
          }
        }
      // accumulate average
        average += (nSum?(sum/nSum+(iProb+1)):0) * probs[iProb]/100;
      }
   // cache result and return
      return pCache[tableSet] = average;
   }
// entry point
   int main()
   {
   // calculate average number of patrons for each case
      TableSeating seating;
      int table0[] = {100};
      std::cout << seating.getExpected(4, Probs(table0, table0+1)) << std::endl;
      int table1[] = {0,100};
      std::cout << seating.getExpected(4, Probs(table1, table1+2)) << std::endl;
      int table2[] = {0,0,0,0,0,50,50};
      std::cout << seating.getExpected(5, Probs(table2, table2+7)) << std::endl;
      int table3[] = {9,9,9,9,9,9,9,9,9,9,10};
      std::cout << seating.getExpected(12, Probs(table3, table3+11)) << std::endl;
      return 0;
   }

(This example uses a set of bits rather than a vector for the arrangements to make it a little easier, and has left out some optimizations (such as checking if all tables are already taken, or if the probability of a certain party size is 0).

icecubeflower · 11-24-2009, 10:48 AM

Thx, neosignal. I'm studying your post.

Also I'm studying another guy's solution. He does it in 8 lines. It's C++ but I can't read the syntax, I'm trying to get help in another thread.

He didn't use recursion but I think he might have done something similar with nested for loops.

neonsignal · 11-24-2009, 05:40 PM

True, you can get rid of the recursion by starting at the end of the cache and working backwards (because the sets at the end of the cache will always recurse to sets past that point). The code above then becomes something like this (the outer loop replacing the recursion):

Code:

// includes
   #include <vector>
   #include <iostream>
   typedef std::vector<int> Probs;
// table seating class
   class TableSeating
   {
   public:
      double getExpected(int numTables, Probs probs);
   };
// calculate average number of patrons
   double TableSeating::getExpected(int numTables, Probs probs)
   {
   // initialize cache
      double *pCache = new double[1<<numTables];
   // for each entry in the cache (from end to finish)
      unsigned int tableSet = 1<<numTables;
      do
      {
      // for each of the party sizes
         pCache[--tableSet] = 0;
         for (size_t iProb = 0; iProb < probs.size(); ++iProb)
         {
         // for each offset position
            double sum = 0.;
            unsigned int nSum = 0;
            for (unsigned int party = (1<<iProb+1)-1; party < 1<<numTables; party <<= 1)
            // if party can be placed here
               if ((tableSet & party) == 0)
               {
               // add to the sum
                  sum += pCache[tableSet|party];
                  ++nSum;
               }
         // accumulate average
            pCache[tableSet] += (nSum?(sum/nSum+(iProb+1)):0) * probs[iProb]/100;
         }
      }
      while (tableSet);
   // calculate average, starting with empty set of tables
      double average = pCache[0];
   // remove cache
      delete[] pCache;
   // return result
      return average;
   }
// entry point
   int main()
   {
   // calculate average number of patrons for each case
      TableSeating seating;
      int table0[] = {100};
      std::cout << seating.getExpected(4, Probs(table0, table0+1)) << std::endl;
      int table1[] = {0,100};
      std::cout << seating.getExpected(4, Probs(table1, table1+2)) << std::endl;
      int table2[] = {0,0,0,0,0,50,50};
      std::cout << seating.getExpected(5, Probs(table2, table2+7)) << std::endl;
      int table3[] = {9,9,9,9,9,9,9,9,9,9,10};
      std::cout << seating.getExpected(12, Probs(table3, table3+11)) << std::endl;
      return 0;
   }

icecubeflower · 11-24-2009, 07:33 PM

Wow you really put a lot effort into illustrating this, thx.