Question
I want to return True if and only if 3 out of 4 boolean values are true.
The closest I've gotten is (x ^ y) ^ (a ^ b):
What should I do?
Solution
I suggest writing the code in a manner that indicates what you mean. If you want 3 values to be true, it seems natural to me that the value 3 appears somewhere.
For instance, in C++:
https://stackoverflow.com/questions/22240396
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianif ((int)a + (int)b + (int)c + (int)d == 3)
...
This is well defined in C++: the standard (§4.7/4) indicates that converting bool to int gives the expected values 0 or 1.
In Java and C#, you can use the following construct:
if ((a?1:0) + (b?1:0) + (c?1:0) + (d?1:0) == 3)
...
OTHER TIPS
#1: Using a branching ?: 3 or 4 operations
A ^ B ? C & D : ( C ^ D ) & A
#2 Non-Branching, 7 operations
(A ^ B ^ C ^ D) & ((A & B) | (C & D))
Back when I use to profile everything, I found non-branching solutions were quite a bit quicker operation-for-operation as the CPU could predict the code path better, and execute more operations in tandem. There is about 50% less work in the branching statement here though.
If this had been Python, I would have written
if [a, b, c, d].count(True) == 3:
Or
if [a, b, c, d].count(False) == 1:
Or
if [a, b, c, d].count(False) == True:
# In Python True == 1 and False == 0
Or
print [a, b, c, d].count(0) == 1
Or
print [a, b, c, d].count(1) == 3
Or
if a + b + c + d == 3:
Or
if sum([a, b, c, d]) == 3:
All these work, since Booleans are subclasses of integers in Python.
if len(filter(bool, [a, b, c, d])) == 3:
Or, inspired by this neat trick,
data = iter([a, b, c, d])
if not all(data) and all(data):
Long but very simple, (disjuntive) normal form:
(~a & b & c & d) | (a & ~b & c & d) | (a & b & ~c & d) | (a & b & c & ~d)
It may be simplified but that requires more thinking :P
Not sure it is simpler, but maybe.
If you want to use this logic in a programming language, my suggestion is
bool test(bool a, bool b, bool c, bool d){
int n1 = a ? 1 : 0;
int n2 = b ? 1 : 0;
int n3 = c ? 1 : 0;
int n4 = d ? 1 : 0;
return n1 + n2 + n3 + n4 == 3;
}
Or if you want, you can put all of these in a single line:
return (a ? 1 : 0) + (b ? 1 : 0) + (C ? 1 : 0) + (d ? 1 : 0) == 3;
Also you can generalize this problem to n of m :
bool test(bool *values, int n, int m){
int sum = 0;
for(int i = 0; i < m; i += 1){
sum += values[i] ? 1 : 0;
}
return sum == n;
}
This answer depends on the system of representation, but if 0 is the only value interpreted as false, and not(false) always returns the same numeric value, then not(a) + not(b) + not(c) + not(d) = not(0) should do the trick.
Keeping in mind that SO if for programming questions, rather than mere logical problems, the answer obviously depends on the choice of a programming language. Some languages support features that are uncommon to others.
For example, in C++ you could test your conditions with:
(a + b + c + d) == 3
This should be the fastest way to do the check in languages that support automatic (low-level) conversion from boolean to integer types. But again, there is no general answer for that problem.
The best I can do is ((x ^ y) ^ (a ^ b)) && ((a || x) && (b || y))
((a xor b) xor (c xor d)) and ((a or b) and (c or d))
The fist expression searchs for 1 or 3 true's out of 4. The second one eliminates 0 or 1 (and sometimes 2) true's out of 4.
Java 8, filter out the false values, and count the remaining true values:
public static long count(Boolean... values) {
return Arrays.stream(values).filter(t -> t).count();
}
Then you can use it as follows:
if (3 == count(a, b, c, d)) {
System.out.println("There... are... THREE... lights!");
}
Easily generalizes to checking for n of m items being true.
To check at least n out of all Boolean are true, ( n must be less than or equal to total number of Boolean :p)
if (((a ? 1:0) + (b ? 1:0 ) + (c ? 1:0) + (d ? 1:0 )) >= n) {
// do the rest
}
Edit : After @Cruncher's comment
To check 3 boolean out of 4
if (((a ? 1:0) + (b ? 1:0 ) + (c ? 1:0) + (d ? 1:0 )) == 3) {
// do the rest
}
Another one :
Here's a way you could solve it in C# with LINQ:
bool threeTrue = new[] { a, b, x, y }.Count(x => x) == 3;
That is the symmetric Boolean function S₃(4). A symmetric Boolean function is a boolean function which only depends on the quantity of inputs set, but doesn't depend on which inputs they are. Knuth mentions functions of this type in section 7.1.2 in Volume 4 of The Art of Computer Programming.
S₃(4) can be computed with 7 operations as follows:
(x && y && (a || b)) ^ ((x || y) && a && b)
Knuth shows that this is optimal, meaning that you cannot do this in less than 7 operations using the normal operators: &&, || , ^, <, and >.
However if you want to use this in a language which uses 1 for true and 0 for false, you can also use addition easily:
x + y + a + b == 3
which makes your intention quite clear.
(a && b && (c xor d)) || (c && d && (a xor b))
From a pure logic point of view this is what I came up with.
By the pigeon hole principle, if exactly 3 are true, then either a and b is true, or c and d is true. Then its just a matter of anding each of those cases with exactly one of the other 2.
If you use a logic visualization tool like Karnaugh Maps, you see that this is a problem where you can't avoid a full blown logic term if you want to write it in one if (...) line. Lopina showed it already, it's not possible to write it simpler. You can factor out a bit, but it will stay hard to read for you AND for the machine.
Counting solutions are not bad and they show what you are really after. How you do the counting efficiently depends on your programming language. The array solutions with Python oder LinQ are nice to look at, but beware, this is SLOW. Wolf's (a+b+x+y)==3 will work nicely and fast, but only if your language equates "true" with 1. If "true" is represented by -1, you will have to test for -3 :)
If your language uses true booleans, you could try to program it explicitly (I use != as XOR test):
if (a)
{
if (b)
return (x != y); // a,b=true, so either x or y must be true
else
return (x && y); // a=true, b=false, so x AND y must be true
}
else
{
if (b)
return (x && y); // a=false, b=true, so x and y must be true
else
return false; // a,b false, can't get 3 of 4
}
"x != y" works only if x,y are of a boolean type. If they are some other type where 0 is false and everything else is true, this can fail. Then use a boolean XOR, or ( (bool)x != (bool)y ), or write "if (x) return (y==false) else return (y==true);", which is a bit more work for the computer.
If your programming language provides the ternary ?: operator, you can shorten it to
if (a)
return b ? (x != y) : (x && y);
else
return b ? (x && y) : false;
which keeps a bit of readability, or cut it aggressively to
return a ? (b ? (x != y) : (x && y)) : (b ? (x && y) : false);
This code does exactly three logic tests (state of a, state of b, comparison of x and y) and should be faster than most of the other answers here. But you need to comment it, or you won't understand it after 3 months :)
There are a lot of good answers here; here is an alternate formulation which no one else has posted yet:
a ? (b ? (c ^ d) : (c && d)) : (b && c && d)
Similar to the first answer, but pure Java:
int t(boolean b) {
return (b) ? 1 : 0;
}
if (t(x) + t(y) + t(a) + t(b) == 3) return true;
return false;
I prefer counting them as integers because it makes for more readable code.
In Python, to see how many of an iterable of elements are True, use sum (it's quite straightforward):
Setup
import itertools
arrays = list(itertools.product(*[[True, False]]*4))
Actual Test
for array in arrays:
print(array, sum(array)==3)
Output
(True, True, True, True) False
(True, True, True, False) True
(True, True, False, True) True
(True, True, False, False) False
(True, False, True, True) True
(True, False, True, False) False
(True, False, False, True) False
(True, False, False, False) False
(False, True, True, True) True
(False, True, True, False) False
(False, True, False, True) False
(False, True, False, False) False
(False, False, True, True) False
(False, False, True, False) False
(False, False, False, True) False
(False, False, False, False) False
If you're after the on-the-paper (non-programming) solution, then K-maps and Quine-McCluskey algorithms are what you're after, they help you minify your boolean function.
In your case, the result is
y = (x̄3 ^ x2 ^ x1 ^ x0) ∨ (x3 ^ x̄2 ^ x1 ^ x0) ∨ (x3 ^ x2 ^ x̄1 ^ x0) ∨ (x3 ^ x2 ^ x1 ^ x̄0)
If you want to do this programmatically, non-fixed amount of variables and a custom "threshold", then simply iterating thru a list of boolean values and counting occurrences of "true" is pretty simple and straightforward.
I want to return true if and only if 3 out of 4 boolean values are true.
Given the 4 boolean values, a, b, x, y, this task translates into the following C statement:
return (a+b+x+y) == 3;
((a^b)^(x^y))&((a|b)&(x|y))
is what you want. Basically I took your code and added checking if actually 3 are true and not 3 are false.
A programming question without an answer involving recursion? Inconceivable!
There are enough "exactly 3 out of 4 trues" answers, but here's a generalised (Java) version for "exactly m out of n trues" (otherwise recursion isn't really worth it) just because you can:
public static boolean containsTrues(boolean[] someBooleans,
int anIndex, int truesExpected, int truesFoundSoFar) {
if (anIndex >= someBooleans.length) {
return truesExpected == truesFoundSoFar; // reached end
}
int falsesExpected = someBooleans.length - truesExpected;
boolean currentBoolean = someBooleans[anIndex];
int truesFound = truesFoundSoFar + (currentBoolean ? 1 : 0);
if (truesFound > truesExpected) {
return false;
}
if (anIndex - truesFound > falsesExpected) {
return false; // too many falses
}
return containsTrues(someBooleans, anIndex + 1, truesExpected,
truesFound);
}
This could be called with something like:
boolean[] booleans = { true, false, true, true, false, true, true, false };
containsTrues(booleans, 0, 5, 0);
which should return true (because 5 of 8 values were true, as expected). Not quite happy with the words "trues" and "falses", but can't think of a better name right now.... Note that the recursion stops when too many true or too many false values have been found.
Since readability is a big concern, you could use a descriptive function call (wrapping any of the suggested implementations). If this calculation needs to be done in multiple places, a function call is the best way to achieve reuse, and makes it clear exactly what you are doing.
bool exactly_three_true_from(bool cond1, bool cond2, bool cond3, bool cond4)
{
//...
}
In PHP, making it more dynamic (just in case you change number of conditions, etc.):
$min = 6;
$total = 10;
// create our boolean array values
$arr = array_map(function($a){return mt_rand(0,1)>0;},range(1,$total));
// the 'check'
$arrbools = array_map(function($a){return (int)$a;},$arr);
$conditionMet = array_sum($arrbools)>=$min;
echo $conditionMet ? "Passed" : "Failed";
(((a AND b) OR (x AND y)) AND ((a XOR b) OR (x XOR y)))
While I could show that this is a good solution, Sam Hocevar's answer is easy both to write and understand later. In my book that makes it better.
Here is some c# code I just wrote because you have inspired me:
It takes any amount of arguments and will tell you if n of them are true.
static bool boolTester(int n, params bool[] values)
{
int sum = 0;
for (int i = 0; i < values.Length; i++)
{
if (values[i] == true)
{
sum += 1;
}
}
if( sum == n)
{
return true;
}
return false;
}
and you call it like so:
bool a = true;
bool b = true;
bool c = true;
bool d = false;
bool test = false;
test = boolTester(3, a, b, c, d);
So you can now test 7/9 or 15/100 as you will.
