# Thread: A Simple (?) Problem

1. ## A Simple (?) Problem

Okie, let's see. I've got a little project I'm trying to work on, and I'm pretty sure it can be done using C++. I only know a litlte bit about C++, though, so I don't know enough to really work the problem out. I understand the basics (or can find information on the net about them), but I don't know too many concepts. I don't think this problem requires any difficult concepts, but I don't know. Let me try to explain a simplified version of the problem (using simplified numbers).

It comes in a number of parts:

******
Part One: Definitons. I know how to define things in C++, but I am including this part here so you know what I am talking about later.

a=1, b=2, c=3, d=4, e=5, f=6

---------

Part Two: Arithmetic.

a*{d,e,f} + b{d,e,f} + c*{d,e,f} = z

(now, by { }, I mean to try all combinations of these variables: a*d + b*d + c*d is one combination, and a*d + b*d + c*e is another. There are 27 combinations, I believe)

if z=20, then continue to next part
if not, then go back up and continue trying combinations until you reach a combination where z=20 (and there is more than one combination where z=20)

-----------
Part Three: Tests. For each combination found where z=20, I want a number of tests to be done.

What was multiplied by a (either d, e, or f) cannot equal what was multiplied by c.

What was multiplied by b (either d, e, or f) cannot equal what was multiplied by c.

if one test is failed, continue with combinations.
if all tests are passed, print the d/e/f values of a, b, and c (in other words, which variables a, b, and c were multiplied by)
******

I don't need an exact working program, but if anyone could help me out with little bits and pieces, or certain topics I should study to figure out how to complete this.

Also: Is it more logical that part two should accumulate all values of z=20 and then test those in part three, or would it be better that when a z=20 value is found, part three is carried out (and if that combination does not pass all the tests, return to part two)? I would prefer the latter.

I'm sorry if this all seems confusing. I don't know any other way to word it. Like I said, *any* help would be appreciated regardless of how detailed it is. Thanks in advance!

Selwyn McPherson.
If you have any questions, you can email me at slcool@neo.rr.com

2. Heh, that's not such a simple problem. How much generality are you aiming for? Do you want it to just be able to solve that specific problem? Is input going to be parsed from a string, or directly incorporated into the code itself? Have you ever written a program to evulate a simple expression, IE, 4+3*3, such would be a good start for this project.

3. No, there won't be any input. It will just run from the code. I can write programs for simple expressions, yes. This isn't the *actual* problem, no - the actual problem has many more variables and tests, but if I know how to do just a simple one, I can expand it to fit the real problem. Thanks a lot )

Selwyn McPherson
slcool@neo.rr.com

4. a*{d,e,f} + b{d,e,f} + c*{d,e,f} = z
Should be z = a*{d,e,f} + b{d,e,f} + c*{d,e,f};
although I've never seen a C++ expression like a * {d, e, f}

5. just an idea how to enumerate all possible combinations
Code:
```// digit[0] is a, digit[1] is b ... digit[5] is f
int digits[6] = {1,2,3,4,5,6};
int z = 0;

for (int d = 3; d < 6; d++)
for (int e = 3; e < 6; e++)
for (int f = 3; f < 6; f++)
{
z = digit[0]*digit[d]+
digit[1]*digit[e]+
digit[2]*digit[f];
if (z == 20)
{
// do whatever you like
} // end if(z==20)
} // end for(f)```

6. Damyan, thanks for the idea. I will test it out and see if I can get it to work. While I was thinking, I had another way of thinking of it. There's really no need to define a, b, c, etc. in part one. In part two, it would be easier to just use

-----
1*{4,5,6} + 2*{4,5,6} + 3*{4,5,6} etc.
-----

For each combinations, though, I need to set the value of { } as a variable. That would make it easier to test in part three.

-----
1*{4,5,6} (now assign either the 4, 5, or 6 as x) + 2*{4,5,6} (now assign either the 4, 5, or 6 as y) + 3*{4,5,6} (now assign either the 4, 5, or 6 as z)
-----

To test:

x cannot equal z
y cannot equal z
and so forth.

I don't know if that's possible, though.

I also had another concern. When z does not equal 20, and the process of finding combinations continues, will it restart? Will it pick up from where it left off? Restarting wouldn't be very productive; the program would just keep trying the same combination over and over again.

Again, I'm sorry if my wording or ideas seem confusing. :-/ I appreciate everyone's brain cells :-)

Selwyn McPherson.
slcool@neo.rr.com

7. so you don't need all possible combination over the {def} elements instead, you need all the permutations over them

so here is an example of enumerating all the permuatations using the STL

Code:
```#include <vector>
#include <algorithm>
using namespace std ;

void main()
{
// declarations
vector<int> intV;
vector<int>::iterator it;
// initialization
for(int i = 4;i< 7; i++)
intV.push_back(i);
int j, z = 0;
// enum permutations
while ( next_permutation(intV.begin(), intV.end()) )
{
z = 0; //calc z
for (j = 1, it=intV.begin(); it !=  intV.end(); it++, j++)
z+=j*(*it);
if (z == 20)
{
// do the job
} // end (if match)
} // end while(have more permutations)
it = it;
} // end main```

8. I think I eventually got it to work. The actual problem is to figure out how to paint a map of the USA with four colors, where no two colors touch. It is possible, and that is just the easy part. The second part is that each of the four paints costs a different amount (\$1, \$2, \$3, and \$4), and I've got to try to figure out the lowest possible combination. The lowest price possible is \$5926 (I've been told - I hope this is right). I used a bunch (48) FOR loops for the combinations, and 100 or so if statements for the tests (to make sure that states of the same color don't touch). The problem is, there are 4^48 possible combinations, so I don't know how long this will take. It doesn't have to go through all of those combinations, mind you, but it still might take a long time. The code may seem a little messy or silly, but I don't know any better :-)

<code>
#include <iostream.h>

int main()
{
int AL = 52;
int AZ = 114;
int AK = 53;
int CA = 159;
int CO = 104;
int CT = 5;
int DL = 2;
int FL = 59;
int GA = 59;
int ID = 84;
int IL = 56;
int IN = 36;
int IO = 56;
int KA = 82;
int KT = 40;
int LO = 49;
int MA = 33;
int MD = 11;
int MC = 8;
int MI = 58;
int MN = 84;
int MP = 48;
int MS = 70;
int MT = 147;
int NB = 77;
int NV = 111;
int NH = 9;
int NJ = 8;
int NM = 122;
int NY = 50;
int NC = 53;
int ND = 71;
int OH = 41;
int OK = 70;
int OR = 97;
int PA = 45;
int RI = 1;
int SC = 31;
int SD = 77;
int TN = 42;
int TX = 267;
int UT = 85;
int VA = 41;
int VT = 10;
int WA = 68;
int WV = 24;
int WI = 56;
int WY = 98;
int aa = 0;
int ab = 0;
int ac = 0;
int ae = 0;
int af = 0;
int ag = 0;
int ah = 0;
int ai = 0;
int aj = 0;
int ak = 0;
int al = 0;
int am = 0;
int an = 0;
int ao = 0;
int ap = 0;
int aq = 0;
int ar = 0;
int as = 0;
int at = 0;
int au = 0;
int av = 0;
int aw = 0;
int ax = 0;
int ay = 0;
int az = 0;
int ba = 0;
int bb = 0;
int bc = 0;
int bd = 0;
int be = 0;
int bf = 0;
int bg = 0;
int bh = 0;
int bi = 0;
int bj = 0;
int bk = 0;
int bl = 0;
int bm = 0;
int bn = 0;
int bo = 0;
int bp = 0;
int bq = 0;
int br = 0;
int bs = 0;
int bt = 0;
int bu = 0;
int bv = 0;
int z = 0;

for (int aa = 1; aa < 5; aa++)
for (int ab = 1; ab < 5; ab++)
for (int ac = 1; ac < 5; ac++)
for (int ae = 1; ae < 5; ae++)
for (int af = 1; af < 5; af++)
for (int ag = 1; ag < 5; ag++)
for (int ah = 1; ah < 5; ah++)
for (int ai = 1; ai < 5; ai++)
for (int aj = 1; aj < 5; aj++)
for (int ak = 1; ak < 5; ak++)
for (int al = 1; al < 5; al++)
for (int am = 1; am < 5; am++)
for (int an = 1; an < 5; an++)
for (int ao = 1; ao < 5; ao++)
for (int ap = 1; ap < 5; ap++)
for (int aq = 1; aq < 5; aq++)
for (int ar = 1; ar < 5; ar++)
for (int as = 1; as < 5; as++)
for (int at = 1; at < 5; at++)
for (int au = 1; au < 5; au++)
for (int av = 1; av < 5; av++)
for (int aw = 1; aw < 5; aw++)
for (int ax = 1; ax < 5; ax++)
for (int ay = 1; ay < 5; ay++)
for (int az = 1; az < 5; az++)
for (int ba = 1; ba < 5; ba++)
for (int bb = 1; bb < 5; bb++)
for (int bc = 1; bc < 5; bc++)
for (int bd = 1; bd < 5; bd++)
for (int be = 1; be < 5; be++)
for (int bf = 1; bf < 5; bf++)
for (int bg = 1; bg < 5; bg++)
for (int bh = 1; bh < 5; bh++)
for (int bi = 1; bi < 5; bi++)
for (int bj = 1; bj < 5; bj++)
for (int bk = 1; bk < 5; bk++)
for (int bl = 1; bl < 5; bl++)
for (int bm = 1; bm < 5; bm++)
for (int bn = 1; bn < 5; bn++)
for (int bo = 1; bo < 5; bo++)
for (int bp = 1; bp < 5; bp++)
for (int bq = 1; bq < 5; bq++)
for (int br = 1; br < 5; br++)
for (int bs = 1; bs < 5; bs++)
for (int bt = 1; bt < 5; bt++)
for (int bu = 1; bu < 5; bu++)
for (int bv = 1; bv < 5; bv++)
{
z = AL*aa + AZ*ab + AK*ac + CA*ad + CO*ae + CT*af + DL*ag + FL*ah +
GA*ai + ID*aj + IL*ak + IN*al + IO*am + KA*an + KT*ao + LO*ap +
MA*aq + MD*ar + MC*as + MI*at + MN*au + MP*av + MS*aw + MT*ax +
NB*ay + NV*az + NH*ba + NJ*bb + NM*bc + NY*bd + NC*be + ND*bf +
OH*bg + OK*bh + OR*bi + PA*bj + RI*bk + SC*bl + SD*bm + TN*bn +
TX*bo + UT*bp + VA*bq + VT*br + WA*bs + WV*bt + WI*bu + WY*bv;
if (z == 5926)
{
if (bs != aj) {
if (bs != bi) {
if (bi != bd) {
if (bi != aj) {
if (az != ab) {
if (az != bp) {
if (az != aj) {
if (aj != ax) {
if (aj != bv) {
if (aj != bp) {
if (bp != ab) {
if (bp != ae) {
if (ab != bc) {
if (ax != bv) {
if (ax != bf) {
if (ax != bm) {
if (bv != ae) {
if (bv != bm) {
if (bv != ay) {
if (ae != bc) {
if (ae != ay) {
if (ae != an) {
if (ae != bh) {
if (bc != bo) {
if (bc != bh) {
if (bf != bm) {
if (bf != au) {
if (bm != au) {
if (bm != am) {
if (bm != ay) {
if (ay != am) {
if (ay != an) {
if (ay != aw) {
if (an != aw) {
if (an != bh) {
if (bh != bo) {
if (bh != ac) {
if (au != bu) {
if (au != am) {
if (am != bu) {
if (am != ak) {
if (am != aw) {
if (aw != ac) {
if (aw != ak) {
if (aw != ao) {
if (aw != bn) {
if (ac != bn) {
if (ac != av) {
if (ac != ap) {
if (bo != ap) {
if (ap != av) {
if (bu != ak) {
if (bu != at) {
if (ak != al) {
if (ak != ao) {
if (al != bg) {
if (al != ao) {
if (al != at) {
if (ao != bg) {
if (ao != bt) {
if (ao != bq) {
if (ao != bn) {
if (bn != bq) {
if (bn != be) {
if (bn != ai) {
if (bn != aa) {
if (bn != av) {
if (av != aa) {
if (aa != ai) {
if (aa != ah) {
if (ah != ai) {
if (ai != bl) {
if (ai != be) {
if (bl != be) {
if (be != bq) {
if (bq != bt) {
if (bq != ar) {
if (bt != bg) {
if (bt != bj) {
if (bt != ar) {
if (bg != bj) {
if (bg != at) {
if (bj != ar) {
if (bj != bd) {
if (bj != bb) {
if (bj != ag) {
if (ar != ag) {
if (bb != bd) {
if (bd != br) {
if (bd != as) {
if (br != af) {
if (br != ba) {
if (br != as) {
if (ba != as) {
if (ba != aq) {
if (as != bk) {
if (af != bk) {
if (af != as) {
cout << aa << endl;
cout << ab << endl;
cout << ac << endl;
cout << ae << endl;
cout << af << endl;
cout << ag << endl;
cout << ah << endl;
cout << ai << endl;
cout << aj << endl;
cout << ak << endl;
cout << al << endl;
cout << am << endl;
cout << an << endl;
cout << ao << endl;
cout << ap << endl;
cout << aq << endl;
cout << ar << endl;
cout << as << endl;
cout << at << endl;
cout << au << endl;
cout << av << endl;
cout << aw << endl;
cout << ax << endl;
cout << ay << endl;
cout << az << endl;
cout << ba << endl;
cout << bb << endl;
cout << bc << endl;
cout << bd << endl;
cout << be << endl;
cout << bf << endl;
cout << bg << endl;
cout << bh << endl;
cout << bi << endl;
cout << bj << endl;
cout << bk << endl;
cout << bl << endl;
cout << bm << endl;
cout << bn << endl;
cout << bo << endl;
cout << bp << endl;
cout << bq << endl;
cout << br << endl;
cout << bs << endl;
cout << bt << endl;
cout << bu << endl;
cout << bv << endl;
cout <<" " << endl;
}
else {
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
return 0;
}
<code>

If anything looks wrong, it'd be nice to know before I wait an eternity for the program to finish only to find no results :-) Thanks a lot for everyone's help so far!

Selwyn McPherson.
slcool@neo.rr.com

9. Yikes. That's what you get for not previewing. Sorry about that. Let me try again.

Code:
```#include <iostream.h>

int main()
{
int AL = 52;
int AZ = 114;
int AK = 53;
int CA = 159;
int CO = 104;
int CT = 5;
int DL = 2;
int FL = 59;
int GA = 59;
int ID = 84;
int IL = 56;
int IN = 36;
int IO = 56;
int KA = 82;
int KT = 40;
int LO = 49;
int MA = 33;
int MD = 11;
int MC = 8;
int MI = 58;
int MN = 84;
int MP = 48;
int MS = 70;
int MT = 147;
int NB = 77;
int NV = 111;
int NH = 9;
int NJ = 8;
int NM = 122;
int NY = 50;
int NC = 53;
int ND = 71;
int OH = 41;
int OK = 70;
int OR = 97;
int PA = 45;
int RI = 1;
int SC = 31;
int SD = 77;
int TN = 42;
int TX = 267;
int UT = 85;
int VA = 41;
int VT = 10;
int WA = 68;
int WV = 24;
int WI = 56;
int WY = 98;
int aa = 0;
int ab = 0;
int ac = 0;
int ae = 0;
int af = 0;
int ag = 0;
int ah = 0;
int ai = 0;
int aj = 0;
int ak = 0;
int al = 0;
int am = 0;
int an = 0;
int ao = 0;
int ap = 0;
int aq = 0;
int ar = 0;
int as = 0;
int at = 0;
int au = 0;
int av = 0;
int aw = 0;
int ax = 0;
int ay = 0;
int az = 0;
int ba = 0;
int bb = 0;
int bc = 0;
int bd = 0;
int be = 0;
int bf = 0;
int bg = 0;
int bh = 0;
int bi = 0;
int bj = 0;
int bk = 0;
int bl = 0;
int bm = 0;
int bn = 0;
int bo = 0;
int bp = 0;
int bq = 0;
int br = 0;
int bs = 0;
int bt = 0;
int bu = 0;
int bv = 0;
int z = 0;

for (int aa = 1; aa < 5; aa++)
for (int ab = 1; ab < 5; ab++)
for (int ac = 1; ac < 5; ac++)
for (int ae = 1; ae < 5; ae++)
for (int af = 1; af < 5; af++)
for (int ag = 1; ag < 5; ag++)
for (int ah = 1; ah < 5; ah++)
for (int ai = 1; ai < 5; ai++)
for (int aj = 1; aj < 5; aj++)
for (int ak = 1; ak < 5; ak++)
for (int al = 1; al < 5; al++)
for (int am = 1; am < 5; am++)
for (int an = 1; an < 5; an++)
for (int ao = 1; ao < 5; ao++)
for (int ap = 1; ap < 5; ap++)
for (int aq = 1; aq < 5; aq++)
for (int ar = 1; ar < 5; ar++)
for (int as = 1; as < 5; as++)
for (int at = 1; at < 5; at++)
for (int au = 1; au < 5; au++)
for (int av = 1; av < 5; av++)
for (int aw = 1; aw < 5; aw++)
for (int ax = 1; ax < 5; ax++)
for (int ay = 1; ay < 5; ay++)
for (int az = 1; az < 5; az++)
for (int ba = 1; ba < 5; ba++)
for (int bb = 1; bb < 5; bb++)
for (int bc = 1; bc < 5; bc++)
for (int bd = 1; bd < 5; bd++)
for (int be = 1; be < 5; be++)
for (int bf = 1; bf < 5; bf++)
for (int bg = 1; bg < 5; bg++)
for (int bh = 1; bh < 5; bh++)
for (int bi = 1; bi < 5; bi++)
for (int bj = 1; bj < 5; bj++)
for (int bk = 1; bk < 5; bk++)
for (int bl = 1; bl < 5; bl++)
for (int bm = 1; bm < 5; bm++)
for (int bn = 1; bn < 5; bn++)
for (int bo = 1; bo < 5; bo++)
for (int bp = 1; bp < 5; bp++)
for (int bq = 1; bq < 5; bq++)
for (int br = 1; br < 5; br++)
for (int bs = 1; bs < 5; bs++)
for (int bt = 1; bt < 5; bt++)
for (int bu = 1; bu < 5; bu++)
for (int bv = 1; bv < 5; bv++)
{
z = AL*aa + AZ*ab + AK*ac + CA*ad + CO*ae + CT*af + DL*ag + FL*ah +
GA*ai + ID*aj + IL*ak + IN*al + IO*am + KA*an + KT*ao + LO*ap +
MA*aq + MD*ar + MC*as + MI*at + MN*au + MP*av + MS*aw + MT*ax +
NB*ay + NV*az + NH*ba + NJ*bb + NM*bc + NY*bd + NC*be + ND*bf +
OH*bg + OK*bh + OR*bi + PA*bj + RI*bk + SC*bl + SD*bm + TN*bn +
TX*bo + UT*bp + VA*bq + VT*br + WA*bs + WV*bt + WI*bu + WY*bv;
if (z == 5926)
{
if (bs != aj) {
if (bs != bi) {
if (bi != bd) {
if (bi != aj) {
if (az != ab) {
if (az != bp) {
if (az != aj) {
if (aj != ax) {
if (aj != bv) {
if (aj != bp) {
if (bp != ab) {
if (bp != ae) {
if (ab != bc) {
if (ax != bv) {
if (ax != bf) {
if (ax != bm) {
if (bv != ae) {
if (bv != bm) {
if (bv != ay) {
if (ae != bc) {
if (ae != ay) {
if (ae != an) {
if (ae != bh) {
if (bc != bo) {
if (bc != bh) {
if (bf != bm) {
if (bf != au) {
if (bm != au) {
if (bm != am) {
if (bm != ay) {
if (ay != am) {
if (ay != an) {
if (ay != aw) {
if (an != aw) {
if (an != bh) {
if (bh != bo) {
if (bh != ac) {
if (au != bu) {
if (au != am) {
if (am != bu) {
if (am != ak) {
if (am != aw) {
if (aw != ac) {
if (aw != ak) {
if (aw != ao) {
if (aw != bn) {
if (ac != bn) {
if (ac != av) {
if (ac != ap) {
if (bo != ap) {
if (ap != av) {
if (bu != ak) {
if (bu != at) {
if (ak != al) {
if (ak != ao) {
if (al != bg) {
if (al != ao) {
if (al != at) {
if (ao != bg) {
if (ao != bt) {
if (ao != bq) {
if (ao != bn) {
if (bn != bq) {
if (bn != be) {
if (bn != ai) {
if (bn != aa) {
if (bn != av) {
if (av != aa) {
if (aa != ai) {
if (aa != ah) {
if (ah != ai) {
if (ai != bl) {
if (ai != be) {
if (bl != be) {
if (be != bq) {
if (bq != bt) {
if (bq != ar) {
if (bt != bg) {
if (bt != bj) {
if (bt != ar) {
if (bg != bj) {
if (bg != at) {
if (bj != ar) {
if (bj != bd) {
if (bj != bb) {
if (bj != ag) {
if (ar != ag) {
if (bb != bd) {
if (bd != br) {
if (bd != as) {
if (br != af) {
if (br != ba) {
if (br != as) {
if (ba != as) {
if (ba != aq) {
if (as != bk) {
if (af != bk) {
if (af != as) {
cout << aa << endl;
cout << ab << endl;
cout << ac << endl;
cout << ae << endl;
cout << af << endl;
cout << ag << endl;
cout << ah << endl;
cout << ai << endl;
cout << aj << endl;
cout << ak << endl;
cout << al << endl;
cout << am << endl;
cout << an << endl;
cout << ao << endl;
cout << ap << endl;
cout << aq << endl;
cout << ar << endl;
cout << as << endl;
cout << at << endl;
cout << au << endl;
cout << av << endl;
cout << aw << endl;
cout << ax << endl;
cout << ay << endl;
cout << az << endl;
cout << ba << endl;
cout << bb << endl;
cout << bc << endl;
cout << bd << endl;
cout << be << endl;
cout << bf << endl;
cout << bg << endl;
cout << bh << endl;
cout << bi << endl;
cout << bj << endl;
cout << bk << endl;
cout << bl << endl;
cout << bm << endl;
cout << bn << endl;
cout << bo << endl;
cout << bp << endl;
cout << bq << endl;
cout << br << endl;
cout << bs << endl;
cout << bt << endl;
cout << bu << endl;
cout << bv << endl;
cout <<" " << endl;
}
else {
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
return 0;
}```
Selwyn McPherson.
slcool@neo.rr.com