Cortés borracho miope bot en un campo minado

11

Como el título puede sugerir, este problema está semi-inspirado por el educado Bot borracho miope de @NP

Nuestro pobre robot se coloca en una cuadrícula cartesiana en el origen, y después de cada minuto, se mueve 1 unidad en una de las cuatro direcciones (arriba, abajo, izquierda, derecha).

Después de n minutos, se activan todas las minas latentes en la cuadrícula, matando a cualquier robot pobre que pueda encontrarse sobre ellas. Las minas se encuentran en todas las coordenadas enteras que satisfacen la ecuación | y | = | x |.

Desafío

Se le proporcionará n , el número de minutos antes de la explosión de las minas, como entrada y como salida, debe encontrar la probabilidad de que el bot esté muerto .

Entrada : un número natural que representa n .

Salida : Supongamos que la probabilidad de que el bot esté muerto sea ​​p / q, donde pyq son números enteros relativamente primos (q no puede ser 0, pero p sí). Salida p.

Reglas

  • Su algoritmo no debe ejecutarse en tiempo exponencial o superior. Idealmente debería ejecutarse en tiempo polinómico o menos.
  • Su algoritmo debe poder manejar entradas de n<20 (puede ajustarse si es demasiado difícil) en un tiempo razonable.
  • Este es un desafío de .
  • Iterar sobre todas las posibilidades para un n dado definitivamente no será aceptado como respuesta.

Casos de prueba

1->0

2->3

4->39

6->135

8->7735

10->28287

Ejemplo de cálculo para n = 6

Tenemos 4 movimientos posibles: U, D, R y L. El número total de caminos que se pueden tomar es 4 ^ 6 o 4096. Hay 4 casos posibles que aterrizan a lo largo de la línea y = x: x, y = ± 1; x, y = ± 2; x, y = ± 3; o x = y = 0. Contaremos el número de formas de terminar en (1,1), (2,2) y (3,3), multiplicarlos por 4 para tener en cuenta los otros cuadrantes y sumar esto a la cantidad de formas de terminar en (0,0).

Caso 1: el bot termina en (3, 3). Para que el bot termine aquí, debe haber tenido 3 movimientos correctos y 3 movimientos hacia arriba. En otras palabras, el número total de formas de llegar aquí es la forma de reorganizar las letras en la secuencia RRRUUU, que es 6, elija 3 = 20.

Caso 2: El bot termina en (2,2). Para que el bot termine aquí, podría haber tenido 2 movimientos hacia arriba, 3 movimientos hacia la derecha y 1 movimiento hacia la izquierda; o 2 movimientos a la derecha, 3 movimientos hacia arriba y 1 movimiento hacia abajo. Por lo tanto, el número total de formas de llegar aquí es la suma de las formas de reorganizar las letras en las secuencias RRRLUU y UUUDRR, las cuales son (6 elegir 1) * (5 elegir 2) = 60, para un total de 120 posibilidades .

Caso 3: El bot termina en (1,1). Para que el bot termine aquí, podría haber tenido: 1 movimiento hacia la derecha, 3 movimientos hacia arriba y 2 movimientos hacia abajo. En este caso, el número de formas de reorganizar las letras en la secuencia RUUUDD es (6 elegir 1) * (5 elegir 2) = 60.

1 movimiento hacia arriba, 3 movimientos hacia la derecha y 2 movimientos hacia la izquierda. En este caso, el número de formas de reorganizar las letras en la secuencia URRRLL es (6 elegir 1) * (5 elegir 2) = 60.

2 movimientos hacia la derecha, 1 movimiento hacia la izquierda, 2 movimientos hacia arriba y 1 movimiento hacia abajo. En este caso, el número de formas de reorganizar las letras en la secuencia UUDRRL es (6 elegir 1) * (5 elegir 1) * (4 elegir 2) = 180.

Por lo tanto, el número total de formas de terminar en (1,1) es 300.

Caso 4: El bot termina en (0,0). Para que el bot termine aquí, podría haber tenido:

3 movimientos a la derecha y 3 movimientos a la izquierda. En este caso, el número de formas de reorganizar las letras en la secuencia RRRLLL es (6 elegir 3) = 20.

3 movimientos hacia arriba y 3 movimientos hacia abajo. En este caso, el número de formas de reorganizar las letras en la secuencia UUUDDD es (6 elegir 3) = 20.

1 movimiento hacia la derecha, 1 movimiento hacia la izquierda, 2 movimientos hacia arriba y 2 movimientos hacia abajo. En este caso, el número de formas de reorganizar las letras en la secuencia RLUUDD es (6 elige 1) * (5 elige 1) * (4 elige 2) = 180.

1 movimiento hacia arriba, 1 movimiento hacia abajo, 2 movimientos hacia la derecha y 2 movimientos hacia la izquierda. En este caso, el número de formas de reorganizar las letras en la secuencia RRLLUD es (6 elegir 1) * (5 elegir 1) * (4 elegir 2) = 180.

Por lo tanto, el número total de formas de terminar en (0,0) es 400.

Al sumar estos casos, obtenemos que el número total de formas de terminar en | y | = | x | es 4 (20 + 120 + 300) + 400 = 2160. Por lo tanto, nuestra probabilidad es 2160/4096. Cuando esta fracción se reduce completamente, es 135/256, por lo que nuestra respuesta es 135 .

Don mil
fuente
Me gusta el desafío, pero creo que sería beneficioso incluir un ejemplo trabajado para uno de los casos de prueba muy pequeños (2 o 3), por ejemplo.
Sr. Xcoder
@ Mr.Xcoder Agregaré uno cuando tenga tiempo.
Don Thousand
2
Interesante reto. Tenga en cuenta que usar la palabra "idealmente" en una regla hace que no sea una regla. Sería útil decir definitivamente de una forma u otra.
trichoplax
1
¿Pero nadie habla del algoritmo de aprendizaje de primera generación?
Programas Redwolf
1
@RedwolfPrograms ahaha sí, pero este bot tiene el nombre más genial
Don Thousand el

Respuestas:

17

Python 2 , 65 bytes

def p(n):b=2**n;r=b*b-((~b)**n/b**(n/2)%-b)**2;print~n%2*r/(r&-r)

Pruébalo en línea!

La probabilidad de que el bot esté muerto se puede expresar como:

f(n)=2ss2, where s=12n(nn/2)

y se entiende que el binomio es igual a cuando no está completo.0n/2

Podemos razonar así. ¿Cuál es la probabilidad de que el bot aterrice en la línea ? Esto sucede si el número total de movimientos hacia arriba y hacia la izquierda es igual al número total de movimientos hacia abajo y hacia la derecha. Esta es la misma probabilidad de que, digamos, arrojes una moneda veces y obtengas tantas colas como caras. Debe elegir volteos para que sean cabezas de volteos, lo que se puede hacer en formas, de posibles secuencias en general, dando probabilidady=xnn/2n(nn/2)2n

s=12n(nn/2)

La probabilidad de aterrizar la línea también es . Entonces, la probabilidad de aterrizar en cualquier línea es la suma de estos o , excepto que estamos contando dos la probabilidad de aterrizar de en ambas líneas, y debemos restarlo para compensar.y=xs2sx=y=0

Resulta que la probabilidad de aterrizar en es solo , el producto de la probabilidad de aterrizar en cada línea. Podemos argumentar que los eventos son independientes de la siguiente manera: si elegimos una secuencia aleatoria de números iguales de "Arriba o Izquierda" y "Abajo o Derecha" para aterrizar en y del mismo modo con "Arriba o Derecha" y "Abajo o Izquierda" "para , podemos combinarlos de forma única en una secuencia de arriba, abajo, izquierda, derecha tomando la intersección de los pares de direcciones en cada posición.x=y=0s2x=yx=y

Entonces, la probabilidad de aterrizar en o es .x=yx=y2ss2

El código calcula el binomio usando esta expresión como con base . Para extraer el numerador de la fracción de probabilidad, observamos que el denominador es una potencia de 2, por lo que usamos la expresión para dividir la potencia máxima de 2 , expresada como el clásico truco de bits .(nn/2)(b+1)**n/b**(n/2)%bb=2**nr/(r&-r)rr&-r

La solución se juega al golf escribiendo como para que solo se haga referencia una vez, y trabajando sin las fracciones para permanecer dentro de los enteros. El cálculo es tiempo polinomial en incluso con la forma funky de calcular binomios.2ss21(1s)2s1/2nn


Después de escribir la prueba de la probabilidad de que el bot muera, encontré una forma posiblemente más limpia de probarlo y presentarlo.

Hagamos un seguimiento de los valores de y después de cada movimiento del bot. Cada una de las cuatro direcciones hacia arriba, abajo, izquierda, y derecha, ya sea incrementos o decrementos cada uno de y , con las cuatro direcciones que corresponden a las cuatro combinaciones.a=x+yb=xyab

Entonces, un movimiento aleatorio es equivalente a agregar aleatoriamente a e independientemente a . Esto es equivalente a hacer paseos aleatorios separados en y .±1a±1bab

Ahora, el robot termina en la línea o exactamente cuando o . Entonces, la probabilidad de terminar con es e igualmente para . Como las caminatas son independientes, la probabilidad de que y sea , por lo que la probabilidad de que al menos uno sea cero es el complemento .x=yx=ya=0b=0a=0s=12n(nn/2)b=0a0b0(1s)21(1s)2

xnor
fuente
3
¡Fantástico! Estaba esperando que alguien dedujera esto. No me imaginaba que fuera tan rápido. La desventaja ahora es que la mayoría de las otras respuestas no tendrán que pensar demasiado :(. Excelente +1
Don Thousand
disfruta de la pequeña recompensa (no tengo mucho que dar, lo siento)
Don Thousand
1
@RushabhMehta ¡Gracias, es muy amable de su parte! Su generosidad me motivó a escribir una prueba más limpia que pensé después.
xnor
La verdadera inspiración para este problema fue el problema 11 de AIME I 2014, si quieres echarle un vistazo.
Don Thousand