Brute force (and enlightened brute force) (cloned)

Brute force

Definitions

Brute force: The process of solving a problem by using a technique that requires no forethought, and a lot of easy work.

Also known as doing things the dumb way or the hard way or the long way.

Enlightened brute force: The process of solving a problem first by examining different options, and realizing that the best solution path involves a larger-than-expected quantity of easy work. It seems like brute force; the enlightened part comes from realizing that not all easy work is bad, provided you took a moment to determine that that work doesn’t miss a shortcut or other more efficient path.

Usually avoided by intermediate-level solvers who have recently learned to find brute force distasteful, because they have not yet learned how much work is necessary, and how much is wasteful.

Sometimes you have to do things the long way. For example, you might write out twenty different possibilities, and calculate each of them by hand. This is called working by brute force. The idea is that you don’t need a ton of smarts to do this; you just need a ton of patience. In general, you should rely on brute force whenever you can solve a problem by doing up to about thirty small bits of work.

Often, you will get partway through a brute force solution when you’ll realize that you don’t actually have to list all the things in order to get to a solution. Maybe it’s enough to just write every other thing. Or maybe you can write ten things then notice some pattern in your work that makes the rest much easier. Or maybe partway through your brute force solution you notice some completely different (but easier) way to tackle the problem.

All of these are examples of enlightened brute force: you are combining brute force with some smarts, and that makes everything go better.

What to do

Like I mentioned earlier, there aren’t any quizzes for this unit. And you’ve done a good chunk of the work of this section just by reading it. But to get full benefit out of this section, you need to try it out on some problems. Find a few problems that be solved using a clever trick. Then find a way to re-work the problem “the long way.” Our goal here is to give you some real-world experience with the difference between unnecessary work and necessary exploration.