algorithm - and - Peg Game: el mejor lugar para colocar la pelota de manera que aterrice en la celda objetivo

statistics and probability (5)

Comience en la parte inferior y asigne una probabilidad de 1 al objetivo y 0 a otros espacios. Luego, para la siguiente fila, asigne probabilidades de la siguiente manera:

1) if there is no peg, use the probability directly below. 2) for a peg, use the average of the probabilities in the adjacent columns one row down.

Esto simplemente propagará las probabilidades a la parte superior donde se le asignará a cada ranura la probabilidad de alcanzar el objetivo desde ese espacio . Sin árbol, sin recursión.

Fuente: ronda de clasificación de Facebook Hacker Cup 2011

En la sala de juegos, puedes jugar un juego simple en el que se coloca una pelota en la parte superior del juego, desde la posición que elijas. Hay una cantidad de clavijas con las que la pelota rebota cuando cae a través del juego. Cuando la pelota golpea una clavija, rebota hacia la izquierda con una probabilidad de 0.5 y hacia la derecha con una probabilidad de 0.5. La única excepción a esto es cuando golpea una clavija en el lado izquierdo o derecho, en cuyo caso rebota hacia el centro.

Cuando el juego se hizo por primera vez, las clavijas se organizaron en una cuadrícula regular. Sin embargo, es un juego antiguo, y ahora algunas de las estacas faltan. Tu objetivo en el juego es lograr que la pelota caiga desde el fondo del juego en un lugar específico. Dada la disposición del juego, ¿cómo podemos determinar el lugar óptimo para lanzar la pelota, de modo que se maximice la probabilidad de llegar a esta ubicación específica?

La imagen a continuación muestra un ejemplo de un juego con cinco filas de cinco columnas. Observe que la fila superior tiene cinco clavijas, la siguiente fila tiene cuatro clavijas, las siguientes cinco, y así sucesivamente. Con cinco columnas, hay cuatro opciones para lanzar la pelota (indexada desde 0). Tenga en cuenta que en este ejemplo, faltan tres clavijas. La fila superior es la fila 0, y la del extremo izquierdo es la columna 0, por lo que las coordenadas de las clavijas faltantes son (1,1), (2,1) y (3,2). En este ejemplo, el mejor lugar para lanzar la pelota está en el extremo izquierdo, en la columna 0, lo que da un 50% de posibilidades de que termine en la portería.

x.x.x.x.x x...x.x x...x.x.x x.x...x x.x.x.x.x G

x indica una clavija,. indica espacio vacío

Esta pregunta fue en Facebook Hacker Cup 2011.

La solución de marcog parece correcta, pero la resolví un poco diferente. Lo solucioné así:

Placa de configuración: leer la entrada, configurar una placa NxM, leer clavijas faltantes e insertar agujeros en la placa.
Para cada posible hoyo inicial, haga un BFS de la siguiente manera:
- El agujero de caída tiene una probabilidad inicial de 1.0.
- Desde el estado actual, puede bajar, izquierda, derecha, izquierda y derecha.
- Si solo puede ir hacia abajo, hacia la izquierda o hacia la derecha, sume la probabilidad de estado actual y agréguela a la cola si aún no está en la cola. Por ejemplo: si está en (1, 2) con probabilidad 0.5 y solo puede descender, suma 0.5 a estado (2,2) y agréguela a la cola si ya no está en la cola.
- Si puede ir hacia la izquierda y hacia la derecha, sume la mitad de la probabilidad de estado actual para cada estado siguiente posible y añádalos a la cola si aún no están allí. Por ejemplo: si está en (3, 3) con probabilidad 0.5 y puede ir tanto a la izquierda como a la derecha, agregue 0.25 a (4, 2) y 0.25 a (4, 4) y llévelos a la cola si no están ya allí .
Actualización actual mejor
Imprime mejor en todo el mundo.

Mi solución (no el código más limpio) en cpp se puede descargar desde: https://github.com/piva/Programming-Challenges/blob/master/peggame.cpp

Espero que haya ayudado ...

Observaciones:

Para una posición inicial dada, en cada fila hay una distribución de probabilidades
De una fila completa a la siguiente, la distribución simplemente se verá borrosa a excepción de los bordes.
Donde haya agujeros, veremos una desviación predecible de la borrosidad en (2)
Podríamos separar estas desviaciones, ya que las bolas se dejan caer de a una por vez, por lo que las probabilidades obedecen al principio de superposición (las computadoras cuánticas serían ideales aquí).
Al separar las desviaciones, podemos ver que realmente hay un conjunto de agujeros superpuestos en una cuadrícula de clavijas, por lo que podemos calcular la distribución desde el conjunto completo de clavijas primero (fácil) y luego pasar las clavijas individualmente para ver su efecto - ¡esto supone que hay más clavijas que agujeros!
Un borde es realmente un espejo: podemos calcular una matriz infinita de estos tableros virtuales reflejados en lugar de usar condiciones para los límites.

Entonces comenzaría en la parte inferior, en la posición deseada, y difundiría la probabilidad. Las clavijas perdidas efectivamente omiten una fila, por lo que mantendrá un registro de bolas que caen verticalmente.

Idealmente, comenzaría con un árbol completo (fibonacci), y por cada falta de las clavijas faltantes en una fila, agregue el efecto de que faltan.

Podemos resolver este problema usando la teoría de la probabilidad. Dejamos caer la pelota en una posición y dividimos recursivamente la trayectoria de la pelota en su (en la pared lateral) o en dos direcciones posibles. En el primer paso, sabemos con probabilidad 1 la posición de la pelota (¡después de todo, la estamos cayendo!). En cada división posterior en dos direcciones, la probabilidad se reduce a la mitad. Si terminamos en la fila inferior de la ubicación de destino, agregamos la probabilidad de que se tome la ruta a nuestro total. Repita este proceso para todas las posiciones iniciales y tome la mayor probabilidad de alcanzar el objetivo.

Podemos mejorar este algoritmo eliminando la recursión y el procesamiento fila por fila usando programación dinámica. Comience con la primera fila establecida en 0, excepto la ubicación de inicio que configuramos en 1. Luego calcule las probabilidades de llegar a cada celda en la siguiente fila comenzando con una matriz de 0 y. Para cada celda en nuestra fila actual, agregue la mitad de su probabilidad a la celda a la izquierda en la siguiente fila y media a la derecha, a menos que sea contra la pared lateral, en cuyo caso agregamos la probabilidad completa a la celda individual. Continúa haciendo esto para cada fila hasta llegar a la última fila.

Hasta ahora hemos descuidado las clavijas perdidas. Podemos tenerlos en cuenta al tener tres probabilidades para cada celda: una para cada dirección en la que la pelota viaja actualmente. Al final, resumimos todas las tres, ya que la dirección no importa.

O(R*C) solución

dp[i][j] da la probabilidad de que la pelota alcance la ranura de gol si está actualmente en la fila i y en la ranura j.

El caso base tiene dp[R-1][goal] = 1.0 y todos los demás espacios en la fila R-1 a 0.0

La recurrencia es entonces

dp[i][j] = dp[i + 2][j] if the peg below is missing dp[i][j] = dp[i + 1][left] if the peg is on the right wall dp[i][j] = dp[i + 1][right] if the peg is on the left wall dp[i][j] = (dp[i + 1][left] + dp[i + 1][right]) / 2 otherwise