Solving for multiple variables in 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 3 of the series. You can find an index of the posts in the series in the specified link.

In the previous few posts, we created a basic abstraction of the brute-force search algorithm, and then extended it to some problems. In this post, we’re going to add some new problems to the mix, to see if our abstractions hold, and come up with new abstractions if necessary.

The last problem we solved with brute-force was a quadratic equation. It’s an equation involving one unknown integer within a range. In order to test our existing abstractions, let’s add a complication.

Find points on a straight line

Is this more complex than the last one?

Let’s try to find points in a straight line defined by the equation:
find x, y ∈ Z, where 3x + 13y — 7 = 0, 10 < x < 25, -10 < y < -1

The line is described by a linear equation of 2 variables, here x and y. And we’re looking only for integer solutions. In the last problem, we solved for a single variable x by creating a range, but now we have 2 variables. We can totally create another function like this:

But whenever we think it’s easy to create a solution is where we miss out on abstractions. Let’s think more about what are the abstractions that would help us out.

The case of the missing abstractions

To find them, you first need to recognize they’re missing

When we described brute-force searches in the first post, we said the brute force algorithm searches for candidate solutions over a solution domain. When we described the problem of finding an integer within certain bounds, that’s also just describing the solution domain. The domain is just described by the 2 functions first and next. When we created an integer range, we had to supply parameters to both of them. In mathematical terms, the domain is the set of valid inputs to a function — it is analogous.

The brute-force algorithm itself doesn’t need a domain, but it’s a useful abstraction that enables us to do powerful things. For example, if we have a solution domain, we could combine 2 of them (in varying ways) to create a new domain. In the case of finding 2 variables x and y, if x had its own domain, and y had its own domain, we could combine them to create an (x, y) domain — without having to do this every time we encounter a new problem with a different number of variables. Also, if they had their own domain, we wouldn’t need to worry about their types! We could easily solve for 2 integers, or for an integer and a string.

Let’s try our hand at an abstraction for a domain for a particular problem:

Now that we have a domain, it must be easy to convert our int_range from earlier into a domain, and to change solve_for_x to work for any data type instead of just integers. Let’s try that:

The calling code will need to change too:

The find_index and find_multiples implementations from earlier posts can also be rewritten to use domain, but I’ll leave that as an exercise to the reader. It’s an implementation change and won’t affect the calling code.

Solving for multiple variables

A product of the domains should be enough

To solve for multiple variables with different domains, we need a cross-product of all the values of all the domains, in the right order. In python, the typing is not as good as it can be to create perfect typings for this situation, so we will create custom override methods to overcome the situation. Here’s our implementation of product of 2, 3, and n domains. We just need to implement an n-product, and the 2 and 3 are just useful overrides with types:

Now that we have a product implementation, writing a 2- or 3- variable solver is very simple. Let’s add those:

That’s literally how easy it is. Let’s go back to solving the problem!

Resuming our solution to the straight line problem

This is much easier with our domain abstraction and product of domains

Now that we have an abstraction for domain, and a way to create a product of 2 domains, it’s way easier to solve for the straight line. Let’s try that:

Wow, looks like with these powerful abstractions, it’s a piece of cake to write a solver for 2 variables, provided they have a domain. But we also made the solver generic. What else can we solve?

Testing out our abstractions with more problems

A satisfying way to test out abstractions you create is to feed them more problems

To see how powerful they are, we’re going to run through a few more problems, where we try to use the abstractions we’ve defined so far. Here’s a way to find values for A, B where A XOR B:

Since we’ve tested for cases where both the domains are the same type, here’s a problem where the domains are different types. Find strings of a certain length:

Here’s us trying to find 5 natural numbers less than 15, that add up to 15:

Since we have a typed solver for 3 variables, we can find 3 numbers that sum to 7 in a typed fashion:

Note that we’re only using the typed version for convenience. We could totally use the generic abstractions if we wanted to, using the default brute_force function. Here’s us trying to solve the same problem using a weakly typed domain:

Inspecting the value of xs in this lambda you’d see that it’s of type Any , making it not type-check. But it works all the same.

Conclusion

Well there’s always time for another post!

In this post, we saw how adding a simple abstraction opens the door to solving a variety of problems. We also saw the difference between strongly and weakly typed abstractions providing different levels of type safety while providing the same results at run-time.

In the next post, we’ll be trying to solve the n queens problem using brute-force search. That would be really interesting. Until then, have fun!

For more fun:
Try to come up with an iterable-based domain, that can take an iterable of type T and create a domain out of it. For example, I should be able to create domains for ranges of integers, or lists of strings.