Finding multiples of a number using 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 1 of the series. You can find an index of the posts in the series in the specified link.

Usually when trying to solve a problem, we’re searching for solutions to a problem — it’s a search. And we need to know what we’re looking for. There are several variants to this — we might want to check if a solution exists. We might want to find the first solution. We may also want to find the first n solutions. Another thing we may want to do is to enumerate all the solutions to a problem. In order to not repeat the same code in different ways but still get the ability to do all of these, we want to use generators as our solvers. So here’s our first abstraction:

We’re going to write an abstraction for an algorithm, and then use it to solve several different problems to show how powerful abstractions can be.

What’s the simplest way to solve a problem?

Run through possible solutions one by one until you find a solution!

One of the simplest search algorithms is the brute-force search algorithm. We can use this to solve a variety of problems, where the search space is known and exhaustible. The algorithm basically generates candidate solutions over a solution domain, and outputs solutions. The brute force algorithm requires 4 simple functions to work. We’re going to use 3, because our output function is handled by the generation of solutions.

Let’s write a function that can solve any problem by brute-force:

The code is pretty self-explanatory with types, but I want to add a few comments. Firstly notice the signature of the brute_force method. It returns a function that takes a Problem and returns a Candidate generator. That’s the same signature as our solver above! A brute-force solver requires 3 pure functions to work:

• first — a function that takes an instance of the problem and generates the first candidate solution. If no candidate solutions exist, it returns None
• next — a function that takes an instance of the problem, and the current candidate solution, and returns the next candidate solution. If there are no more candidate solutions, it returns None.
• accept — a function that takes an instance of the problem, and a candidate solution, and returns True if the candidate is an acceptable solution to the problem instance.

The algorithm itself is very simple: for any problem, we first get the first candidate solution. As long as there are available candidates, we keep checking if they are accepted. If they are, we yield them as solutions. When done checking for a candidate, we use it to get the next candidate.

What can you do with this?

At least find multiples of a number, apparently

Okay, so we have an abstraction of the brute-force algorithm. What can we do with it? Let’s try solving some problems. Let’s say I want to find the multiples of the number 417. Here’s a simple solver:

Turns out, finding the multiples of a number can be done using a simple brute-force search! And the find_multiples function is just an application of our brute_force abstraction, supplied with a few functions.

Here’s what the calling code looks like:

Wow, turns out it’s pretty useful. But is this really extensible? What if I wanted to find multiples of a number within a certain range? Aha! The problem space has changed. Let’s see what we can do about that.

Dealing with a variety of problems

Time to create newer abstractions

Brute-force relies upon problem instances to generate candidate solutions. If the problem described the search space, it can be used in the first and next functions. Let’s created a bounded search for multiples (but without breaking the current API):

The calling code doesn’t have to change, as the new parameters are all optional. While internally for the brute force algorithm we provide a problem instance which has rich data inside a data class instance, the API itself is simple to use as earlier. Here’s what the calling code looks like:

But we’re doing a lot of work! We go through the numbers one by one when we’re trying to find multiples of 417. Isn’t there a better way to brute-force the solutions? I’m glad you asked.

Optimizing the brute-force search

It’s often possible to reduce the search space

For the previous example, we could instead create a brute-force search where the candidates are just multiples of the given number. That would cut down the computations, and we can also just blindly accept all candidate solutions!

The calling code doesn’t have to change at all, but the search is now more optimized — to the extent that there’s no search at all!

But we’re just finding multiples of a number!

Is there anything else we can do?

Yes, lots! Notice that as we changed the parameters of the problem, we never went back to change the definition of the brute_force function. We wrote it once, and it’s served us well so far. That’s a sign of a good abstraction. But we’re still just working very close to the initial problem.

In the next post, let’s look at a few more problems. It’d be interesting to see how they can be solved using brute-force, for sure. In addition, it’d be exciting to learn what other interesting abstractions we can come up with in the process. See you next time!