# Thread: A Quicker Way Than Brute Force to solve a problem

1. ## 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. Post Your code... my crystal ball is in for service this week... and I haven't finished my remote viewing traning yet...

3. haha can do, let me comment it and clean it up, then i'll post.

4. 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???

5. Originally Posted by GReaper
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. Originally Posted by CommonTater
386 processor, maybe?
And that , but by trial and error I know that extreme slowdown points to ( really ) nasty bugs!

7. Originally Posted by GReaper
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. 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.

9. 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.

10. got it down to 10 minutes! that's better haha

11. Originally Posted by jeremygw
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. 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.

13. Originally Posted by iMalc
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. 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.

15. 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.