Este es el segundo de una serie de rompecabezas que publicaré todos los lunes a la medianoche PST. El primer rompecabezas se encuentra aquí .
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 4 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.
Oracle (M): Devuelve el valor medio de los siguientes sobres M en la pila, sin incluir el que actualmente puede Leer ().
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.
Si usa Oracle (M) en el turno T, se devolverán los sobres T + 1 a T + M. Oracle () está desactivado hasta el turno T + M.
Escribe un algoritmo que termine el juego con la cantidad máxima de dinero.
Si está escribiendo su algoritmo en Python, no dude en usar este controlador provisto por @Maltysen: https://gist.github.com/livinginformation/70ae3f2a57ecba4387b5
Notas 1: "Máximo" en este caso significa el valor medio en su billetera después de N> = 1000 ejecuciones. 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.
Nota 2: como todas las soluciones a la parte anterior de este rompecabezas son válidas aquí, volver a publicarlas tiene poco valor. Solo se considerarán mejoras algorítmicas de rompecabezas anteriores para la parte II.
Editar: La condición del premio se ha eliminado, a la luz de esta publicación en meta.
fuente
M
valores, donde puede elegirM
.Respuestas:
Groovy
$ 713 337$ 817 829$ 818,227 milCódigo Bootstrap:
Algoritmo
Comparo los valores restantes con los posibles valores. Este script no es rápido (tarda 1 minuto por cada 1000 simulaciones) ... pero realizará las simulaciones simultáneamente.
No tengo idea de por qué funciona mi algoritmo, pero fue solo prueba y error: agrupar operaciones matemáticas y manipular las constantes. Lo ejecuté 5000x para el puntaje actual, en un intento de reducir las fluctuaciones del puntaje (es +/- $ 4000 dependiendo del recuento de iteraciones).
Incluso sin el oráculo al final, todavía debería estar (apenas) superando la solución de @ orlp para el rompecabezas anterior.
fuente
C # - $ 803.603 ahora -> $ 804.760 (con oráculo)
Código Bootstrap
Código de juego:
El crédito pertenece a Reto Koradi ( /codegolf//a/54181/30910 )
Editar: Uso básico de Oracle implementado. Si el siguiente oráculo está por encima del umbral a utilizar, expanda el sobre actual al índice del índice Oracle. Esto no golpea a menudo pero ES una mejora ;-)
fuente
Python - $ 74112
Solo tome, si el valor actual es menor que el siguiente valor (es decir, puede tomar ambos).
Python - (aún calculando la media)
Esta respuesta tarda mucho en calcularse. Alcanza alrededor de 670.000 $ . Recuerdo cada sobre que vi. Cada vez que tengo que tomar una decisión, genero dos listas de sobres restantes que podría agregar a mi billetera si tomo el sobre actual o lo dejo, respectivamente.
No optimicé el código.
Y init_game comienza así:
fuente
C # - $ 780.176
Compruebe si el siguiente valor está dentro del 5% inferior de todos los valores restantes. Relájate a medida que lleguemos al final.
Y mi clase de juego, muy fea, ni siquiera valida si Oracle está permitido, pero dado que solo uso Oracle (1) eso no debería ser un problema.
fuente
Java, $ 804,991
La puntuación es de 1001 rondas. Probablemente esté demasiado cerca de llamar entre esta respuesta y la de Stephan Schinkel .
Esto se basa en mi respuesta en el desafío anterior, ya que usa el mismo cálculo basado en entropía para estimar los pagos. La principal diferencia es que ahora simplemente toma sobres en pares (1 y 2, luego 3 y 4, etc.) y analiza las posibles combinaciones de toma, toma, pase, pase, etc. También calcula el puntaje exacto estimado cuando el número de sobres válidos es realmente pequeño.
El "envoltorio" que escribí no es realmente un envoltorio verdadero, solo da sobres en pares en lugar de llamar a una
Oracle(1)
función cada dos asaltos.En general, diría que, a pesar de la mayor complejidad, este bot realmente no es mejor que el anterior.
Jugador
Controlador
Dirección de Bitcoin: 1BVBs9ZEP8YY4EpV868nxi2R23YfL7hdMq
fuente
Python 3 - $ 615570
En realidad no usa el oráculo ... Eh :)
Construye una lista de todos los sobres anteriores y verifica si el sobre actual es menor que el número de sobres anteriores en incrementos de 10 sobres.
fuente
Python, 87,424
Aquí hay un algoritmo simple y llano, los siete afortunados.
Básicamente, lo que hace es convertir read () en una cadena y verifica si hay un siete. Si lo hay, toma el sobre. Si no, lo pasa.
Tiene un promedio de alrededor de 81,000, no he estado haciendo un seguimiento.
fuente