Contexto:
Un multimillonario solitario ha creado un programa de juegos para atraer a los mejores y más brillantes programadores del mundo. Los lunes a la medianoche, elige a una persona de un grupo de solicitantes para ser el concursante de la semana, y les proporciona un juego. ¡Eres el concursante afortunado de esta semana!
El juego de esta semana:
El host le proporciona acceso API a una pila de 10,000 sobres digitales. Estos sobres se ordenan aleatoriamente y contienen dentro de ellos un valor en dólares, entre $ 1 y $ 10,000 (no hay dos sobres que contengan el mismo valor en dólares).
Tienes 3 comandos a tu disposición:
Leer (): lee la cifra en dólares en el sobre en la parte superior de la pila.
Take (): Agregue la figura del dólar en el sobre a la billetera de su programa de juegos y saque el sobre de la pila.
Pase (): salta el sobre en la parte superior de la pila.
Las normas:
Si usa Pass () en un sobre, el dinero dentro se pierde para siempre.
Si usa Take () en un sobre que contiene $ X, a partir de ese momento, nunca podrá usar Take () en un sobre que contenga <$ X. Tomar () en uno de estos sobres agregará $ 0 a su billetera.
Escribe un algoritmo que termine el juego con la cantidad máxima de dinero.
Si está escribiendo una solución en Python, siéntase libre de usar este controlador para probar algoritmos, cortesía de @Maltysen: https://gist.github.com/Maltysen/5a4a33691cd603e9aeca
Si usa el controlador, no puede acceder a los globales, solo puede usar los 3 comandos API proporcionados y las variables de ámbito local. (@Beta Decay)
Notas: "Máximo" en este caso significa el valor medio en su billetera después de N> 50 carreras. Espero, aunque me encantaría que me demuestren lo contrario, que el valor medio para un algoritmo dado convergerá a medida que N aumente hasta el infinito. En su lugar, siéntase libre de intentar maximizar la media, pero tengo la sensación de que es más probable que la media sea arrojada por una pequeña N que la mediana.
Editar: cambió el número de sobres a 10k para un procesamiento más fácil e hizo Take () más explícito.
Edición 2: La condición del premio se ha eliminado, a la luz de esta publicación en meta.
Puntajes altos actuales:
PhiNotPi - $ 805,479
Reto Koradi - $ 803,960
Dennis - $ 770,272 (revisado)
Alex L. - $ 714,962 (Revisado)
fuente
Respuestas:
CJam,
$ 87,143$ 700,424$ 720,327$ 727,580$ 770,272Este programa simula todo el juego varias veces y calcula la mediana.
Como correr
He puntuado mi presentación haciendo 100.001 pruebas:
Enfoque
Para cada sobre, hacemos lo siguiente:
Calcule la cantidad de dinero que inevitablemente se perderá al tomar el sobre.
Si R es el contenido y M es el máximo que se ha tomado, la cantidad puede estimarse como R (R-1) / 2 - M (M + 1) / 2 , lo que le da al dinero todos los sobres con contenido X en el intervalo (M, R) contiene.
Si todavía no se hubieran pasado sobres, la estimación sería perfecta.
Calcule la cantidad de dinero que inevitablemente se perderá al pasar el sobre.
Esto es simplemente el dinero que contiene el sobre.
Compruebe si el cociente de ambos es inferior a 110 + 0.016E , donde E es el número de sobres restantes (sin contar los sobres que ya no se pueden tomar).
Si es así, tómalo. De lo contrario, pase.
fuente
Python,
$ 680,646$ 714,962Toma cantidades cada vez más grandes en pasos de tamaño entre $ 125 y $ 190. Funcionó con N = 10,000 y obtuvo una mediana de $ 714962. Estos tamaños de paso provienen de prueba y error y ciertamente no son óptimos.
El código completo, incluida una versión modificada del controlador de @ Maltysen que imprime un gráfico de barras mientras se ejecuta:
Dirección de BitCoin: 1CBzYPCFFBW1FX9sBTmNYUJyMxMcmL4BZ7
Wow OP entregado! Gracias @LivingInformation!
fuente
max_taken
tu propio código, ya que no es parte de la API oficial del juego. Pero eso es trivial de hacer.read()
,take()
ypass()
métodos en el código publicado, ya que esos son los "3 comandos a su disposición", basada en la definición de la cuestión.C ++, $ 803,960
El resultado reportado es la mediana de 10,001 juegos.
fuente
C ++, ~ $ 815,000
Basado en la solución de Reto Koradi, pero cambia a un algoritmo más sofisticado una vez que quedan 100 sobres (válidos), barajando permutaciones aleatorias y calculando la subsecuencia cada vez mayor. Comparará los resultados de tomar y no tomar el sobre, y seleccionará con avidez la mejor opción.
fuente
Java, $ 806,899
Esto es de una prueba de 2501 rondas. Todavía estoy trabajando en optimizarlo. Escribí dos clases, una envoltura y un jugador. El contenedor crea una instancia del jugador con el número de sobres (siempre 10000 para el objeto real) y luego llama al método
takeQ
con el valor del sobre superior. El jugador luego regresatrue
si lo toman,false
si lo pasan.Jugador
Envoltura
Pronto habrá una explicación más detallada, después de que termine las optimizaciones.
La idea central es poder estimar la recompensa de jugar un juego a partir de un conjunto dado de sobres. Si el conjunto actual de sobres es {2,4,5,7,8,9}, y el sobre superior es el 5, entonces hay dos posibilidades:
Si calculamos la recompensa esperada de {7,8,9} y la comparamos con la recompensa esperada de {2,4,7,8,9}, podremos saber si vale la pena tomar el 5.
Ahora la pregunta es, dado un conjunto de sobres como {2,4,7,8,9} ¿cuál es el valor esperado? Descubrí que el valor esperado parece ser proporcional a la cantidad total de dinero en el conjunto, pero inversamente proporcional a la raíz cuadrada del número de sobres en los que se divide el dinero. Esto vino de jugar "perfectamente" varios juegos pequeños en los que todos los sobres tienen un valor casi idéntico.
El siguiente problema es cómo determinar el " número efectivo de sobres". En todos los casos, la cantidad de sobres se conoce exactamente al realizar un seguimiento de lo que ha visto y hecho. Algo así como {234,235,236} es definitivamente tres sobres, {231,232,233,234,235} es definitivamente 5, pero {1,2,234,235,236} realmente debería contar como 3 y no 5 sobres porque el 1 y 2 son casi inútiles, y nunca pasarías un 234 así más tarde podría recoger un 1 o 2. Tuve la idea de usar la entropía de Shannon para determinar el número efectivo de sobres.
Dirigí mis cálculos a situaciones en las que los valores de la envolvente se distribuyen uniformemente en algún intervalo, que es lo que sucede durante el juego. Si tomo {2,4,7,8,9} y trato eso como una distribución de probabilidad, su entropía es 1.50242. Luego hago
exp()
para obtener 4.49254 como el número efectivo de sobres.La recompensa estimada de {2,4,7,8,9} es
30 * 4.4925^-0.5 * 4/3 = 18.87
El número exacto es
18.1167
.Esta no es una estimación exacta, pero estoy realmente orgulloso de cuán bien se ajusta a los datos cuando los sobres se distribuyen uniformemente en un intervalo. No estoy seguro del multiplicador correcto (estoy usando 4/3 por ahora) pero aquí hay una tabla de datos que excluye el multiplicador.
La regresión lineal entre lo esperado y lo real da un valor R ^ 2 de 0.999994 .
Mi próximo paso para mejorar esta respuesta es mejorar la estimación cuando el número de sobres comienza a ser pequeño, que es cuando los sobres no están distribuidos de manera aproximadamente uniforme y cuando el problema comienza a ser granular.
Editar: si esto se considera digno de bitcoins, acabo de recibir una dirección en(Esto fue aquí cuando el autor del desafío estaba repartiendo premios).1PZ65cXxUEEcGwd7E8i7g6qmvLDGqZ5JWg
. ¡Gracias!fuente