views:

692

answers:

15

This is my first post here so be easy on me!

I'm a beginner C++ programmer, and to stretch my mind I've been trying some of the problems on projecteuler.net. Despite an interest in maths at school, I've found myself automatically going for brute force solutions to the problems, rather than looking for something streamlined or elegant.

Does this sound like a bad mindset to have? I feel a bit guilty doing it like this, but maybe quick and dirty is OK some of the time...

+3  A: 

I would say that no, it's not a bad sign. In fact you're doing yourself a favor by trending away from premature optimizations, which is definitely a Good Thing.

Erik Forbes
+1  A: 

learning is a brute force process. I wouldn't say its bad. In trying to do something that way you may notice a pattern. I think as long as you are thinking about something and trying to find solutions you will learn. There are few people who just jump to the most elegant or efficient solutions.

It would be hard to convince me that people that are trying to learn could ever be called bad. Except maybe an evil scientist :P

good luck.

Arthur Thomas
+6  A: 

No, this isn't a bad thing. I've had solutions that were so elegant they were wrong.

John at CashCommons
+1 - I laughed.
Andrew Heath
+4  A: 

The elegant solutions weren't created spontaneously; they were derived from the brute-force solutions when more speed or less memory consumption were required from the current solution.

So no, it's not. It's how the elegant solutions came into being.

Robert C. Barth
+1 and I wish I could add another.
daub815
@daub815: I did it for you. Damn, now I can't upvote it like I wanted to ;)
schnaader
+2  A: 

Ken Thompson: "When in doubt, use brute force"

Mehrdad Afshari
+1  A: 

Do you fit inside the 1 minute runtime rule for the problems? If yes, then your "brute force" solution fulfils all the requirements, and that's actually a very good sign that you can quickly come up with something that works!

These kinds of problems encourage micro-optimisation and very clever algorithms, but in general a very readable straightforward implementation will be much easier to maintain, and will be favoured in the business world.

small_duck
+18  A: 

I think you should look at what your end goal is and what your constraints are.

Sometimes a bruteforce method can solve a problem in 50ms trying out every combination of solutions and a "clever" solution can solve it in 10ms. At that point, the less clever but easier to understand solution trumps the clever solution.

However, there are some problems where brute forcing will not only be inelegant but simply won't work. There are many problems where if you attempt to naively brute force them it will take a significant amount of time to solve them. So obviously, these types of problems need a more elegant approach.

So ask yourself, why you are attempting these Project Euler problems? Are you doing it to learn? Then maybe trying a clever solution would be in your best interest but only after you have initially tried a brute force solution to help get a grasp of the problem.

When doing the Python Challenge problems I try to do it the most succinct way I can, pushing the limits of my abilities. After I solve it I then review other peoples answers and take mental notes of people who were more clever than myself and what they did. Some people will make special use of a data structure I hadn't thought of that is more suited to the task or they will have little mathematical tricks they use to make their algorithm more efficient. In the end I try to absorb as much of their cleverness as I can and make it show the next time I'm presented with a problem of a similar nature.

Simucal
Take for example Project Euler/Problem 18, "Find the maximum sum travelling from the top of the triangle to the base." (height=15) and problem 67, which is the same with height=100. Brute force will *not* work for the latter.
Federico Ramponi
Great answer to the question!
Tall Jeff
Thanks for this (and all the others - I'd comment individually if I had time!). Very useful, and reassuring too.@Federico - I'm not quite there yet, but good point. I think in that case, from what I've learnt here, I'd implement a brute force solution on a scaled-down version, then optimise.
Skilldrick
I would think that ANY solution is generally better than NO solution, and brute forcing a solution can sometimes give you insight into the problem to allow you to do something more clever.
Dolphin
Note that the "significant amount of time" it may take to solve some of those programs by brute force is thought to exceed the remaining lifetime of the universe by several or even many orders of magnitude.
Doug McClean
+7  A: 

As a beginner programmer, you will be spending more of your mental energy figuring out how to actually implement things in C++, rather than spending energy on finding a clever solution to each problem. This is fine, because it gives you the opportunity to explore different areas of C++ while working on a range of various kinds of problems.

When you become proficient in C++ and you don't have to think about how to do every little thing, then you will be able to spend more time inventing non-brute-force solutions.

Greg Hewgill
+1. Further, when you become proficient, you will be more certain that you can implement any solution you can think of, which gives you the confidence to try solutions other than the most immediately apparent one.
ShreevatsaR
+3  A: 

I've sort of gone through this evolution:

  1. Get it to compile
  2. Make it work as expected
  3. Figure out one solution that works
  4. Figure out one good solution
  5. Figure out multiple solutions, and find the best
  6. Figure out multiple solutions, and find the best for this situation
  7. ?? haven't gotten there yet
John MacIntyre
+1  A: 

If it happens to be a situation where "brute force" => "simple" and "elegant" => "complex", then brute force wins. And this is very often true.

le dorfier
A: 

Contrary to most of the other answers, I would say "Yes and No"! The early Project Euler problems can be solved quite easily by brute force approaches. Many of the later ones require that some analysis is done in order to make a narrowed brute-force search feasible. For example, problem 18 can be solved by a brute force approach, while the larger problem of the same type (Problem 67) cannot (as stated in the problem).

The intended audience include students for whom the basic curriculum is not feeding their hunger to learn, adults whose background was not primarily mathematics but had an interest in things mathematical, and professionals who want to keep their problem solving and mathematics on the edge.

Mitch Wheat
that's one example where i tried hard to get the 'clever' solution. at first i thought i was 'cheating' when simply adding memoization allowed me to solve the 'big' problem. after a little analysis, it turned out that the 'clever' solution was a longwinded way to do memoization.
Javier
A: 

It's definitely not a bad sign to trend to brute force, especially as a beginner because you may not know any better. Especially with Project Euler, it is a bad sign to implement a brute force method and not review the comments to learn a more efficient method.

I often end up in the same boat you're in and that's actually why I started doing P.E. problems -- I was implementing a lot of brute force approaches and wanted to expose myself to more elegant solutions...

Austin Salonen
+1  A: 

Not at all. Get the problem solved correctly and completely then make it more performant or elegant as necessary.

That's not to say you should ignore obvious performance improvements... Just don't focus on them until you understand the problem better.

Chris Nava
A: 

To put this in a different context:

When you use a library that you don't know very well (for creating UI, for instance) you can solve a simple problem in a perfectly performant way, though you know there's a "correct way" to do it. If you are curious and worried that your brute-force code makes you look like a moron, you will soon find the "correct way" to do it (e.g., on weekends, or while you sleep). In the meantime, through brute force, you will have something that works.

I actually forget to use brute force sometimes, and start scanning the API for the "right" solution. This is definitely an error in many cases. If the brute force solution is easy to implement, scales as you need it to (really, if it works), then forget about the correct solution. You'll find it soon enough (and many times you already knew it!), but in the meantime, you solved the problem and were able to go on to the next one.

Roadblocks are terrible when coding, and should definitely be avoided more than brute force solutions.

Yar
A: 

You have weigh your option. If the brute force solution will get the job done and perform ok, it is a good solution.

fastcodejava