// File: dartgame.cpp
// Darts game program. Throw x darts with goal y points. How many combs???

#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <iomanip>
#define MaxValues 10

using namespace std;

// We'll use a quick & dirty class for 2 reasons:
//  1. In order to be able to initialize the DartsByValue array automatically.
//  2, We can't use an array alone because it is important that DartsByValue
//     be passed by value. See ThrowDarts() below
class DartRec {
public:
 DartRec();
 int DartsByValue[MaxValues];
};

// Implement the class' constructor
DartRec::DartRec()
{for (int i=0;i<MaxValues;i++)
  DartsByValue[i]=0;
}


int
   Value[MaxValues],		// Maximum Values Darts can Take
   DartsToThrow,		// Number of Darts to Throw
   Goal,			// Point Goal
   Combinations,		// Number of Successful Combinations Found
   Values;			// Number of Possible Values


void GetInfo(int [],int &,int &,int &);
void ThrowDarts(int,int,DartRec,int); // Note all arguments are pass by value

int main()
{DartRec HowManyOfEach;		// How Many of Each Value Thrown.
				// Constructor inits values to 0
 GetInfo(Value,Values,Goal,DartsToThrow);// Get Info so problem can be solved
 cout << "Solutions:\nValues:"; // Print Output Header
 cout.setf(ios::left);
 for (int i=0;i<Values;i++)
  cout << setw(2) << Value[i] << "  ";
 cout << endl;
 ThrowDarts(0,0,HowManyOfEach,0); // Throw the darts
 cout << Combinations << " Combinations Found\n";
 return(0);
}

// Input the necessary info. Arguments:
//	Points: array that holds possible dart values	[Output]
//	Count: # of possible values			[Output]
//	Goal: Total darts must add up to		[Output]
//	DartsToThrow: Do you need an explanation?	[Output]
// Pre: None
// Post:All arguments defined. There are Count (>=0) values in Value array
void GetInfo(int Points[],int &Count,int &Goal,int &DartsToThrow)
{char *DartPt=new char[10];
 Count=0;
 // Get possible dart values
 cout << "Enter the Point Values for Darts, 1 Integer to a line\n";
 cout << "When done, press return............\n";
 do {
  cin.getline( DartPt,'\n');
  if (strlen(DartPt)>0)
   Points[Count++]=atoi(DartPt);
 } while (strlen(DartPt)>0);
 // Get Goal
 cout << "Enter the # of Points that the Darts Should Total >";
 cin >> Goal;
 assert(Goal>0);
 // Get # to throw
 cout << "Enter the # of Darts To Throw >";
 cin >> DartsToThrow;
 assert(DartsToThrow>0);
}

// Display a successful combination, showing the number of darts of
// each possible value. Args:
// 	Comb: Holds array with # of darts of each value.
//		Comb.dartsByValue[i] holds # of darts thrown with Value[i]
// Pre: Comb holds a legitimate combination
// Post:Contents of Comb have been output
void ShowResult(const DartRec &Comb)
{cout << "       ";
 cout.setf(ios::left);
 for (int i=0;i<Values;i++)
  cout << setw(2) << Comb.DartsByValue[i] << "  ";
 cout << "\n";
}

// Try all possible value combinations for the darts.  Arguments:
//	Darts: # of darts thrown when function called
//	PointsSoFar: Points of Darts thrown at time of fn call
//	HowMany: # of darts of each previous value thrown
//	Index: Which element of the value array is being considered
// Base Cases:
//	1. PointsSoFar==Goal => Success...Print HowMany
//	2. PointsSoFar>Goal or run out of values => Fail...Stop
// Recursive Step:
//	Throw all possible darts of the present value
void ThrowDarts(int Darts,int PointsSoFar,DartRec HowMany,int Index)
{if (PointsSoFar==Goal) {
  ShowResult(HowMany);
  Combinations++;
  return;
 }
 if (PointsSoFar>Goal || Index==Values) return;
 for (int i=0;i<=(DartsToThrow-Darts);i++) {
  HowMany.DartsByValue[Index]=i;
  ThrowDarts(Darts+i,Value[Index]*i+PointsSoFar,HowMany,Index+1);
 }
}