Vérifiez si au moins deux booléens sur trois sont vrais

Un intervieweur m'a récemment posé cette question: étant donné trois variables booléennes, a, b et c, retourne vrai si au moins deux des trois sont vraies.

Ma solution suit:

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    if ((a && b) || (b && c) || (a && c)) {
        return true;
    }
    else{
        return false;
    }
}

Il a dit que cela pouvait encore être amélioré, mais comment?

Plutôt que d'écrire:

if (someExpression) {
    return true;
} else {
    return false;
}

Écrire:

return someExpression;

Quant à l'expression elle-même, quelque chose comme ceci:

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    return a ? (b || c) : (b && c);
}

ou ceci (selon ce que vous trouvez plus facile à saisir):

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    return a && (b || c) || (b && c);
}

Il teste aet bexactement une fois, et cau plus une fois.

Références

• Opérateur conditionnel JLS 15.25? :

Juste pour le plaisir d'utiliser XOR pour répondre à un problème relativement simple ...

return a ^ b ? c : a

Pourquoi ne pas l'implémenter littéralement? :)

(a?1:0)+(b?1:0)+(c?1:0) >= 2

En C, vous pouvez simplement écrire a+b+c >= 2(ou !!a+!!b+!!c >= 2pour être très sûr).

En réponse à la comparaison de TofuBeer du bytecode java, voici un test de performance simple:

class Main
{
    static boolean majorityDEAD(boolean a,boolean b,boolean c)
    {
        return a;
    }

    static boolean majority1(boolean a,boolean b,boolean c)
    {
        return a&&b || b&&c || a&&c;
    }

    static boolean majority2(boolean a,boolean b,boolean c)
    {
        return a ? b||c : b&&c;
    }

    static boolean majority3(boolean a,boolean b,boolean c)
    {
        return a&b | b&c | c&a;
    }

    static boolean majority4(boolean a,boolean b,boolean c)
    {
        return (a?1:0)+(b?1:0)+(c?1:0) >= 2;
    }

    static int loop1(boolean[] data, int i, int sz1, int sz2)
    {
        int sum = 0;
        for(int j=i;j<i+sz1;j++)
        {
            for(int k=j;k<j+sz2;k++)
            {
                sum += majority1(data[i], data[j], data[k])?1:0; 
                sum += majority1(data[i], data[k], data[j])?1:0; 
                sum += majority1(data[j], data[k], data[i])?1:0; 
                sum += majority1(data[j], data[i], data[k])?1:0; 
                sum += majority1(data[k], data[i], data[j])?1:0; 
                sum += majority1(data[k], data[j], data[i])?1:0; 
            }
        }
        return sum;
    }

    static int loop2(boolean[] data, int i, int sz1, int sz2)
    {
        int sum = 0;
        for(int j=i;j<i+sz1;j++)
        {
            for(int k=j;k<j+sz2;k++)
            {
                sum += majority2(data[i], data[j], data[k])?1:0; 
                sum += majority2(data[i], data[k], data[j])?1:0; 
                sum += majority2(data[j], data[k], data[i])?1:0; 
                sum += majority2(data[j], data[i], data[k])?1:0; 
                sum += majority2(data[k], data[i], data[j])?1:0; 
                sum += majority2(data[k], data[j], data[i])?1:0; 
            }
        }
        return sum;
    }

    static int loop3(boolean[] data, int i, int sz1, int sz2)
    {
        int sum = 0;
        for(int j=i;j<i+sz1;j++)
        {
            for(int k=j;k<j+sz2;k++)
            {
                sum += majority3(data[i], data[j], data[k])?1:0; 
                sum += majority3(data[i], data[k], data[j])?1:0; 
                sum += majority3(data[j], data[k], data[i])?1:0; 
                sum += majority3(data[j], data[i], data[k])?1:0; 
                sum += majority3(data[k], data[i], data[j])?1:0; 
                sum += majority3(data[k], data[j], data[i])?1:0; 
            }
        }
        return sum;
    }

    static int loop4(boolean[] data, int i, int sz1, int sz2)
    {
        int sum = 0;
        for(int j=i;j<i+sz1;j++)
        {
            for(int k=j;k<j+sz2;k++)
            {
                sum += majority4(data[i], data[j], data[k])?1:0; 
                sum += majority4(data[i], data[k], data[j])?1:0; 
                sum += majority4(data[j], data[k], data[i])?1:0; 
                sum += majority4(data[j], data[i], data[k])?1:0; 
                sum += majority4(data[k], data[i], data[j])?1:0; 
                sum += majority4(data[k], data[j], data[i])?1:0; 
            }
        }
        return sum;
    }

    static int loopDEAD(boolean[] data, int i, int sz1, int sz2)
    {
        int sum = 0;
        for(int j=i;j<i+sz1;j++)
        {
            for(int k=j;k<j+sz2;k++)
            {
                sum += majorityDEAD(data[i], data[j], data[k])?1:0; 
                sum += majorityDEAD(data[i], data[k], data[j])?1:0; 
                sum += majorityDEAD(data[j], data[k], data[i])?1:0; 
                sum += majorityDEAD(data[j], data[i], data[k])?1:0; 
                sum += majorityDEAD(data[k], data[i], data[j])?1:0; 
                sum += majorityDEAD(data[k], data[j], data[i])?1:0; 
            }
        }
        return sum;
    }

    static void work()
    {
        boolean [] data = new boolean [10000];
        java.util.Random r = new java.util.Random(0);
        for(int i=0;i<data.length;i++)
            data[i] = r.nextInt(2) > 0;
        long t0,t1,t2,t3,t4,tDEAD;
        int sz1 = 100;
        int sz2 = 100;
        int sum = 0;

        t0 = System.currentTimeMillis();

        for(int i=0;i<data.length-sz1-sz2;i++)
            sum += loop1(data, i, sz1, sz2);

        t1 = System.currentTimeMillis();

        for(int i=0;i<data.length-sz1-sz2;i++)
            sum += loop2(data, i, sz1, sz2);

        t2 = System.currentTimeMillis();

        for(int i=0;i<data.length-sz1-sz2;i++)
            sum += loop3(data, i, sz1, sz2);

        t3 = System.currentTimeMillis();

        for(int i=0;i<data.length-sz1-sz2;i++)
            sum += loop4(data, i, sz1, sz2);

        t4 = System.currentTimeMillis();

        for(int i=0;i<data.length-sz1-sz2;i++)
            sum += loopDEAD(data, i, sz1, sz2);

        tDEAD = System.currentTimeMillis();

        System.out.println("a&&b || b&&c || a&&c : " + (t1-t0) + " ms");
        System.out.println("   a ? b||c : b&&c   : " + (t2-t1) + " ms");
        System.out.println("   a&b | b&c | c&a   : " + (t3-t2) + " ms");
        System.out.println("   a + b + c >= 2    : " + (t4-t3) + " ms");
        System.out.println("       DEAD          : " + (tDEAD-t4) + " ms");
        System.out.println("sum: "+sum);
    }

    public static void main(String[] args) throws InterruptedException
    {
        while(true)
        {
            work();
            Thread.sleep(1000);
        }
    }
}

Cela affiche les éléments suivants sur ma machine (exécutant Ubuntu sur Intel Core 2 + sun java 1.6.0_15-b03 avec HotSpot Server VM (14.1-b02, mode mixte)):

Première et deuxième itérations:

a&&b || b&&c || a&&c : 1740 ms
   a ? b||c : b&&c   : 1690 ms
   a&b | b&c | c&a   : 835 ms
   a + b + c >= 2    : 348 ms
       DEAD          : 169 ms
sum: 1472612418

Itérations ultérieures:

a&&b || b&&c || a&&c : 1638 ms
   a ? b||c : b&&c   : 1612 ms
   a&b | b&c | c&a   : 779 ms
   a + b + c >= 2    : 905 ms
       DEAD          : 221 ms

Je me demande ce que pourrait faire une machine virtuelle Java qui dégrade les performances au fil du temps pour (a + b + c> = 2).

Et voici ce qui se passe si j'exécute java avec un -clientcommutateur VM:

a&&b || b&&c || a&&c : 4034 ms
   a ? b||c : b&&c   : 2215 ms
   a&b | b&c | c&a   : 1347 ms
   a + b + c >= 2    : 6589 ms
       DEAD          : 1016 ms

Mystère...

Et si je l'exécute dans GNU Java Interpreter , cela devient presque 100 fois plus lent, mais la a&&b || b&&c || a&&cversion gagne alors.

Résultats de Tofubeer avec le dernier code fonctionnant sous OS X:

a&&b || b&&c || a&&c : 1358 ms
   a ? b||c : b&&c   : 1187 ms
   a&b | b&c | c&a   : 410 ms
   a + b + c >= 2    : 602 ms
       DEAD          : 161 ms

Résultats de Paul Wagland avec un Mac Java 1.6.0_26-b03-383-11A511

a&&b || b&&c || a&&c : 394 ms 
   a ? b||c : b&&c   : 435 ms
   a&b | b&c | c&a   : 420 ms
   a + b + c >= 2    : 640 ms
   a ^ b ? c : a     : 571 ms
   a != b ? c : a    : 487 ms
       DEAD          : 170 ms

Ce type de questions peut être résolu avec une carte de Karnaugh :

      | C | !C
------|---|----
 A  B | 1 | 1 
 A !B | 1 | 0
!A !B | 0 | 0
!A  B | 1 | 0

à partir de laquelle vous déduisez que vous avez besoin d'un groupe pour la première ligne et de deux groupes pour la première colonne, obtenant la solution optimale de lubrifiants polygéniques:

(C && (A || B)) || (A && B)  <---- first row
       ^
       |
   first column without third case

La lisibilité devrait être l'objectif. Une personne qui lit le code doit comprendre immédiatement votre intention. Voici donc ma solution.

int howManyBooleansAreTrue =
      (a ? 1 : 0)
    + (b ? 1 : 0)
    + (c ? 1 : 0);

return howManyBooleansAreTrue >= 2;

return (a==b) ? a : c;

Explication:

Si a==b, alors les deux sont vrais ou les deux sont faux. Si les deux sont vrais, nous avons trouvé nos deux vrais booléens et pouvons retourner vrai (en revenant a). Si les deux sont faux, il ne peut pas y avoir deux vrais booléens même si cc'est vrai, donc nous retournons faux (en revenant a). Voilà la (a==b) ? apartie. Et alors : c? Eh bien, si a==best faux, alors exactement l'un de aou bdoit être vrai, nous avons donc trouvé le premier vrai booléen, et la seule chose qui reste est si cest également vrai, alors nous revenons ccomme réponse.

Vous n'avez pas besoin d'utiliser les formes de court-circuit des opérateurs.

return (a & b) | (b & c) | (c & a);

Cela effectue le même nombre d'opérations logiques que votre version, mais est complètement sans branche.

Voici une approche générale pilotée par les tests. Pas aussi "efficace" que la plupart des solutions proposées jusqu'à présent, mais claire, testée, fonctionnelle et généralisée.

public class CountBooleansTest extends TestCase {
    public void testThreeFalse() throws Exception {
        assertFalse(atLeastTwoOutOfThree(false, false, false));
    }

    public void testThreeTrue() throws Exception {
        assertTrue(atLeastTwoOutOfThree(true, true, true));
    }

    public void testOnes() throws Exception {
        assertFalse(atLeastTwoOutOfThree(true, false, false));
        assertFalse(atLeastTwoOutOfThree(false, true, false));
        assertFalse(atLeastTwoOutOfThree(false, false, true));
    }

    public void testTwos() throws Exception {
        assertTrue(atLeastTwoOutOfThree(false, true, true));
        assertTrue(atLeastTwoOutOfThree(true, false, true));
        assertTrue(atLeastTwoOutOfThree(true, true, false));
    }

    private static boolean atLeastTwoOutOfThree(boolean b, boolean c, boolean d) {
        return countBooleans(b, c, d) >= 2;
    }

    private static int countBooleans(boolean... bs) {
        int count = 0;
        for (boolean b : bs)
            if (b)
                count++;
        return count;
    }
}

Résumer. Cela s'appelle l'algèbre booléenne pour une raison:

  0 x 0 = 0
  1 x 0 = 0
  1 x 1 = 1

  0 + 0 = 0
  1 + 0 = 1
  1 + 1 = 0 (+ carry)

Si vous regardez les tables de vérité là-bas, vous pouvez voir que la multiplication est booléenne et, et simplement l'addition est xor.

Pour répondre à ta question:

return (a + b + c) >= 2

boolean atLeastTwo(boolean a, boolean b, boolean c) 
{
  return ((a && b) || (b && c) || (a && c));
}

Cela dépend vraiment de ce que vous entendez par «amélioré»:

Plus clair?

boolean twoOrMoreAreTrue(boolean a, boolean b, boolean c)
{
    return (a && b) || (a && c) || (b && c);
}

Terser?

boolean moreThanTwo(boolean a, boolean b, boolean c)
{
    return a == b ? a : c;
}

Plus général?

boolean moreThanXTrue(int x, boolean[] bs)
{
    int count = 0;

    for(boolean b : bs)
    {
        count += b ? 1 : 0;

        if(count > x) return true;
    }

    return false;
}

Plus évolutif?

boolean moreThanXTrue(int x, boolean[] bs)
{
    int count = 0;

    for(int i < 0; i < bs.length; i++)
    {
        count += bs[i] ? 1 : 0;

        if(count > x) return true;

        int needed = x - count;
        int remaining = bs.length - i;

        if(needed >= remaining) return false;
    }

    return false;
}

Plus rapide?

// Only profiling can answer this.

Laquelle est "améliorée" dépend fortement de la situation.

Voici une autre implémentation utilisant map / Reduce. Cela évolue bien à des milliards de booléens ^© dans un environnement distribué. Utilisation de MongoDB:

Création d'une base valuesde données de booléens:

db.values.insert({value: true});
db.values.insert({value: false});
db.values.insert({value: true});

Création de la carte, réduction des fonctions:

Edit : J'aime la réponse de CurtainDog à propos de l'application de map / réduire aux listes génériques, alors voici une fonction de carte qui prend un rappel qui détermine si une valeur doit être comptée ou non.

var mapper = function(shouldInclude) {
    return function() {
        emit(null, shouldInclude(this) ? 1 : 0);
    };
}

var reducer = function(key, values) {
    var sum = 0;
    for(var i = 0; i < values.length; i++) {
        sum += values[i];
    }
    return sum;
}

Exécution de la carte / réduction:

var result = db.values.mapReduce(mapper(isTrue), reducer).result;

containsMinimum(2, result); // true
containsMinimum(1, result); // false


function isTrue(object) {
    return object.value == true;
}

function containsMinimum(count, resultDoc) {
    var record = db[resultDoc].find().next();
    return record.value >= count;
}

Prendre les réponses (jusqu'à présent) ici:

public class X
{
    static boolean a(final boolean a, final boolean b, final boolean c)
    {
    return ((a && b) || (b && c) || (a && c));
    }

    static boolean b(final boolean a, final boolean b, final boolean c)
    {
    return a ? (b || c) : (b && c);
    }

    static boolean c(final boolean a, final boolean b, final boolean c)
    {
    return ((a & b) | (b & c) | (c & a));
    }

    static boolean d(final boolean a, final boolean b, final boolean c)
    {
    return ((a?1:0)+(b?1:0)+(c?1:0) >= 2);
    }
}

et les exécuter via le décompilateur (javap -c X> results.txt):

Compiled from "X.java"
public class X extends java.lang.Object{
public X();
  Code:
   0:   aload_0
   1:   invokespecial   #1; //Method java/lang/Object."<init>":()V
   4:   return

static boolean a(boolean, boolean, boolean);
  Code:
   0:   iload_0
   1:   ifeq    8
   4:   iload_1
   5:   ifne    24
   8:   iload_1
   9:   ifeq    16
   12:  iload_2
   13:  ifne    24
   16:  iload_0
   17:  ifeq    28
   20:  iload_2
   21:  ifeq    28
   24:  iconst_1
   25:  goto    29
   28:  iconst_0
   29:  ireturn

static boolean b(boolean, boolean, boolean);
  Code:
   0:   iload_0
   1:   ifeq    20
   4:   iload_1
   5:   ifne    12
   8:   iload_2
   9:   ifeq    16
   12:  iconst_1
   13:  goto    33
   16:  iconst_0
   17:  goto    33
   20:  iload_1
   21:  ifeq    32
   24:  iload_2
   25:  ifeq    32
   28:  iconst_1
   29:  goto    33
   32:  iconst_0
   33:  ireturn

static boolean c(boolean, boolean, boolean);
  Code:
   0:   iload_0
   1:   iload_1
   2:   iand
   3:   iload_1
   4:   iload_2
   5:   iand
   6:   ior
   7:   iload_2
   8:   iload_0
   9:   iand
   10:  ior
   11:  ireturn

static boolean d(boolean, boolean, boolean);
  Code:
   0:   iload_0
   1:   ifeq    8
   4:   iconst_1
   5:   goto    9
   8:   iconst_0
   9:   iload_1
   10:  ifeq    17
   13:  iconst_1
   14:  goto    18
   17:  iconst_0
   18:  iadd
   19:  iload_2
   20:  ifeq    27
   23:  iconst_1
   24:  goto    28
   27:  iconst_0
   28:  iadd
   29:  iconst_2
   30:  if_icmplt   37
   33:  iconst_1
   34:  goto    38
   37:  iconst_0
   38:  ireturn
}

Vous pouvez voir que les?: Ceux sont légèrement meilleurs que la version corrigée de votre original. Celui qui est le meilleur est celui qui évite complètement les branchements. C'est bon du point de vue de moins d'instructions (dans la plupart des cas) et mieux pour les parties de prédiction de branche du CPU, car une mauvaise estimation dans la prédiction de branche peut entraîner le blocage du CPU.

Je dirais que le plus efficace est celui de moonshadow dans l'ensemble. Il utilise le moins d'instructions en moyenne et réduit les risques de blocage du pipeline dans le CPU.

Pour être sûr à 100%, vous devrez connaître le coût (en cycles de processeur) de chaque instruction, qui, malheureusement, n'est pas facilement disponible (vous devrez consulter la source du point d'accès puis les spécifications des fournisseurs de CPU pour le moment). prises pour chaque instruction générée).

Voir la réponse mise à jour par Rotsor pour une analyse d'exécution du code.

Un autre exemple de code direct:

int  n = 0;
if (a) n++;
if (b) n++;
if (c) n++;
return (n >= 2);

Ce n'est évidemment pas le code le plus succinct.

Addenda

Une autre version (légèrement optimisée) de ceci:

int  n = -2;
if (a) n++;
if (b) n++;
if (c) n++;
return (n >= 0);

Cela peut s'exécuter légèrement plus rapidement, en supposant que la comparaison avec 0 utilisera du code plus rapide (ou peut-être moins) que la comparaison avec 2.

Encore une autre façon de le faire, mais pas très bonne:

return (Boolean.valueOf(a).hashCode() + Boolean.valueOf(b).hashCode() + Boolean.valueOf(c).hashCode()) < 3705);

Les Booleanvaleurs du code de hachage sont fixées à 1231 pour true et 1237 pour false, donc auraient également pu utiliser<= 3699

Les améliorations les plus évidentes sont les suivantes:

// There is no point in an else if you already returned.
boolean atLeastTwo(boolean a, boolean b, boolean c) {
    if ((a && b) || (b && c) || (a && c)) {
        return true;
    }
    return false;
}

et alors

// There is no point in an if(true) return true otherwise return false.
boolean atLeastTwo(boolean a, boolean b, boolean c) {
    return ((a && b) || (b && c) || (a && c));
}

Mais ces améliorations sont mineures.

Je n'aime pas le ternaire (d' return a ? (b || c) : (b && c);après la première réponse), et je ne pense pas avoir vu quelqu'un le mentionner. Il est écrit comme ceci:

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    if (a) {
        return b||c;
    } 
    else {
        return b&&C;
    }

À Clojure :

(defn at-least [n & bools]
  (>= (count (filter true? bools)) n)

Usage:

(at-least 2 true false true)

Je ne pense pas avoir encore vu cette solution:

boolean atLeast(int howMany, boolean[] boolValues) {
  // check params for valid values

  int counter = 0;
  for (boolean b : boolValues) {
    if (b) {
      counter++;

      if (counter == howMany) {
        return true;
      }
    }
  }
  return false;
}

Son avantage est qu'une fois qu'il atteint le nombre que vous recherchez, il casse. Donc, si c'était "au moins 2 de ces 1 000 000 valeurs sont vraies" alors que les deux premières sont réellement vraies, alors cela devrait aller plus vite que certaines des solutions les plus "normales".

Nous pouvons convertir les bools en entiers et effectuer cette vérification facile:

(int(a) + int(b) + int(c)) >= 2

Comme il n'a pas été précisé comment le code doit être amélioré, je m'efforcerai d'améliorer le code en le rendant plus amusant. Voici ma solution:

boolean atLeastTwo(boolean t, boolean f, boolean True) {
    boolean False = True;
    if ((t || f) && (True || False)) 
        return "answer" != "42";
    if (t && f) 
        return !"France".contains("Paris");
    if (False == True) 
        return true == false;
    return Math.random() > 0.5;
}

Si quelqu'un se demande si ce code fonctionne, voici une simplification utilisant la même logique:

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    if ((a || b) && (c)) 
        return true;
    if (a && b) 
        return true;
    if (true) 
        return false;
    // The last line is a red herring, as it will never be reached:
    return Math.random() > 0.5; 

}

Cela peut se résumer comme suit:

return ((a || b) && (c)) || (a && b);

Mais maintenant ce n'est plus drôle.

Function ReturnTrueIfTwoIsTrue(bool val1, val2, val3))
{
     return (System.Convert.ToInt16(val1) +
             System.Convert.ToInt16(val2) +
             System.Convert.ToInt16(val3)) > 1;
}

Trop de façons de le faire ...

Solution AC.

int two(int a, int b, int c) {
  return !a + !b + !c < 2;
}

ou vous pouvez préférer:

int two(int a, int b, int c) {
  return !!a + !!b + !!c >= 2;
}

return 1 << $a << $b << $c >= 1 << 2;

La manière la plus simple (IMO) qui n'est pas déroutante et facile à lire:

// Three booleans, check if two or more are true

return ( a && ( b || c ) ) || ( b && c );

Une interprétation littérale fonctionnera dans toutes les langues principales:

return (a ? 1:0) + (b ? 1:0) + (c ? 1:0) >= 2;

Mais je rendrais probablement la lecture plus facile, et extensible à plus de trois - quelque chose qui semble être oublié par de nombreux programmeurs:

boolean testBooleans(Array bools)
{
     int minTrue = ceil(bools.length * .5);
     int trueCount = 0;

     for(int i = 0; i < bools.length; i++)
     {
          if(bools[i])
          {
               trueCount++;
          }
     }
     return trueCount >= minTrue;
}

En complément de l'excellent message de @TofuBeer TofuBeer, considérez la réponse de @pdox pdox:

static boolean five(final boolean a, final boolean b, final boolean c)
{
    return a == b ? a : c;
}

Considérez également sa version démontée comme donnée par "javap -c":

static boolean five(boolean, boolean, boolean);
  Code:
    0:    iload_0
    1:    iload_1
    2:    if_icmpne    9
    5:    iload_0
    6:    goto    10
    9:    iload_2
   10:    ireturn

La réponse de pdox se compile en moins de code d'octet que n'importe laquelle des réponses précédentes. Comment son temps d'exécution se compare-t-il aux autres?

one                5242 ms
two                6318 ms
three (moonshadow) 3806 ms
four               7192 ms
five  (pdox)       3650 ms

Au moins sur mon ordinateur, la réponse de pdox est juste un peu plus rapide que la réponse de @moonshadow moonshadow, faisant de pdox la plus rapide dans l'ensemble (sur mon ordinateur portable HP / Intel).

En rubis:

[a, b, c].count { |x| x } >= 2

Qui pourrait être exécuté dans JRuby sur JavaVM. ;-)

Il ne cherche probablement rien de compliqué comme les opérateurs de comparaison au niveau du bit (pas normalement compliqué mais avec des booléens, il est extrêmement étrange d'utiliser des opérateurs au niveau du bit) ou quelque chose de très détourné comme la conversion en int et leur résumé.

La façon la plus directe et la plus naturelle de résoudre ce problème est d'utiliser une expression comme celle-ci:

a ? (b || c): (b && c)

Mettez-le dans une fonction si vous préférez, mais ce n'est pas très compliqué. La solution est logiquement concise et efficace.

En C:

return !!a + !!b + !!c >= 2;