Puzzle Fontaine de Champagne

Les verres d'eau vides sont disposés dans l'ordre suivant:

Lorsque vous versez du liquide dans le premier verre s'il est plein, le liquide supplémentaire sera envoyé dans les verres 2 et 3 en quantités égales. Lorsque le verre 2 est plein, le liquide supplémentaire serait transporté en 4 et 5 et ainsi de suite.

Étant donné un N litres de liquide et la capacité maximale de chaque verre est de 1 litre, donnez la quantité de liquide présente dans n'importe quel verre si vous videz N litres de liquide en versant dans du verre en remplissant la fonction getWaterInBucket(int N, int X)où X est le numéro du verre. Donc par exemple si je veux avoir 4 litres au début et que je veux trouver l'eau dans le verre 3 la fonction estgetWaterInBucket(4, 3)

Comment résoudre ce problème par programme? J'ai essayé de trouver une solution mathématique en utilisant le triangle de Pascal. Cela n'a pas fonctionné. Je l'ai considéré comme un arbre, je peux donc ajouter un paramètre comme celui-ci getWaterInBucket(BTree root, int N, int X), puis essayer une solution récursive pour chaque niveau, mais les paramètres ne sont pas autorisés dans ce problème. Y a-t-il quelque chose d'évident, une astuce?

Vous avez juste besoin de simuler la coulée, quelque chose comme

void pour(double glasses[10], int glass, double quantity)
{
    glasses[glass] += quantity;
    if(glasses[glass] > 1.0)
    {
         double extra = glasses[glass] - 1.0;
         pour( glasses, left_glass(glass), extra / 2 );
         pour( glasses, right_glass(glass), extra / 2 );
         glasses[glass] = 1.0;
    }
}

double getWaterInGlass(int N, int X)
{
    double glasses[10] = {0,0,0,0,0,0};
    pour(glasses, 0, X);
    return glasses[N];
}

En l'état, ce n'est pas un arbre. Parce que différents verres se déversent dans les mêmes verres, cela l'empêche d'être un arbre.

Voici comment je répondrais à cette question dans une situation d'entrevue (je n'ai jamais vu cette question auparavant, et je n'ai pas regardé les autres réponses avant d'avoir ma solution):

Tout d'abord, j'ai essayé de le comprendre (que vous avez appelé la "solution mathématique") et quand je suis arrivé au verre 8, j'ai réalisé que ce serait plus difficile qu'il n'y paraissait parce que le verre 5 commence à déborder avant le verre 4. À ce stade, j'ai a décidé d'emprunter la voie de la récursivité (juste un FYI, beaucoup de questions d'entrevue de programmation nécessitent une récursivité ou une induction pour résoudre).

En pensant récursivement, le problème devient beaucoup plus facile: combien d'eau est dans le verre 8? La moitié de la quantité qui a débordé des verres 4 et 5 (jusqu'à ce qu'elle soit pleine). Bien sûr, cela signifie que nous devons répondre aux débordements des verres 4 et 5, mais il s'avère que ce n'est pas trop difficile non plus. Combien a coulé du verre 5? Cependant, la moitié de la quantité de liquide renversée dans les verres 2 et 3, moins le litre restant dans le verre 5.

Résoudre cela complètement (et malproprement) donne:

#include <iostream>
#include <cmath>
using namespace std;

double howMuchSpilledOutOf(int liters, int bucketId) {
    double spilledInto = 0.0;
    switch (bucketId) {
        case 1:
            spilledInto = liters; break;
        case 2:
            spilledInto = 0.5 * howMuchSpilledOutOf(liters, 1); break;
        case 3:
            spilledInto = 0.5 * howMuchSpilledOutOf(liters, 1); break;
        case 4:
            spilledInto = 0.5 * howMuchSpilledOutOf(liters, 2); break;
        case 5:
            spilledInto = 0.5 * howMuchSpilledOutOf(liters, 2) + 0.5 * howMuchSpilledOutOf(liters, 3); break;
        case 6:
            spilledInto = 0.5 * howMuchSpilledOutOf(liters, 3); break;
        default:
            cerr << "Invalid spill bucket ID " << bucketId << endl;
    }
    return max(0.0, spilledInto - 1.0);
}

double getWaterInBucket(int liters, int bucketId) {
    double contents = 0.0;
    switch (bucketId) {
        case 1:
            contents = liters; break;
        case 2:
            contents = 0.5 * howMuchSpilledOutOf(liters, 1); break;
        case 3:
            contents = 0.5 * howMuchSpilledOutOf(liters, 1); break;
        case 4:
            contents = 0.5 * howMuchSpilledOutOf(liters, 2); break;
        case 5:
            contents = 0.5 * howMuchSpilledOutOf(liters, 2) + 0.5 * howMuchSpilledOutOf(liters, 3); break;
        case 6:
            contents = 0.5 * howMuchSpilledOutOf(liters, 3); break;
        case 7:
            contents = 0.5 * howMuchSpilledOutOf(liters, 4); break;
        case 8:
            contents = 0.5 * howMuchSpilledOutOf(liters, 4) + 0.5 * howMuchSpilledOutOf(liters, 5); break;
        case 9:
            contents = 0.5 * howMuchSpilledOutOf(liters, 5) + 0.5 * howMuchSpilledOutOf(liters, 6); break;
        case 10:
            contents = 0.5 * howMuchSpilledOutOf(liters, 6); break;
        default:
            cerr << "Invalid contents bucket ID" << bucketId << endl;
    }
    return min(1.0, contents);
}

int main(int argc, char** argv)
{
    if (argc == 3) {
        int liters = atoi(argv[1]);
        int bucket = atoi(argv[2]);
        cout << getWaterInBucket(liters, bucket) << endl;
    }
    return 0;
}

À ce stade (ou au moment où j'écrivais ceci), je dirais à l'intervieweur que ce n'est pas la solution idéale en production: il y a du code en double entre howMuchSpilledOutOf()et getWaterInBucket(); il devrait y avoir un emplacement central qui mappe les compartiments à leurs «alimenteurs». Mais dans une interview, où la vitesse et la précision de la mise en œuvre sont plus importantes que la vitesse d'exécution et la maintenabilité (sauf indication contraire), cette solution est préférable. Ensuite, je proposerais de refactoriser le code pour qu'il soit plus proche de ce que je considère comme une qualité de production, et laisser l'intervieweur décider.

Remarque finale: je suis sûr que mon code contient une faute de frappe quelque part; Je le mentionnerais aussi à l'intervieweur et je lui dirais que je me sentirais plus en confiance après l'avoir refactorisé ou testé à l'unité.

Penser à cela comme un problème d'arbre est un redingue, c'est vraiment un graphique dirigé. Mais oubliez tout ça.

Pensez à un verre n'importe où sous celui du haut. Il aura un ou deux verres au-dessus qui peuvent déborder. Avec le choix approprié du système de coordonnées (ne vous inquiétez pas, voir la fin), nous pouvons écrire une fonction pour obtenir les verres "parents" pour n'importe quel verre donné.

Maintenant, nous pouvons penser à un algorithme pour obtenir la quantité de liquide versée dans un verre, indépendamment du débordement de ce verre. La réponse est cependant que beaucoup de liquide est versé dans chaque parent moins la quantité stockée dans chaque verre parent, divisée par 2. Additionnez cela pour tous les parents. L'écriture en tant que fragment python du corps d'une fonction amount_poured_into ():

# p is coords of the current glass
amount_in = 0
for pp in parents(p):
    amount_in += max((amount_poured_into(total, pp) - 1.0)/2, 0)

Le max () est de s'assurer que nous n'obtenons pas une quantité négative de débordement.

Nous avons presque fini! Nous choisissons un système de coordonnées avec «y» en bas de la page, les verres de la première rangée sont 0, la deuxième rangée est 1, etc. Les coordonnées «x» ont un zéro sous le verre de la rangée supérieure et la deuxième rangée a les coordonnées x de -1 et +1, troisième ligne -2, 0, +2, etc. Le point important est que le verre le plus à gauche ou à droite du niveau y aura abs (x) = y.

Enveloppant tout cela en python (2.x), nous avons:

def parents(p):
    """Get parents of glass at p"""

    (x, y) = p
    py = y - 1          # parent y
    ppx = x + 1         # right parent x
    pmx = x - 1         # left parent x

    if abs(ppx) > py:
        return ((pmx,py),)
    if abs(pmx) > py:
        return ((ppx,py),)
    return ((pmx,py), (ppx,py))

def amount_poured_into(total, p):
    """Amount of fluid poured into glass 'p'"""

    (x, y) = p
    if y == 0:    # ie, is this the top glass?
        return total

    amount_in = 0
    for pp in parents(p):
        amount_in += max((amount_poured_into(total, pp) - 1.0)/2, 0)

    return amount_in

def amount_in(total, p):
    """Amount of fluid left in glass p"""

    return min(amount_poured_into(total, p), 1)

Donc, pour obtenir la quantité réellement dans un verre à p, utilisez amount_in (total, p).

Ce n'est pas clair à partir de l'OP, mais le peu de "vous ne pouvez pas ajouter de paramètres" peut signifier que la question d'origine doit être répondue en termes de numéros de verre affichés. Ceci est résolu en écrivant une fonction de mappage des numéros de verre d'exposition au système de coordonnées interne utilisé ci-dessus. C'est compliqué, mais une solution itérative ou mathématique peut être utilisée. Une fonction itérative facile à comprendre:

def p_from_n(n):
    """Get internal coords from glass 'number'"""

    for (y, width) in enumerate(xrange(1, n+1)):
        if n > width:
            n -= width
        else:
            x = -y + 2*(n-1)
            return (x, y)

Maintenant, réécrivez simplement la fonction amount_in () ci-dessus pour accepter un numéro de verre:

def amount_in(total, n):
    """Amount of fluid left in glass number n"""

    p = p_from_n(n)
    return min(amount_poured_into(total, p), 1)

Intéressant.

Cela prend l'approche de simulation.

private void test() {
  double litres = 6;
  for ( int i = 1; i < 19; i++ ) {
    System.out.println("Water in glass "+i+" = "+getWater(litres, i));
  }
}

private double getWater(double litres, int whichGlass) {
  // Don't need more glasses than that.
  /*
   * NB: My glasses are numbered from 0.
   */
  double[] glasses = new double[whichGlass];
  // Pour the water in.
  pour(litres, glasses, 0);
  // Pull out the glass amount.
  return glasses[whichGlass-1];
}

// Simple non-math calculator for which glass to overflow into.
// Each glass overflows into this one and the one after.
// Only covers up to 10 glasses (0 - 9).
int[] overflowsInto = 
{1, 
 3, 4, 
 6, 7, 8, 
 10, 11, 12, 13, 
 15, 16, 17, 18, 19};

private void pour(double litres, double[] glasses, int which) {
  // Don't care about later glasses.
  if ( which < glasses.length ) {
    // Pour up to 1 litre in this glass.
    glasses[which] += litres;
    // How much overflow.
    double overflow = glasses[which] - 1;
    if ( overflow > 0 ) {
      // Remove the overflow.
      glasses[which] -= overflow;
      // Split between two.
      pour(overflow / 2, glasses, overflowsInto[which]);
      pour(overflow / 2, glasses, overflowsInto[which]+1);
    }
  }
}

qui imprime (pour 6 litres):

Water in glass 1 = 1.0
Water in glass 2 = 1.0
Water in glass 3 = 1.0
Water in glass 4 = 0.75
Water in glass 5 = 1.0
Water in glass 6 = 0.75
Water in glass 7 = 0.0
Water in glass 8 = 0.25
Water in glass 9 = 0.25
Water in glass 10 = 0.0
...

qui semble être à peu près juste.

Ceci est la fonction binomiale. Le rapport de l'eau entre les verres de niveau N peut être découvert en utilisant nCr pour chaque verre du niveau. De plus, le nombre total de verres avant le niveau N est la somme de 1 à (N - 1), une formule pour laquelle vous devriez pouvoir trouver les produits disponibles assez facilement. Ainsi, étant donné X, vous devriez pouvoir déterminer son niveau et utiliser nCr pour vérifier les rapports des verres pour ce niveau, et ainsi déterminer la quantité d'eau dans X, s'il y a suffisamment de litres pour descendre jusqu'à X de toute façon.

Deuxièmement, votre idée d'utiliser le BTree est très bien, c'est juste que le BTree est une variable interne, pas un paramètre externe.

IOW, si vous avez couvert ces mathématiques dans votre éducation (ici au Royaume-Uni, elles sont enseignées avant l'université), vous devriez être en mesure de résoudre ce problème sans trop de problèmes.