Champaign Fountain Puzzle

Copos vazios de água são organizados na seguinte ordem:

Quando você derramar líquido no primeiro copo, se estiver cheio, o líquido extra será jogado nos copos 2 e 3 em quantidades iguais. Quando o vidro 2 estiver cheio, o líquido extra será transportado para 4 e 5 e assim por diante.

Dado um N litros de líquido e a capacidade máxima de cada copo é de 1 litro, forneça a quantidade de líquido presente em qualquer copo se você esvaziar N litros de líquido derramando no copo, preenchendo a função em getWaterInBucket(int N, int X)que X é o número do copo. Por exemplo, se eu quero 4 litros no início e quero encontrar a água no copo 3, a função égetWaterInBucket(4, 3)

Como resolvo isso programaticamente? Tentei encontrar uma solução matemática usando o triângulo de Pascal. Isso não funcionou. Eu considerei uma árvore para que eu possa adicionar um parâmetro como este getWaterInBucket(BTree root, int N, int X)e tentar uma solução recursiva para cada nível, mas os parâmetros não são permitidos neste problema. Existe algo óbvio, algum truque?

Você só precisa simular o vazamento, algo como

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

Tal como está, esta não é uma árvore. Como copos diferentes caem nos mesmos copos, isso impede que seja uma árvore.

Aqui está como eu responderia a essa pergunta em uma situação de entrevista (eu não a vi antes e não olhei para as outras respostas até ter minha solução):

Primeiro, tentei descobrir (que você chamou de "solução matemática") e, quando cheguei ao copo 8, percebi que seria mais difícil do que parecia porque o copo 5 começa a transbordar antes do copo 4. Nesse ponto, eu decidiu seguir o caminho da recursão (apenas um FYI, muitas perguntas da entrevista de programação exigem recursão ou indução para resolver).

Pensando recursivamente, o problema se torna muito mais fácil: quanta água há no copo 8? Metade da quantidade derramada nos copos 4 e 5 (até que esteja cheia). Obviamente, isso significa que temos que responder quanto derramou dos óculos 4 e 5, mas também não é muito difícil. Quanto derramou fora do vidro 5? Metade de qualquer quantidade derramada nos copos 2 e 3, menos o litro que ficou no copo 5.

Resolver isso completamente (e confuso) fornece:

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

Nesse ponto (ou enquanto eu escrevia isso), eu diria ao entrevistador que essa não é a solução ideal na produção: existe um código duplicado entre howMuchSpilledOutOf()e getWaterInBucket(); deve haver um local central que mapeie os baldes para seus "alimentadores". Porém, em uma entrevista, onde a velocidade e a precisão da implementação são mais importantes que a velocidade de execução e a manutenção (a menos que indicado de outra forma), essa solução é preferível. Então, eu ofereceria refatorar o código para estar mais próximo do que considero qualidade de produção e deixaria o entrevistador decidir.

Nota final: tenho certeza que meu código tem um erro de digitação em algum lugar; Eu mencionaria isso também ao entrevistador e diria que me sentiria mais confiante depois de refatorá-lo ou testá-lo.

Pensar nisso como um problema de árvore é um problema, é realmente um gráfico direcionado. Mas esqueça tudo isso.

Pense em um copo em qualquer lugar abaixo do topo. Terá um ou dois copos acima dele que podem transbordar para ele. Com a escolha apropriada do sistema de coordenadas (não se preocupe, veja o final), podemos escrever uma função para obter os óculos "originais" de qualquer vidro.

Agora podemos pensar em um algoritmo para obter a quantidade de líquido derramado em um copo, independentemente do transbordamento desse copo. A resposta é, no entanto, muito líquido é derramado em cada progenitor menos a quantidade armazenada em cada copo progenitor, dividido por 2. Basta somar isso para todos os progenitores. Escrevendo isso como um fragmento python do corpo de uma função 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)

O máximo () é para garantir que não recebamos uma quantidade negativa de excesso.

Estamos quase terminando! Escolhemos um sistema de coordenadas com 'y' na página, os óculos da primeira linha são 0, a segunda linha é 1 etc. As coordenadas 'x' têm um zero sob o vidro da linha superior e a segunda linha tem as coordenadas x de -1 e +1, terceira linha -2, 0, +2 e assim por diante. O ponto importante é que o copo mais à esquerda ou à direita no nível y terá abs (x) = y.

Embrulhando tudo isso em python (2.x), temos:

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)

Portanto, para obter a quantidade realmente em um copo em p, use amount_in (total, p).

Não está claro no OP, mas o pouco sobre "você não pode adicionar parâmetros" pode significar que a pergunta original deve ser respondida em termos dos números de vidro mostrados. Isso é resolvido escrevendo uma função de mapeamento dos números do vidro de exibição para o sistema de coordenadas interno usado acima. É complicado, mas pode ser usada uma solução iterativa ou matemática. Uma função iterativa fácil de entender:

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)

Agora basta reescrever a função amount_in () acima para aceitar um número de copo:

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)

Interessante.

Isso adota a abordagem de simulação.

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

que imprime (para 6 litros):

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

o que parece estar certo.

Esta é a função binomial. A proporção da água entre os copos do nível N pode ser descoberta usando nCr para cada copo no nível. Além disso, o número total de óculos anteriores ao nível N é a soma de 1 a (N - 1), uma fórmula para a qual você deve encontrar os disponíveis com bastante facilidade. Assim, dado X, você deve poder determinar seu nível e usar nCr para verificar as proporções dos copos para esse nível e, assim, determinar quanta água há em X, se houver litros suficientes para descer para X de qualquer maneira.

Em segundo lugar, sua idéia de usar o BTree é boa, mas o BTree é uma variável interna, não um parâmetro externo.

IOW, se você cobriu essa matemática em sua educação (aqui no Reino Unido ela é ensinada antes da universidade), você deve ser capaz de resolver isso sem muito problema.