C/C++ Matrix Algorithm

[Vectorizm]

I know it's a bad practice to post the same question on more than one help site (I posted it on Stackoverflow, but after some time your question loses its place on the "active" list and people stop reading it) but I'm really desperate here. So my question is:

I have a matrix that looks like this (the letters and numbers beside it are indexes):

   A  B  C
1 {2, 0, 2}
2 {1, 0, 1}

A couple of terms that will be used in the problem:

A pair is a pair of a letter and a number. The number always comes first. Each pair is basically an index to an element. (e.g. 1A = 2, 2B = 0, 1C = 2, etc.).

A command is a pair of two pairs. The "syntax" is [sourcePair][destinationPair]. The sourcePair always has to be a non-zero value while the destinationPair always has to be a zero value. This of course also prevents you from using the same pair as the sourcePair and the destinationPair. It works like this: whatever value is in the sourcePair (either 1 or 2) will be moved into the destinationPair and then the sourcePair will be set to 0 (it will modify the matrix). (e.g. 1A1B -> 1B = 2, 1A = 0; 1C2B -> 2B = 2, 1C = 0; etc.).

A key is a set of 16 commands (64 characters in total).

GOAL: To find all of the possible combinations for the key that will make the matrix look like this:

   A  B  C
1 {1, 0, 1}
2 {2, 0, 2}

The rows of the matrix are basically swapped. The algorithm doesn't have to be super-efficient as I will only be printing the key when the user presses a button. Also the key has to be exactly 16 commands long (64 characters). It doesn't matter if you for example use the first x commands to do something just to occupy some space and then use y commands to do the actual thing.

An actual example would be:

1A3B3C1A1C3C3A1C3B3A1A3B3C1A1C3C3A1C3B3A3C3B1A3C3A1A1C3A3B1B1B1C - I found this one by hand (pen and paper). The first 5 commands make it look like the desired matrix, then the next 5 commands are the same (putting it back into the original state) and then the next 6 commands (I just extended the 5 command swap by modifying it a bit and adding a redudant command) make it the desired matrix again.

Thanks for reading,

Vectorizm.

[Ancient Dragon]

Interesting ... but you failed to ask the question, or I failed to find it.

[Vectorizm]

Thanks for leaving a reply. So the question is: what kind of an approach should I use? I don't have any ideas. What kind of an algorithm could compute a random key which consists of exactly 14 commands and brings the matrix into the desired state?

[Vectorizm]

Interesting ... but you failed to ask the question, or I failed to find it.

So... Any ideas, suggestions, links, etc?

[Ancient Dragon]

ideas or suggestions about what? From the description it appears to be just a simple swapping algorithm, take two pairs and swap their cell values. Most sorting algorithms do something similar. The first step would be to get a pair, 1A for example, then convert it into indices that C/C++ can understand, 1A = 0 and 0

int array[5][5];
char* pair = "1A";
int a,b;
a = pair[0] - '0' - 1;
b = pair[1] - 'A';
int value = array[a][b]

[Vectorizm]

I am aware that this is just some basic swapping but I need to develop an algorithm that will generate me a random key each time. The problem is that the swapping has to be done in exactly 16 commands and the matrix has to look like this: {1,0,1}{2,0,2} on the end. The swapping should be easy, but knowing what to swap and when to swap (because of the 16 swap limit) is the hard part.

[Vectorizm]

So I'm basically looking for all combinations of exactly 16 commands that will bring my matrix from this {2,0,2}{1,0,1} to this {1,0,1}{2,0,2}.

[Vectorizm]

1A3B3C1A1C3C3A1C3B3A1A3B3C1A1C3C3A1C3B3A3C3B1A3C3A1A1C3A3B1B1B1C

I made a mistake here. All 3s should be switched to 2s. Sorry!

[mike_2000_17]

Of course, you can easily generate one random key:

char k1[2]; k1[0] = '1' + (rand() % 2); k1[1] = 'A' + (rand() % 3);

then, you can easily check if it is occupied. If it corresponds to a 0 cell, then generate a new key until it corresponds to a non-zero one. Then, you do the same for the second key in one command, but now you require that it corresponds to a zero cell. That procedure will give you a random command which is valid. This basic algorithm can be used on the overall problem too.

Once you can generate random valid commands, you generate one, execute it, and repeat 16 times. At the end, if you arrived at the form you wanted, then that 16 command sequence is valid, and you can give it as output. Generating them all might take a very long time. This algorithm is, of course, a brute-force algorithm, there are more clever things you can do.

Overall, you have to look at this problem as a decision-tree. At every point in time there are 4 possible cells to move and 2 possible cells to move them to. This gives you 8 possible commands at any one point in time. Because you have at most 16 commands to execute, you can see this whole problem as a tree with a depth of 16 and a branching factor of 8. That's a gizillion possibilities, so, an exhaustive search is going to take a long time (and memory). To cut down on the need for searching this entire tree of possibilities, you need to devise reasons to stop searching. You've already mentioned one obvious structure in this problem, which is the fact that there are a number of sequences of commands (of any length) that would leave the matrix unchanged. The most trivial such sequence is, of course, to move an element and then move it back, this is a sequence of two commands that bring you back to the same state. While traversing the tree of possibilities, everytime you see the original pattern again, you know that all the commands between the start and this node of the tree is just a sequence of commands that leaves the matrix unchanged. You don't need to look any further in that branch of the tree because you know that it will just be a repetition of the start of the tree. You can record all the sequences that you find which bring the pattern back to the original, plus all the sequences which produce the final pattern (they don't have to be 16 commands long), and, in any of these cases, you stop searching the tree (down that branch) because there is nothing new to discover there. Once you have finished searching the tree, you should end up with a list of sequences of varying lengths to leave the pattern unchanged, and a list of sequences of varying lengths to get from the original pattern to the destination pattern. Then, it is just a matter of putting sequences together which make up exactly 16 commands, and contain an odd number of (original -> destination) sequences and any number of unchanging sequences.

I don't know what your level is, and if you are expected to do just a brute-force or something along the lines of the strategy I described. Anyways, that's my "ideas about it".

[Vectorizm]

Finally! This is really helpful. Now I just need to think about it for a while and get to work. I'm actually going to use this in a key generator for a reversing challenge (I don't know if you're familiar with the site but it's called www.crackmes.de - nothing illegal! :)), so, do you think the first idea will be fast enough to generate a key without the user waiting?

[mike_2000_17]

do you think the first idea will be fast enough to generate a key without the user waiting?

Test it and see. If you are going to do the second solution (tree), then you will probably want to try the first solution before anyways. So, start with implementing the first solution and see if it is fast enough, if not, move on to the next solution.

[Vectorizm]

Test it and see. If you are going to do the second solution (tree), then you will probably want to try the first solution before anyways. So, start with implementing the first solution and see if it is fast enough, if not, move on to the next solution.

Alright. :) I've already started. Thank you very much for your ideas. :D Is it okay if I send you a PM if I get really really stuck somewhere? Thanks a lot! :)

[Vectorizm]

Hey! I did it! I used the first idea! It completes in 0.033s. This is amazing! Thanks so much!!! I can't describe how thankful I am. :) Thanks a lot!!

[mike_2000_17]

It finds all the possible solutions in 0.033s? That's impressive.

It would be interesting to do the second approach too, just to see how it compares, and it is also a good exercise in programming (and these kinds of tree-structured algorithms are also the basis for many artificial intelligence algorithms, like the basic Minimax algorithm). If you do, post the result here.

If you consider this problem solved, mark the thread as "solved".

[Vectorizm]

No, no. :) It finds one key in 0.033s. :) That's all I needed. The user presses a button to generate it. Thanks a lot for you help! I might try the tree approach, we'll see. Anyway, it was a pleasure talking to you. :) Thanks.