Existe un apoyo bastante sólido en el meta para que las preguntas de redacción de desafíos estén en el tema principal, siempre que estas preguntas sean específicas y respondan. Sin embargo, todavía no tenemos ninguna de esas preguntas, así que pensé que probaría las aguas. Esta pregunta probablemente está entrando en un buen territorio subjetivo, malo subjetivo , pero creo que es probable que esas preguntas de redacción de desafíos tengan que ser. Para garantizar que sigan generando contenido de alta calidad, no publique solo ideas especulativas en las respuestas. Explique por qué evitan los problemas mencionados a continuación o, idealmente, señale los desafíos existentes que han utilizado con éxito la técnica sugerida en el pasado.

Para ciertos desafíos de optimización, un parámetro libre para establecer el desafío es el tamaño del problema a optimizar. Por "desafío de optimización" no me refiero a cosas como nuestro género de código más rápido , donde generalmente se requiere que las respuestas sean exactas / óptimas, y el desafío se califica en un tamaño de problema fijo o en el tamaño de problema más grande que se puede manejar en un tiempo fijo Me refiero específicamente a desafíos donde las soluciones subóptimas al problema subyacente están permitidas e incluso son probables, y el objetivo es hacerlo lo mejor posible.

En aras de la claridad, considere los desafíos de los castores ocupados , aunque en principio esto también se aplica a otros tipos de desafíos sin soluciones óptimas conocidas (solo estoy usando castores ocupados aquí porque exacerban los problemas mencionados a continuación). Digamos que quería desafiar la búsqueda del castor Brainfuck más ocupado. El parámetro libre en problemas de castores ocupados es el tamaño del código. No puedo establecer el desafío sin hacer referencia al tamaño del código de alguna manera. En cierto modo, cada valor del parámetro de tamaño del problema Nofrece un desafío separado (cada vez más difícil). Mi pregunta principal es cómo puedo hacer que tal desafío funcione sin tener problemas de equilibrio.

La solución obvia es arreglar N: "Encuentre un programa Brainfuck final con Nbytes de código fuente que imprima tantos caracteres como sea posible / ejecute tantos ticks como sea posible". Esto tiene problemas de equilibrio masivos: si elijo el tamaño demasiado pequeño, alguien podría encontrar rápidamente elCastor más ocupado y el desafío ha terminado. Si elijo el tamaño demasiado grande, la solución óptima imprimirá una cantidad astronómica de caracteres antes de terminar, lo que significa que probablemente sea trivial encontrar dichos programas y el desafío se convierte en una tarea / ejercicio de paciencia, esto también deja el territorio donde los castores ocupados se pueden encontrar mediante programación, y en su lugar las personas tendrían que comenzar a probar sus resultados formalmente, lo que mucha gente no consideraría muy divertido. Por supuesto, este problema es más pronunciado en los desafíos de castores ocupados que otros tipos, debido al crecimiento de las soluciones óptimas, pero se aplica a otros desafíos de todos modos.

La siguiente opción sería dejar Nsin restricciones y hacerlo parte de la puntuación a través de alguna función. Incluso para los desafíos "normales", lograr el equilibrio de puntajes combinados es increíblemente difícil, pero en el caso de los castores ocupados es realmente imposible, debido al hecho de que las soluciones óptimas crecen más rápido Nque cualquier función computable. Eso significa que siempre puedo superar la mejor respuesta existente yendo a un sitio lo suficientemente grande Ndonde pueda encontrar fácilmente un programa que se ejecute durante tanto tiempo que pueda obtener una mejor puntuación sin mucho esfuerzo.

También he considerado establecer un sistema fijo Ny permitir que las personas también envíen castores para Nque sean más grandes y que se utilizarán como sucesivos desempates. Esto tiene un problema similar, en el sentido de que alguien puede "encontrar un castor ocupado igualmente bueno" para un N, creando así un empate y luego enviando prácticamente cualquier cosa para el siguiente, Ndonde es más fácil encontrar un puntaje grande (incluso si encuentra el puntaje óptimo se vuelve más difícil). En estos casos, ¿cómo trataría con varias personas usando la misma solución? Prohibirlo también sería extraño en caso de que sea óptimo.

Tal vez uno podría llegar a un punto medio, haciendo una suposición educada a un Nprecio razonable y luego pidiendo castores ocupados para todos los tamaños dentro de (digamos) 5 bytes N, para que haya margen de maniobra en ambas direcciones (y luego combine los ~ 10 puntajes en una sola por una técnica u otra). Esto tampoco se siente bastante satisfactorio porque mi conjetura inicial Naún podría estar muy lejos del rango que genera desafíos interesantes.

TL; DR: en casos donde el desafío es (resolver de manera subóptima y) optimizar un problema cuyo tamaño es variable, ¿cómo incorporo el tamaño en el desafío? Idealmente, me gustaría que las personas pudieran trabajar con un valor Ncercano al extremo superior del rango de tamaños manejables. Pero en caso de que resulten posibles soluciones óptimas para eso N, sería genial si las soluciones para un poco más grandes Ncomenzaran a tener peso, de modo que el desafío podría continuar con un tamaño de problema más interesante.

Encuentra la próxima N

El desafío indicaría Nque las presentaciones deben comenzar en.

Luego, las personas enviarían respuestas en la actualidad N. Si se demuestra que una presentación dada es óptima, entonces Nse incrementa en 1 y el proceso se repite.

Hay varias formas de calificar esto:

1. Obtener la mejor presentación en la actualidad N
2. Dé un punto a la mejor presentación en la actualidad N, más un punto para cada solución óptima
3. Igual que el n. ° 2, pero también da un punto a la persona que demostró que una presentación dada era óptima.

Dar puntos por soluciones dentro de una N acotada

Permitir Nestar dentro de límites fijos. El límite inferior debe excluir respuestas obviamente triviales, y que el límite superior no debe estar muy lejos del límite inferior.

Luego, otorgue 1 punto por cada persona que tenga la mejor solución para cada uno Ndentro de los límites. Si mayor Nsignifica que la solución es más difícil, entonces déles N puntos. (o alguna fórmula basada en N).

Este método es similar a cómo lo hace AZsPCs , pero no se dan puntos parciales.