Puzzle Fontanna Champaign

30

Puste szklanki wody są ułożone w następującej kolejności:

wprowadź opis zdjęcia tutaj

Gdy wlejesz płyn do 1. szklanki, jeśli jest pełna, dodatkowy płyn zostanie wlany do szklanek 2 i 3 w równych ilościach. Gdy szklanka 2 jest pełna, dodatkowa ciecz zostanie przelana do 4 i 5 i tak dalej.

Biorąc pod uwagę N litrów płynu, a maksymalna pojemność każdej szklanki wynosi 1 litr, podaj ilość płynu obecnego w dowolnej szklance, jeśli opróżnisz N litrów płynu, wlewając do szklanki wypełniając funkcję, getWaterInBucket(int N, int X)gdzie X jest liczbą szklaną. Na przykład, jeśli chcę mieć 4 litry na początku i chcę znaleźć wodę w szklance 3, funkcja jestgetWaterInBucket(4, 3)

Jak rozwiązać to programowo? Próbowałem znaleźć rozwiązanie matematyczne, używając trójkąta Pascala. To nie zadziałało. Uznałem to za drzewo, więc mogę dodać taki parametr, getWaterInBucket(BTree root, int N, int X)a następnie wypróbować rekurencyjne rozwiązanie dla każdego poziomu, ale parametry nie są dozwolone w tym problemie. Czy jest coś oczywistego, jakaś sztuczka?

Slartibartfast
źródło
18
Nie chciałbym pracować w firmie, w której problemy kierownictwa dotyczą fontann szampana ...
mouviciel
Czy kiedykolwiek wlejesz do szklanki innej niż szklanka 1? Jeśli nie, na każdym poziomie będą znajdować się równe ilości wody w każdej szklance. W ten sposób będziesz mieć pełne poziomy za każdym razem, gdy wlejesz 1, 3, 6, 10 ... litrów. Jeśli wlejesz 7 litrów, czwarty rząd ma 4 szklanki, więc każda będzie 1/4 pełna. Wszystkie poziomy powyżej będą pełne.
GlenPeterson
5
@GlenPeterson Z tego, jak to czytam, nie sądzę, żeby wypełniły się jednakowo. Tak, 2 i 3 wypełniłyby się równomiernie, ponieważ napełnia je tylko jedna rzecz, ale gdy są pełne, 2 wlewa równomiernie do 4/5 i 3 wlewa równomiernie do 5/6, w ten sposób 5 wypełnia się dwukrotnie przy szczurze 4/6 . Miseczki środkowe zawsze napełniają się szybciej niż miseczki zewnętrzne. do czasu zapełnienia 4/6 8/9 zapełnia się w 25%, a 7/10 jest pustych.
Brad
1
Przypomina mi to również Trójkąt Pascala ..
Brad
@mouviciel Haha GlenPeterson - Pierwszą nalewaną szklanką jest zawsze szklanka 1. Ankieter powiedział również, aby wykorzystać te informacje. Wydawał się bardziej zdezorientowany niż ja, jeśli chodzi o właściwą odpowiedź na ten problem.
Slartibartfast

Odpowiedzi:

35

Musisz tylko zasymulować nalewanie, coś w tym rodzaju

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

W tej chwili nie jest to drzewo. Ponieważ różne kieliszki wlewają się do tych samych kieliszków, co zapobiega temu, że jest drzewem.

Winston Ewert
źródło
16
+1 za wielką obserwację, że to nie jest drzewo.
Mihai Danila
2
Dobra odpowiedź. W wywiadzie powinieneś powiedzieć, że może to mieć problemy ze skalowalnością, ponieważ oblicza zawartość wszystkich okularów. Ponadto musisz poradzić sobie z walizką, w której woda wylewa się z dolnego rzędu szklanek. I chcesz return glasses[N-1], bo szklane liczby zaczynają się od 1 zamiast 0.
Tom Panning
1
Myślę, że trudną częścią może być ustalenie wskaźników dla lewego i prawego dziecka. Jeśli to przedstawiłeś, ankieter poprosi Cię o wdrożenie tych funkcji. Może istnieć wyraźna formuła.
James
To naprawdę eleganckie rozwiązanie. Dzięki. Byłbym wdzięczny, gdybyś mógł go edytować, aby dodać komentarze do wierszy kodu i wyjaśnić, co oznacza każdy krok w procesie myślowym. Również liczba okularów nie jest ograniczona do 10. To może być cokolwiek
Slartibartfast
1
Jak znaleźć lewe i prawe okulary?
kiewic
7

Oto jak odpowiedziałbym na to pytanie w wywiadzie (nie widziałem tego pytania wcześniej i nie patrzyłem na inne odpowiedzi, dopóki nie znalazłem rozwiązania):

Najpierw próbowałem to rozgryźć (co nazywacie „rozwiązaniem matematycznym”), a kiedy dotarłem do szklanki 8, zdałem sobie sprawę, że będzie trudniej niż się wydawało, ponieważ szklanka 5 zaczyna przelewać się przed szklanką 4. W tym momencie ja postanowiłem pójść ścieżką rekurencyjną (tylko FYI, wiele pytań do wywiadu programowego wymaga rekurencji lub indukcji do rozwiązania).

Myśląc rekurencyjnie, problem staje się znacznie łatwiejszy: ile wody jest w szklance 8? Połowa kwoty, która wylała się z szklanek 4 i 5 (aż będzie pełna). Oczywiście oznacza to, że musimy odpowiedzieć, ile wylało się z okularów 4 i 5, ale okazuje się, że to też nie jest zbyt trudne. Ile wylało się ze szkła 5? Połowa z tego, co dużo, wylała się ze szklanek 2 i 3, minus litr, który pozostał w szklance 5.

Rozwiązanie tego całkowicie (i niechlujnie) daje:

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

W tym momencie (lub jak to pisałem) powiedziałbym ankieterowi, że nie jest to idealne rozwiązanie w produkcji: istnieje zduplikowany kod między howMuchSpilledOutOf() i getWaterInBucket(); powinna istnieć centralna lokalizacja, która mapuje wiadra do ich „podajników”. Ale w wywiadzie, w którym szybkość i dokładność wdrożenia są ważniejsze niż szybkość wykonania i łatwość konserwacji (o ile nie wskazano inaczej), takie rozwiązanie jest lepsze. Następnie zaproponowałbym przeredagowanie kodu, aby był bliższy jakości, którą uważam za produkcyjną, i pozwoliłbym ankieterowi zdecydować.

Ostatnia uwaga: jestem pewien, że mój kod gdzieś ma literówkę; Wspominam o tym również ankieterowi i mówię, że czułbym się bardziej pewny po refaktoryzacji lub testowaniu jednostkowym.

Tom Panning
źródło
6
To rozwiązanie jest na przykład zakodowane na stałe. Dodanie okularów oznacza dodanie „skrzynki” do przełącznika ... Nie sądzę, że to dobre rozwiązanie.
Luigi Massa Gallerano
2
@LigiigiassaGallerano - w tym przypadku jest to w porządku, ponieważ jest to pytanie do rozmowy kwalifikacyjnej; to nie powinno być idealne rozwiązanie. Ankieter stara się lepiej zrozumieć proces myślowy kandydata. I Tom już to podkreśla this isn't the ideal solution.
1
Szczerze mówiąc nie jest. Zapewniam cię, że ten scenariusz nie był przeznaczony na stałe. Gdybym zadał pytanie podczas rozmowy kwalifikacyjnej i przedstawił scenariusz testowy, w którym rozmówca przedstawił rozwiązanie zakodowane na sztywno, lepiej być przygotowanym na zaproponowanie ogólnego rozwiązania, w przeciwnym razie prawdopodobnie nie przejdzie rozmowy kwalifikacyjnej.
Rig
5

Myślenie o tym jak o problemie z drzewem to śledź czerwony, to tak naprawdę wykres kierunkowy. Ale zapomnij o tym wszystkim.

Pomyśl o szklance gdziekolwiek poniżej górnej. Będzie miał jedną lub dwie szklanki nad nim, które mogą się do niego przelać. Przy odpowiednim wyborze układu współrzędnych (nie martw się, patrz koniec) możemy napisać funkcję, aby uzyskać okulary „macierzyste” dla dowolnego szkła.

Teraz możemy pomyśleć o algorytmie, aby uzyskać ilość płynu wlewaną do szklanki, niezależnie od przelewu z tego szkła. Odpowiedź jest jednak taka, że ​​do każdego rodzica wlewa się dużo płynu minus ilość przechowywana w każdym szkle rodzicielskim, podzielona przez 2. Wystarczy zsumować to dla wszystkich rodziców. Zapisanie tego jako fragmentu Pythona w treści funkcji quant_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)

Funkcja max () ma zapewnić, że nie wystąpi ujemna przepełnienie.

Jesteśmy prawie skończeni! Wybieramy układ współrzędnych z „y” w dół strony, szklanki pierwszego rzędu to 0, drugi rząd to 1 itd. Współrzędne „x” mają zero pod szkłem górnego rzędu, a drugi rząd ma współrzędne x -1 i +1, trzeci rząd -2, 0, +2 i tak dalej. Ważną kwestią jest to, że lewe lub prawe szkło na poziomie y będzie miało abs (x) = y.

Podsumowując wszystko w Pythonie (2.x), mamy:

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)

Tak więc, aby uzyskać ilość faktycznie w szklance przy p, użyj kwoty_w (ogółem, p).

Z PO nie jest to jasne, ale fragment dotyczący „nie można dodać parametrów” może oznaczać, że na oryginalne pytanie należy odpowiedzieć pod względem wyświetlanych liczb szklanych . Rozwiązuje się to poprzez zapisanie funkcji mapowania z numerów szkieł pokazowych na wewnętrznym układzie współrzędnych stosowanym powyżej. To kłopotliwe, ale można zastosować iteracyjne lub matematyczne rozwiązanie. Łatwa do zrozumienia funkcja iteracyjna:

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)

Teraz po prostu przepisz powyżej funkcję quant_in (), aby zaakceptować liczbę szklaną:

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
źródło
2

Ciekawy.

To wymaga podejścia symulacyjnego.

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

który drukuje (na 6 litrów):

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

co wydaje się być w porządku.

OldCurmudgeon
źródło
-1

To jest funkcja dwumianowa. Stosunek wody między szklankami poziomu N można ustalić za pomocą nCr dla każdej szklanki na poziomie. Ponadto łączna liczba okularów przed poziomem N to suma od 1 do (N - 1), wzór, dla którego powinieneś być w stanie dość łatwo znaleźć. Tak więc, biorąc pod uwagę X, powinieneś być w stanie określić jego poziom i użyć nCr, aby sprawdzić proporcje szklanek dla tego poziomu, a tym samym określić, ile wody jest w X, jeśli i tak jest wystarczająca ilość litrów, aby zejść do X.

Po drugie, twój pomysł użycia BTree jest w porządku, po prostu BTree jest zmienną wewnętrzną, a nie parametrem zewnętrznym.

IOW, jeśli omawiałeś tę matematykę w swojej edukacji (tutaj w Wielkiej Brytanii uczy się jej przed uniwersytetem), powinieneś być w stanie rozwiązać to bez większego problemu.

DeadMG
źródło
1
Nie sądzę, że jest to funkcja dwumianowa. Osiąga trzeci poziom w proporcjach 1,2,1, jak sugerowałaby funkcja dwumianowa, ale środkowa szklanka wypełnia się pierwsza, a następnie wzór jest łamany.
Winston Ewert
Czas nie jest częścią symulacji i nie wpłynie na wyniki końcowe.
DeadMG
4
ponieważ jego płyn do modelowania wypełnia się i wypływa z okularów, musiałbym utrzymać ten czas jako domyślny element symulacji. Przy 5 litrach 4 i 6 będą w połowie pełne, a 5 będzie pełne. Po dodaniu szóstego litra zacznie wlewać się do 8 i 9, ale 7 i 10 nie otrzymają wody, ponieważ 4 i 6 nie osiągnęły jeszcze pojemności. Zatem funkcja dwumianowa nie będzie przewidywać prawidłowych wartości.
Winston Ewert
3
-1, to źle. Poziomy nie będą wypełniane równomiernie.
dan_waterworth
Masz rację, nie zastanawiałem się. Ale po chwili zastanowienia zdałem sobie sprawę, że masz rację. Nie wiesz, jak dostosować formułę, aby to uwzględnić.
DeadMG