4 replies to this topic

[Nois]

I've been browsing codecall for quite a while but only till now have I actually created an account. I am looking to not only learn how to solve the problem I have below but a way to learn how to solve problems like the one below. I mean that by basically learning the methods that are used in coming up with programming instructions. I suppose something like pseudo code and required/recommended reads.

My issue: I have a matrix of integers which represent objects per-say. Like:

022

110

212

And I have them in a two dimensional array and I wish to transform this array of integers which represent objects that follow rules in how they can be transformed. Like:

//1 CAN ONLY GO DIAGONAL WITH 2

021 //< 1 has switched with the 2

120 //< The 2 located in the middle switched with the 1 in the upper right by

212 //the 1 being allowed to switch diagonal positions with the "1" integer/object.

Now I don't know if I have explained myself right but in-case I haven't here is an example of what the program I am trying to write must be able to do:

022

110       //ORIGINAL MATRIX

212


/**** STEPS ****/

021

120       //1 CAN ONLY GO DIAGONAL WITH 2

212


021

102       //0 CAN ONLY GO HORIZONTAL WITH 2

212


022

101       //2 CAN ONLY GO VERTICAL WITH 1

212

/**** STEPS ****/


022

101       //WANTED MATRIX

212

Now this is only an example which is why I do not wish to learn how to only solve the problem above but to learn HOW to solve problems like the one above they can change in rules and matrix size and complexity.

Thanks, Nois.

Note: I hope this is in the right category as I don't know if it should be in Programming Theory or not but I know that it is a open question for any developer of any language. Thus I chose General Programming.

[WingedPanther]

Learning about data structures and algorithms will help a lot, but the big key to learning how to solve problems is by solving problems.

[WingedPanther]

Following up on my earlier comment, can you clarify what part of the problem you want help with?

I can see a few areas that need to be addressed:
1) How to represent the start and goal states (should be easy)
2) How to encode the rules (not discussed in the above)
3) How to attempt to get from start to goal (also not discussed above)
4) How to report the solution, once found (above is a good representation)

I would recommend encoding rules as follows:
Place the number of interest in the center of a 3x3 array. Around the edges place the value of another number where it can be swapped out, and -1 for other places. For example:

-1 -1 1
-1 2 1
-1 1 -1

[Nois]

Steps 2 and 3 would be my areas of interest but mainly the 3rd one. From your example I now understand how I need to go about with the encoding of the rules to the solution.

Now, as far as the steps go; how would you recommend me going about that? Not only will multiple integers in the matrix be displaced but sometimes to move one integer somewhere you will first have to move several other integers to set up for the move (as the 3x3 matrix is just an example and the matrix size can be any size).

Now that I think it over I believe that I can do it by:
1) examining which integers have changed and seeing if they still do contain the same array of integers (to see if the transformation is even possible because if somehow there is an added 3 it would just blow everything up)
2) start with the piece and find every possible displacement path it can follow to get where it needs to be (and then choose the shortest one)
3) set the newly displaced integer as one that can no longer be moved in attempt to displace the others (so that when there is more than one that needs to be displaced it will not in turn displace that one to get there)

What is your input on this WingedPanther? I understand that I will not to create a recursive method that will examine all possible paths it can take. Do you believe that what I stated above is the best solution and isn't too (wouldn't care if it was to be honest) memory extensive (with 5x5 arrays)?

[WingedPanther]

I would NOT do recursion on this, simply because you could end up stuck in a loop. I'd look at all the level 1 transformations possible, then from each of those all the level 2 transformations that have not all been achieved already, etc. Level 0 = original state.