A Quicker Way Than Brute Force to solve a problem

This is a discussion on A Quicker Way Than Brute Force to solve a problem within the C Programming forums, part of the General Programming Boards category; I just want a few ideas of ways to sort through some info besides brute force. I am trying to ...

  1. #1
    Registered User
    Join Date
    Oct 2011
    Posts
    6

    A Quicker Way Than Brute Force to solve a problem

    I just want a few ideas of ways to sort through some info besides brute force.

    I am trying to finish a project, and I am not asking for a solution, just wanting to know a few other ways to solve this problem that isn't brute force.

    It is a pick up sticks game where given the number of sticks and a series of conditions, the program would print Valid or Impossible.
    The conditions are just stick x is over stick y.

    I need to solve files with 1,000,000 conditions under 1 minute, and right now it takes over 45 minutes.

    What are ways to shorten this check?

    It is similar to this problem
    UVa Online Judge

  2. #2
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Post Your code... my crystal ball is in for service this week... and I haven't finished my remote viewing traning yet...

  3. #3
    Registered User
    Join Date
    Oct 2011
    Posts
    6
    haha can do, let me comment it and clean it up, then i'll post.

  4. #4
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,625
    Say you have a list containing the cases. You compare the sticks that are below( the second in each pair ) with every single above ones ( the first in pair ). If you find one above that isn't equal with any of the belows, you take that pair off the list. If you find no value, then it's Impossible. If the list becomes empty, it's Valid.

    I think what I just described is the brute force algo, but why would it take 45 min???
    Devoted my life to programming...

  5. #5
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by GReaper View Post
    Say you have a list containing the cases. You compare the sticks that are below( the second in each pair ) with every single above ones ( the first in pair ). If you find one above that isn't equal with any of the belows, you take that pair off the list. If you find no value, then it's Impossible. If the list becomes empty, it's Valid.

    I think what I just described is the brute force algo, but why would it take 45 min???
    386 processor, maybe?

  6. #6
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,625
    Quote Originally Posted by CommonTater View Post
    386 processor, maybe?
    And that , but by trial and error I know that extreme slowdown points to ( really ) nasty bugs!
    Devoted my life to programming...

  7. #7
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by GReaper View Post
    And that , but by trial and error I know that extreme slowdown points to ( really ) nasty bugs!
    LOL... yes, it's usually our own silly faults...

  8. #8
    Registered User
    Join Date
    Oct 2011
    Posts
    6
    Code:
    void conditionTesting (int sticks, int lines, int **conditions){
        int x;
        int y;
        int z;
        int stickisbelow = 0;
        int removed[sticks];
        
        for (x = 0; x < sticks-1; x++)
        {
            removed[x] = 0;
        }
        //tests each stick to see if it can be removed
        for (x = 1; x <= sticks; x++)
        {
            //will see if the stick is below any others, if it isn't, then it can be removed.
            for (y = 0; y < lines; y++)
            {
                if (x == conditions[y][1])
                {
                    //increments if it finds the stick below any others
                    //if it doesn't increment, that means that the stick is only above
                    stickisbelow++;
                }
            }
            
            //if it only is above, then it will remove it from the above columnn and it moves all the sticks that were below it to the above column
            //will also keep track of sticks removed.
            if (stickisbelow == 0)
            {
                for (z = 0; z < lines; z++)
                {
                    if (x == conditions[z][0])
                    {
                        conditions[z][0] = conditions[z][1];
                        conditions[z][1] = 0;
                        removed[x]++;
                    }
                }
            }
        }
        
        //checks to see if all sticks removed, if all the spots are 0 in the array
        int notremoved = 0;
        for (x = 0; x < lines; x++)
        {
            if (conditions[x][0] != 0 || conditions[x][1] != 0)
            {
                notremoved++;
            }
        }
        
        if (notremoved == 0)
        {
            printf("Valid\n");
        }
        else
        {
            printf("Impossible\n");
        }
    }
    It will take this long if you are checking
    if each stick is below another and repeating check until you find it's impossible or if all the sticks are removed.

    Is this similar to what you are talking about with the lists?

    This isn't full, but it explains what i was working on. I know there must be a faster one, since we are supposed to get it to be able to return an answer in under a minute.
    Last edited by jeremygw; 10-09-2011 at 06:23 PM.

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
        int removed[sticks];
         
        for (x = 0; x < sticks-1; x++)
        {
            removed[x] = 0;
        }
    I don't know why you aren't initializing the whole thing, but you could throw that loop out entirely:
    Code:
    int removed[ sticks ] = {0};
    You also walk off the end of your array here possibly:
    Code:
        for (x = 1; x <= sticks; x++)
        {
            //will see if the stick is below any others, if it isn't, then it can be removed.
            ...
                        removed[x]++;

    Quzah.
    Hope is the first step on the road to disappointment.

  10. #10
    Registered User
    Join Date
    Oct 2011
    Posts
    6
    got it down to 10 minutes! that's better haha

  11. #11
    Registered User
    Join Date
    Oct 2011
    Posts
    6
    Quote Originally Posted by jeremygw View Post
    got it down to 10 minutes! that's better haha
    nope. that ended up with a wrong answer.

    currently 30 minutes and hopefully right answer.

  12. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Your code appears to be O(sticks * lines) in big-Oh notation and I'm guessing that those are high numbers. Any minor tweaks probably wont bring down the execution time that much. I expect that they've got the time limit set such that no O(sticks * lines) implementation can complete in under the time limit.

    There are some similarities with how this code operates with that of how a naieve prime sieve works. My thoughts on improving the speed would be to apply the same kind of optimisation that The Sieve of Eratosthenes applies to prime sieving, to this problem.
    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"

  13. #13
    Registered User
    Join Date
    Oct 2011
    Posts
    6
    Quote Originally Posted by iMalc View Post
    There are some similarities with how this code operates with that of how a naieve prime sieve works. My thoughts on improving the speed would be to apply the same kind of optimisation that The Sieve of Eratosthenes applies to prime sieving, to this problem.
    Wow. that makes a lot of sense, and what i have been trying to reach. I have been looking through prime sieving and it has given me possible ideas to try or add to what I have been trying. As soon as I can figure out how all the variables are related, i'll be in business, which is a bigger hassle than i think it will be haha.

  14. #14
    Registered User
    Join Date
    Mar 2009
    Posts
    344
    A totally separate approach is to eliminate the need for looping over every line of the input to check each stick. Instead, when you read the file in sort the over/under relationship into buckets which reduces the search time. What I did for a quick test is have an array called is_above. Each entry in is_above[x] is a list of sticks which are on top of stick x. Se for each input line <upper, lower>, you'd do add_to_list(is_above[lower], upper). You make each entry of is_above a linked list or an array depending on how you want to do it - but I'd recommend a linked list to start since you'll be doing lots of random deletes from it later.

    This way, instead of searching over a million lines to see what's possibly above a given stick, you can just check to see if is_above[x] is empty or not. This replaces a search of a million lines with a single test.

    Then you just run through is_above[x], looking for entries which are empty and removing them. Removing is simple - add it to the results list and remove all references to stick x in any of the is_above[x] lists. You can do this brute force (i.e. iterate over every entry of each list in each is_above[0..sticks-1]), or you can be smarter and create a second list as well. This one keeps track of all the sticks which are below the current entry. When you remove a given stick x, iterate over this second list (call it is_below[x]) - the full content of this list will be the complete set of is_above[] entries which hold the stick you're removing. You'll then remove x from the lists at each of those locations in is_above[] - that last bit is still a linear search but will still shrink the run time quite a bit.
    Last edited by KCfromNC; 10-10-2011 at 10:00 AM.

  15. #15
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    An interesting problem to solve in a 5 second run time limit. A million sticks seems a bit bold!

    I thought the array algorithm could work (and be substantially faster than the OP posted), but for a million sticks, in < 5 seconds??

    I'm not real confident about that.

    Seems like you need a linked list, where the sticks can be inserted and deleted, anywhere in the list, as they are either read in from the data, or the sticks are removed by the program.

    Then I took some straws and tossed them into a pile on the kitchen table. LOTS of those straws wound up resting on top of more than one straw. I'm not sure if that would make the way I was thinking about the linked list, into the linked list from hell, or not. Just seemed ugly, at that point.

    Then a little voice inside said "This could be a problem for Dancing Links", but I don't know enough about it yet. It's a coloring problem algorithm, but with a bit of adaption, it's VERY fast solving Sudoku, and other problems - and it uses linked lists like crazy!

    If I were doing a program for this today, I'd use an array, but optimize the way it's used, so it would be fast, but I'm doubtful it could solve the puzzle with a million sticks, in less than 5 seconds.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Brute Force
    By 123sample in forum C Programming
    Replies: 4
    Last Post: 09-12-2010, 01:37 AM
  2. Brute Force
    By swgh in forum A Brief History of Cprogramming.com
    Replies: 6
    Last Post: 08-16-2007, 02:41 AM
  3. Replies: 2
    Last Post: 03-21-2004, 08:21 PM
  4. Brute Force
    By Wiz_Nil in forum C++ Programming
    Replies: 13
    Last Post: 02-15-2002, 01:28 PM
  5. Brute-Force
    By red11514 in forum C Programming
    Replies: 1
    Last Post: 11-13-2001, 12:53 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21