Puzzle Fontaine de Champagne

30

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

entrez la description de l'image ici

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?

Slartibartfast
la source
18
Je ne voudrais pas travailler dans une entreprise où les problèmes de gestion concernent les fontaines à champagne ...
mouviciel
Pouvez-vous jamais verser dans un verre autre que le verre 1? Sinon, chaque niveau aura des quantités égales d'eau dans chaque verre. Ainsi, vous aurez des niveaux complets chaque fois que vous versez 1, 3, 6, 10 ... litres. Si vous versez 7 litres, la quatrième rangée contient 4 verres, chacun sera donc rempli au 1/4. Tous les niveaux supérieurs seront pleins.
GlenPeterson
5
@GlenPeterson D'après la façon dont je le lis, je ne pense pas qu'ils se rempliraient également. Oui, 2 et 3 se rempliraient également car ils ne contiennent qu'une seule chose, mais une fois qu'ils sont pleins, 2 versent également dans 4/5 et 3 versent également dans 5/6, donc 5 se remplit à deux fois le rat de 4/6 . Les tasses centrales se remplissent toujours plus rapidement que les tasses extérieures. au moment où 4/6 sont pleins, 8/9 sont remplis à 25% et 7/10 sont encore vides.
Brad
1
De plus, cela me rappelle le triangle de Pascal ..
Brad
@mouviciel Haha GlenPeterson - Le premier verre à couler est toujours le verre 1. L'intervieweur a également dit d'utiliser ces informations. Il semblait plus confus que moi sur la bonne réponse à ce problème.
Slartibartfast

Réponses:

35

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.

Winston Ewert
la source
16
+1 pour la grande observation que ce n'est pas un arbre.
Mihai Danila
2
Bonne réponse. Dans une interview, vous devez dire que cela pourrait avoir des problèmes d'évolutivité car il calcule le contenu de tous les verres. En outre, vous devez gérer le cas où l'eau se déverse de la rangée inférieure de verres. Et vous voulez return glasses[N-1], parce que les numéros de verre commencent à 1 au lieu de 0.
Tom Panning
1
Je pense que la partie difficile pourrait être de déterminer les index des enfants gauche et droit. Si vous l'avez présenté, l'intervieweur va simplement vous demander de mettre en œuvre ces fonctions. Il peut y avoir une formule explicite.
James
C'est une solution vraiment élégante. Merci. Je serais reconnaissant si vous pouviez le modifier pour ajouter des commentaires aux lignes de code pour expliquer ce que chaque étape signifie dans le processus de réflexion. De plus, le nombre de verres n'est pas limité à 10. Cela pourrait être n'importe quoi
Slartibartfast
1
Comment trouvez-vous les lunettes gauche et droite?
kiewic
7

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é.

Tom Panning
la source
6
Cette solution est codée en dur pour l'exemple. Ajouter des lunettes signifie ajouter un "étui" au commutateur ... Je ne pense pas que ce soit une bonne solution.
Luigi Massa Gallerano
2
@LuigiMassaGallerano - c'est correct dans ce cas car c'est une question d'entrevue; ce n'est pas censé être une solution parfaite. L'intervieweur essaie de mieux comprendre le processus de réflexion du candidat. Et Tom le fait déjà remarquer this isn't the ideal solution.
1
Ce n'est vraiment pas le cas. Je peux vous assurer que ce scénario n'était pas destiné à être codé en dur. Si j'ai posé une question d'entrevue et présenté un scénario de test selon lequel l'enquêté a présenté une solution codée en dur, il vaut mieux être prêt à offrir une solution générale ou il ne va probablement pas passer l'entretien.
Rig
5

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)
rzzzwilson
la source
2

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.

OldCurmudgeon
la source
-1

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.

DeadMG
la source
1
Je ne pense pas que ce soit la fonction binomiale. Il atteint le troisième niveau dans des proportions de 1,2,1 comme le suggère la fonction binomiale, mais le verre du milieu se remplit en premier et le motif est cassé par la suite.
Winston Ewert
Le temps ne fait pas partie de la simulation et n'affectera pas les résultats finaux.
DeadMG
4
puisque son liquide de modélisation se remplit et sort des verres, je dois maintenir que le temps fait implicitement partie de la simulation. À 5 litres, 4 et 6 seront à moitié pleins et 5 seront tous pleins. Lorsque le sixième litre est ajouté, il commencera à couler dans 8 et 9, mais 7 et 10 ne recevront pas d'eau car 4 et 6 n'ont pas encore atteint leur capacité. Ainsi, la fonction binomiale ne prédira pas les valeurs correctes.
Winston Ewert
3
-1, c'est faux. Les niveaux ne seront pas remplis uniformément.
dan_waterworth
Tu as raison, je n'y ai pas pensé. Mais après y avoir réfléchi pendant un moment, j'ai réalisé que vous aviez raison. Vous ne savez pas comment ajuster la formule pour en tenir compte.
DeadMG