Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Matrix Transforming With Rules

matrix

  • Please log in to reply
4 replies to this topic

#1 Nois

Nois

    CC Lurker

  • Just Joined
  • Pip
  • 2 posts

Posted 07 May 2011 - 01:40 PM

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.
  • 0

#2 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 07 May 2011 - 06:00 PM

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

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/


#3 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 08 May 2011 - 01:10 PM

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
  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/


#4 Nois

Nois

    CC Lurker

  • Just Joined
  • Pip
  • 2 posts

Posted 08 May 2011 - 01:39 PM

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)?
  • 0

#5 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 08 May 2011 - 05:11 PM

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.
  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/






Also tagged with one or more of these keywords: matrix

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download