Code:
#include <list>
#include <stdlib.h>
using namespace std;
struct FamilyMember
{
int Name; //Represents an enumerated name eg 1 can represent "Mother"
int Time;
};
struct TripRecord
{
int * Names;
int NNames;
};
int GetSelectionCount(int SetSize, int SelectionSize)
{
//5C2 = 5*4 /2 where order is irrelevant 5!/3!2!
int Count = 1;
int Count2 = 1;
for(int i = 0; i < SelectionSize; i++)
{
Count *= (SetSize - i); //5,4
Count2 *= (i + 1); //1,2
}
return Count/Count2;
}
void GotoNextSelectionState(int SetSize, int SelSize, int ElementsSelected[])
{
/*
That is
0,1
0,2
0,3
0,4
1,2
1,3
1,4
2,3
2,4
3,4
*/
//increase the last number until it reaches the max - 1 then icrease the previous number by 1
//and assign the latter to be 1 greater. Repeat upwards. that last state is 4,5,6 in 7C3
/*
//eg 7C3
0,1,2
...6
0,1,6
0,2,3
...5
0,2,6
0,3,4
...4
0,3,6
*/
for(int i = 1; i <= SelSize; i++)
{
if(ElementsSelected[SelSize - i] < (SetSize - i))
{
ElementsSelected[SelSize - i]++;
}
else
{
for(int c = SelSize - i + 1; c < SelSize; c++)
{
ElementsSelected[c] = ElementsSelected[c - 1] + 1;
}
}
}
}
class Paths
{
public:
int * (*s); //Array of (Indices of the Elements Selected)
int * sSelSize;
int * sSetSize;
int * p;
int * pmax;
int l;
Paths(int FamilySize, int PulleyLimit, int PulleyReturn = 1)
{
std::list<int> TripSelection; //A list of the maximun branch that can be tried
std::list<int>::iterator itTripSelection, itSelSize, itSetSize;
std::list<int> SelectionParameterSelectionSize; //<edit>This suppose to be not neccessary
std::list<int> SelectionParameterSetSize; //<edit>This suppose to be not neccessary
int right = FamilySize;
//int trip = 0;//forward_trips = 0;
//int return__trips = 0;
while(true)
{
if(right <= PulleyLimit)//if this is the last trip, considering that the pulley can have empty seats now
{
TripSelection.push_back(1); //There is only one possible path
SelectionParameterSelectionSize.push_back(right);
SelectionParameterSetSize.push_back(right);
}
else
{
TripSelection.push_back(GetSelectionCount(right, PulleyLimit));
SelectionParameterSelectionSize.push_back(PulleyLimit);
SelectionParameterSetSize.push_back(right);
}
right -= PulleyLimit; //<edit>optimise
//trip++;
if(right <= 0)
break;
TripSelection.push_back(GetSelectionCount(FamilySize - right, PulleyReturn));
SelectionParameterSelectionSize.push_back(PulleyReturn);
SelectionParameterSetSize.push_back(FamilySize - right);
right += PulleyReturn;
//trip++;
}
//load array of counters
l = TripSelection.size(); //l = trip;
//l = 2 * (FamilySize - PulleyLimit) - 1;//<edit> this has not be check with varying pulley size
pmax = new int[l];
p = new int[l];
s = new int *[l];
sSelSize= new int[l];
sSetSize= new int[l];
itTripSelection = TripSelection.begin();
itSelSize = SelectionParameterSelectionSize.begin();
itSetSize = SelectionParameterSetSize.begin();
for(int i = 0; itTripSelection != TripSelection.end(); itTripSelection++, i++, itSelSize++, itSetSize++)//int i = 0; i < l; i++)
{
pmax[i] = (*itTripSelection);//l - i;
p[i] = 0;
sSelSize[i] = (*itSelSize);
sSetSize[i] = (*itSetSize);
s[i] = new int[sSelSize[i]];
for(int c = 0; c < sSelSize[i]; c++)
{
s[i][c] = c; //0,1
}
}
//pmax[l - 1] = 1; //For the last trip the is just one possible path???????????
};
~Paths()
{
delete [] p;
delete [] pmax;
//<edit>
}
bool GotoNextPath() //return true if Path is all zero
{
int l2 = l - 1; //ignore the last array member because it represents the last trip <edit> there is a cleaner way to do this</edit>
for(int i = 0; i < l2; i++) //<edit> Make this include the last member ie use proper logic
{
if(p[i] == pmax[i])
{
p[i] = 0;
//<edit>optimize
for(int c = 0; c < sSelSize[i]; c++)
{
s[i][c] = c; //0,1
}
continue;
}
else
{
p[i]++;
//<edit>need optimization
//Change which members is selected
GotoNextSelectionState(sSetSize[i], sSelSize[i], s[i]);
break;
}
}
return is_zero(); //<edit> only needed if there is no soultion
};
bool is_zero() //<edit> only needed if there is no soultion
{
for(int i = 0; i < l; i++)
{
if(p[i] != 0)
return false;
}
return true;
}
};
inline int MakeTrip(
list<FamilyMember> & MembersBoarding,
list<FamilyMember> & MembersAcross,
int IndicesMembersBoarding[], /*Indices of the boarding members in the MembersRight list*/
int MembersBoardingCount, /*Number of members boarding*/
list<TripRecord> & RecordOfCurrentPath
)
{
int MaxTime = 0xFFFFFFFF;
//Calculate the time by the max time of all the Boarding members
std::list<FamilyMember>::iterator i;
std::list<FamilyMember>::iterator * iMembersTranfer = new std::list<FamilyMember>::iterator[MembersBoardingCount];
int iMTCount = 0;
//<edit> it wouldbe better as a table with name as the primary key
for(int c = 0; c < MembersBoardingCount; c++)
{
int CurrentIndex = IndicesMembersBoarding[c];
int c2 = 0;
for(i = MembersBoarding.begin(); i != MembersBoarding.end(); i++, c2++)
{
if(c2 == CurrentIndex)
{
MaxTime = max((*i).Time, MaxTime);
iMembersTranfer[iMTCount] = i;
iMTCount++;
break;
}
}
}
////////////
TripRecord trNewRecord;
trNewRecord.Names = new int [MembersBoardingCount];//<edit> this is not a good move unless I use a list
trNewRecord.NNames = 0;
//Do the Transfer
for(c = 0; c < iMTCount; c++)
{
trNewRecord.Names[trNewRecord.NNames] = (*(iMembersTranfer[c])).Name;
trNewRecord.NNames++;
MembersAcross.push_back(*(iMembersTranfer[c]));
MembersBoarding.erase(iMembersTranfer[c]);
}
// and record it
RecordOfCurrentPath.push_back(trNewRecord);
return MaxTime;//(max(MemberTime, MinTime) + min(MemberTime, MinTime));
}
int main()
{
/*
Send any two of the right members across
Store the time
Send any one of the left members basck across
Store the time
Repeat until done and calulate the total time
See if it is less than the time limit
Try the next possible path
(There are Select(2 from n)
*/
/*
Generic Information
*/
const int Family[] = {12, 8, 6, 3, 1};
const int FamilySize = sizeof(Family)/sizeof(int);
/*const*/int TimeLimit = 30;
const int PulleyLimit = 2; //<edit> heve not uaed this variable yet
const int PulleyReturn = 1; //one person is needed to pull back the pulley
char FamilyNames[][64] = { "Grandpa",
"Father",
"Mother",
"Daugther",
"Son" };
/*
Variables
*/
int TotalTime = 0;
list<FamilyMember> MembersRight;
list<FamilyMember> MembersLeft;
//int TimesOfMembersLeftToCross;
list<FamilyMember>::iterator itMember;
//int PathsTaken[FamilySize];
//int NBranches = FamilySize;
//Loop through all the possible paths. Eg of a path is Mother Sent --> Then Brother Sent --> Then Sister Sent --> ...
Paths pathCurrent(FamilySize, PulleyLimit); //Minus 1 because there is no trip back for the last person
list<TripRecord> RecordOfCurrentPath;
list<TripRecord>::iterator itRecordOfCurrentPath;
list<TripRecord> RecordOfPathWithLowestTime;
while(true)
{
//Initailize Members to Cross
MembersRight.clear(); //<edit> It may already be cleared
for(int i = 0; i < FamilySize; i++)
{
FamilyMember MemberToAdd;
MemberToAdd.Name = i;
MemberToAdd.Time = Family[i];
MembersRight.push_back(MemberToAdd);
}
MembersLeft.clear();
RecordOfCurrentPath.clear();
//For the current Path Calulate the Total time
TotalTime = 0;
i = 0;
while( true)
//for(int i = 0; i < pathCurrent.l;)
{
//<edit I think the max exception is taken care of in the timing function
TotalTime += MakeTrip(MembersRight, MembersLeft, pathCurrent.s[i]/*MembersRightIndices*/, min(int(MembersRight.size()), PulleyLimit), RecordOfCurrentPath);//(pathCurrent.p[i], TimesOfMembersLeftToCross);
i++;
if(i == pathCurrent.l)
break;
TotalTime += MakeTrip(MembersLeft, MembersRight, pathCurrent.s[i]/*MembersRightIndices*/, PulleyReturn, RecordOfCurrentPath);//(pathCurrent.p[i], TimesOfMembersLeftToCross);
i++;
if(i == pathCurrent.l)
break;
}
/*
if(TotalTime <= TimeLimit)
goto SOLUTION_FOUND;
if(pathCurrent.GotoNextPath()) //If all possible paths are tested
goto SOLUTION_NOTFOUND;
*/
//Only use this line when getting the shortest time
if(TotalTime <= TimeLimit)
{
TimeLimit = TotalTime;
RecordOfPathWithLowestTime.swap(RecordOfCurrentPath);
}
if(pathCurrent.GotoNextPath()) //If all possible paths are tested
{
break;
}
}
SOLUTION_FOUND:
//Diplay stuff
//Only use this line when getting the shortest time
RecordOfCurrentPath.swap(RecordOfPathWithLowestTime);
printf("Total time taken was %d\n", TotalTime);
for(int i = 0; i < pathCurrent.l; i++)
{
printf("%d\n", pathCurrent.p[i]);
}
for(itRecordOfCurrentPath = RecordOfCurrentPath.begin(); itRecordOfCurrentPath != RecordOfCurrentPath.end(); itRecordOfCurrentPath++)
{
printf("Move ");
for(int i = 0; i < (*itRecordOfCurrentPath).NNames; i++)
{
printf("%s (%d) ", FamilyNames[(*itRecordOfCurrentPath).Names[i]], Family[(*itRecordOfCurrentPath).Names[i]]);
}
printf("\n");
}
SOLUTION_NOTFOUND:
return 0;
}
Hardcore Techie
Originally Posted by Mr. Unstoppable
You solved it for everyone, that is not cool.
thanks for the example TJRAKS. The challenge for me still is to optimise. I will be attempting that now, but first I will try to strip it down and simplify it.
Posting Permissions
Reply With Quote
