Thread: Please suggest a better algorithm..

  1. #1
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657

    Please suggest a better algorithm..

    The problem is to find the no. of 3x3 matrices of perfect squares....like:
    121
    256
    169
    whose transpose is same as the original..
    The solution I came up with is:
    1.Make an array of vectors of the sq nos within the range..(such that..each array contains a vector of the no.s beginning with its(the array's) index...)
    2.Iterate over the square nos in the range
    --1.Put the current no. as the first row.
    --2.Iterate over the set(that array of vectors!) which begins with the middle digit of the first row.
    ----1.Put the current no. as the 2nd row.
    ----2..Iterate over the set which begins with the 3rd digit of the first row.
    ------1.Put the no as the 3rd row.
    ------2.If the 3rd digit of the 2nd row == 2nd digit of the 3rd row.
    ----------<You have found one of such a matrix>
    ------3.Continue.
    3.Output ..etc etc..
    _____________________
    It works...as expected..and finds out all of the matrices..
    ..But the 2 nested loops feels very ..err...clumsy ...take a look..
    Code:
    for(c=10;c*c<1000;c++)
        {
            temp.v1=itotr(c*c);
            for(VI it1=st[temp.v1[1]].begin();it1!=st[temp.v1[1]].end();it1++)
            {
                temp.v2=*it1;
                for(VI it2=st[temp.v1[2]].begin();it2!=st[temp.v1[2]].end();it2++)
                {
                    temp.v3=*it2;
                    if(temp.v2[2]==temp.v3[1])
                    {
                        mc++;
                        storage.push_back(temp);
                    }
                }
            }
        }
    ..... I figured out(not having a good idea about the mathematical aspects of algorithms..)..that this is better than iterating over all(more than 20!) the possible matrices..
    IS there a better and simpler way of doing this...??
    Last edited by manasij7479; 06-12-2011 at 11:52 AM.

  2. #2
    3735928559
    Join Date
    Mar 2008
    Location
    RTP
    Posts
    838
    what is a 'matrix of perfect squares'?

  3. #3
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    ..actually..a matrix of no.s... Isn't the example clear enough ? :P

  4. #4
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    733
    Code:
    121
    256
    169
    I don't get it too. 6 isn't square of any number, and:

    ..actually..a matrix of no.s...
    ???

    EDIT:

    If you mean:

    121 (11 * 11)
    256 (16 * 16)
    169 (13 * 13)

    This is not 3x3 matrix but 1x3.
    Last edited by kmdv; 06-13-2011 at 08:09 AM.

  5. #5
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    ...I meant.. ..the rows form perfect squares...and the matrix of no.s is a 3x3 ... It was difficult to phrase it ....so I thought that the example would suffice.

  6. #6
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    733
    Quote Originally Posted by manasij7479 View Post
    ...I meant.. ..the rows form perfect squares...and the matrix of no.s is a 3x3 ... It was difficult to phrase it ....so I thought that the example would suffice.
    What is the "matrix of no.s"? Numbers? Number of squares? The example of the input you provided may be a 2-dimensional array of characters as well as 1-dimentional array of integers. Or both mixed together. Not to mention that your code contains some magic identifiers, whatever they were supposed to mean.
    Last edited by kmdv; 06-13-2011 at 12:10 PM.

  7. #7
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by kmdv View Post
    What is the "matrix of no.s"? Numbers? Number of squares? The example of the input you provided may be a 2-dimensional array of characters as well as 1-dimentional array of integers. Or both mixed together. Not to mention that your code contains some magic identifiers, whatever they were supposed to mean.
    The code is working alright....I pasted it to show that it looks a bit clumsy ...
    What I'm looking for ..is a better algorithm for the process...

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by kmdv View Post
    121 (11 * 11)
    256 (16 * 16)
    169 (13 * 13)
    Thanks, that really sheds some light on things.

    3-digit perfect squares range from 0*0 to 31*31, so there are only 32 of them (assume leading zeros is okay). You want to pick three of them. I'd let that dictate how my program is structured.
    Then you need to make sure that certain digits in one number correspond with certain digits in another.
    Last edited by iMalc; 06-13-2011 at 01:28 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    There are only 20 possible choices for each row (31 if you allow numbers starting with 0), so you probably wouldn't notice much in the way of speed. But if you do want to cut down on the search space: once you pick the first row, that sets numbers for the first column as well, so that really restricts your choices for the second row.

  10. #10
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Then you need to make sure that certain digits in one number correspond with certain digits in another.
    that sets numbers for the first column as well, so that really restricts your choices for the second row.
    That is exactly what I did.
    Should I assume that is the best possible solution ?

  11. #11
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    I think your algorithm is good; but, your code is not very easy to understand.

    I would try to make it more readable.

    Tim S.

  12. #12
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    not very easy to understand
    Maybe because it was just a snippet....
    Here is the whole code!....to annoy everyone...
    Code:
    #include<iostream>
    #include<vector>
    #include<array>
    using namespace std;
    array<int,3> itotr(int); //int to triad row
    typedef vector<array<int,3>>::iterator VI;
    
    class Tr //triad
    {
        public:
        array<int,3> v1;
        array<int,3> v2;
        array<int,3> v3;
        void disp()
        {
            cout<<endl;
            cout<<v1[0]<<v1[1]<<v1[2]<<endl;
            cout<<v2[0]<<v2[1]<<v2[2]<<endl;
            cout<<v3[0]<<v3[1]<<v3[2]<<endl;
        }
    };
    int main()
    {
        vector<Tr> storage;
        Tr temp;
        vector<array<int,3>> st[10];
        int c,mc(0);
        for(c=10;c*c<1000;c++)
        {
            st[(c*c)/100].push_back(itotr(c*c));
        }
        for(c=10;c*c<1000;c++)
        {
            temp.v1=itotr(c*c);
            for(VI it1=st[temp.v1[1]].begin();it1!=st[temp.v1[1]].end();it1++)
            {
                temp.v2=*it1;
                for(VI it2=st[temp.v1[2]].begin();it2!=st[temp.v1[2]].end();it2++)
                {
                    temp.v3=*it2;
                    if(temp.v2[2]==temp.v3[1])
                    {
                        mc++;
                        storage.push_back(temp);
                    }
                }
            }
        }
    
        for(vector<Tr>::iterator it3=storage.begin();it3!=storage.end();it3++)
        {
            (*it3).disp();
        }
        cout<<endl<<"Total: "<<mc;
        cin.get();
        return 0;
    }
    
    array<int,3> itotr(int x)
    {
        array<int,3> v;
        v[0]=x/100;
        v[1]=(x/10)%10;
        v[2]=x%10;
        return v;
    }
    Any criticism? ___except for the fact that I'm scared of 2d arrays...and made the Tr class to make things easier for this small case___
    Last edited by manasij7479; 06-13-2011 at 07:44 PM.

  13. #13
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Some spaces would really improve readability.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  14. #14
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657

    Lightbulb

    Wouldn't
    Code:
    for(VI it1=st[temp.v1[1]].begin();it1!=st[temp.v1[1]].end();it1++)
    look more cumbersome if written as
    Code:
    for ( VI it1 = st[ temp.v1[1]].begin() ; it1 != st[temp.v1[1]].end() ;  it1++)
    ?
    I always remove most of the the extra spaces when reviewing the code for the first time...
    It mainly evolved from my netbook, having to sidescroll to read a long line in most IDEs.

  15. #15
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    733
    Here is the whole code!....to annoy everyone...
    I don't know how you could even think that will be able to understand your first code snippet. You didn't even tell what types the variables are of.
    Stick to n-column rule EmacsWiki: Eighty Column Rule.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Please Suggest....
    By thecrazycoerian in forum Networking/Device Communication
    Replies: 1
    Last Post: 01-10-2004, 04:07 AM