Champagner Brunnen Puzzle

30

Leere Gläser Wasser werden in der folgenden Reihenfolge angeordnet:

Bildbeschreibung hier eingeben

Wenn Sie Flüssigkeit in das erste Glas einfüllen, wenn es voll ist, wird die zusätzliche Flüssigkeit in gleichen Mengen in die Gläser 2 und 3 eingefüllt. Wenn Glas 2 voll ist, wird die zusätzliche Flüssigkeit in 4 und 5 usw. geflogen.

Bei einem Flüssigkeitsgehalt von N Litern und einem maximalen Fassungsvermögen von 1 Liter pro Glas geben Sie die in einem Glas vorhandene Flüssigkeitsmenge an, wenn Sie N Liter Flüssigkeit durch Eingießen in das Glas leeren, indem Sie die Funktion ausfüllen, getWaterInBucket(int N, int X)bei der X die Glaszahl ist. Wenn ich zum Beispiel am Anfang 4 Liter haben möchte und das Wasser in Glas 3 finden möchte, ist die FunktiongetWaterInBucket(4, 3)

Wie löse ich das programmatisch? Ich habe versucht, mit Pascals Dreieck eine mathematische Lösung zu finden. Das hat nicht funktioniert. Ich habe es als einen Baum betrachtet, also kann ich einen Parameter wie diesen hinzufügen getWaterInBucket(BTree root, int N, int X)und dann eine rekursive Lösung für jede Ebene versuchen, aber Parameter sind in diesem Problem nicht zulässig. Gibt es einen offensichtlichen Trick?

Slartibartfast
quelle
18
Ich würde nicht in einer Firma arbeiten wollen, in der die Probleme des Managements Champagnerbrunnen sind ...
mouviciel
Können Sie jemals in ein anderes Glas als Glas 1 gießen? Wenn nicht, enthält jede Stufe in jedem Glas die gleiche Menge Wasser. So haben Sie volle Stufen, wenn Sie 1, 3, 6, 10 ... Liter einfüllen. Wenn Sie 7 Liter einfüllen, hat die vierte Reihe 4 Gläser, sodass jedes 1/4 voll ist. Alle Ebenen darüber werden voll sein.
GlenPeterson
5
@ GlenPeterson Nach dem, was ich lese, glaube ich nicht, dass sie sich gleichermaßen füllen würden. Ja, 2 & 3 füllen sich gleichermaßen, weil sie nur eines haben, aber wenn sie voll sind, gießen sie 2 zu 4/5 und 3 zu 5/6, so dass 5 mit dem doppelten Wert von 4/6 gefüllt werden . Die mittleren Tassen füllen sich immer schneller als die äußeren Tassen. Zu dem Zeitpunkt, an dem 4/6 voll sind, sind 8/9 zu 25% voll und 7/10 sind noch leer.
Brad
1
Das erinnert mich auch an Pascals Dreieck.
Brad
@mouviciel Haha GlenPeterson - Das erste Glas, das gegossen wird, ist immer Glas 1. Der Interviewer sagte auch, diese Informationen zu verwenden. Er wirkte verwirrter als ich, als es um die richtige Antwort auf dieses Problem ging.
Slartibartfast

Antworten:

35

Sie müssen nur das Gießen simulieren, so etwas wie

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];
}

So wie es aussieht, ist dies kein Baum. Weil verschiedene Gläser in die gleichen Gläser fließen, wird verhindert, dass es sich um einen Baum handelt.

Winston Ewert
quelle
16
+1 für die großartige Beobachtung, dass dies kein Baum ist.
Mihai Danila
2
Gute Antwort. In einem Interview sollten Sie sagen, dass dies Skalierbarkeitsprobleme haben könnte, da der Inhalt aller Gläser berechnet wird. Sie müssen auch den Fall behandeln, in dem Wasser aus der unteren Reihe der Gläser herausläuft. Und das wollen Sie return glasses[N-1], denn die Glaszahlen beginnen bei 1 statt bei 0.
Tom Panning
1
Ich denke, der herausfordernde Teil könnte darin bestehen, die Indexe der linken und rechten Kinder herauszufinden. Wenn Sie dies präsentiert haben, wird der Interviewer Sie nur bitten, diese Funktionen zu implementieren. Es kann eine explizite Formel geben.
James
Das ist eine wirklich elegante Lösung. Vielen Dank. Ich wäre Ihnen dankbar, wenn Sie es so bearbeiten könnten, dass Sie den Codezeilen Kommentare hinzufügen, um zu erklären, was jeder Schritt im Denkprozess bedeutet. Auch die Anzahl der Gläser ist nicht auf 10 beschränkt. Es könnte alles sein
Slartibartfast
1
Wie findet man linke und rechte Brille?
Kiewic
7

So würde ich diese Frage in einer Interview-Situation beantworten (ich habe diese Frage vorher noch nicht gesehen und mir die anderen Antworten nicht angesehen, bis ich meine Lösung gefunden habe):

Zuerst habe ich versucht, es herauszufinden (was Sie die "mathematische Lösung" nannten), und als ich zu Glas 8 kam, wurde mir klar, dass es härter sein würde, als es schien, weil Glas 5 vor Glas 4 überzulaufen beginnt. An diesem Punkt begann ich beschlossen, den Rekursionsweg zu beschreiten (nur zu Ihrer Information, viele Fragen zu Programmierinterviews erfordern eine Rekursion oder Induktion, um sie zu lösen).

Beim rekursiven Denken wird das Problem viel einfacher: Wie viel Wasser ist in Glas 8? Die Hälfte der Menge, die aus den Gläsern 4 und 5 verschüttet wurde (bis sie voll ist). Das bedeutet natürlich, dass wir beantworten müssen, wie viel aus den Gläsern 4 und 5 verschüttet wurde, aber es stellt sich heraus, dass das auch nicht allzu schwer ist. Wie viel ist aus Glas 5 verschüttet worden? Die Hälfte davon wurde jedoch aus den Gläsern 2 und 3 verschüttet, abzüglich des in Glas 5 verbleibenden Liters.

Wenn Sie dies vollständig (und unordentlich) lösen, erhalten Sie:

#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;
}

An diesem Punkt (oder als ich dies schrieb) würde ich dem Interviewer sagen, dass dies nicht die ideale Lösung in der Produktion ist: Es gibt doppelten Code zwischen howMuchSpilledOutOf()und getWaterInBucket(); Es sollte einen zentralen Ort geben, an dem die Eimer ihren "Feedern" zugeordnet werden. In einem Interview, in dem Schnelligkeit und Genauigkeit der Implementierung wichtiger sind als Schnelligkeit der Ausführung und Wartbarkeit (sofern nicht anders angegeben), ist diese Lösung vorzuziehen. Dann würde ich anbieten, den Code umzugestalten, um näher an der Qualität zu sein, die ich für die Produktion halte, und den Interviewer entscheiden lassen.

Letzte Anmerkung: Ich bin sicher, dass mein Code irgendwo einen Tippfehler enthält. Ich würde das auch dem Interviewer gegenüber erwähnen und sagen, dass ich mich sicherer fühlen würde, wenn ich es entweder überarbeitet oder auf Unit-Tests getestet hätte.

Tom Panning
quelle
6
Diese Lösung ist für das Beispiel hartcodiert. Eine Brille hinzuzufügen bedeutet, dem Schalter "Etui" hinzuzufügen ... Ich denke nicht, dass es eine gute Lösung ist.
Luigi Massa Gallerano
2
@LuigiMassaGallerano - das ist in diesem Fall in Ordnung, da es sich um eine Interviewfrage handelt. Es soll keine perfekte Lösung sein. Der Interviewer versucht, den Denkprozess des Kandidaten besser zu verstehen. Und darauf weist Tom bereits hin this isn't the ideal solution.
1
Es ist ehrlich gesagt nicht. Ich kann Ihnen versichern, dass dieses Szenario nicht hart codiert sein sollte. Wenn ich eine Interviewfrage stellte und ein Testfall-Szenario auslegte, in dem der Befragte eine fest codierte Lösung vorstellte, sollte er besser darauf vorbereitet sein, eine allgemeine Lösung anzubieten, oder er wird das Interview wahrscheinlich nicht bestehen.
Rig
5

Wenn man dies als ein Baumproblem betrachtet, ist es ein roter Hering, es ist wirklich eine gerichtete Grafik. Aber vergiss das alles.

Denken Sie an ein Glas irgendwo unter dem oberen. Darüber befinden sich ein oder zwei Gläser, die überlaufen können. Mit der richtigen Wahl des Koordinatensystems (keine Sorge, siehe Ende) können wir eine Funktion schreiben, um die "Eltern" -Brille für jedes gegebene Glas zu erhalten.

Nun können wir uns einen Algorithmus überlegen, mit dem die in ein Glas gegossene Flüssigkeitsmenge unabhängig vom Überlauf aus diesem Glas ermittelt werden kann. Die Antwort ist jedoch, dass jedem Elternteil viel Flüssigkeit eingefüllt wird, abzüglich der Menge, die in jedem Elternglas gespeichert ist, geteilt durch 2. Summieren Sie dies einfach für alle Eltern. Schreiben Sie dies als Python-Fragment des Körpers einer amount_poured_into () -Funktion:

# 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)

Mit max () soll sichergestellt werden, dass kein negativer Überlauf auftritt.

Wir sind fast fertig! Wir wählen ein Koordinatensystem mit 'y' auf der ganzen Seite, die erste Reihe ist 0, die zweite Reihe ist 1 usw. Die 'x'-Koordinaten haben eine Null unter der oberen Reihe und die zweite Reihe hat x-Koordinaten von -1 und +1, dritte Reihe -2, 0, +2 und so weiter. Der wichtige Punkt ist, dass das Glas ganz links oder ganz rechts in Stufe y abs (x) = y hat.

Wenn Sie das alles in Python (2.x) packen, haben wir:

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)

Verwenden Sie also amount_in (total, p), um die tatsächliche Menge in einem Glas bei p zu erhalten.

Es ist nicht von der OP klar, aber das Bit über „Sie Parameter hinzufügen kippen“ bedeuten kann , die ursprüngliche Frage in Bezug auf dem Glas beantwortet werden muss Zahlen gezeigt. Dies wird gelöst, indem eine Zuordnungsfunktion von den Showglasnummern in das oben verwendete interne Koordinatensystem geschrieben wird. Es ist fummelig, aber es kann entweder eine iterative oder eine mathematische Lösung verwendet werden. Eine leicht verständliche iterative Funktion:

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)

Schreiben Sie jetzt einfach die Funktion amount_in () um, um eine Glaszahl zu akzeptieren:

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
quelle
2

Interessant.

Dies erfolgt nach dem Simulationsansatz.

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);
    }
  }
}

welche druckt (für 6 liter):

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

das scheint in etwa richtig zu sein.

OldCurmudgeon
quelle
-1

Dies ist die Binomialfunktion. Das Verhältnis des Wassers zwischen den Gläsern der Stufe N kann mit nCr für jedes Glas in der Stufe ermittelt werden. Darüber hinaus ist die Gesamtzahl der Gläser vor der Stufe N die Summe von 1 bis (N - 1), eine Formel, für die Sie ziemlich leicht verfügbare finden sollten. Wenn X gegeben ist, sollten Sie in der Lage sein, den Füllstand zu bestimmen, und nCr verwenden, um die Verhältnisse der Gläser für diesen Füllstand zu überprüfen und so zu bestimmen, wie viel Wasser in X ist, wenn es genug Liter gibt, um trotzdem zu X zu gelangen.

Zweitens ist Ihre Idee, den BTree zu verwenden, in Ordnung. Der BTree ist lediglich eine interne Variable, kein externer Parameter.

IOW, wenn Sie diese Mathematik in Ihrer Ausbildung behandelt haben (hier in Großbritannien wird sie vor der Universität unterrichtet), sollten Sie in der Lage sein, dies ohne zu große Probleme zu lösen.

DeadMG
quelle
1
Ich glaube nicht, dass es die Binomialfunktion ist. Es erreicht die dritte Stufe in Proportionen von 1,2,1, wie die Binomialfunktion nahelegt, aber das mittlere Glas füllt sich zuerst und das Muster wird danach gebrochen.
Winston Ewert
Die Zeit ist nicht Teil der Simulation und hat keinen Einfluss auf die Endergebnisse.
DeadMG
4
Da sich die Modellierflüssigkeit füllt und aus den Gläsern fließt, muss ich diese Zeit unbedingt einhalten. Bei 5 Litern sind 4 & 6 halb voll und 5 sind alle voll. Wenn der sechste Liter hinzugefügt wird, fängt er an, in 8 & 9 zu fließen, aber 7 & 10 erhalten kein Wasser, weil 4 & 6 noch nicht die Kapazität erreicht haben. Daher kann die Binomialfunktion die korrekten Werte nicht vorhersagen.
Winston Ewert
3
-1, das ist falsch Levels werden nicht gleichmäßig gefüllt.
Dan_waterworth
Du hast recht, ich habe es nicht in Betracht gezogen. Aber nachdem ich eine Weile darüber nachgedacht hatte, wurde mir klar, dass Sie Recht hatten. Ich bin nicht sicher, wie ich die Formel anpassen soll, um dies zu berücksichtigen.
DeadMG