C++ Question Need some elegance in an algorithm!

[jedidia]

The problem I have is trivial. But then I start an algorithm to solve it, and it gets so convoluted and uggly that I just can't bare it. There must be a much more elegant solution that I'm missing.

The problem, as stated, doesn't sound like much. I have 3 variables that can have 3 valid states, and an invalid one (showing that the variable has not yet been assigned a valid value).

Any of the variables can have any valid state, but they must all have a different one (i.e. every valid value must be assigned to a variable).

Initially, it is possible for all three variables to be invalid, or for one or two of them to already have a valid value. The algorithm must do nothing more than find out which values are still available and assign them to the available variables. It doesn't matter which one goes to which one.

Sounds simple, and probably is, but I'm getting into a nasty spaghetti pot. Can anyone tell me how to solve the problem with as simple an algorithm as possible (pseudo-code or real code, doesn't really matter).

 

[Urwumpe]

Sounds simple, and probably is, but I'm getting into a nasty spaghetti pot. Can anyone tell me how to solve the problem with as simple an algorithm as possible (pseudo-code or real code, doesn't really matter).

If I understand this correctly... you have only (3*2) possible valid states for the three variables, right?

And if two or three variables are uninitialized... how should the algorithm behave?

 

[Artlav]

Can you define the values?
If yes, it's trivial.

byte v[3]; are your variables.
1, 2 and 4 are your values, 0 is uninitialized.

Given that, something like this should work:

for (int i = 0; i < 3; i++) {
 byte all = v[0] | v[1] | v[2];
 byte shl = 1 << i;
 if ((all | shl) == 0) for (int j = 0; j < 3; j++) if (v[j] == 0) { v[j] = shl; break;}
}

It tries every value (which are orthogonal to each other) for it's existence among the variables, and if nonexistent - assigns it to the first uninitialized one.

P.S. It assumes no error conditions, like same value already assigned to several variables.
You can check for existence of such condition with "if (((v[0] | v[1] | v[2]) != 7) && v[0] && v[1] && v[2]) error();".

 

[dgatsoulis]

I have 3 variables that can have 3 valid states, and an invalid one (showing that the variable has not yet been assigned a valid value).
Any of the variables can have any valid state, but they must all have a different one (i.e. every valid value must be assigned to a variable).

Initially, it is possible for all three variables to be invalid, or for one or two of them to already have a valid value. The algorithm must do nothing more than find out which values are still available and assign them to the available variables. It doesn't matter which one goes to which one.

Not sure how much this helps, but I find that the 3 variables can have 28 different combinations:

1,2,3 = valid 4 = invalid

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
1 4 4
1 2 4
1 3 4
2 4 4
2 1 4
2 3 4
3 4 4
3 1 4
3 2 4
4 1 4
4 1 2
4 1 3
4 2 4
4 2 1
4 2 3
4 3 4
4 3 1
4 3 2
4 4 1
4 4 2
4 4 3
4 4 4

 

[jedidia]

Given that, something like this should work:

Thanks, that's exactly the kind of thing I was looking for.

byte all = v[0] | v[1] | v[2];

I had absolutely no idea that a declaration like that was possible :blink:

 

[Jarod]

When I saw Artlav's solution, I thought "what the heck is that ?", and didn't really tried to understand.
I tried to write something which resulted in spaghetti code, and then I tried to think as each valid state as a vector orthogonal to each other, and then to map their coordinates to binary, when I was writing the OR operation to find which states are missing, I thought "what the heck ?", came back to Artlav's solution and saw that it was exactly what he already wrote.
Damn, well, at least now I understand.
It allowed me to spot an error in Artlav's code too.
The if condition on the last line shoud read :

if ((all & shl) == 0)

for (int i = 0; i < 3; i++) {
 byte all = v[0] | v[1] | v[2];
 byte shl = 1 << i;
 if ((all & shl) == 0) for (int j = 0; j < 3; j++) if (v[j] == 0) { v[j] = shl; break;}
}

 

[ADSWNJ]

Keeping it tight:

  int v[3] = {2,1,0};
  int a = v[0] | v[1] | v[2];
  for (int b = 4; b > 0; b/=2) if ((a & b) == 0) for (int i=0; i<3; i++) v[i]= v[i]>0? v[i] : b;

Not sure abut the byte definition, but I'll happily waste a few bits and make them ints!!

 

[Artlav]

I had absolutely no idea that a declaration like that was possible :blink:

What exactly surprised you in it?

It allowed me to spot an error in Artlav's code too.

Well, i did write that code at 1 am, in bed and on a cellphone, so i couldn't exactly test it.

Always be wary of a code that runs on the first try - it only means that the error is subtle and will bite you later.

 

[jedidia]

What exactly surprised you in it?

That you can declare a variable that has several possible states (if that is what it's actually doing). Although I generally suck at bit-level manipulation big time. It's just one of the many things I never learned to use...

 

[Urwumpe]

That you can declare a variable that has several possible states (if that is what it's actually doing). Although I generally suck at bit-level manipulation big time. It's just one of the many things I never learned to use...

Its not declared... its a bitwise-or operation, with the variable states defined as such by Artlav, that every state has its own bit position.

 

[meson800]

If the values of the "v" array are 1,2,4, the declaration

byte all = v[0] | v[1] | v[2];

is the exact same thing as,

byte all = 7;

Because you just or them all together

1: 0 0 1
2: 0 1 0
4: 1 0 0
-------- (or operation of the above)
7: 1 1 1

 

[Shifty]

came back to Artlav's solution and saw that it was exactly what he already wrote.

Yeah, I spent 10 minutes sketching out a solution on my whiteboard, came back, reloaded the forum and Artlav had already posted pretty much exactly the same thing, except I assumed a generic type for the variables and had an initial routine to convert them to the bitflag states and back.

 

[jedidia]

Well, thanks a whole lot to everyone for posting from their cellphones in bed, getting out their whiteboards aso. I didn't quite expect that amount of feedback. :embarrassed: