Puzzle Fontanna Champaign

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

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?

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.

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.

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)

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.

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.