Solving different types of problems with brute-force search

NOTE: This post is part of a series of posts on Solving problems with simple yet powerful abstractions in Python. This is Part 2 of the series. You can find an index of the posts in the series in the specified link.

In the previous post, we created a simple brute-force abstraction and were able to use it to find multiples of a given number within a range. In this post, we’re going to identify a few more abstractions, and a few more problems to solve by brute force. Let’s begin!

A note on abstractions and over-engineering

Let’s put some arguments to rest

In our implementation for finding multiples of a number using brute_force, you might’ve noticed that instead of a multiple_of function, we opted to write a remainder_equals function. This is NOT an oversight, or over-engineering. We are totally allowed to build up functionality using smaller more meaningful abstractions. Here, remainder_equals as an abstraction is helpful as it creates opportunities to write things like:

Notice that the order of the elements is important as well, in order to use it effectively. A useful way to think about abstractions in the case of functions, is whether it’s meaningful, and reusable — whether it exposes all variables while allowing to fix some of them. Even though we didn’t end up creating these other functions,remainder_equals is a simple (yet powerful) abstraction that let us complete our task.

For now, let’s take a look at another problem that can be solved using brute-force, and see if our abstraction holds up.

Find an element in a list

Go through the items one by one until you find a match! Sounds like brute-force.

But how do we do that? Firstly, let’s identify the types of the problem and the candidates. Every problem instance is about a list of items, and a particular item to find. The candidates can be indices of the items in the list, while solutions are those candidate indices that contain the item we’re trying to find. Now that we have that figured out, let’s go:

As usual, we have created a find_index function that can be partially applied to a list to allow searching for elements within a list. But internally while there’s a dataclass to represent the problem, the API itself is very clean and doesn’t expose implementation details. Here’s what the calling code looks like:

Hmm, nifty! It looks like we’re able to use the same algorithm yet again with no changes. That’s great! Let’s look at another problem!

Find the solution to a quadratic equation

Hmmm, another problem, another solution. Oh wait — same solution!

In trying to throw a wrench into our brute force abstraction, we’re going to try to solve a quadratic equation: x² — 4x — 5 = 0 where x ∈ [-10, 10).

Taking a detour

It looks like there’s a pattern here

In the last 3 problems (including the current one), we seem to be doing the same thing: find a number within a range such that it matches some condition. Interesting. If the problem can dictate a range, and a match condition, maybe that’s an abstraction we can come up with! Let’s try to encode this idea into an abstraction:

Now that we have an abstraction to deal with problems that have integer ranges as candidates, let’s rewrite our earlier 2 solutions to make use of them. Here’s our latest solution to the multiples problem:

Notice that while the code isn’t necessarily shorter, it’s clearer and simpler.

Let’s try to rewrite our find_index function as well, to see if our int_range abstraction holds:

Notice that this time, we don’t need to specify the step function as it’s the default. Looks like our abstraction holds! None of the callers need to change, as the change is just in the implementation. With that done, let’s get back to our original problem.

Resuming our solution to the quadratic equation

We’ve had enough of a diversion

Now that we have our abstraction for integer ranges, writing a solver for a quadratic equation is a piece of cake. So much so, that we don’t even need to write it by hand. For the supplied arguments, we can just take any function of x:

Now, let’s see how to solve our quadratic equation:

Whoa, we got there! Not only can we solve this particular quadratic equation, but we can solve any problem which involves a range of integers, using brute-force search. Pretty cool, if you ask me!

Looking for other abstractions

I don’t want to say find or search, we’ve beaten those words to death

In certain cases, we just need a function that disregards its parameters and always returns the same value. Writing a function for this really helps. Here’s what I came up with:

Here’s a sample place we can use it:

It can also be used in several other places in our code so far, but I’ll leave that as an exercise for you to figure out.

We’re not done yet!

Good things come to those who wait

We’re definitely not done. We’re barely scratching the surface of what I have planned in store for us. In the meantime, if you have any comments or ideas for problems to include, feel free to share them!

In the next post, we’re going to look at a few more problems, and come up with even more abstractions. Until then, have fun!