Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game. 
Notices 
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
Are you new to LinuxQuestions.org? Visit the following links:
Site Howto 
Site FAQ 
Sitemap 
Register Now
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQrelated cookies.

Introduction to Linux  A Hands on Guide
This guide was created as an overview of the Linux Operating System, geared toward new users as an exploration tour and getting started guide, with exercises at the end of each chapter.
For more advanced trainees it can be a desktop reference, and a collection of the base knowledge needed to proceed with system and network administration. This book contains many real life examples derived from the author's experience as a Linux system and network administrator, trainer and consultant. They hope these examples will help you to get a better understanding of the Linux system and that you feel encouraged to try out things on your own.
Click Here to receive this Complete Guide absolutely free. 


11232009, 10:06 AM

#1

Member
Registered: Mar 2008
Location: USA
Distribution: Slackware 13.1
Posts: 304
Rep:

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 1e9, 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<numTablesir;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<numTablesir;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.
Last edited by icecubeflower; 11232009 at 10:08 AM.



11242009, 02:57 AM

#2

Senior Member
Registered: Sep 2009
Location: Washington U.S.
Distribution: M$ Windows / Debian / Ubuntu / DSL / many others
Posts: 2,280

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



11242009, 10:06 AM

#3

Senior Member
Registered: Jan 2005
Location: Melbourne, Australia
Distribution: Debian Wheezy (Fluxbox WM)
Posts: 1,374

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(tableSetparty);
++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).



11242009, 10:48 AM

#4

Member
Registered: Mar 2008
Location: USA
Distribution: Slackware 13.1
Posts: 304
Original Poster
Rep:

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.



11242009, 05:40 PM

#5

Senior Member
Registered: Jan 2005
Location: Melbourne, Australia
Distribution: Debian Wheezy (Fluxbox WM)
Posts: 1,374

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[tableSetparty];
++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;
}
Last edited by neonsignal; 11242009 at 05:46 PM.



11242009, 07:33 PM

#6

Member
Registered: Mar 2008
Location: USA
Distribution: Slackware 13.1
Posts: 304
Original Poster
Rep:

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



Thread Tools 
Search this Thread 


Posting Rules

You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off



All times are GMT 5. The time now is 02:58 PM.

LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.

Latest Threads
LQ News

