Rompecabezas de la fuente Champaign

Se disponen vasos de agua vacíos en el siguiente orden:

Cuando vierte líquido en el primer vaso si está lleno, entonces el líquido extra fluirá a los vasos 2 y 3 en cantidades iguales. Cuando el vaso 2 está lleno, el líquido extra fluiría a 4 y 5 y así sucesivamente.

Dado un N litros de líquido y la capacidad máxima de cada vaso es de 1 litro, proporcione la cantidad de líquido presente en cualquier vaso si vacía N litros de líquido vertiéndolo en el vidrio completando la función getWaterInBucket(int N, int X)donde X es el número de vidrio. Entonces, por ejemplo, si quiero tener 4 litros al principio y quiero encontrar el agua en el vaso 3, la función esgetWaterInBucket(4, 3)

¿Cómo resuelvo esto mediante programación? Traté de encontrar una solución matemática usando el triángulo de Pascal. Esto no funcionó. Lo consideré un árbol, así que puedo agregar un parámetro como este getWaterInBucket(BTree root, int N, int X)y luego intentar una solución recursiva para cada nivel, pero los parámetros no están permitidos en este problema. ¿Hay algo obvio, algún truco?

Solo necesitas simular el vertido, 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á, esto no es un árbol. Debido a que se vierten diferentes vasos en los mismos vasos, eso evita que sea un árbol.

Así es como respondería esta pregunta en una situación de entrevista (no he visto esta pregunta antes, y no miré las otras respuestas hasta que tuve mi solución):

Primero, traté de resolverlo (lo que usted llamó la "solución matemática") y cuando llegué al vidrio 8 me di cuenta de que sería más difícil de lo que parecía porque el vidrio 5 comienza a desbordarse antes que el vidrio 4. En ese punto, decidió seguir la ruta de la recursividad (solo un FYI, muchas preguntas de entrevistas de programación requieren recursividad o inducción para resolverlas).

Pensando recursivamente, el problema se vuelve mucho más fácil: ¿cuánta agua hay en el vaso 8? La mitad de la cantidad que se ha derramado de los vasos 4 y 5 (hasta que esté lleno). Por supuesto, eso significa que tenemos que responder cuánto se ha derramado de los vasos 4 y 5, pero resulta que tampoco es demasiado difícil. ¿Cuánto se ha derramado del vidrio 5? La mitad de lo mucho que se derramó de los vasos 2 y 3, menos el litro que quedó en el vaso 5.

Resolver esto completamente (y desordenadamente) da:

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

En este punto (o mientras escribía esto), le diría al entrevistador que esta no es la solución ideal en producción: hay un código duplicado entre howMuchSpilledOutOf()y getWaterInBucket(); debe haber una ubicación central que asigne los cubos a sus "alimentadores". Pero en una entrevista, donde la velocidad y la precisión de la implementación son más importantes que la velocidad de ejecución y mantenimiento (a menos que se indique lo contrario), esta solución es preferible. Luego, ofrecería refactorizar el código para estar más cerca de lo que considero calidad de producción, y dejar que el entrevistador decida.

Nota final: estoy seguro de que mi código tiene un error tipográfico en alguna parte; También se lo mencionaría al entrevistador y le diría que me sentiría más seguro después de refactorizarlo o probarlo en la unidad.

Pensando en esto como un problema de árbol es una pista falsa, es realmente un gráfico dirigido. Pero olvídate de eso.

Piense en un vaso en cualquier lugar debajo del superior. Tendrá uno o dos vasos encima que pueden desbordarse. Con la elección adecuada del sistema de coordenadas (no se preocupe, vea el final) podemos escribir una función para obtener las gafas "principales" para cualquier vidrio dado.

Ahora podemos pensar en un algoritmo para obtener la cantidad de líquido vertido en un vaso, independientemente del desbordamiento de ese vaso. Sin embargo, la respuesta es que se vierte mucho líquido en cada padre menos la cantidad almacenada en cada vaso padre, dividido por 2. Simplemente suma eso para todos los padres. Escribiendo esto como un fragmento de Python del cuerpo de una función 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)

El máximo () es para garantizar que no tengamos una cantidad negativa de desbordamiento.

¡Ya casi terminamos! Elegimos un sistema de coordenadas con 'y' hacia abajo de la página, los cristales de la primera fila son 0, la segunda fila es 1, etc. Las coordenadas 'x' tienen un cero debajo del cristal de la fila superior y la segunda fila tiene coordenadas x de -1 y +1, tercera fila -2, 0, +2, y así sucesivamente. El punto importante es que el vidrio más a la izquierda o a la derecha en el nivel y tendrá abs (x) = y.

Envolviendo todo eso en python (2.x), tenemos:

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)

Entonces, para obtener la cantidad realmente en un vaso en p, use cantidad_in (total, p).

No está claro en el OP, pero el bit sobre "no puede agregar parámetros" puede significar que la pregunta original debe responderse en términos de los números de vidrio que se muestran. Esto se resuelve escribiendo una función de mapeo a partir de los números de vidrio de muestra en el sistema de coordenadas interno utilizado anteriormente. Es complicado, pero se puede usar una solución iterativa o matemática. Una función 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)

Ahora solo reescriba la función cantidad_in () anterior para aceptar un número de vidrio:

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)

Interesante.

Esto toma el enfoque de simulación.

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

que parece ser lo correcto.

Esta es la función binomial. La proporción del agua entre los vasos de nivel N se puede descubrir usando nCr para cada vaso en el nivel. Además, el número total de anteojos antes del nivel N es la suma de 1 a (N - 1), una fórmula para la cual debería poder encontrar fácilmente disponible. Por lo tanto, dado X, debería poder determinar su nivel y usar nCr para verificar las proporciones de los vasos para ese nivel, y así determinar cuánta agua hay en X, si de todos modos hay suficientes litros para bajar a X.

En segundo lugar, su idea de usar BTree está bien, es solo que BTree es una variable interna, no un parámetro externo.

IOW, si has cubierto estas matemáticas en tu educación (aquí en el Reino Unido se enseña antes de la universidad), entonces deberías poder resolver esto sin demasiados problemas.