Champaign Fountain Puzzle

30

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

insira a descrição da imagem aqui

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?

Slartibartfast
fonte
18
Eu não gostaria de trabalhar em uma empresa onde os problemas de gestão são sobre fontes de champanhe ...
mouviciel
Você pode derramar em um copo que não seja o vidro 1? Caso contrário, cada camada terá quantidades iguais de água em cada copo. Assim, você terá níveis completos sempre que derramar 1, 3, 6, 10 ... litros. Se você derramar 7 litros, a quarta fila terá 4 copos, de modo que cada um ficará com 1/4 de xícara. Todas as camadas acima estarão cheias.
GlenPeterson
5
@GlenPeterson Pelo jeito que estou lendo, não acho que eles sejam preenchidos igualmente. Sim, 2 e 3 seriam preenchidos igualmente porque eles têm apenas uma coisa sendo derramada, mas uma vez cheios, 2 fluem igualmente em 4/5 e 3 fluem igualmente em 5/6, assim 5 são preenchidos com o dobro do rato de 4/6 . Os copos centrais estão sempre enchendo mais rápido que os copos externos. quando 4/6 estão cheios 8/9 estão cheios de 25% e 7/10 ainda estão vazios.
Brad
11
Além disso, isso me lembra do triângulo de Pascal ..
Brad
@mouviciel Haha GlenPeterson - O primeiro copo a ser derramado é sempre o copo 1. O entrevistador também disse usar essas informações. Ele parecia mais confuso do que eu sobre a resposta certa para esse problema.
Slartibartfast

Respostas:

35

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.

Winston Ewert
fonte
16
+1 pela grande observação de que isso não é uma árvore.
Mihai Danila
2
Boa resposta. Em uma entrevista, você deve dizer que isso pode ter problemas de escalabilidade, pois calcula o conteúdo de todos os óculos. Além disso, você precisa lidar com o caso em que a água sai da fileira inferior dos copos. E você quer return glasses[N-1], porque os números de vidro começam em 1 em vez de 0.
Tom Panning
11
Acho que a parte desafiadora pode ser descobrir os índices das crianças esquerda e direita. Se você apresentou isso, o entrevistador apenas pedirá para você implementar essas funções. Pode haver uma fórmula explícita.
James
Essa é uma solução realmente elegante. Obrigado. Ficaria grato se você pudesse editá-lo para adicionar comentários às linhas de código para explicar o que cada etapa significa no processo de pensamento. Além disso, o número de óculos não é restrito a 10. Poderia ser qualquer coisa #
Slartibartfast 28/01
11
Como você encontra os óculos esquerdo e direito?
Kevic #
7

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.

Tom Panning
fonte
6
Esta solução é codificada para o exemplo. Adicionar óculos significa adicionar "estojo" ao comutador ... Não acho que seja uma boa solução.
Luigi Massa Gallerano
2
@ LuigiMassaGallerano - tudo bem nesse caso, pois é uma pergunta de entrevista; não deveria ser uma solução perfeita. O entrevistador está tentando entender melhor o processo de pensamento do candidato. E Tom já aponta isso this isn't the ideal solution.
11
Sinceramente, não é. Posso garantir que esse cenário não foi projetado para ser codificado. Se eu fizesse uma pergunta da entrevista e apresentasse um cenário de caso de teste em que o entrevistado apresentasse uma solução codificada, é melhor ele estar preparado para oferecer uma solução geral ou ele provavelmente não passará na entrevista.
Rig
5

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)
rzzzwilson
fonte
2

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.

OldCurmudgeon
fonte
-1

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.

DeadMG
fonte
11
Não acho que seja a função binomial. Atinge o terceiro nível em proporções de 1,2,1, como sugere a função binomial, mas o vidro do meio se enche primeiro e o padrão é quebrado depois disso.
Winston Ewert
O tempo não faz parte da simulação e não afeta os resultados finais.
DeadMG
4
como o líquido de modelagem se enche e flui dos óculos, eu teria que manter esse tempo implicitamente parte da simulação. Com 5 litros, 4 e 6 estarão meio cheios e 5 estarão todos cheios. Quando o sexto litro é adicionado, ele começa a despejar em 8 e 9, mas 7 e 10 não recebem água porque 4 e 6 ainda não atingiram a capacidade. Assim, a função binomial não prevê os valores corretos.
Winston Ewert
3
-1, isso está errado. Os níveis não serão preenchidos de maneira uniforme.
precisa saber é o seguinte
Você está certo, eu não considerei isso. Mas depois de pensar um pouco, percebi que você estava certa. Não sabe como ajustar a fórmula para levar isso em consideração.
precisa saber é