LinuxQuestions.org (/questions/)
-   Programming (https://www.linuxquestions.org/questions/programming-9/)
-   -   recursion pitfalls (https://www.linuxquestions.org/questions/programming-9/recursion-pitfalls-770983/)

 icecubeflower 11-23-2009 10:06 AM

recursion pitfalls

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

 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.

 All times are GMT -5. The time now is 05:16 AM.