How to write code that can solve logic without a loop
Using integer linear programming to solve complex logic
Imagine the following scenario. You have a set of logical constraints. These constraints can only be satisfied by a certain combination of input variables. You need to write code that returns the valid input , i.e. one that satisfies all the logical constraints. One can proceed in two ways.
Option 1: Testing in a loop
The first idea is to come up with code that tests each possible input combination against the logic. Start with a list of all possible input combinations, pass each one of them to a loop containing all logical constraints, test each input combination against the constraints in the loop, repeat the process for all the possible combinations. In the end, return the combinations that satisfy all constraints. We can make such algorithms faster, more efficient, cleaner etc., but it doesn’t refute the fact that we still run a loop over all possibilities to return the right output.
Option 2: No-testing, no loop
There is no loop here whatsoever. This means a method where the code arrives at the answer without ‘testing’ anything. Instead of checking all possibilities one-by-one against the logical constraints, the constraints are ‘solved’ to arrive at the only possible outcome. The objective of the post it to show how one can write such a code.
The no-testing approach
The first idea that comes to mind is parallelisation. One would check the logical constraints in parallel and arrive at the right outcome. The problem is, even if we parallelise the code, we are still checking all possibilities against the constraints. The loop is still present in one form or another. This does not serve our purpose.
What if we could write logical constraints as linear equations? Doing so would reduce a bunch of if-else clauses into a set of linear equations. Then all that remains is solving those linear equations and finding the right answer! So is there a method where we can solve all linear constraints simultaneously to arrive at the right outcome? Yes there is. Solving a bunch of constraints simultaneously sounds a lot like linear programming (if the said constraints are linear in nature). If you followed my last post, or have come across linear programming you can guess where this is going. As I mentioned in my last post
A linear program finds an optimum solution for a problem where the variables are subject to numerous linear relationships.
So how can one write a logical constraint in the form of a linear relationship, i.e. a linear equation? The answer is by using binary variables and a bit of creativity. Let us consider the example of the AND logic gate. The output is TRUE if both the inputs are the same. In binary form, we can write 0 as FALSE (or OFF) and 1 as TRUE (or ON). Thus, I could write the equation for this gate with two inputs In1 and In2, where both can be either 0 or 1, as
Now that we understand how a logic gate can be transformed into a linear equation (in binary variables), we are ready to write a code that can actually solve a bunch of such constraints in one shot!
The challenge
I recently came across a puzzle in the periodical La Settimana Enigmastica, which I wanted to solve by writing a code that does not loop over all possibilities but instead solves for the right logical outcome. I paraphrase the problem below.
A person goes to a carousel operator at the fair. The carousel operator tells him that anyone who can guess what happens when he turns on all 5 switches gets free rides for life. The 5 switches do the following:
- Switch 1: Turns on red when yellow is on
- Switch 2: Red and green are never on together
- Switch 3: Blue and green can only be on and off together
- Switch 4: Blue and purple cannot be off at the same time
- Switch 5: If purple is on, blue and yellow have to be on
The approach: integer linear program
We will solve this problem by writing a code that does not really 'test' anything. It just solves the equations (logical constraints) and arrives at the answer.
First, let us define variables for coloured lights
- Y: Yellow
- R: Red
- G: Green
- B: Blue
- P: Purple
Each of these lights (or variables) can either be ON or OFF, and we further define
- value of 1: ON
- value of 0: OFF
By applying the same logic as we did for the AND gate, we will try and understand the logic behind each switch and write it as an equation. This will require us to first write down what the switch allows (or does not allow), and how those combinations can be expressed as a linear equation for each switch.
Switch 1: Turns on Red when Yellow is on
This allows for the following values for [Y,R]: [1,1],[0,1],[0,0].
Note that in the first case, Yellow is ON and Red is ON. In the second and third cases, if Yellow is OFF, Red could be ON or OFF as the condition does not say anything about the status of Red if Yellow is OFF. I can write it in equation form as
Switch 2: Red and Green are never on together
This allows for the following values of [R,G]: [0,0],[0,1], [1,0].
This is because both can be off together but not ON together. In equation form
Switch 3: Blue and Green can only be on and off together
The possible [B,G] combinations are: [0,0],[1,1]. As an equation
Switch 4: Blue and Purple cannot be off at the same time
The possible [B,P] combinations are: [0,1],[1,0],[1,1]. The condition does not say anything about them being ON together, hence the last option. As an equation
Switch 5: If Purple is on, Blue and Yellow have to be on
This condition is better seen as a combination of two sub-constraints.
If Purple is ON, Blue has to be ON and if Purple is ON, Yellow has to be ON.
It looks a lot like Switch 1 but we need to apply the logic twice, i.e.
maximum of Purple minus Blue is 0 and maximum of Purple minus Yellow is 0. Or in other words
Thus, the binary nature of our variables allowed us to re-write the logical constraints in a simple mathematical form. We express the above 4 inequalities (Switch 1,2,4,5) and one equality (Switch 3) in matrix form by writing
This is now beginning to look a lot like a linear program except all variables only take the value of 0 or 1 (a light can be either ON or OFF). A linear program (LP) where all variables can only assume integer values is called an integer linear program or an ILP. Ours is a special case 0–1 ILP as the variables are only allowed two values in order to simulate a boolean logic (note that an ILP is different from a mixed-integer linear program, or MILP, as in a MILP only some variables take integer values).
Cost function
So far I have not touched upon the cost function. In a linear program, a cost function is designed to optimise the result, i.e. minimise or maximise a linear combination of the variables we are solving for. In this particular case we are trying to find the (only) possible answer. So is there even something to optimise? I would say that in this case a cost function might not even be necessary as we are only checking the feasibility of the problem (the only possible answer). Thus, I define the cost function simply as a matrix containing five elements all equal to 0.
The problem is now reduced to a familiar LP construct
where of course the first condition (of minimising the cost function) is purely written for the sake of completeness.
Coding the problem in Python
My Python setup is as follows
- Python 3.8.2
- Numpy 1.4.1
- Cvxopt 1.2.3
My previous post discussed how one can implement a LP in Python using the optimize library in SciPy, and GLPK solver in CVXOPT. Our current problem at hand is an ILP, i.e. I only permit integer values (0,1 to be more specific) for my variables. The SciPy implementation in Python does not allow one to pass such constraints. However, this is certainly possible with other libraries.
The CVXOPT library with the GLPK solver allows you to specify which variables are binary in nature, i.e. assume either a 0 or 1 value. In our case, all our 5 variables are binary in nature thus the binary indices would be 0,1,2,3,4.
# define the indices of the variables that are binary in nature
# in our case all 5 variables are binaryBinary_ind = range(5)# …(rest of the code)…# pass these indices to the glpk ilp solver as a set
# of indices under the parameter ‘B’, i.e. binary indicesstatus, solution = glpk.ilp(c, A_ineq, B_ineq, A_eq, B_eq, B=set(Binary_ind))
Equipped with our matrix formulation and knowledge of how to tell the solver which variables are binary, we can now code up the problem as shown below.
This returns
solution found
Yellow is OFF , Red is OFF , Green is ON , Blue is ON , Purple is OFFWe have found the right answer!
The code for this article (and the previous one on LP) is hosted on my GitHub repo.
Outlook
A simple logical riddle prompted the exploration of the different ways it could be answered using Python. Furthermore, it forced me to ask the question ‘could you make the code mimic a human thought process?’.
In my opinion, a human thought process in such cases is one where we eliminate the clearly implausible solutions and reason our way through the remaining options. The ILP approach mimics this process, by limiting the solution space and only navigating a sub-set of possibilities, ultimately arriving at the right solution. This is very different to an ensemble of if-else conditions against which we test all possibilities. Thus by using an ILP in such cases, the plausible outcome of a set of logical constraints can be found in one go without actually going through all the possibilities.
